实验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 {
26
unsigned int weight;
unsigned int parent, lchild, rchild;
} HTNode, *HuffmanTree; //动态分配数组存储哈夫曼树 typedef char * * HuffmanCode; //动态分配数组存储哈夫曼编码表
注意问题：
1．递归算法的灵活应用。 2．多级指针的使用。
27
实验07 图的两种存储和遍历
实验学时：2学时 实验类型：上机
背景知识：图的存储、遍历及其应用。 目的要求：
1．掌握图的存储思想及其存储实现。
2．掌握图的深度、广度优先遍历算法思想及其程序实现。
实验内容：
（1） 键盘输入数据，分别建立一个有向图和一个无向图的邻接表。 （2） 输出该邻接表。
（3） 在有向图的邻接表的基础上计算各顶点的度，并输出。 （4） 采用邻接表存储实现无向图的深度优先遍历。 （5） 采用邻接表存储实现无向图的广度优先遍历。 （6） 在主函数中设计一个简单的菜单，分别调试上述算法。 （7） *综合训练
地下迷宫探索：假设有一个地下通道迷宫，它的通道都是直的，而通道所有交叉点（包括通道的端点）上都有一盏灯和一个开关。请问你如何从某个起点开始在迷宫中点亮所有的灯并回到起点？
输入格式：
输入第一行给出三个正整数，分别表示地下迷宫的节点数N（1 若可以点亮所有节点的灯，则输出从S开始并以S结束的包含所有节点的序列，序列中相邻的节点一定有边（通道）；否则虽然不能点亮所有节点的灯，但还是输出点亮部分灯的节点 28 序列，最后输出0，此时表示迷宫不是连通图。 由于深度优先遍历的节点序列是不唯一的，为了使得输出具有唯一的结果，我们约定以节点小编号优先的次序访问（点灯）。在点亮所有可以点亮的灯后，以原路返回的方式回到起点。 输入样例： 6 8 1 1 2 2 3 3 4 4 5 5 6 6 4 3 6 1 5 输出样例： 1 2 3 4 5 6 5 4 3 2 1 实验说明： 1．类型定义（邻接表存储） #define MAX_VERTEX_NUM 20 //顶点最大个数 typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; int weight; //边的权值 }ArcNode; //表结点 #define VertexType int //顶点元素类型 typedef struct VNode{ VertexType data; ArcNode *firstarc; }VNode, AdjList[MAX_VERTEX_NUM]; // typedef struct{ AdjList vertices; int vexnum, arcnum; //顶点的实际数，边的实际数 int kind; }ALGraph; 2．上述类型定义可以根据实际情况适当调整。 3．算法4、5分别利用栈、队列实现非递归算法。 29 注意问题： 1．注意理解各算法实现时所采用的存储结构。 2．注意区别正、逆邻接。 30