自己用c++写的哈夫曼编码/译码系统，经过反复测试，绝对没问题，请放心使

用。

3、哈夫曼编码/译码系统（树应用）

[问题描述]

利用哈夫曼编码进行通信，可以压缩通信的数据量，提高传输效率，缩短信息的传输时间，还有一定的保密性。现在要求编写一程序模拟传输过程，实现在发送前将要发送的字符信息进行编码，然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。 [实现提示]

在本例中设置发送者和接受者两个功能， 发送者的功能包括： ①输入待传送的字符信息；

②统计字符信息中出现的字符种类数和各字符出现的次数（频率）； ②根据字符的种类数和各自出现的次数建立哈夫曼树； ③利用以上哈夫曼树求出各字符的哈夫曼编码； ④将字符信息转换成对应的编码信息进行传送。 接受者的功能包括：

①接收发送者传送来的编码信息；

②利用上述哈夫曼树对编码信息进行翻译，即将编码信息还原成发送前的字符信息。

从以上分析可发现，在本例中的主要算法有三个： （1）哈夫曼树的建立； （2）哈夫曼编码的生成； （3）对编码信息的翻译。

测试结果

源代码

#include #include #include #include typedef struct { int weight; int parent,lchild,rchild; char data;

}HTNode,*HuffmanTree; typedef char **HuffmanCode;

void tongji(char *a,int *w,char *d,int &n) { int j=0; for(int i=0;i<100&&a[i]!='\\0';i++){ for(int k=0;k

if(a[i]==d[k]) { w[k]++; break; } } if(k==j){ d[j]=a[i]; w[j]++; j++;} } n=j; d[j]='\\0'; }

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n,char *d) { if(n<=1)return; int m=2*n-1; HT=new HTNode[m+1]; HuffmanTree p; int i; for(p=HT+1,i=1;i<=n;i++,++p) { p->data=d[i-1]; p->lchild=p->parent=p->rchild=0; p->weight=w[i-1]; } for(;i<=m;++i,++p) { p->lchild=p->parent=p->rchild=0; p->weight=0; } for(i=n+1;i<=m;++i){ int s1,s2,u,t; for (u=1;u<=i-1;u++)if(HT[u].parent==0){s1=u;break;} for(u=u+1;u<=i-1;u++) { if(HT[s1].weight>HT[u].weight&&HT[u].parent==0) s1=u; } for(t=1;t<=i-1;t++) if(HT[t].parent==0&&t!=s1){s2=t;break;} for(t=t+1;t<=i-1;t++) { if(HT[s2].weight>HT[t].weight&&HT[t].parent==0&&t!=s1) s2=t; } 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; } HC=new char*[n+1]; char *cd=new char[n];