English
资源说明：一、 功能简介
本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法执行过程中数据的逻辑结构或存储结构的变化状况或递归算法执行过程中栈的变化状况。整个系统使用菜单驱动方式, 每个菜单包括若干菜单项。每个菜单项对应一个动作或一个子菜单。系统一直处于选择菜单项或执行动作状态, 直到选择了退出动作为止。
二、 系统内容
本系统内含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）斐波那契查找 (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)
13． 外部排序
（1）多路平衡归并排序(K-Merge)
（2）置换-选择排序(Repl_Selection)
各个算法演示屏的补充说明如下：
1． 顺序表和链表的插入、删除和链表的生成
算法演示屏由显示顺序表或链表的图示、算法文本及变量等三个窗口组成。在演示算法之前，需先在弹出的小窗口中输入线性表的数据元素及算法参数 i（插入或删除的位置）和 b（被插的数据元素）的值。顺序表的图示窗口在演示屏的上方，链表的图示窗口在左侧。
2． 有序表的操作
算法演示屏的状态和 1 中所述相同。
3． 汉诺塔问题
算法演示屏由4个窗口组成。右侧上方为算法文本，在算法中有4个形式参量，其中值参 n 为圆盘个数，x、y、和 z 分别表示3个塔座；右侧下方为递归工作栈，栈中每个记录包含调用语句行号 adr 及值参 n 和 x、y、z；左侧上方显示汉诺塔图形及移动操作结果；左侧下方显示移动操作的记录。
4． 迷宫问题
左侧窗口显示迷宫的逻辑结构，由 N×N 个方格组成，左上[1,1]为入口，右下[N,N]为出口，并且以红色钉子填充表示障碍，空白表示通路，红色交通灯表示已游历过的路，箭头表示继续游历的方向，演示结束时显示一条通路或迷宫不通的信息。右侧下窗口为递归工作栈，栈中每个记录含6个数据项，其中 adr 指示调用语句行号，k 指示步数，(x,y) 表示当前坐标，i 指示路径方向（起始方向为 1，顺时针方向旋转搜索）。
5． 皇后问题
左侧图示窗口包含棋盘和递归工作栈两部分，栈中记录含3个数据项，其中 adr 指示调用语句行号，k 指示列号，i 指示行号。此算法演示可求得所有可行结果，在求得每一种排布的结果之后，均会弹出一个窗口显示“找到第 j (j=1,2,…) 种排布”，单击“确定”按钮将继续进行，直至找到所有可能构成的排布。
6． 背包问题
右侧图示窗口的上方显示背包、物件及其体积。 若有解，则在求得每一组结果之后，均会弹出一个窗口提示求得一组解，单击提示窗口中的小人将继续进行。该窗口的下方为递归工作栈，栈中的记录含3个数据项，其中 adr 指示调用语句所在行号，n 指示物件个数，t 指示背包总体积。
7． 阿克曼函数
整个演示屏只有显示算法文本和显示算法执行过程中栈的状态两个窗口。在执行算法之前，首先应按照提示输入参数 m 和 n 的值。
8． 栈的输出序列
图示窗口的内容为：由算法 Gen 生成的栈的操作序列(列出在窗口的下方)、算法 Perform 执行时栈的操作过程（该窗口的上方）以及算法 Perform 执行的结果——栈的输出序列（列出在图示窗口的右侧）。
9． 表达式求值
图示窗口的内容主要为显示表达式求值过程中操作数栈和运算符栈的变化情况以及主要操作。上方的小窗口显示在算法演示之前设定的表达式。
10． 离散事件模拟
图示窗口分成3部分：中间部分或显示客户流动情况的动画，或显示程序执行过程中事件表和4个队列的数值，上方两个按钮用以切换动画或静态数据，下方则显示客户总人数、客户逗留的累计时间以及调节动画中小人移动速度的指针。
11． 串的模式匹配
上窗口显示算法文本，下窗口显示串的匹配过程或求 next 函数的过程。
12． 稀疏矩阵
图示窗口显示矩阵的状态或其三元组的表示。
13． 求广义表的深度
图示窗口显示广义表的存储结构，图中指针 ls 指向当前所求深度的广义表，值为空时不显示。演示结束时弹出窗口显示求得的深度。
14． 复制广义表
图示窗口的上方显示已知广义表的存储结构，图示窗口的下方显示复制求得的广义表的存储结构。递归工作栈中含调用语句行号 adr、变参 nls 和值参 ls。
15． 创建广义表的存储结构
图示窗口显示广义表存储结构的建立过程和算法执行过程中参数Sub的当前值。
16． 遍历二叉树
图示窗口显示二叉树的逻辑结构和遍历结果输出的结点序列，图中指针 bt 指向当前遍历的二叉树的根结点。
17． 线索二叉树
图示窗口显示二叉树的存储结构，但结点中只含标志域，而以结点间的黑色连线表示指针，红色连线表示前驱线索，蓝色连线表示后继线索。在二叉树线索化的过程中，图中指针 p 指向当前层二叉树的根结点，指针 pre 指向当前被访问的结点的前驱。在演示线索树的插入和删除过程时，图示窗口的下方还包括“输入行”和“提示行”。
18． 按先序序列建二叉链表
图示窗口显示输入的先序序列和生成二叉链表的过程。
19． 森林和二叉树的相互转换
图示窗口在显示屏的上方，其左侧为森林，右侧为二叉树。
20． 赫夫曼树和赫夫曼编码
图示窗口显示生成的赫夫曼树的逻辑结构和每个叶子结点的编码。
21． 图的深度优先搜索
图示窗口的上半部分显示图的逻辑结构，初始状态用青色圆圈表示顶点，结点间的黑色连线表示边或弧（连线上画有箭头）。演示过程中用红色覆盖已访问的顶点和边（或弧）。窗口下方显示图的邻接表，演示过程中以红色框边表示已访问过的弧。图示窗口的下方显示遍历后输出的顶点序列。
22． 图的广度优先搜索
与深度优先不同的是，在窗口的下方增加一个队列，其左端为队头，右端为队尾。
23． 求有向图的强连通分量
图示窗口自上而下分别显示有向图的逻辑结构、存储结构和 Finished 数组在算法执行过程中的变化情况。所求得的各个强连通分量，将以不同颜色的顶点组表示。
24． 求关节点和重连通分量
图示窗口的上半部分显示无向图，下半部分自上而下分别显示 Vexnum、Vexdata、Visited、Low、Squlow（求得 low 值的顺序）和 artpoint（关节点）的信息。
25． 有向图的拓扑排序
图示窗口由5部分组成。其中左上显示有向图的邻接表；左下显示有向图，其中顶点和弧的初始状态分别为绿色和黑色，从栈中退出的顶点(i)用红色表示，分别以蓝色和红色指示当前访问的邻接点(k)和它们之间的弧(ik)，灰白色表示已经输出的顶点；右下显示顶点的入度；右上显示入度为零的栈。当拓扑排序不成功时，在演示屏的中央将会弹出一个窗口，显示提示信息“网中存在自环！”，此时用户可在左下显示的有向图中由绿色顶点和黑色弧构成的子图中找到这个环。
26． 有向图的关键路径
图示窗口包含5部分信息。左上显示带入度域的邻接表；左下显示有向网的逻辑结构和顶点的入度及各顶点事件的最早发生时间和最迟发生时间；右下显示拓扑排序过程中入度为零的顶点的栈S，右上显示的栈 T 存放拓扑序列，其入栈顺序和栈 S 的出栈顺序相同，从栈顶到栈底的顶点顺序即为顶点的逆拓扑序列。算法执行结束后将弹出窗口列出全部结果，其中红色字体的弧表示关键活动。
27． 普里姆算法
图示窗口包含3部分内容。右上是邻接矩阵；左上是无向网的逻辑结构，图中顶点的初始状态为黄色，算法执行过程中，红色覆盖的顶点和边则表示已加入生成树的顶点和生成树上的边；窗口的下方则显示 closedge 数组中的值。
28． 克鲁斯卡尔算法
图示窗口的左侧为无向网，以红色标定已落在生成树上的边；右侧自上而下列出各条边的信息以及选择生成树的边的执行过程。
29． 边界标识法
图示窗口的初始状态为 64KB 的模拟存储器，演示过程中，以绿色覆盖占用块。各个存储块的头部左侧所示为该块的起始地址，头部结构或其他信息参见教科书。用户可根据弹出窗口的操作提示信息进行操作，输入请求分配的空间大小或释放块的首地址。
30． 伙伴系统
在图示窗口中，左侧为可利用空间链表的逻辑结构，右侧为存储结构，其中红色覆盖部分为占用块。弹出窗口为输入窗口，由用户输入请求分配的空间大小或释放块的首地址。
31． 紧缩无用单元
右侧显示存储空间，空白表示空闲块，其他颜色覆盖表示占用块，在存储空间不足分配时将进行空闲块压缩。左侧显示存储映像。弹出窗口为输入窗口，由用户输入请求分配的空间大小和分配或释放块的块名。
32． 静态查找
上窗口为图示窗口，演示查找过程；左下和右下分别为算法文本和变量窗口。
33． B-树和B+树
整个屏幕分为上、下两个窗口，上窗口演示插入或删除结点过程中B-树或B+ 树结构的变化状况；下窗口内显示如查找关键字、插入位置、结点分裂等操作信息。下窗口上面左侧的小窗口为编辑窗口，由用户输入待插或待删的关键字，输入之后其右侧的操作命令将由隐式状态改为显式状态。
34． 内部排序
图示窗口演示排序过程以及排序过程中关键字之间进行的比较次数和记录移动的次数。
本源码包内暂不包含可直接显示的源代码文件，请下载源码包。
