哈夫曼编码算法实现完整版

1、实验三树的应用.实验题目：树的应用一一哈夫曼编码二. 实验内容：利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。 根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。要求：从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立 哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出字符及对应的哈夫曼编码。三、程序源代码：#i nclude#in clude#i ncludevstri ng.h#in cludetypedefstructchardata;in tweight;in tpare nt,lchild,rc

2、hild;HTNode,*Huffma nTree;typedefchar*Huffma nCode;voidSelect(Huffma nTree&H T,i ntn ,i ntm)Huffma nTreep二HT;in ttmp;for(i ntj二n+1;j=m;j+)in ttag1,tag2,s1,s2;tag仁tag2=32767;for(i ntx=1;x二j-1;x+)if(px.pare nt=0&px.weighttag1)tag1=px.weight;s1=x;for(i nty=1;y二j-1;y+)if(py.pare nt=0&y !=s1 &py.weights2

3、) / 将选出的两个节点中的序号较小的始终赋给 tmp=s1;s1=s2;s2=tmp;ps1.parent=j;ps2.parent=j;pj.lchild=s1;pj.rchild=s2;pj.weight=ps1.weight+ps2.weight; voidHuffmanCoding(HuffmanTree&HT,intn,char*w1,int*w2) intm=2*n-1;if(n=1)return;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);HuffmanTreep=HT;for(inti=1;i=n;i+)pi.data=w1i-1;p

4、i.weight=w2i;pi.parent=pi.lchild=pi.rchild=0;for(;i=m;i+)pi.weight=pi.parent=pi.lchild=pi.rchild=0; Select(HT,n,m);ofstreamoutfile;/ 生成 hfmTree 文件 outfile.open(hfmTree.txt,ios:out);for(i=1;i=m;i+) outfileHTi.weighttHTi.parenttHTi.lchild tHTi.rchildtendl;outfile.close();cout 初始化结果已保存在 hfmTree 文件中 n;v

5、oidToBeTree() / 将正文写入文件 ToBeTree 中 ofstreamoutfile; outfile.open(ToBeTree.txt,ios:out); outfileTHISPROGRAMISMYFAVORITE; outfile.close();voidEncoding(HuffmanTree&HT,intn) / 编码HuffmanCodeHC; HC=(HuffmanCode)malloc(n+1)*sizeof(char*); char*cd;cd=(char*)malloc(n*sizeof(char); cdn-1=0;for(intk=1;k=n;k+)

6、intstart=n-1;for(intc=k,f=HTk.parent;f!=0;c=f,f=HTf.parent) if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCk=(char*)malloc(n-start)*sizeof(char); strcpy(HCk,&cdstart); cout 输出哈夫曼编码 :endl; for(inth=1;h=n;h+) / 输出编码 coutHTh.data:;coutHCh; cout;if(h%8=0)coutendl;coutendl 输出正文编码 :endl; ToBeTree();/ 读取 TOBE

7、TREE 文件里的正文，并进行编码 fstreaminfile;infile.open(ToBeTree.txt,ios:in); chars80;while(!infile.eof() infile.getline(s,sizeof(s); infile.close();fstreamoutfile; outfile.open(CodeFile.txt,ios:out);intcount=0; for(h=0;sh!=0;h+) for(k=1;k=n;k+) if(sh=HTk.data)coutHCk;cout;count+; outfileHCk;break; if(count%9=0

8、)coutendl; / 每输出 7 个换行outfile.close();coutn 编码结果已保存在文件 CodeFile 中 .; coutendl; voidDecoding(HuffmanTree&HT,intn) / 译码intf=2*n-1; fstreaminfile;infile.open(CodeFile.txt,ios:in);chars1000;while(!infile.eof()infile.getline(s,sizeof(s); infile.close();inti=0;intj=0;fstreamoutfile;outfile.open(TextFile.t

9、xt,ios:out);while(si!=0)f=2*n-1;while(HTf.lchild!=0)/ 以 f 对应的节点的左孩子的值 =0 作为结束 if(sj=0)f=HTf.lchild;elsef=HTf.rchild;j+;i=j;coutHTf.data;outfileHTf.data;outfile.close();coutn 译码结果已保存在文件 TextFile 中.;coutendl;voidPrint() / 印代码文件intcount=0;fstreaminfile;infile.open(CodeFile.txt,ios:in);chars1000;while(!

10、infile.eof()infile.getline(s,sizeof(s);for(inti=0;si!=0;i+)coutsi;count+;if(count%50=0)coutendl; / 在终端上每行显示 50 个代码 infile.close();coutendl;charmenu() / 菜单函数cout 功能菜单如下 :endl;endl;coutcoutI: 初始化 (Initialization)endl;coutE: 编码 (Encoding)endl; coutD: 译码 (Decoding)endl;coutP: 印代码文件 (Print)endl;coutQ: 退出

11、 (Exit)endl;endl;cout coutch;returnch;voidmain()intn;intArray100;charcArray100;HuffmanTreeHT; cout 输入 n 个字符 :;cin.getline(cArray,100);n=strlen(cArray);cout 共n个字符.n;coutvv依次输入各个字符的权值:endl;for(i nti=1;i Arrayi;in ttag;charx=me nu();while(1)switch(x)caseT:Huffma nCodi ng(HT ,n ,cArray,Array);break;case

12、E:E ncodi ng(HT ,n );break;caseD:Decodi ng(HT, n);break;caseP:Pri nt();break;caseQ:tag=0;cout结束e ndl;break;default:cout你输入错误!endl;if(tag=0)break;couty(继续)orn(退出) ch;if(ch=y)coutvv请输入功能字符:;charc;cin c;x=c;elseexit(l);测试数据：用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的译码和编码:THISPROGRAMISMYFAVORITE字符空格 ABCDEFGHIJKLM频度 1866413223210321154757153220字符 NOPQRSTUVWXYZ频度 5763151485180238181161四. 测试结果：如图一所示五. 实验体会通过本次实验，尤其在自己对程序的调试过程中，感觉对树的存储结构，终结状态，还有编码，译 码的过程都有了比较清晰的认识。 在做本次实验时，其他的都没什么问题，