数据结构算法演示

《数据结构算法演示》由会员分享，可在线阅读，更多相关《数据结构算法演示（14页珍藏版）》请在金锄头文库上搜索。

1、数据结构算法演示(Windows版)使用手册一、功能简介本课件是一个动态演示数据结构算法执行过程的辅助教学软件 , 它可适应读者对算法的输入数据 和过程执行的控制方式的不同需求 , 在计算机的屏幕上显示算法执行过程中数据的逻辑结构或存储结 构的变化状况或递归算法执行过程中栈的变化状况。整个系统使用菜单驱动方式 , 每个菜单包括若干 菜单项。每个菜单项对应一个动作或一个子菜单。系统一直处于选择菜单项或执行动作状态 , 直到选 择了退出动作为止。二、系统内容本系统内含84个算法，分属 13部分内容，由主菜单显示，与数据结构教科书中自第 2章至第 11章中相对应。各部分演示算法如下：1顺序表(1 )

2、在顺序表中插入一个数据元素(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) 栈的输出序列(

3、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)快

4、速矩阵转置 (Fast_Transpos)( 3)矩阵乘法 (Multiply_Sparmat)6广义表(1) 求广义表的深度(Ls_Depth)(2) 复制广义表(Ls_Copy)(3) 创建广义表的存储结构(Crt_Lists)7二叉树( 1 )遍历二叉树 先序遍历(Pre_order) 中序遍历(I n_order)后序遍历(Post_order)(2) 按先序建二叉树(CrtBT_PreOdr)(3) 线索二叉树 二叉树的线索化 生成先序线索(前驱或后继)(Pre_thre) 中序线索(前驱或后继)(In_thre) 后序线索(前驱或后继)(Post_thre) 遍历中序线索二叉树(I

5、norder_thlinked) 中序线索树的插入(i ns_lchild_inthr)和删除(del_lchild_inthr)结点(4) 建赫夫曼树和求赫夫曼编码(HufftaanCoding)(5) 森林转化成二叉树(Forest2BT)(6) 二叉树转化成森林(BT2Forest)(7) 按表达式建树(ExpTree)并求值(CalExpTreeByPostOrderTrav) 8图( 1 )图的遍历 深度优先搜索(Travel_DFS) 广度优先搜索(Travel_BFS)(2) 求有向图的强连通分量(Strong_comp)(3) 有向无环图的两个算法 拓扑排序(Toposort)

6、关键路径(Critical_path)( 4)求最小生成树 普里姆算法(Prim) 克鲁斯卡尔算法(Kruscal)(5 )求关节点和重连通分量(Get_artical)( 6)求最短路径 弗洛伊德算法(shortpath_Floyd) 迪杰斯特拉算法(shortpath_DJ)9存储管理( 1)边界标识法 (Boundary_tag_method)( 2)伙伴系统 (Buddy_system)( 3)紧缩无用单元 (Storage_compaction)10静态查找(1)顺序查找(Search_Seq)( 2)折半查找 (Serch_Bin)( 3)插值查找 (Search_Ins)( 4)

7、斐波那契查找 (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)重排(Ar

8、range)两个算法) 起泡排序(BubbleSort) 简单选择排序(SelectSort)(2)复杂排序法堆排序(HeapSort) 快速排序(Quicksort) 锦标赛排序(Tournament)(3)其他 快速地址排序(QkAddrst) 基数排序(RadixSort)13外部排序(1) 多路平衡归并排序(K-Merge)(2) 置换-选择排序(Repl_Selection)三、运行环境1. 硬件：PentiumlO0以上PC机。2. 软件：Windows95及以上版本的操作系统。四、运行本系统的执行文件为DSDEMOW.EXE。五、如何使用本课件 读者可以利用鼠标移动光标选择“演示

9、算法”或“菜单命令”来控制课件的运行过程。1课件的演示算法菜单为页式菜单。第一级菜单中的各项与上述“系统内容”中各大项相对 应，读者运行“算法演示课件”后 , 即进入“算法选择一级菜单”画面，此时可移动光标进 行选择，当光标所在菜单项改为红色时，单击鼠标即进入“算法选择二级菜单”，进行相同 操作之后，或进入算法选择三级菜单(如图 1所示)，或进入算法演示的执行状态(如图 2所 示)。二级菜单序遍历土叉树三级菜单退出巍数据结构算法二叉树 扇遍历一级菜单0?中序遍历三则 巒后序遍历二文树 Pascal语言 C语言图1图2在算法选择菜单画面中，形如旦區的图标意为尚有下级菜单，示将直接进入算法演示状态

10、。此时也可直接单击一级菜单或二级菜单的标题直接返回之，注 意：菜单右侧上方的“退出”按钮意为退出整个演示课件。2算法演示执行状态下的屏幕分为三部分：第一行为“标题行”，第二行为“菜单命令”，以下为算法演示屏上各菜单的说明。菜单命令中各项自左至右的功能分别为： 数据一一设置算法演示的数据（数据结构）。 调用栈一一察看当前函数（或过程）嵌套或递归的历程。 说明一一察看算法说明。 暂停一一中断演示过程。 执行一一连续执行算法直至所设断点或至算法执行完毕。 单步一一执行一行算法，遇到子程序调用时，连续执行完子程序。 跟踪一一执行一行算法，遇到子程序调用时，进入子程序。 执行到一一演示算法到当前所设最近

11、的断点或算法窗口中的当前行。 恢复一一重置屏幕为当前算法执行前的初始状态。 断点一一在算法窗口的当前选择行设置断点或清除断点。 设置一一设置连续演示时的速度或开/闭背景音乐（或动作音效）开关。 返回一一返回算法选择菜单。 3断点的设置方法为：移动光标至“断点语句”所在行，点击鼠标后即出现绿色光条，之后单击“断点”菜单中的“设置断点”命令项即可，此时该断点语句所在行上将出现红色光条。六、算法演示屏的详细说明 本系统对屏幕设计的基本原则是集数据结构、算法和其他重要信息（如栈等）于同一屏幕。一般 情况下演示屏由图示、算法和变量三个窗口组成，特殊情况下将根据演示内容适当增加。一般情况 下， 左侧图示窗

12、口显示演示数据的逻辑结构或存储结构，右侧上方窗口显示算法文本，右侧下方窗 口显示当前算法中各变量的值或递归工作栈的状态。各窗口间的边界大小均可自由调节，且可按需扩 大至全屏。算法窗口显示当前演示的算法文本，并以深蓝色的光条覆盖将要执行的语句。若算法中含有函数 或过程调用语句，则当光条覆盖到该过程调用语句时，随即自动隐去原算法文本而显示子过程的文 本，而从此过程返回时再重新显示原算法文本。类似地，在演示递归算法执行过程时，每当执行递归 调用本过程的语句时，随即隐去当前层次的算法文本而显示下一层的算法文本，并且以不同颜色的算 法文本表示递归的不同层次。如第一层的算法文本为深绿色，第二层为紫色，第三

13、层为深红色，第四 层为深蓝色，第五层为浅蓝色，第六层为玫瑰红色等。当演示递归算法执行过程中递归工作栈的变化状态时，递归工作栈显示在右侧下窗口，递归工作 栈的状态和算法文本窗口中相应语句执行后的结果相对应，栈顶记录为当前递归层的参量值。每进入 一层递归时，就产生一个新的工作记录（包括调用语句行号、变量参数或全程变量、数值参数和局部 变量）压入栈顶；每退出一层递归时，先根据栈顶的调用语句行号返回至上层，然后在传递完变量参 数的值后退栈。各个算法演示屏的补充说明如下：1顺序表和链表的插入、删除和链表的生成 算法演示屏由显示顺序表或链表的图示、算法文本及变量等三个窗口组成。在演示算法之前，需 先在弹出

14、的小窗口中输入线性表的数据元素及算法参数i（插入或删除的位置）和b （被插的数据元 素）的值。顺序表的图示窗口在演示屏的上方，链表的图示窗口在左侧。2有序表的操作算法演示屏的状态和 1 中所述相同。3汉诺塔问题 算法演示屏由4个窗口组成。右侧上方为算法文本，在算法中有4个形式参量，其中值参 n 为圆 盘个数，x、y、和z分别表示3个塔座；右侧下方为递归工作栈，栈中每个记录包含调用语句行号 adr及值参n和x、y、z；左侧上方显示汉诺塔图形及移动操作结果；左侧下方显示移动操作的记 录。4迷宫问题左侧窗口显示迷宫的逻辑结构，由NXN个方格组成，左上1,1为入口，右下N,N为出口，并 且以红色钉子填

15、充表示障碍，空白表示通路，红色交通灯表示已游历过的路，箭头表示继续游历的方 向，演示结束时显示一条通路或迷宫不通的信息。右侧下窗口为递归工作栈，栈中每个记录含 6个数 据项，其中 adr 指示调用语句行号， k 指示步数， （x,y） 表示当前坐标， i 指示路径方向（起始方向 为 1，顺时针方向旋转搜索）。5 皇后问题左侧图示窗口包含棋盘和递归工作栈两部分，栈中记录含3个数据项，其中adr指示调用语句行 号， k 指示列号， i 指示行号。此算法演示可求得所有可行结果，在求得每一种排布的结果之后，均 会弹出一个窗口显示“找到第j （j=1,2,）种排布”，单击“确定”按钮将继续进行，直至找到所有 可能构成的排布。6背包问题右侧图示窗口的上方显示背包、物件及其体积。 若有解，则在求得每一组结果之后，均会弹出 一个窗口提示求得一组解，单击提示窗口中的小人将继续进行。该窗口的下方为递归工作栈，栈中的 记录含3个数据项，其