哈夫曼树的构造.doc

学习资料收集于网络，仅供参考实验二 哈夫曼树及哈夫曼编码的实现班级：计算机1131 学号： 10210413121 姓名：卢仁浩完成时间一、预习报告实验目的1、掌握用Turbo C上机调试层次结构的基本方法；2、掌握二叉树的结构特性及二叉树的存储结构特征；3、设计哈夫曼树及哈夫曼编码的实现的程序 ；基本原理与方法 按哈夫曼树的形成原理构造哈夫曼树操作算法用C语言编程实现实验设备 PC机一台、配置Turbo C软件二、 实验内容要求：1. 输入一个字符串序列，将其构造哈夫曼树；2. 根据哈夫曼树形成哈夫曼编码；分析：1. 初始化：将tree1.m中的2n-1个结点的3个指针场置空，权值置0；2. 输入：读入n个叶子的权值存于数组的前n个元素中，形成森林；3. 合并：对森林中的树进行n1次合并，产生的新结点存于数组的第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 codeMAX_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 = strlength - 1 - i; strlength - 1 - i = stri; stri = c; int main()char strMAX_NUM; /定义一个最大长度为1000的字符数组TreeNode *HFTree; /定义一个TreeNode类型的结构体的指针HFTreeint i, j;int length;int count; /定义一个判断TreeNode *treeMAX_CHAR_KINDS; /定义一个TreeNode类型的结构体的指针数组treeTreeNode *eachCharMAX_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 data) treej-weight+; existed = 1; break; if (existed = 0) treecount = (TreeNode *)malloc(sizeof(TreeNode);/申请一个存储单位 treecount-weight = 1; /赋数组中的第一个元素的权值为1 treecount-data = stri;/将输入的数组存入tree指针数组中 treecount-parent = NULL;/头结点 treecount-lChild = NULL; treecount-rChild = NULL; eachCharcount = treecount; /再将指针数组tree值存入指针数组eachchar count+; if (count = 0)/ 判断是否输入字符 printf(对不起，你没有输入字符。n); return (0);for (i = 0; i count - 1; i+)/将数组tree的数据的权值进行排序，从小到大。 for (j = 0; 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;/将两者的权值相加赋值个指针temp treei-1-parent = temp;/再将temp的全值的赋值给双亲结点 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; else break; HFTree = treecount-1;/将数组tree的值传递给HFTree for (i = 0; i count - 1; i+) 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-bin; temp = temp-parent; codeBit+; HFCodei.codecodeBit = 0; shuru(HFCodei.code); printf(%5s%8s%13sn, 字符, 权值, 哈夫曼编码);for (i = 0; i data, eachChari-weight, HFCodei.code); printf(n); getch(); printf(输入结束，按回车键结束。); return (0)