数据结构算法演示( 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) 解迷宫的算法(Mae) 解背包问题的算法(Knap)
1 数据结构算法演示(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函数值进行匹配( ndex Kmp(next) (3)求Next修正值 Get nextva)和按Next修正值进行匹配( Index Kmp( nextval)) 5.稀疏矩阵 (1)矩阵转置( Trans Sparmat) (2)快速矩阵转置( Fast Transpose) (3)矩阵乘法( Multiply_ Sparmat) 6.广义表 (1)求广义表的深度( Ls Depth) (2)复制广义表( Ls Copy) (3)创建广义表的存储结构( rt Lists) 7.二叉树 (1)遍历二叉树 二叉树的线索化 先序遍历( Pre order) 中序遍历( In order) 后序遍历( Post order) (2)按先序建二叉树( CrtBT PreOdr) (3)线索二叉树 ●二叉树的线索化 生成先序线索(前驱或后继)( Pre thre) 中序线索(前驱或后继)( In thre) 后序线索(前驱或后继)( Post thre) 遍历中序线索二叉树( Inorder thlinked) ·中序线索树的插入( ins lchild inthe)和删除( del child inthe)结点 (4)建赫夫曼树和求赫夫曼编码( Huffman coding) (5)森林转化成二叉树( Forest2BT) (6)二叉树转化成森林(BT2 Forest) (7)按表达式建树( ExpTree并求值( CalExpTree By PostOrderTrav) 8.图 (1)图的遍历
2 （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_DL .存储管理 (1)边界标识法( Boundary tag_ method) (2)伙伴系统( Buddy system) (3)紧缩无用单元( Storage compaction) 10.静态查找 (1)顺序查找( Search Seq) (2)折半查找( Serch bin) (3)插值查找( Search Ins) (4)斐波那契查找( Search fib) (5)次优查找树( BiTree sostree 动态查找 (1)在二叉排序树上进行查找( betsch)、插入结点( ins bstree和删除结点( del bstree (2)在二叉平衡树上插入结点( ins AVLtree和删除结点(delAⅤtree) (3)在B-树上插入结点( Ins btree.和删除结点( Del btree (4)在B+树上插入结点( Ins Petree和删除结点( Del PETree .内部排序 (1)简单排序法 直接插入排序( Insert sort 表插入排序(内含插入( Ins Tsort)重排( Arrange)两个算法) 起泡排序( Bubblesort 简单选择排序( SelectSort
3 ⚫ 深度优先搜索(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）斐波那契查找 (Search_Fib) （5）次优查找树(BiTree_SOSTree) 11．动态查找 （1）在二叉排序树上进行查找(bstsrch)、插入结点(ins_bstree)和删除结点(del_bstree) （2）在二叉平衡树上插入结点(ins_AVLtree) 和删除结点(del_AVLtree) （3）在 B-树上插入结点(Ins_BTree) 和 删除结点(Del_BTree) （4）在 B+树上插入结点(Ins_PBTree) 和 删除结点(Del_PBTree) 12．内部排序 （1）简单排序法 ⚫ 直接插入排序(Insert_sort) ⚫ 表插入排序(内含插入(Ins_Tsort) 重排(Arrange)两个算法) ⚫ 起泡排序(BubbleSort) ⚫ 简单选择排序(SelectSort)
(2)复杂排序法 ·堆排序( Heapsort 快速排序( QuickSort) 锦标赛排序( Tournament (3)其他 快速地址排序( QkAddrst) 基数排序( Radixsort .外部排序 (1)多路平衡归并排序( K-Merge (2)置换-选择排序( Repl selection) 、运行环境 1.硬件: Pentium100以上PC机 2.软件: Windows95及以上版本的操作系统 四、运行 本系统的执行文件为 DSDEMOW.EXE 五、如何使用本课件 读者可以利用鼠标移动光标选择“演示算法”或“菜单命令”来控制课件的运行过程 1.课件的演示算法菜单为页式菜单。第一级菜单中的各项与上述“系统内容”中各大项相对 应,读者运行“算法演示课件”后,即进入“算法选择一级菜单”画面,此时可移动光标进行 选择,当光标所在菜单项改为红色时,单击鼠标即进入“算法选择二级菜单”,进行相同操 作之后,或进入算法选择三级菜单(如图1所示),或进入算法演示的执行状态(如图2所
4 （2）复杂排序法 ⚫ 堆排序(HeapSort) ⚫ 快速排序(QuickSort) ⚫ 锦标赛排序(Tournament) （3）其他 ⚫ 快速地址排序（QkAddrst） ⚫ 基数排序(RadixSort) 13．外部排序 （1）多路平衡归并排序(K-Merge) （2）置换-选择排序(Repl_Selection) 三、运行环境 1. 硬件：Pentium100以上PC机。 2. 软件：Windows95及以上版本的操作系统。 四、运行 本系统的执行文件为DSDEMOW.EXE。 五、如何使用本课件 读者可以利用鼠标移动光标选择“演示算法”或“菜单命令”来控制课件的运行过程。 1． 课件的演示算法菜单为页式菜单。第一级菜单中的各项与上述“系统内容”中各大项相对 应，读者运行“算法演示课件”后, 即进入“算法选择一级菜单”画面，此时可移动光标进行 选择，当光标所在菜单项改为红色时，单击鼠标即进入“算法选择二级菜单”，进行相同操 作之后，或进入算法选择三级菜单（如图1所示），或进入算法演示的执行状态（如图2所 示）
1数据结构算法 级菜单 二叉树< 遍历< 级菜单 韩序遍质又树< 三级菜单 1中序遍历二》树 后序遍历二又树 ■ Pascal语言■C语言 图 强连通分 |函 强速通分量 ◆算法 THEN ufs tail(g:vi); [ufs head(g, vi):e AStrong Comp distal dfshead ◆变量 当前值 Finished 10 在算法选择菜单画面中,形如A的图标意为尚有下级菜单, 的图标则表 示将直接进入算法演示状态。此时也可直接单击一级菜单或二级菜单的标题直接返回之,注 意:菜单右侧上方的“退出”按钮意为退出整个演示课件
5 图1 图2 在算法选择菜单画面中，形如 的图标意为尚有下级菜单，形如 的图标则表 示将直接进入算法演示状态。此时也可直接单击一级菜单或二级菜单的标题直接返回之，注 意：菜单右侧上方的“退出”按钮意为退出整个演示课件。 三级菜单 一级菜单 二级菜单 三级菜单