哈夫曼编码算法实现完整版教学提纲.doc

《哈夫曼编码算法实现完整版教学提纲.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、哈夫曼编码算法实现完整版__________________________________________________实验三树的应用一.实验题目：树的应用——哈夫曼编码二.实验内容：利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。要求：从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出字符及对应的哈夫曼编码。三、程序源代码:#include

2、.h>#include#include#includetypedefstruct{chardata;intweight;intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;voidSelect(HuffmanTree&HT,intn,intm){HuffmanTreep=HT;inttmp;for(intj=n+1;j<=m;j++)__________________________________

3、__________________________________________________________________{inttag1,tag2,s1,s2;tag1=tag2=32767;for(intx=1;x<=j-1;x++){if(p[x].parent==0&&p[x].weight

4、if(s1>s2)//将选出的两个节点中的序号较小的始终赋给s1{tmp=s1;s1=s2;s2=tmp;}p[s1].parent=j;p[s2].parent=j;p[j].lchild=s1;p[j].rchild=s2;p[j].weight=p[s1].weight+p[s2].weight;}}voidHuffmanCoding(HuffmanTree&HT,intn,char*w1,int*w2){intm=2*n-1;if(n<=1)return;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)

5、);HuffmanTreep=HT;for(inti=1;i<=n;i++){p[i].data=w1[i-1];p[i].weight=w2[i];p[i].parent=p[i].lchild=p[i].rchild=0;}____________________________________________________________________________________________________for(;i<=m;i++){p[i].weight=p[i].parent=p[i].lchild=p[i].rchild=

6、0;}Select(HT,n,m);ofstreamoutfile;//生成hfmTree文件outfile.open("hfmTree.txt",ios::out);for(i=1;i<=m;i++){outfile<

7、ofstreamoutfile;outfile.open("ToBeTree.txt",ios::out);outfile<<"THISPROGRAMISMYFAVORITE";outfile.close();}voidEncoding(HuffmanTree&HT,intn)//编码{HuffmanCodeHC;HC=(HuffmanCode)malloc((n+1)*sizeof(char*));char*cd;cd=(char*)malloc(n*sizeof(char));cd[n-1]='';for(intk=1;k<=n;k++){

8、intstart=n-1;________________________________________________