哈夫曼树的构造

1、实验二 哈夫曼树及哈夫曼编码的实现班级：计算机 1131 学号： 姓名：卢仁浩 完成时间一、预习报告实验目的1、掌握用 Turbo C 上机调试层次结构的基本方法；2、掌握二叉树的结构特性及二叉树的存储结构特征；3、设计哈夫曼树及哈夫曼编码的实现的程序；基本原理与方法 按哈夫曼树的形成原理构造哈夫曼树操作算法用C 语言编程实现实验设备 PC 机一台、配置 Turbo C 软件二、实验内容要求： 1. 输入一个字符串序列，将其构造哈夫曼树；2. 根据哈夫曼树形成哈夫曼编码；分析： 1. 初始化：将 tree1.m 中的 2n-1 个结点的 3 个指针场置空，权值置 0；2. 输入：读入 n 个叶

2、子的权值存于数组的前 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

3、#define MAX_NUM 1000typedef struct TreeNodeint weight; / 结点的权值char data;char bin;struct TreeNode *parent; / 双亲链表的定义struct TreeNode *lChild, *rChild; /孩子链表的定义 TreeNode; / 定义一个 TreeNode 类型的结构体typedef structchar data; / 数据域char codeMAX_CHAR_KINDS; / 定义一个最大长度为 128 的字符数组 Code; / 定义一个 Code 类型的结构体void shur

4、u(char *str) / 输入函数int i;char c;int length;length = strlen(str); /计算字符长度for (i = 0; i length / 2; i+) /建立一个循环将输入的字符位置进行前后交换c = strlength - 1 - i;strlength - 1 - i = stri;stri = c;int main()char strMAX_NUM; / 定义一个最大长度为 1000 的字符数组TreeNode *HFTree; / 定义一个 TreeNode 类型的结构体的指针 HFTree int i, j;int length;i

5、nt count; / 定义一个判断TreeNode *treeMAX_CHAR_KINDS; / 定义一个 TreeNode 类型的结构体的指针 数组 treeTreeNode *eachCharMAX_CHAR_KINDS; / 定义一个 TreeNode 类型的结构体 的指针数组 eachCharTreeNode *temp; /Code *HFCode; /定义一个 TreeNode 类型的结构体的指针 temp定义一个Code类型的结构体的指针HFCodeint codeBit;short existed; / 定义一个短整型printf( 请输入一串字符字符型 :); gets(s

6、tr); / 格式化数输入数组 str计算数组长度printf(n);length = strlen(str); / count = 0; / 自变量for (i = 0; i length; i+)existed = 0;/ 用于控制简历循环链表的结束for (j = 0; j data)treej-weight+;existed = 1;break;if (existed = 0)treecount = (TreeNode *)malloc(sizeof(TreeNode);/申请一个存储单位treecount-weight = 1; / treecount-data = stri;/ t

7、reecount-parent = NULL;/ treecount-lChild = NULL; treecount-rChild = NULL; eachCharcount = treecount; / eachchar赋数组中的第一个元素的权值为 1 将输入的数组存入 tree 指针数组中 头结点再将指针数组 tree 值存入指针数组count+;if (count = 0)/判断是否输入字符printf( 对不起，你没有输入字符。 n);return (0);for (i = 0; i count - 1; i+)/将数组 tree 的数据的权值进行排序，从小到大。for (j = 0

8、; j weight treej+1-weight)temp = treej;treej = treej+1;treej+1 = temp;for (i = 1; i lChild = treei-1;/ 将 tree 数组中最左边的数赋值给指针 temp 的左指针temp-rChild = treei; / 将 tree 数组中左边第二个数赋值给指针 temp 的右指针temp-parent = NULL;temp-weight = treei-1-weight + treei-weight;/将两者的权值相加赋值个指针 temptreei-1-parent = temp;/ 再将 temp

9、 的全值的赋值给双亲结点 treei-1-bin = 0;treei-parent = temp; treei-bin = 1;treei = temp;/ 再把双亲结点当孩子结点重负上述操作， 直到没有 tree 中没有值为止。for (j = i; j weight treej+1-weight) /比较兄弟结点的权值大小, 将小的换到左边。temp = treej;treej = treej+1; treej+1 = temp;elsebreak;HFTree = treecount-1;/ 将数组 tree 的值传递给 HFTree for (i = 0; i count - 1; i

10、+)for (j = 0; j weight eachCharj+1-weight)/ 比较字符权值大 小，将它们从小到大排列起来(从上到下)temp = eachCharj; eachCharj = eachCharj+1;eachCharj+1 = temp;HFCode = (Code *)malloc(count * sizeof(Code);/ 申请存储单元 for (i = 0; i data;codeBit = 0;while (temp-parent != NULL)/ 当访问到头结点时自动换对象HFCodei.codecodeBit = temp-b in;temp = temp-pare nt;codeBit+;HFCodei.codecodeBit = 0;shuru(HFCodei.code);printf(%5s%8s%13sn,字符,权值,哈夫曼编码);for (i = 0; i data, eachChari-weight,HFCodei.code);prin tf(n);getch();printf( 输入结束，按回车键结束。);r