汉诺塔和二叉树演示

　　数据结构算法演示(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）斐波那契查找 (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. 硬件：Pentium100以上PC机。 2. 软件：Windows95及以上版本的操作系统。 四、 运行 本系统的执行文件为DSDEMOW.EXE。 五、 如何使用本课件 读者可以利用鼠标移动光标选择“演示算法”或“菜单命令”来控制课件的运行过程。 1． 课件的演示算法菜单为页式菜单。第一级菜单中的各项与上述“系统内容”中各大项相对应，读者运行“算法演示课件”后, 即进入“算法选择一级菜单”画面，此时可移动光标进行选择，当光标所在菜单项改为红色时，单击鼠标即进入“算法选择二级菜单”，进行相同操作之后，或进入算法选择菜单（如图1所示），或进入算法演示的执行状态（如图2所示）。 图1 图2 在算法选择菜单画面中，形如 的图标意为尚有下级菜单，形如 的图标则表示将直接进入算法演示状态。此时也可直接单击一级菜单或二级菜单的标题直接返回之，注意：菜单右侧上方的“退出”按钮意为退出整个演示课件。 2． 算法演示执行状态下的屏幕分为三部分：第一行为“标题行”，第二行为“菜单命令”，以下为算法演示屏上各菜单的说明。 菜单命令中各项自左至右的功能分别为：  数据——设置算法演示的数据（数据结构）。  调用栈——察看当前函数（或过程）嵌套或递归的历程。  说明——察看算法说明。  暂停——中断演示过程。  执行——连续执行算法直至所设断点或至算法执行完毕。  单步——执行一行算法，遇到子程序调用时，连续执行完子程序。  跟踪——执行一行算法，遇到子程序调用时，进入子程序。  执行到——演示算法到当前所设最近的断点或算法窗口中的当前行。  恢复——重置屏幕为当前算法执行前的初始状态。  断点——在算法窗口的当前选择行设置断点或清除断点。  设置——设置连续演示时的速度或开/闭背景音乐（或动作音效）开关。  返回——返回算法选择菜单。 3． 断点的设置方法为：移动光标至“断点语句”所在行，点击鼠标后即出现绿色光条，之后单击“断点”菜单中的“设置断点”命令项即可，此时该断点语句所在行上将出现红色光条。 六、 算法演示屏的详细说明 本系统对屏幕设计的基本原则是集数据结构、算法和其他重要信息（如栈等）于同一屏幕。一般情况下演示屏由图示、算法和变量三个窗口组成，特殊情况下将根据演示内容适当增加。一般情况下， 左侧图示窗口显示演示数据的逻辑结构或存储结构，右侧上方窗口显示算法文本，右侧下方窗口显示当前算法中各变量的值或递归工作栈的状态。各窗口间的边界大小均可自由调节，且可按需扩大至全屏。 算法窗口显示当前演示的算法文本，并以深蓝色的光条覆盖将要执行的语句。若算法中含有函数或过程调用语句，则当光条覆盖到该过程调用语句时，随即自动隐去原算法文本而显示子过程的文本，而从此过程返回时再重新显示原算法文本。类似地，在演示递归算法执行过程时，每当执行递归调用本过程的语句时，随即隐去当前层次的算法文本而显示下一层的算法文本，并且以不同颜色的算法文本表示递归的不同层次。如第一层的算法文本为深绿色，第二层为紫色，第三层为深红色，第四层为深蓝色，第五层为浅蓝色，第六层为玫瑰红色等。 当演示递归算法执行过程中递归工作栈的变化状态时，递归工作栈显示在右侧下窗口，递归工作栈的状态和算法文本窗口中相应语句执行后的结果相对应，栈顶记录为当前递归层的参量值。每进入一层递归时，就产生一个新的工作记录（包括调用语句行号、变量参数或全程变量、数值参数和局部变量）压入栈顶；每退出一层递归时，先根据栈顶的调用语句行号返回至上层，然后在传递完变量参数的值后退栈。 各个算法演示屏的补充说明如下： 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)和它们之间的弧(ik)，灰白色表示已经输出的顶点；右下显示顶点的入度；右上显示入度为零的栈。当拓扑排序不成功时，在演示屏的中央将会弹出一个窗口，显示提示信息“网中存在自环！”，此时用户可在左下显示的有向图中由绿色顶点和黑色弧构成的子图中找到这个环。 26． 有向图的关键路径 图示窗口包含5部分信息。左上显示带入度域的邻接表；左下显示有向网的逻辑结构和顶点的入度及各顶点事件的最早发生时间和最迟发生时间；右下显示拓扑排序过程中入度为零的顶点的栈S，右上显示的栈 T 存放拓扑序列，其入栈顺序和栈 S 的出栈顺序相同，从栈顶到栈底的顶点顺序即为顶点的逆拓扑序列。算法执行结束后将弹出窗口列出全部结果，其中红色字体的弧表示关键活动。 27． 普里姆算法 图示窗口包含3部分内容。右上是邻接矩阵；左上是无向网的逻辑结构，图中顶点的初始状态为，算法执行过程中，红色覆盖的顶点和边则表示已加入生成树的顶点和生成树上的边；窗口的下方则显示 closedge 数组中的值。 28． 克鲁斯卡尔算法 图示窗口的左侧为无向网，以红色标定已落在生成树上的边；右侧自上而下列出各条边的信息以及选择生成树的边的执行过程。 29． 边界标识法 图示窗口的初始状态为 64KB 的模拟存储器，演示过程中，以绿色覆盖占用块。各个存储块的头部左侧所示为该块的起始地址，头部结构或其他信息参见教科书。用户可根据弹出窗口的操作提示信息进行操作，输入请求分配的空间大小或释放块的首地址。 30． 伙伴系统 在图示窗口中，左侧为可利用空间链表的逻辑结构，右侧为存储结构，其中红色覆盖部分为占用块。弹出窗口为输入窗口，由用户输入请求分配的空间大小或释放块的首地址。 31． 紧缩无用单元 右侧显示存储空间，空白表示空闲块，其他颜色覆盖表示占用块，在存储空间不足分配时将进行空闲块压缩。左侧显示存储映像。弹出窗口为输入窗口，由用户输入请求分配的空间大小和分配或释放块的块名。 32． 静态查找 上窗口为图示窗口，演示查找过程；左下和右下分别为算法文本和变量窗口。 33． B-树和B+树 整个屏幕分为上、下两个窗口，上窗口演示插入或删除结点过程中B-树或B+ 树结构的变化状况；下窗口内显示如查找关键字、插入位置、结点等操作信息。下窗口上面左侧的小窗口为编辑窗口，由用户输入待插或待删的关键字，输入之后其右侧的操作命令将由隐式状态改为显式状态。 34． 内部排序 图示窗口演示排序过程以及排序过程中关键字之间进行的比较次数和记录移动的次数。 七、 用户自行输入数据指南 算法操作的对象——数据结构，或由用户自行输入，或由系统随机产生，并在获得用户的确认之前，可反复随机产生，直至用户满意，用鼠标点击“OK”按钮确认为止。 多数情况下的输入界面上有足够的提示信息，以指示用户需要进行何种操作。补充说明如下： 1． 表的数据元素为任意的单个字符。 2． 迷宫的输入界面如图3所示。图中砖墙图案表示障碍，连续点击鼠标可将光标所在位置设置成通道或者障碍，建议用户先点击“随机生成”按钮随机生成一个迷宫，然后移动鼠标调整成所需。所设迷宫可以利用“保存数据”按钮生成dat类型文件，并在需要时可以利用“取出数据”按钮读入。 图3 3． 演示背包问题的算法之前，首先需要输入物品个数，之后将出现如图4所示的输入界面，可以利用“随机生成”的按钮或各个相应的小窗口输入物品体积 wi 和背包体积 T 。背包的总体积不得超过 30 ,单个物品的体积不得超过 10 。 图4 4． “表达式求值”和“建表达式树”时的输入界面如图5所示。用户可在窗口内自行输入，并以“Enter”键为结束符；也可以连续点击左侧蓝色的表达式由系统自动生成，直至用户点击右侧的计算器表示确认为止。“求值”可实现带括弧的四则运算和幂次运算，并支持sin、cos、tan、arcsin 和 arccos 等函数计算，其操作数为实数。“建树”的表达式仅限于带括弧的四则运算，其操作数为单个字母的字符。 图5 5． 稀疏矩阵的输入界面如图6所示。用户可随意进行矩阵中任意位置元素的输入，只要将光标移动至待输入的元素位置，单击鼠标后将弹出计算器，单击数字按钮，可进行随意输入，之后点击“OK”按钮表示确认。 图6 6． 广义表的数据输入方式为自左向右顺序输入广义表的字符串。输入过程中，图7所示输入界面中的“确定”为灰色字体，只有当用户正确输入完毕时，“确定”两字才改为黑色字体，此时用户可单击此按钮表示确认。 图7 7． 图的输入界面如图8所示。之前尚需确认是否为有向图和带权图。在用户自行输入图时，首先按下“创建节点”按钮，之后可移动光标至窗口的任意位置单击鼠标创建顶点；然后单击“创建弧”按钮，可在任意两个顶点之间构建弧或边。构建弧（或边）的操作为：先将光标移动至弧尾的顶点，单击一次鼠标，然后移动光标至弧头位置，再单击一次鼠标。对于带权的图，则在构建弧（或边）的同时，在当时弹出的窗口中输入权值，权值的默认值为 1。 图8 8． 内部排序的关键字均为单个字符。
　　案例一 贪吃蛇游戏 案例二 计算器 案例三 黑白棋游戏 案例四 迷宫问题 案例五 扫地雷游戏 案例六 速算24 案例七 数据结构CAI系统 7.3.1 栈的应用—递归算法（汉诺塔）演示 7.3.2 双链表创建演示 7.3.3 冒泡排序演示 7.3.4 基数排序演示 7.3.5 二分查找演示 7.3.6 二叉树遍历演示 案例八 进程调度 案例九 存储管理分区分配算法 案例十 通讯录 案例十一 学生成绩管理 案例十二 工资管理 案例十三 图书借阅管理 案例十四 教师工作量计算
　　一、 功能简介 本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法执行过程中数据的逻辑结构或存储结构的变化状况或递归算法执行过程中栈的变化状况。整个系统使用菜单驱动方式, 每个菜单包括若干菜单项。每个菜单项对应一个动作或一个子菜单。系统一直处于选择菜单项或执行动作状态, 直到选择了退出动作为止。 二、 系统内容 本系统内含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)和它们之间的弧(ik)，灰白色表示已经输出的顶点；右下显示顶点的入度；右上显示入度为零的栈。当拓扑排序不成功时，在演示屏的中央将会弹出一个窗口，显示提示信息“网中存在自环！”，此时用户可在左下显示的有向图中由绿色顶点和黑色弧构成的子图中找到这个环。 26． 有向图的关键路径 图示窗口包含5部分信息。左上显示带入度域的邻接表；左下显示有向网的逻辑结构和顶点的入度及各顶点事件的最早发生时间和最迟发生时间；右下显示拓扑排序过程中入度为零的顶点的栈S，右上显示的栈 T 存放拓扑序列，其入栈顺序和栈 S 的出栈顺序相同，从栈顶到栈底的顶点顺序即为顶点的逆拓扑序列。算法执行结束后将弹出窗口列出全部结果，其中红色字体的弧表示关键活动。 27． 普里姆算法 图示窗口包含3部分内容。右上是邻接矩阵；左上是无向网的逻辑结构，图中顶点的初始状态为，算法执行过程中，红色覆盖的顶点和边则表示已加入生成树的顶点和生成树上的边；窗口的下方则显示 closedge 数组中的值。 28． 克鲁斯卡尔算法 图示窗口的左侧为无向网，以红色标定已落在生成树上的边；右侧自上而下列出各条边的信息以及选择生成树的边的执行过程。 29． 边界标识法 图示窗口的初始状态为 64KB 的模拟存储器，演示过程中，以绿色覆盖占用块。各个存储块的头部左侧所示为该块的起始地址，头部结构或其他信息参见教科书。用户可根据弹出窗口的操作提示信息进行操作，输入请求分配的空间大小或释放块的首地址。 30． 伙伴系统 在图示窗口中，左侧为可利用空间链表的逻辑结构，右侧为存储结构，其中红色覆盖部分为占用块。弹出窗口为输入窗口，由用户输入请求分配的空间大小或释放块的首地址。 31． 紧缩无用单元 右侧显示存储空间，空白表示空闲块，其他颜色覆盖表示占用块，在存储空间不足分配时将进行空闲块压缩。左侧显示存储映像。弹出窗口为输入窗口，由用户输入请求分配的空间大小和分配或释放块的块名。 32． 静态查找 上窗口为图示窗口，演示查找过程；左下和右下分别为算法文本和变量窗口。 33． B-树和B+树 整个屏幕分为上、下两个窗口，上窗口演示插入或删除结点过程中B-树或B+ 树结构的变化状况；下窗口内显示如查找关键字、插入位置、结点等操作信息。下窗口上面左侧的小窗口为编辑窗口，由用户输入待插或待删的关键字，输入之后其右侧的操作命令将由隐式状态改为显式状态。 34． 内部排序 图示窗口演示排序过程以及排序过程中关键字之间进行的比较次数和记录移动的次数。
　　数据结构算法演示(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）斐波那契查找 (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. 硬件：Pentium100以上PC机。 2. 软件：Windows95及以上版本的操作系统。 四、 运行 本系统的执行文件为DSDEMOW.EXE。 五、 如何使用本课件 读者可以利用鼠标移动光标选择“演示算法”或“菜单命令”来控制课件的运行过程。 1． 课件的演示算法菜单为页式菜单。第一级菜单中的各项与上述“系统内容”中各大项相对应，读者运行“算法演示课件”后, 即进入“算法选择一级菜单”画面，此时可移动光标进行选择，当光标所在菜单项改为红色时，单击鼠标即进入“算法选择二级菜单”，进行相同操作之后，或进入算法选择菜单（如图1所示），或进入算法演示的执行状态（如图2所示）。 图1 图2 在算法选择菜单画面中，形如 的图标意为尚有下级菜单，形如 的图标则表示将直接进入算法演示状态。此时也可直接单击一级菜单或二级菜单的标题直接返回之，注意：菜单右侧上方的“退出”按钮意为退出整个演示课件。 2． 算法演示执行状态下的屏幕分为三部分：第一行为“标题行”，第二行为“菜单命令”，以下为算法演示屏上各菜单的说明。 菜单命令中各项自左至右的功能分别为：  数据——设置算法演示的数据（数据结构）。  调用栈——察看当前函数（或过程）嵌套或递归的历程。  说明——察看算法说明。  暂停——中断演示过程。  执行——连续执行算法直至所设断点或至算法执行完毕。  单步——执行一行算法，遇到子程序调用时，连续执行完子程序。  跟踪——执行一行算法，遇到子程序调用时，进入子程序。  执行到——演示算法到当前所设最近的断点或算法窗口中的当前行。  恢复——重置屏幕为当前算法执行前的初始状态。  断点——在算法窗口的当前选择行设置断点或清除断点。  设置——设置连续演示时的速度或开/闭背景音乐（或动作音效）开关。  返回——返回算法选择菜单。 3． 断点的设置方法为：移动光标至“断点语句”所在行，点击鼠标后即出现绿色光条，之后单击“断点”菜单中的“设置断点”命令项即可，此时该断点语句所在行上将出现红色光条。 六、 算法演示屏的详细说明 本系统对屏幕设计的基本原则是集数据结构、算法和其他重要信息（如栈等）于同一屏幕。一般情况下演示屏由图示、算法和变量三个窗口组成，特殊情况下将根据演示内容适当增加。一般情况下， 左侧图示窗口显示演示数据的逻辑结构或存储结构，右侧上方窗口显示算法文本，右侧下方窗口显示当前算法中各变量的值或递归工作栈的状态。各窗口间的边界大小均可自由调节，且可按需扩大至全屏。 算法窗口显示当前演示的算法文本，并以深蓝色的光条覆盖将要执行的语句。若算法中含有函数或过程调用语句，则当光条覆盖到该过程调用语句时，随即自动隐去原算法文本而显示子过程的文本，而从此过程返回时再重新显示原算法文本。类似地，在演示递归算法执行过程时，每当执行递归调用本过程的语句时，随即隐去当前层次的算法文本而显示下一层的算法文本，并且以不同颜色的算法文本表示递归的不同层次。如第一层的算法文本为深绿色，第二层为紫色，第三层为深红色，第四层为深蓝色，第五层为浅蓝色，第六层为玫瑰红色等。 当演示递归算法执行过程中递归工作栈的变化状态时，递归工作栈显示在右侧下窗口，递归工作栈的状态和算法文本窗口中相应语句执行后的结果相对应，栈顶记录为当前递归层的参量值。每进入一层递归时，就产生一个新的工作记录（包括调用语句行号、变量参数或全程变量、数值参数和局部变量）压入栈顶；每退出一层递归时，先根据栈顶的调用语句行号返回至上层，然后在传递完变量参数的值后退栈。 各个算法演示屏的补充说明如下： 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)和它们之间的弧(ik)，灰白色表示已经输出的顶点；右下显示顶点的入度；右上显示入度为零的栈。当拓扑排序不成功时，在演示屏的中央将会弹出一个窗口，显示提示信息“网中存在自环！”，此时用户可在左下显示的有向图中由绿色顶点和黑色弧构成的子图中找到这个环。 26． 有向图的关键路径 图示窗口包含5部分信息。左上显示带入度域的邻接表；左下显示有向网的逻辑结构和顶点的入度及各顶点事件的最早发生时间和最迟发生时间；右下显示拓扑排序过程中入度为零的顶点的栈S，右上显示的栈 T 存放拓扑序列，其入栈顺序和栈 S 的出栈顺序相同，从栈顶到栈底的顶点顺序即为顶点的逆拓扑序列。算法执行结束后将弹出窗口列出全部结果，其中红色字体的弧表示关键活动。 27． 普里姆算法 图示窗口包含3部分内容。右上是邻接矩阵；左上是无向网的逻辑结构，图中顶点的初始状态为，算法执行过程中，红色覆盖的顶点和边则表示已加入生成树的顶点和生成树上的边；窗口的下方则显示 closedge 数组中的值。 28． 克鲁斯卡尔算法 图示窗口的左侧为无向网，以红色标定已落在生成树上的边；右侧自上而下列出各条边的信息以及选择生成树的边的执行过程。 29． 边界标识法 图示窗口的初始状态为 64KB 的模拟存储器，演示过程中，以绿色覆盖占用块。各个存储块的头部左侧所示为该块的起始地址，头部结构或其他信息参见教科书。用户可根据弹出窗口的操作提示信息进行操作，输入请求分配的空间大小或释放块的首地址。 30． 伙伴系统 在图示窗口中，左侧为可利用空间链表的逻辑结构，右侧为存储结构，其中红色覆盖部分为占用块。弹出窗口为输入窗口，由用户输入请求分配的空间大小或释放块的首地址。 31． 紧缩无用单元 右侧显示存储空间，空白表示空闲块，其他颜色覆盖表示占用块，在存储空间不足分配时将进行空闲块压缩。左侧显示存储映像。弹出窗口为输入窗口，由用户输入请求分配的空间大小和分配或释放块的块名。 32． 静态查找 上窗口为图示窗口，演示查找过程；左下和右下分别为算法文本和变量窗口。 33． B-树和B+树 整个屏幕分为上、下两个窗口，上窗口演示插入或删除结点过程中B-树或B+ 树结构的变化状况；下窗口内显示如查找关键字、插入位置、结点等操作信息。下窗口上面左侧的小窗口为编辑窗口，由用户输入待插或待删的关键字，输入之后其右侧的操作命令将由隐式状态改为显式状态。 34． 内部排序 图示窗口演示排序过程以及排序过程中关键字之间进行的比较次数和记录移动的次数。 七、 用户自行输入数据指南 算法操作的对象——数据结构，或由用户自行输入，或由系统随机产生，并在获得用户的确认之前，可反复随机产生，直至用户满意，用鼠标点击“OK”按钮确认为止。 多数情况下的输入界面上有足够的提示信息，以指示用户需要进行何种操作。补充说明如下： 1． 表的数据元素为任意的单个字符。 2． 迷宫的输入界面如图3所示。图中砖墙图案表示障碍，连续点击鼠标可将光标所在位置设置成通道或者障碍，建议用户先点击“随机生成”按钮随机生成一个迷宫，然后移动鼠标调整成所需。所设迷宫可以利用“保存数据”按钮生成dat类型文件，并在需要时可以利用“取出数据”按钮读入。 图3 3． 演示背包问题的算法之前，首先需要输入物品个数，之后将出现如图4所示的输入界面，可以利用“随机生成”的按钮或各个相应的小窗口输入物品体积 wi 和背包体积 T 。背包的总体积不得超过 30 ,单个物品的体积不得超过 10 。 图4 4． “表达式求值”和“建表达式树”时的输入界面如图5所示。用户可在窗口内自行输入，并以“Enter”键为结束符；也可以连续点击左侧蓝色的表达式由系统自动生成，直至用户点击右侧的计算器表示确认为止。“求值”可实现带括弧的四则运算和幂次运算，并支持sin、cos、tan、arcsin 和 arccos 等函数计算，其操作数为实数。“建树”的表达式仅限于带括弧的四则运算，其操作数为单个字母的字符。 图5 5． 稀疏矩阵的输入界面如图6所示。用户可随意进行矩阵中任意位置元素的输入，只要将光标移动至待输入的元素位置，单击鼠标后将弹出计算器，单击数字按钮，可进行随意输入，之后点击“OK”按钮表示确认。 图6 6． 广义表的数据输入方式为自左向右顺序输入广义表的字符串。输入过程中，图7所示输入界面中的“确定”为灰色字体，只有当用户正确输入完毕时，“确定”两字才改为黑色字体，此时用户可单击此按钮表示确认。 图7 7． 图的输入界面如图8所示。之前尚需确认是否为有向图和带权图。在用户自行输入图时，首先按下“创建节点”按钮，之后可移动光标至窗口的任意位置单击鼠标创建顶点；然后单击“创建弧”按钮，可在任意两个顶点之间构建弧或边。构建弧（或边）的操作为：先将光标移动至弧尾的顶点，单击一次鼠标，然后移动光标至弧头位置，再单击一次鼠标。对于带权的图，则在构建弧（或边）的同时，在当时弹出的窗口中输入权值，权值的默认值为 1。 图8 8． 内部排序的关键字均为单个字符。
　　汉诺塔 演示程序 二叉树 演示动画 实现动态的观看到汉诺塔的盘子移动过程，动态的观看到树的遍历过程，树的查找过程
　　二分查找1.c 二分查找2.c 二叉树.c 单元加 单循环链表.c 单链表.c 图.c 字符 定长串.c 小写数字转为大写数字 带头结点双链循环线性表.c 底层编程 效验算法 数学问题 数据结构 数组 文件程序 求进制 汉诺塔 硬币情况 逆阵 链串.c 链栈.c 链队列.c 问题算法 顺序栈.c 顺序表.c 顺序队列.c ./ c语言窗体实例.zip 傻瓜递归.c 冒泡法改进.c 小字库DIY-.c 小字库DIY.c 小白鼠钻迷宫.c 扫描码.C 挽救软盘.c 汉字字模.c 神经元模型.c 穷举搜索法.c 简单数据库.c 编程汉字问题.txt 编随机数.c 试题.C 递堆法.C ./单元加 erre2.c erre.c 数组完全单元.c 栈单元加.c ./字符 单词倒转.c 反出字符.c 回文.c 字符串查找.c 字符编辑.c 字符编辑技术插入和删除 .c ./小写数字转为大写数字 小写数字转换成大写数字1.c 小写数字转换成大写数字2.c 小写数字转换成大写数字3.c ./底层编程 asm.c C标志符命名源程序.c ping.c winsock2.c 时间陷阱.c 检出错误.c 检测鼠标.c ./效验算法Crctable.c ./数学问题 乘法矩阵.c 凉东问题 十五人排序.c 叠代整除.c 四分砝码.c 圆周率 多位阶乘2.c 多位阶乘.c 大加数.c 大小倍约.c 大整数.c 完数.c 小孩分糖果.c 小明买书 平方根.c 数学算法 桃子猴问题 灯塔问题.c 百鸡百钱.c 简单计算器.c 苹果纠纷 递推.c 逻辑移动.c 阶乘递归.c 阿姆斯特朗数.c 黑白.c ./数学问题/凉东问题 32.c re.c 数组递归退出2.c 数组递归退出.c ./数学问题/圆周率 圆周率.c 狐狸圆周率.cpp ./数学问题/小明买书 小明买书.c 小明买书.cpp ./数学问题/数学算法 余弦曲线.c 余弦直线.c 符号图形.c 绘制圆.c ./数学问题/桃子猴问题 _notes 乘方函数桃子猴.c 桃子猴.c 猴子和桃.c 递归桃猴.c 题目.txt ./数学问题/桃子猴问题/_notes ./数学问题/苹果纠纷 ff.c 苹果分法.c ./数据结构 二叉排序树.c 二叉树实例.c 单链表 双链表正排序.c 各种排序法.c 哈夫曼算法.c 哈慢树.c 大整数.c 建树和遍历.c 排序法.c 推箱子.c 数据结构2.c 数据结构3.c 数据结构.c 无向图.c 栈操作.c 线性顺序存储结构.c 线索化二叉树.c 迷宫.c 迷宫问题.c 逆波兰计算器.c 递归车厢.c 队列.c ./数据结构/单链表 ww.c 冒泡排序.c 单链表1.c 单链表2.c 单链表.c 单链表倒序.c 单链表的处理全集.c 建立链表1.c 节点.c 质因子.c 链表十五人排序.c 链表（递归）.c ./数组 数字移动.c 数组操作.c 杨辉三角形.c 桶排序.c 矩阵转换.c 螺旋数组1.c 螺旋数组2.c ./文件程序 实例1.c 实例2.c 实例3.c 文件加密.c 文件复制.c 文件连接.c 自我复制.c 读写文本文件.c 输出自已.c ./求进制 16进制10进制.c 二进制数2.c 二进制数.c ./汉诺塔 四塔1.c 四塔2.c 换位递归.c 汉诺塔2.c 汉诺塔.c 诺汉塔画图版.c 非递归.c ./硬币情况 for循环的.c 硬币分法.c ./逆阵 简单逆阵.c 逆矩阵.c 逆阵.c ./问题算法 N皇后问题回溯算法.c 万年历 动态计算网络最长最短路线.c 矩阵乘法动态规划.c 网络最短路径Dijkstra算法.c 货郎担分枝限界图形演示.c 货郎担限界算法.c 骑士遍历 ./问题算法/万年历 万年历.c 万年历的算法 .c ./问题算法/骑士遍历 骑士遍历1.c 骑士遍历2.c 骑士遍历回逆.c
　　01-001数据结构的概念和基本术语、抽象数据类型的表示与实现 01-002算法设计的要求、算法效率的度量 02-001线线性表的顺序表示与实现、线单链表的创建与操作、加工型操作、单链表合并 03-001栈的定义与应用、循环链表的定义与操作 03-002栈的应用、数制转换、括号匹配、行编辑问题、迷宫问题 03-003栈的应用：表达式求值、后缀表达式的表示 03-004队列的定义与存储、顺序队列、链式队列、循环队列 04-001串的定义、表示与实现 04-002串的模式匹配算法 04-003串的模式匹配算法的一种改进算法 05-001数组的定义、顺序表示和实现 05-002矩阵相乘的一般算法、稀疏矩阵相乘算法 06-001树的定义和基本术语 06-002习题课：链表、双向循环链表的相关基本操作 06-003习题课：栈的基本操作、KMP算法回顾 06-004二叉树的定义、性质与存储结构 06-005二叉树的前序、中序和后序遍历的递归与非递归算法 06-006统计二叉树中叶子结点个数、按给定的先序序列建立二叉链表 06-007线树的存储结构、森林和二叉树的转换、树和森林的遍历 06-009建立树的存储结构的算法、输出树中所有从根到叶子结点路径的算法 06-010前缀编码、哈夫曼树、哈夫曼编码 07-001图的定义、术语与存储结构 07-002图的遍历：深度优先搜索和广度优先搜索 07-003最小生成树算法：普里姆算法、克鲁斯卡尔算法 07-004双连通图和关节点、源点到其他各点的最短路径 07-005每一对顶点间的最短路径、拓扑排序、关键路径 07-006广义表的定义、表示 07-007创建广义表的存储结构、广义表的删除 07-008习题课：广义表的存储、递归算法、汉诺塔问题、二叉树的基本操作 07-009习题课：图的简单路径、深度优先遍历图的非递归算法等 09-001顺序表的查找、有序表的查找、二分查找 09-002顺序表的查找与有序表的查找性能分析 09-003二分查找的平均查找长度、查找树表 09-004动态查找表：二叉排序树的插入和删除操作 09-005查找的性能分析、平衡二叉树、B-树的定义 09-006B-树的查找过程、B+树的定义与查找 09-007键树的结构特点、哈希表的定义、哈希表的构造方法 09-008哈希表的查找与删除操作、处理冲突的方法 10-001排序的定义、直接插入排序、冒泡排序、快速排序 10-002堆排序、多关键字的排序、基数排序、排序时间复杂度的分析 10-003外部排序的基本过程、索引文件、哈希文件的结构 10-004多关键字文件的特点、倒排文件、判定树、二叉平衡树
　　【内容简介】 本书可帮助读者： 通过由基于JAVA的演示所组成的可视专题讨论来掌握数据结构和算法 学会如何为常见和不太常见的编程条件选择正确的算法 利用数据结构和算法为现实世界的处理过程建模 了解不同的数据结构的优势和弱点，考虑如何利用它们改进编程的效率 学会如何用面向对象的编程简化数据结构和算法 本书以一种易懂的方式教授如何安排和操纵数据的问题，其中不乏一些难题；了解这些知识以期使计算机的应用获得最好的表现。 不管使用何种语言或平台，掌握了数据结构和算法将改进程序的质量和性能。 书中提供了一套独创的可视讨论专题用以阐明主要的论题；它使用JAVA语言说明重要的概念，而避免了C/C++语言的复杂性，以便集中精力论述数据结构和算法。 经验丰富的作者Robert Lafore先生提供了许多简单明了的例子，避免了对于这类命题常见的冗长、繁琐的数学证明。在第二版中，他利用Java语言最新特性，修改并扩充了他的例子。在每一章后都有问题和练习，使读者有机会测试自己的理解程序。 【原 书 名】 Data Structures & Algorithms in Java 【原出版社】 SAMS 【作者】[美]Robert Lafore [同作者作品] [作译者介绍] 【译者】 计晓云[同译者作品] 赵研 曾希 狄小菡 【丛 书 名】 国外经典计算机科学教材 【出 版 社】 中国电力出版社 【书 号】 7508319117 【出版日期】 2004年2月 【开 本】 16开 【页 码】 560 【版 次】2-1 本书以一种易懂的方式教授如何安排和操纵数据的问题，其中不乏一些难题；了解这些知识以期使计算机的应用获得最好的表现。不管使用何种语言或平台，掌握了数据结构和算法将改进程序的质量和性能。 书中提供了一套独创的可视讨论专题用以阐明主要的论题；它使用Java语言说明重要的概念，而避免C/C++语言的复杂性，以便集中精力论述数据结构和算法。 经验丰富的作者Robert Lafore先生提供了许多简单明了的例子，避免了对于这类命题常见的冗长、繁琐的数学证明。在第二版中，他利用Java语言最新特性，修改并扩充了他的例子。在每一章后都有问题和练习，使读者有机会测试自己的理解程序。 出版说明 献词 简介 第1章 综述 数据结构和算法能起到什么作用？ 数据结构的概述 算法的概述 一些定义 面向对象编程 软件工程 对于C++程序员的Java Java数据结构的类库 小结 问题 第2章 数组 Array专题Applet Java中数组的基础知识 将程序划分成类 类接口 Ordered专题applet 有序数组的Java代码 对数 存储对象 大O表示法 为什么不用数组表示一切？ 小结 问题 实验 编程作业 第3章 简单排序 如何排序？ 冒泡排序 选择排序 插入排序 对象排序 几种简单排序之间的比较 小结 问题 实验 编程作业 第4章 栈和队列 不同的结构类型 栈 队列 优先级队列 解析算术表达式 小结 问题 实验 编程作业 第5章 链表 链结点（Link） LinkList专题Applet 单链表 查找和删除指定链结点 双端链表 链表的效率 抽象数据类型 有序链表 双向链表 迭代器 小结 问题 实验 编程作业 第6章 递归 三角数字 阶乘 变位字 递归的二分查找 汉诺（Hanoi）塔问题 归并排序 清除递归 一些有趣的递归应用 小结 问题 实验 编程作业 第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树 为什么使用二叉树？ 树的术语 一个类比 二叉搜索树如何工作 查找节点 插入一个节点 遍历树 查找最大值和最小值 删除节点 二叉树的效率 用数组表示树 重复关键字 完整的tree.java程序 哈夫曼（Huffman）编码 小结 问题 实验 编程作业 第9章 红-黑树 本章讨论的方法 平衡树和非平衡树 使用RBTree专题applet 用专题applet做试验 旋转 插入一个新节点 删除 红-黑树的效率 红-黑树的实现 其他平衡树 小结 问题 实验 第10章 2-3-4树和外部存储 2-3-4树的介绍 Tree234专题applet 2-3-4树的Java代码 2-3-4树和红-黑树 2-3-4树的效率 2-3树 外部存储 小结 问题 实验 编程作业 第11章 哈希表 哈希化简介 开放地址法 链地址法 哈希函数 哈希化的效率 哈希化和外部存储 小结 问题 实验 编程作业 第12章 堆 堆的介绍 Heap专题applet 堆的Java代码 基于树的堆 堆排序 小结 问题 实验 编程作业 第13章 图 图简介 搜索 最小生成树 有向图的拓扑排序 有向图的连通性 小结 问题 实验 编程作业 第14章 带权图 带权图的最小生成树 最短路径问题 每一对顶点之间的最短路径问题 效率 难题 小结 问题 实验 编程作业 第15章 应用场合 通过数据结构 专用数据结构 排序 图 外部存储 前进 附录A 运行专题applet和示例程序 专题applet 示例程序 Sun Microsystem软件开发工具集 重名的类文件 其他开发系统 附录B 进一步学习 数据结构和算法 面向对象程序语言 面向对象设计（OOD）和软件工程 附录C 问题答案 第1章，综述 第2章，数组 第3章，简单排序 第4章，栈与队列 第5章，链表 第6章，递归 第7章，高级排序 第8章，二叉树 第9章，红-黑树 第10章，2-3-4树和外部存储 第11章，哈希表 第12章，堆 第13章，图 第14章，带权图
　　因为小弟权限不够，所以分开两个帖子上存，资源名称分别是： Java数据结构和算法中文第二版(1) Java数据结构和算法中文第二版(2) 【内容简介】 本书可帮助读者： 通过由基于JAVA的演示所组成的可视专题讨论来掌握数据结构和算法 学会如何为常见和不太常见的编程条件选择正确的算法 利用数据结构和算法为现实世界的处理过程建模 了解不同的数据结构的优势和弱点，考虑如何利用它们改进编程的效率 学会如何用面向对象的编程简化数据结构和算法 本书以一种易懂的方式教授如何安排和操纵数据的问题，其中不乏一些难题；了解这些知识以期使计算机的应用获得最好的表现。 不管使用何种语言或平台，掌握了数据结构和算法将改进程序的质量和性能。 书中提供了一套独创的可视讨论专题用以阐明主要的论题；它使用JAVA语言说明重要的概念，而避免了C/C++语言的复杂性，以便集中精力论述数据结构和算法。 经验丰富的作者Robert Lafore先生提供了许多简单明了的例子，避免了对于这类命题常见的冗长、繁琐的数学证明。在第二版中，他利用Java语言最新特性，修改并扩充了他的例子。在每一章后都有问题和练习，使读者有机会测试自己的理解程序。 【原 书 名】 Data Structures & Algorithms in Java 【原出版社】 SAMS 【作者】[美]Robert Lafore [同作者作品] [作译者介绍] 【译者】 计晓云[同译者作品] 赵研 曾希 狄小菡 【丛 书 名】 国外经典计算机科学教材 【出 版 社】 中国电力出版社 【书 号】 7508319117 【出版日期】 2004年2月 【开 本】 16开 【页 码】 560 【版 次】2-1 本书以一种易懂的方式教授如何安排和操纵数据的问题，其中不乏一些难题；了解这些知识以期使计算机的应用获得最好的表现。不管使用何种语言或平台，掌握了数据结构和算法将改进程序的质量和性能。 书中提供了一套独创的可视讨论专题用以阐明主要的论题；它使用Java语言说明重要的概念，而避免C/C++语言的复杂性，以便集中精力论述数据结构和算法。 经验丰富的作者Robert Lafore先生提供了许多简单明了的例子，避免了对于这类命题常见的冗长、繁琐的数学证明。在第二版中，他利用Java语言最新特性，修改并扩充了他的例子。在每一章后都有问题和练习，使读者有机会测试自己的理解程序。 出版说明 献词 简介 第1章 综述 数据结构和算法能起到什么作用？ 数据结构的概述 算法的概述 一些定义 面向对象编程 软件工程 对于C++程序员的Java Java数据结构的类库 小结 问题 第2章 数组 Array专题Applet Java中数组的基础知识 将程序划分成类 类接口 Ordered专题applet 有序数组的Java代码 对数 存储对象 大O表示法 为什么不用数组表示一切？ 小结 问题 实验 编程作业 第3章 简单排序 如何排序？ 冒泡排序 选择排序 插入排序 对象排序 几种简单排序之间的比较 小结 问题 实验 编程作业 第4章 栈和队列 不同的结构类型 栈 队列 优先级队列 解析算术表达式 小结 问题 实验 编程作业 第5章 链表 链结点（Link） LinkList专题Applet 单链表 查找和删除指定链结点 双端链表 链表的效率 抽象数据类型 有序链表 双向链表 迭代器 小结 问题 实验 编程作业 第6章 递归 三角数字 阶乘 变位字 递归的二分查找 汉诺（Hanoi）塔问题 归并排序 清除递归 一些有趣的递归应用 小结 问题 实验 编程作业 第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树 为什么使用二叉树？ 树的术语 一个类比 二叉搜索树如何工作 查找节点 插入一个节点 遍历树 查找最大值和最小值 删除节点 二叉树的效率 用数组表示树 重复关键字 完整的tree.java程序 哈夫曼（Huffman）编码 小结 问题 实验 编程作业 第9章 红-黑树 本章讨论的方法 平衡树和非平衡树 使用RBTree专题applet 用专题applet做试验 旋转 插入一个新节点 删除 红-黑树的效率 红-黑树的实现 其他平衡树 小结 问题 实验 第10章 2-3-4树和外部存储 2-3-4树的介绍 Tree234专题applet 2-3-4树的Java代码 2-3-4树和红-黑树 2-3-4树的效率 2-3树 外部存储 小结 问题 实验 编程作业 第11章 哈希表 哈希化简介 开放地址法 链地址法 哈希函数 哈希化的效率 哈希化和外部存储 小结 问题 实验 编程作业 第12章 堆 堆的介绍 Heap专题applet 堆的Java代码 基于树的堆 堆排序 小结 问题 实验 编程作业 第13章 图 图简介 搜索 最小生成树 有向图的拓扑排序 有向图的连通性 小结 问题 实验 编程作业 第14章 带权图 带权图的最小生成树 最短路径问题 每一对顶点之间的最短路径问题 效率 难题 小结 问题 实验 编程作业 第15章 应用场合 通过数据结构 专用数据结构 排序 图 外部存储 前进 附录A 运行专题applet和示例程序 专题applet 示例程序 Sun Microsystem软件开发工具集 重名的类文件 其他开发系统 附录B 进一步学习 数据结构和算法 面向对象程序语言 面向对象设计（OOD）和软件工程 附录C 问题答案 第1章，综述 第2章，数组 第3章，简单排序 第4章，栈与队列 第5章，链表 第6章，递归 第7章，高级排序 第8章，二叉树 第9章，红-黑树 第10章，2-3-4树和外部存储 第11章，哈希表 第12章，堆 第13章，图 第14章，带权图
　　编程思路：首先在程序开始处，开通语句#include引入头函数，建立函数，然后定义结构体变量Snow，并且编写雪花的一系列操作的函数；最后在main函数的内部实现对各子函数的调用，实现雪花飘落的过程。 三．主要解决问题的方法及技术关键 1．用keyx,keyy函数完成对内存空间保存，用DrawSnow函数完具体实现，change函数改变雪的颜色，Choose选择演示内容Init(void),Close(void)函数完成图形驱动和关闭等。 2．结构体函数实现图形的关闭，区域保存，在雪中输出文字等.用While，for循环，If语句等完成雪花的设计，包括速度、颜色、显示标题、闪烁效果等 。 3．用起泡排序、汉诺塔、双链表、起泡排序、基数排序、二分查找、二叉树遍历等设置雪花颜色。