发布时间 : 星期五 文章数据结构实验指导书(1)更新完毕开始阅读
数据结构试验指导书
实验05 二叉树的基本操作
实验学时：2学时 实验类型：上机
背景知识：二叉树的存储、建立、遍历及其应用。
目的要求：
1．掌握二叉树的存储实现。 2．掌握二叉树的遍历思想。
3．掌握二叉树的常见算法的程序实现。
实验内容：
（1） 从键盘上输入数据，建立二叉链表。
（2） 前序遍历、中序遍历、后序遍历二叉树：递归算法。 （3） 前序遍历、中序遍历、后序遍历二叉树：非递归算法。 （4） 借助队列实现二叉树的层次遍历。
（5） 在主函数中设计一个简单的菜单，分别调试上述算法。 （6） *综合训练：
家族关系查询系统：建立家族关系数据库，可以实现家族成员的添加，可以查询家族成员的双亲、祖先、兄弟、孩子和后代等信息。
实验说明：
1．类型定义 //二叉链表存储
#define TElemType char //元素类型 typedef struct BiTNode{ TElemType data;
struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;
注意问题：
1．注意理解递归算法的执行步骤，重点理解如何利用栈结构实现非递归算法。
2．注意字符类型数据在输入时的处理。
23
数据结构试验指导书
实验06 哈夫曼编码
实验学时：4学时 实验类型：综合型实验
背景知识：二叉树的应用、哈夫曼树。
目的要求：
掌握哈夫曼树和哈夫曼编码的基本思想和算法的程序实现。
实验内容：
（1）修理牧场：农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数Li个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是Li的总和。
但是农夫自己没有锯子，请人锯木头的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。
请编写程序帮助农夫计算将木头锯成N块的最少花费。
首先输入一个正整数N（N≤104），表示要将木头锯成N块。接着给出N个正整数Li（Li≤50），表示每段木块的长度。输出一个整数，即将木头锯成N块的最少花费。 例如： 输入：
8
4 5 1 2 1 3 1 1 输出：
49
*（2）压缩软件：
给定一篇文章，只含有英文大小写字母和空格，以.txt格式存储，统计该文件中各种字符的频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成源文件。
实验说明：
1．参考类型定义 //双亲孩子表示法 typedef struct {
unsigned int weight;
unsigned int parent, lchild, rchild;
24
数据结构试验指导书
} HTNode, *HuffmanTree; //动态分配数组存储哈夫曼树 typedef char * * HuffmanCode; //动态分配数组存储哈夫曼编码表
注意问题：
1．递归算法的灵活应用。 2．多级指针的使用。
25
数据结构试验指导书
实验07 图的两种存储和遍历
实验学时：2学时 实验类型：上机
背景知识：图的存储、遍历及其应用。
目的要求：
1．掌握图的存储思想及其存储实现。
2．掌握图的深度、广度优先遍历算法思想及其程序实现。
实验内容：
（1） 键盘输入数据，分别建立一个有向图和一个无向图的邻接表。 （2） 输出该邻接表。
（3） 在有向图的邻接表的基础上计算各顶点的度，并输出。 （4） 采用邻接表存储实现无向图的深度优先遍历。 （5） 采用邻接表存储实现无向图的广度优先遍历。 （6） 在主函数中设计一个简单的菜单，分别调试上述算法。 （7） *综合训练
地下迷宫探索：假设有一个地下通道迷宫，它的通道都是直的，而通道所有交叉点（包括通道的端点）上都有一盏灯和一个开关。请问你如何从某个起点开始在迷宫中点亮所有的灯并回到起点？
输入格式：
输入第一行给出三个正整数，分别表示地下迷宫的节点数N（1 若可以点亮所有节点的灯，则输出从S开始并以S结束的包含所有节点的序列，序列中相邻的节点一定有边（通道）；否则虽然不能点亮所有节点的灯，但还是输出点亮部分灯的节点序列，最后输出0，此时表示迷宫不是连通图。 26