? 若ax=bx，则数出拆分，退栈兵修改栈顶元
素，返回（2）
i=i-1;a[i]=a[i]+1,ax=a[i],bx=b[i] ? 其余情况，bx/2
回（2）
a[i]=a[i]+1,ax=a[i]
实验三 二叉树的操作
一．实验目的
1、 基本要求：深刻理解二叉树性质和及各种存储结构的特点及适用范围；掌握用指针类型描述、访问和处理二叉树的运算；熟练掌握二叉树的遍历算法；
2、 较高要求: 在遍历算法的基础上设计二叉树更复杂操作算法；认识哈夫曼树、哈夫曼编码的作用和意义;掌握树与森林的存储与便利。 二. 实验学时：
课内实验学时：3学时 课外实验学时：6学时 三．备选实验题目
1． 以二叉链表为存储结构，实现二叉树的创建、遍历（实验类型：验证型）
1）问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能：
1…建立树
2…前序遍历树
3…中序(非递归)遍历树
14
4…后序遍历树
0…结束
2）实验要求：在程序中定义下述函数，并实现要求的函数功能：
CreateTree(): 按从键盘输入的前序序列，创建树 PreOrderTree()：前序遍历树（递归） InOrderTree()：中序(非递归)遍历树 LaOrderTree(): 后序遍历树（递归） 3）实验提示:
? 二叉链表存储数据类型定义
# define ElemType char //元素类型 typedef struct BiTNode { ElemType data;
struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;
? 元素类型可以根据实际情况选取。 4）注意问题:
? 注意理解递归算法的执行步骤。 ? 注意字符类型数据在输入时的处理。 ? 重点理解如何利用栈结构实现非递归算法
2． 编写算法交换二叉树中所有结点的左、右子树（实验类型：综合型）
1）问题描述：编写一算法，交换二叉树中所有结点的左、右子树
2）实验要求：以二叉链表作为存储结构
15
3) 实现提示：设二叉树的根指针未t，且以二叉链表表示，可利用一个类型为seqstack的指针来实现，且栈单元包含两个域，一个为data，另一个为top，整个栈容量为maxsize，当树非空时，将当前的树根结点入栈，同时将当前栈顶元素出栈当作根结点，然后依据当前的根结点是否具有孩子结点来判定是否将其左、右指针进行交换；再将交换后的左指针或右指针入栈，这样反复进行，直到栈空为止。
4）注意问题:
? 注意理解算法中栈结构的利用
3． 试编写按层次顺序遍历二叉树的算法（实验类型：综合型） 1）问题描述：编写按层次顺序遍历二叉树的算法 2）实验要求：以二叉链表作为存储结构
3) 实现提示：本算法要采用一个队列q，先将二叉树根结点入队列，然后出队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉树目的。
4）注意问题:
? 理解算法中队列结构的利用
4． 实现一个哈夫曼编/译码系统（实验类型：综合型） 1）问题描述：利用哈夫曼编码进行信息通信可以大大编写按层次顺序遍历二叉树的算法提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码。对于双工信道，每端都需要一个完整的编码/译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。
16
2）实验要求：一个完整的系统应具有以下功能： (1) I：初始化(Initialization)。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
(2) E：编码(Encoding)。利用已建好的哈夫曼树对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
(3) D：译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
(4) P：打印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。
(5) T：打印哈夫曼树(Tree printing)。将已在内存中的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
3) 实现提示：
(1) 文件CodeFile的基类型可以设为字节型。 (2) 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“E”为止。
(3) 在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。
5． 森林（孩子兄弟链表）的建立与遍历（实验类型：验证型） 1）问题描述：以“孩子兄弟二叉链表”为存储结构，建立和遍历一个森林
2）实验要求：以“孩子兄弟二叉链表”作为存储结构
17
3) 实现提示：
? 可参考二叉树的前序遍历和中序遍历算法 4）注意问题:
? 理解二叉树与树的对应关系 ? 理解树和森林遍历的实质
实验四 图的遍历
一、 实验目的
1、 基本要求：通过实验掌握理解图的两种主要存储结构，掌握图的构造算法，掌握图的深度优先遍历、广度优先遍历算法。
2、 较高要求：理解拓扑排序、AOV网、AOE网等图型结构的操作方法应用价值。 二. 实验学时：
课内实验学时：3学时 课外实验学时：6学时 三. 备选实验题目
1． 键盘输入的数据建立图，并进行深度优先搜索和广度优先搜索（实验类型：验证型）
1）问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能：
1…图的建立
2…深度优先遍历图 3…广度优先遍历图 0…结束
18
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《数据结构》实验指导书(4)在线全文阅读。
相关推荐：