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

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

2、ode,*HuffmanTree;typedef char * * HuffmanCode;void Select(HuffmanTree &HT,int n,int m)HuffmanTree p=HT;int tmp;for(int j=n+1;j=m;j+)int tag1,tag2,s1,s2;tag1=tag2=32767;for(int x=1;x=j-1;x+) if(px.parent=0&px.weighttag1) tag1=px.weight;s1=x;for(int y=1;y=j-1;y+) if(py.parent=0&y!=s1&py.weights2) aren

3、t=j;ps2.parent=j;pj.lchild=s1;pj.rchild=s2;pj.weight=ps1.weight+ps2.weight;void HuffmanCoding(HuffmanTree &HT,int n,char *w1,int*w2)int m=2*n-1;if(n=1) return;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);HuffmanTree p=HT;for(int i=1;i=n;i+) pi.data=w1i-1;pi.weight=w2i;pi.parent=pi.lchild=pi.rchild=0;f

4、or(;i=m;i+) pi.weight=pi.parent=pi.lchild=pi.rchild=0; Select(HT,n,m);ofstreameighttHTi.parenttHTi.lchildtHTi.rchildtendl;();cout 初始化结果已保存在hfmTree 文件中 n;voidarent;f!=0;c=f,f=HTf.parent)outfile;ToBeTree() if(HTf.lchild=c) cd-start=0;else cd-start=1;HCk=(char *)malloc(n-start)*sizeof(char);strcpy(HCk,

5、&cdstart);)cout输出哈夫曼编码:endl;for(int h=1;h=n;h+)ata:;coutHCh;cout ;if (h%8=0) coutendl;)coutendl输出正文编码:endl;ToBeTree();ata) coutHCk;cout ;count+;outfileHCk;break;)if (count%9=0) coutendl;coutendl;void Decoding(HuffmanTree &HT,int n) child!=0)child;else f=HTf.rchild;j+;i=j;coutHTf.data;outfileHTf.data

6、;();coutn 译码结果已保存在文件 TextFile 中.;coutendl;void Print() n;cout 依次输入各个字符的权值:endl;for (int i=1;iArrayi;int tag;char x=menu();while(1) switch (x)case I:HuffmanCoding(HT,n,cArray,Array);break;case E:Encoding(HT,n);break;case D:Decoding(HT,n);break;case P:Print();break;case Q:tag=0;cout 结束 endl;break;defa

7、ult:cout 你输入错误!endl;if(tag=0) break;couty( 继续 ) or n( 退出 )ch;if (ch=y) coutc;x=c;else exit(1);测试数据：用下表给出的字符集和频度的实际统计数据建立哈夫曼树， 并实现以下报文的译码和编码 : THIS PROGRAM IS MY FAVORIT.E字符空格 A B C D E F G H I J K L M频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z频度 57 63 15 1 48 51 80 23 8 18 1 16 14 .测试结果：如图一所示5 .实验体会通过本次实验，尤其在自己对程序的调试过程中，感觉对树的存储结构， 终结状态，还有编码，译码的过程都有了比较清晰的认识。在做本次实验时，其 他的都没什么问题，以前很少进行文件操作，刚开始有点手生，但是在实验作完 后，文件操作已经用的比较熟练了。 最近几次实验，感到自己对本题实验