数据结构哈夫曼树.doc

《数据结构哈夫曼树.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、__________________________________________________数据结构实验报告1.问题描述已知n个字符在原文中出现的频率，求它们的哈夫曼编码。2.问题分析求哈夫曼编码，首先要根据字符出现的频率，即权值，构建哈夫曼树，然后根据哈夫曼树求出哈夫曼编码。3.算法设计创建哈夫曼树：对n个权值，创建2n-1个节点，parent都默认为0，然后进行循环查找，每次循环都从所有节点中找出parent为0且weight最小的两个节点，序号分别为s1和s2，将s1节点和s2节点作为本节点的lchild和rchild，构建出一颗哈夫

2、曼树，循环2n-1次，最后只剩下一颗哈夫曼树，即所要求的哈夫曼树。哈夫曼编码：从叶子节点出发，寻找双亲节点，若没有则说明已经到根节点；若有双亲节点，如果本节点是双亲节点的左孩子，则编码为0，右孩子编码为1，依次寻找直到走到根节点。最后将所求编码倒序输出即为哈夫曼编码。4.测试数据测试数据为8个字符，权值分别为：5,29,7,8,14,23,3,11。测试结果：收集于网络，如有侵权请联系管理员删除__________________________________________________1.总结建立哈夫曼树的时候，是逆向构建，即先创建叶节点，

3、再创建根节点，从下往上创建。求哈夫曼编码的时候也是一样，从叶子节点不断找该节点的根节点，直到找到该哈夫曼树的根节点。2.附录#include#include#include#defineERROR0#defineOK1//-----------赫夫曼树和赫夫曼编码的存储表示----------typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**

4、HuffmanCode;//-----------赫夫曼算法------------------------------voidSelect(HuffmanTreeHT,intn,int&min1,int&min2){unsignedintm1,m2;m1=m2=-1;//随意确定两个权值为最小for(inti=1;i<=n;i++){if(m2!=-1)break;if(HT[i].parent==0){if(m1==-1){m1=HT[i].weight;min1=i;}else{m2=HT[i].weight;min2=i;}收集于网络，如有

5、侵权请联系管理员删除__________________________________________________}}//找最小权值for(intk=1;k<=n;k++){if(HT[k].parent==0){intw=HT[k].weight;if(k==min1

6、

7、k==min2)continue;if(w

8、的权值（均>0），构造赫夫曼树HT，并求出n个字符的赫夫曼编码HCif(n<=1)return;intm=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用inti;HuffmanTreep=HT;for(p++,i=1;i<=n;i++,p++,w++){p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;}for(;i<=m;i++,p++){p->weight=0;p->parent=0;p->lchild=0;p->rchild

9、=0;}ints1,s2;for(i=n+1;i<=m;i++){//建赫夫曼树//在HT[1..i-1]选择parent为0且weight最小的两个节点，其序号分别为s1和s2Select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}//----从叶子到根逆向求每个字符的赫夫曼编码----收集于网络，如有侵权请联系管理员删除_______________

10、___________________________________HC=(HuffmanCode)malloc((n+