实验二 哈夫曼树及哈夫曼编码的实现班级：计算机1131 学号： 10210413121 姓名：卢仁浩完成时间一、预习报告实验目的1、掌握用Turbo C上机调试层次结构的基本方法；2、掌握二叉树的结构特性及二叉树的存储结构特征；3、设计哈夫曼树及哈夫曼编码的实现的程序 ；基本原理与方法 按哈夫曼树的形成原理构造哈夫曼树操作算法用C语言编程实现实验设备 PC机一台、配置Turbo C软件二、 实验内容要求：1. 输入一个字符串序列，将其构造哈夫曼树；2. 根据哈夫曼树形成哈夫曼编码；分析：1. 初始化：将tree[1..m]中的2n-1个结点的3个指针场置空，权值置0；2. 输入：读入n个叶子的权值存于数组的前n个元素中，形成森林；3. 合并：对森林中的树进行n－1次合并，产生的新结点存于数组的第i个元素中（n<=i<=m）合并分两步：（1） 在当前森林中选两个权值最小的结点s1，s2为合并对象； （2） 将根为左右两个子树组成新树，新树的根为i，则将s1，s2分别送入新树的左右子树指针场中，s1，s2的双亲指针场置为i，且新树的权值为s1，s2的权值之和。
由于s1，s2的双亲指针场已置I，所有再组树时就不会选中它了实现程序: #include #include #include #define MAX_CHAR_KINDS 128#define MAX_NUM 1000typedef struct TreeNode{ int weight; //结点的权值 char data; char bin; struct TreeNode *parent; //双亲链表的定义 struct TreeNode *lChild, *rChild; //孩子链表的定义 } TreeNode; //定义一个TreeNode类型的结构体typedef struct{ char data; //数据域 char code[MAX_CHAR_KINDS]; // 定义一个最大长度为128的字符数组} Code; //定义一个Code类型的结构体void shuru(char *str) //输入函数{ int i; char c; int length; length = strlen(str); //计算字符长度 for (i = 0; i < length / 2; i++) //建立一个循环将输入的字符位置进行前后交换 { c = str[length - 1 - i]; str[length - 1 - i] = str[i]; str[i] = c; }}int main(){char str[MAX_NUM]; //定义一个最大长度为1000的字符数组TreeNode *HFTree; //定义一个TreeNode类型的结构体的指针HFTreeint i, j;int length;int count; //定义一个判断TreeNode *tree[MAX_CHAR_KINDS]; //定义一个TreeNode类型的结构体的指针数组treeTreeNode *eachChar[MAX_CHAR_KINDS]; //定义一个TreeNode类型的结构体的指针数组eachChar TreeNode *temp; //定义一个TreeNode类型的结构体的指针tempCode *HFCode; //定义一个Code类型的结构体的指针HFCodeint codeBit;short existed; //定义一个短整型printf("请输入一串字符《字符型》:"); gets(str); //格式化数输入数组strprintf("\n");length = strlen(str); //计算数组长度count = 0; //自变量for (i = 0; i < length; i++) { existed = 0;//用于控制简历循环链表的结束 for (j = 0; j < count; j++) { if (str[i] == tree[j]->data) { tree[j]->weight++; existed = 1; break; } } if (existed == 0) { tree[count] = (TreeNode *)malloc(sizeof(TreeNode));//申请一个存储单位 tree[count]->weight = 1; //赋数组中的第一个元素的权值为1 tree[count]->data = str[i];//将输入的数组存入tree指针数组中 tree[count]->parent = NULL;//头结点 tree[count]->lChild = NULL; tree[count]->rChild = NULL; eachChar[count] = tree[count]; //再将指针数组tree值存入指针数组eachchar count++; }}if (count == 0)// 判断是否输入字符{ printf("对不起，你没有输入字符。
\n"); return (0);}for (i = 0; i < count - 1; i++)//将数组tree的数据的权值进行排序，从小到大 { for (j = 0; j < count - 1 - i; j++) { if (tree[j]->weight > tree[j+1]->weight) { temp = tree[j]; tree[j] = tree[j+1]; tree[j+1] = temp; } }}for (i = 1; i < count; i++)//哈夫曼树的建立 { temp = (TreeNode *)malloc(sizeof(TreeNode));//申请存储单元 temp->lChild = tree[i-1];//将tree数组中最左边的数赋值给指针temp的左指针 temp->rChild = tree[i]; //将tree数组中左边第二个数赋值给指针temp的右指针 temp->parent = NULL; temp->weight = tree[i-1]->weight + tree[i]->weight;//将两者的权值相加赋值个指针temp tree[i-1]->parent = temp;//再将temp的全值的赋值给双亲结点 tree[i-1]->bin = '0'; tree[i]->parent = temp; tree[i]->bin = '1'; tree[i] = temp;//再把双亲结点当孩子结点重负上述操作，直到没有tree中没有值为止。
for (j = i; j < count - 1; j++) { if (tree[j]->weight > tree[j+1]->weight) //比较兄弟结点的权值大小,将小的换到左边 { temp = tree[j]; tree[j] = tree[j+1]; tree[j+1] = temp; } else { break; } }}HFTree = tree[count-1];//将数组tree的值传递给HFTree for (i = 0; i < count - 1; i++) { for (j = 0; j < count - 1 - i; j++) { if (eachChar[j]->weight > eachChar[j+1]->weight)//比较字符权值大小，将它们从小到大排列起来（从上到下） { temp = eachChar[j]; eachChar[j] = eachChar[j+1]; eachChar[j+1] = temp; } } }HFCode = (Code *)malloc(count * sizeof(Code));//申请存储单元for (i = 0; i < count; i++)//将指针temp的数据赋值给数组eachChar{ temp = eachChar[i]; HFCode[i].data = temp->data; codeBit = 0; while (temp->parent != NULL)//当访问到头结点时自动换对象 { HFCode[i].code[codeBit] = temp->bin; temp = temp->parent; codeBit++; } HFCode[i].code[codeBit] = '\0'; shuru(HFCode[i].code);} printf("%5s%8s%13s\n", "字符", "权值", "哈夫曼编码");for (i = 0; i < count; i++)//输出数组的值和对应的权值以及编码{ printf(" %c%8d%13s\n", eachChar[i]->data, eachChar[i]->weight, HFCode[i].code);} printf("\n"); getch(); printf("输入结束，按回车键结束。
"); return (0);}三、 实验结果分析讨论1、 输入的字符串为“aabcdefabcdefggabbcedffaa”输出程序运行结果2、 阅读程序，加注释已完成四、巩固题 若输入的数据是：input n ：8 input 8 weight:5 29 7 8 14 23 3 11 对应的字符为：A B C D E F G H 程序应如何编制？。