《实验9 哈夫曼树》由会员分享，可在线阅读，更多相关《实验9 哈夫曼树（3页珍藏版）》请在金锄头文库上搜索。
1、实验9二叉树应用实验网络B11-1班 姓名 张永真 学号25三、实验目的了解二叉树及存储结构；掌握建立哈夫曼树的方法，实现哈夫曼编码。四、二、实验内容编制赫夫曼编码问题描述：对任意输入的一段英文，为每个字符编制其相应的赫夫曼编码； 并利用该编码为任意输入的0、1序列进行解码.基本要求：一个完整的系统应具有以下功能：(1) 初始化从终端读入一段英文字符，统计每个字符出现的频率，建立 赫夫曼树，并将该树存入某文件；(2) 编码利用建好的赫夫曼树对各字符进行编码，用列表的形式显示在 屏幕上，并将编码结果存入另一文件中；(3) 解码 利用保存的赫夫曼编码，对任意输入的0，1序列能正确解码；五、算法分析
2、与设计。首先定义了哈夫曼树的结构体类型HTnode和结构体指针类型 *Huffmantree,其中包含有权值(weight)、双亲(parent)、左孩子(lchild)、 右孩子(rchild)，而typedef char * *Huffmancode;则是把一维字符型数组 指针重定义为Huffmancode。1. 当从n个叶子节点中选择两个权值最小的数时，首先定义一个较大的数 t=1000，判断它是否有双亲。再把森林中的权值与t进行比较，求出最小 权值，即：for(i=1;iv=n;i+) if(HTi.parent=O&HTi.weightvt) t=HTi.weight;s1=i;fo
3、r(i=1;iv=n;i+)if(HTi.parent=0&H Ti.weightvt&i!=s1) t=HTi.weight;s2=i;2. 当构造哈夫曼树时，首先要判断叶子节点n，如果n小于等于1，则退 出，否则，求出节点数目，然后分配一个树的指针节点，把权值放进去， 然后定义双亲、左孩子、右孩子的初值为0，然后求出权值最小的两个数, 然后用他们俩构造一个新的树，即： HT=(Huffmantree)malloc(m+1) * sizeof(HTnode);for(p=HT+1,i=1;iv=n;+i,+p,+w)p-weight=*w; p-parent=0; p-lchild=0;p-
4、rchild=0;for(;iweight=0; p-parent=0; p-lchild=0;p-rchild=0;for(i=n+1;i=m;+i)select(HT,i-1,s1,s2);HTsl.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;3当存储哈夫曼编码表时，要判断节点是否有双亲，如果有双亲，那么如 果该双亲有左孩子，则为标记0右孩子，标记为1,然后再把编码表存 储在一维字符型数组中。即for(i=1;iv=n;+i)start=n-1;for(c=i,f
5、=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c) cd-start=0;else cd-start=T;HCi=(char *)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);4.最后，输出哈夫曼树和叶子节点的哈弗曼编码表即：for(i=1;iv=2*n-1;i+)printf(%2d %3d %3d,i,HTi.weight,HTi.parent);printf( %3d %3dn,HTi.lchild,HTi.rchild);printf(Print the Humancode :n);for(i=1;in+1;i+)printf(the code of %2d is %sn,i,HCi);定义结构体指针类型HT为空，一维字符型指针HC为空, 定义整型 n=1,data,wMAX输入每一个字符的权值，以-1结束makeHuffmantree(HT,w,n);Huffmancoding(HT,HC,w,n);六、运行结果七、实验体会刚开始看程序的时候，感觉有点头晕，虽然老师在课上已经讲了 哈夫曼树的思路，还是有点不太理解，之后我又把代码仔细看了 几遍，对其中的源代码的算法开始有了一定的理解，明白了每一 段代码所要表达的意思，但是，要让我自己独立的写代码，还是 有一段距离的。
