数据结构试验报告---赫夫曼树

《数据结构试验报告---赫夫曼树》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、赫夫曼树：代码：#include#includeusingnamespacestd;#include#include#include#includetypedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;intmini(HuffmanTreet,inti){intj,flag;unsi

2、gnedintk=UINT_MAX;for(j=1；jv=i;j++)if(t[j].weight*s2)*s1=*s2;*s2=j;}}voidHuffmanCoding(HuffmanTree*HT,HuffmanCode*HC,int*w,intn){i

3、ntm,i,s1,s2,start;unsignedc,f;HuffmanTreep;char*cd;if(n<=1)return;m=2*n-1;*HT=(HuffmanTree)malloc((m4-1)*sizeof(HTNode));for(p=*HT+1,i=1;iv=n;++i,++p,++w){(*p).weight=*w;(*p).parent=O;(*p).lchild=O;(*p).rchild=O;}for(;iv=m;++i,++p)(*p).parent=O;for(i=n+1;iv=m;++i){select(*HT,i-1，&s1,

4、&s2);(*HT)[s1].parent=(*HT)[s2].parent=i;(*HT)[i].lchild=s1;(*HT)[i].rchild=s2;(*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;}*HC=(HuffmanCode)malloc((n4-1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-1]='';for(i=1;iv=n;i++){start=n-1;for(c=i,t=(*HT)[i].parent;f!=0;c=f

5、,f=(*HT)[f].parent)if((*HT)[f].lchild==c)cd[—start]=*O*;elsecd[—start]='r；(*HC)[i]=(char*)malloc((n-start)*sizeof(char));strcpy((*HC)[i],&cd[start]);}free(cd);}voidmain()〃主程序{HuffmanTreeHT;HuffmanCodeHC;inti,j=O,w[27]={186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,

6、8,18,1,16,1}；HuffmanCoding(&HT,&HC,w,27);printf(”对应的赫夫曼编码：”);charc='a';putchar(*,);cout«,,«HC[1]«,'«'for(i=2;iv=27;i++){putchar(c+4-);cout«f,«HC[i]«,*«•if(j%4==0)cout«endl;}printf(H输入要翻译的句子:”);chars[100];gets(s);puts(s);while(s[j]){if(s[j]==*•)cout«HC[1];elsecout«HC[s[j]-,a,+2];j

7、++;}cout«endl;}运行结果:对应的赫夫曼编码：110a1010b100100c00010d10110e010f111110g100101h0000■10110j1111011100k11110110110111nmilln0111o1000p100110q11110111011*0010s0011t1110u00011v1111010w111100x1111011110y100111z1111011111输△要翻译的®子:thisprogramisnyfavoritethisprogramisnyfavorite1110000001100011110

8、100110001010