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