數(shù)據(jù)結(jié)構(gòu)算法演示(Windows版) 使 用 手 冊 一、 功能簡介 本課件是一個(gè)動(dòng)態(tài)演示數(shù)據(jù)結(jié)構(gòu)算法執(zhí)行過程的輔助教學(xué)軟件, 它可適應(yīng)讀者對算法的輸入數(shù)據(jù)和過程執(zhí)行的控制方式的不同需求, 在計(jì)算機(jī)的屏幕上顯示算法執(zhí)行過程中數(shù)據(jù)的邏輯結(jié)構(gòu)或存儲(chǔ)結(jié)構(gòu)的變化狀況或遞歸算法執(zhí)行過程中棧的變化狀況。整個(gè)系統(tǒng)使用菜單驅(qū)動(dòng)方式, 每個(gè)菜單包括若干菜單項(xiàng)。每個(gè)菜單項(xiàng)對應(yīng)一個(gè)動(dòng)作或一個(gè)子菜單。系統(tǒng)一直處于選擇菜單項(xiàng)或執(zhí)行動(dòng)作狀態(tài), 直到選擇了退出動(dòng)作為止。 二、 系統(tǒng)內(nèi)容 本系統(tǒng)內(nèi)含84個(gè)算法，分屬13部分內(nèi)容，由主菜單顯示，與《數(shù)據(jù)結(jié)構(gòu)》教科書中自第2章至第11章中相對應(yīng)。各部分演示算法如下： 1． 順序表 （1）在順序表中插入一個(gè)數(shù)據(jù)元素(ins_sqlist) （2）刪除順序表中一個(gè)數(shù)據(jù)元素(del_sqlist) （3）合并兩個(gè)有序順序表(merge_sqlist) 2． 鏈表 （1）創(chuàng)建一個(gè)單鏈表(Crt_LinkList) （2）在單鏈表中插入一個(gè)結(jié)點(diǎn)(Ins_LinkList) （3）刪除單鏈表中的一個(gè)結(jié)點(diǎn)(Del_LinkList) （4）兩個(gè)有序鏈表求并(Union) （5）歸并兩個(gè)有序鏈表(MergeList_L) （6）兩個(gè)有序鏈表求交(ListIntersection_L) （7）兩個(gè)有序鏈表求差(SubList_L) 3． 棧和隊(duì)列 （1）計(jì)算阿克曼函數(shù)(AckMan) （2）棧的輸出序列(Gen、Perform) （3）遞歸算法的演示 ? 漢諾塔的算法(Hanoi) ? 解皇后問題的算法(Queen) ? 解迷宮的算法(Maze) ? 解背包問題的算法(Knap) （4）模擬銀行(BankSimulation) （5）表達(dá)式求值(Exp_reduced) 4． 串的模式匹配 （1）古典算法(Index_BF) （2）求Next 函數(shù)值(Get_next)和按Next 函數(shù)值進(jìn)行匹配 (Index_KMP(next)) （3）求 Next 修正值(Get_nextval)和按 Next 修正值進(jìn)行匹配(Index_KMP(nextval)) 5． 稀疏矩陣 （1）矩陣轉(zhuǎn)置 (Trans_Sparmat) （2）快速矩陣轉(zhuǎn)置 (Fast_Transpos) （3）矩陣乘法 (Multiply_Sparmat) 6． 廣義表 （1）求廣義表的深度(Ls_Depth) (2）復(fù)制廣義表(Ls_Copy) （3）創(chuàng)建廣義表的存儲(chǔ)結(jié)構(gòu)(Crt_Lists) 7． 二叉樹 （1）遍歷二叉樹 ? 二叉樹的線索化 ? 先序遍歷(Pre_order) ? 中序遍歷(In_order) ? 后序遍歷(Post_order) (2) 按先序建二叉樹(CrtBT_PreOdr) (3) 線索二叉樹 ? 二叉樹的線索化 ? 生成先序線索(前驅(qū)或后繼) (Pre_thre) ? 中序線索（前驅(qū)或后繼) (In_thre) ? 后序線索(前驅(qū)或后繼) (Post_thre) ? 遍歷中序線索二叉樹(Inorder_thlinked) ? 中序線索樹的插入(ins_lchild_inthr)和刪除(del_lchild_inthr)結(jié)點(diǎn) （4）建赫夫曼樹和求赫夫曼編碼(HuffmanCoding) （5）森林轉(zhuǎn)化成二叉樹(Forest2BT) （6）二叉樹轉(zhuǎn)化成森林(BT2Forest) （7）按表達(dá)式建樹(ExpTree)并求值(CalExpTreeByPostOrderTrav) 8． 圖 （1）圖的遍歷 ? 深度優(yōu)先搜索(Travel_DFS) ? 廣度優(yōu)先搜索(Travel_BFS) （2）求有向圖的強(qiáng)連通分量(Strong_comp) （3）有向無環(huán)圖的兩個(gè)算法 ? 拓?fù)渑判?Toposort) ? 關(guān)鍵路徑(Critical_path) （4）求最小生成樹 ? 普里姆算法(Prim) ? 克魯斯卡爾算法(Kruscal) （5）求關(guān)節(jié)點(diǎn)和重連通分量(Get_artical) （6）求最短路徑 ? 弗洛伊德算法(shortpath_Floyd) ? 迪杰斯特拉算法(shortpath_DIJ) 9． 存儲(chǔ)管理 （1）邊界標(biāo)識法 (Boundary_tag_method) （2）伙伴系統(tǒng) (Buddy_system) （3）緊縮無用單元 (Storage_compaction) 10． 靜態(tài)查找 （1）順序查找(Search_Seq) （2）折半查找 (Serch_Bin) （3）插值查找 (Search_Ins) （4）斐波那契查找 (Searc