1）内容：利用 Huffman 编码进行通信可以大大提高信道的利用率，缩短信息传输时间，降低传输成本。

但是，这要求在发送端通过一个编码系统对待传数据进行预先编码，在接收端进行解码。

对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/解码系统。

2）要求：一个完整的huffman编解码系统应该具有以下功能：初始化（Initialization）。

从终端读入字符集大小n，以及n个字符和n个权值，建立Huffman 树，并将它存入hfmTree 中。

编码（Encoding）。

利用已经建好的Huffman树（如果不在内存，则应从文件hfmTree 中读取），对文件ToBeTran中的正文进行编码，然后将结果存入文件hfmTree中读取），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

解码（Decoding）。

利用已经建立好的Huffman树将文件CodeFile中的代码进行解码，结果存入TextFile中。

打印代码文件（Print）。

将文件CodeFile以紧凑的格式显示在终端上，每行 50 个代码。

同时将此字符形式的编码文件写入文件CodePrint中。

打印Huffman树（Tree Printing）。

将已经在内存中的Huffman树以直观的形式（树或者凹入的形式）显示在终端上，同时将此字符形式的Huffman 树写入文件TreePrint中。

3) 测试数据:用下表给出的字符集和频度的实际统计数据建立Huffman树，并对以下报文进行编码和译码：“THIS PROGRAM IS MY FAVORITE”。

完整代码如下：#include<stdio.h>#include<iostream>#include<string>#define N 100int *w;char *c,stack[N],code[N][N];int s1,s2;typedef struct HuffmanTree{int weight;int parent;int lchild;int rchild;}HuffmanTree,*Huff;void menu(void);void Select(struct HuffmanTree HT[],int i);void HuffmanTree(Huff &HT,int *w,int n);void visite(Huff HT,int i,int flag,int rear);void translatef(char *scource,char *save,int n);bool uncodef(FILE *fp1,FILE *fp2,Huff HT,int n);int inputHuff();void screanio(int n);void fileio(int n);int initHuff();void Print_tree(int n,Huff HT);void Convert_tree(Huff HT,unsigned char T[100][100],int tt[100][100],int s,int *i,int j);void decoding(int n);void coding(int n);void main(){int n=0;menu();Huff HT;char state;do{std::cout<<"input:\n";std::cin>>state;fflush(stdin); //读取状态switch(state){case'I':n=inputHuff();HuffmanTree(HT,w,n);std::cout<<"\nHuffmanTree 初始化完毕\n";break;case'C':coding(n);break;case'D':decoding(n);break;case'P':Print_tree(n,HT);break;case'Q':break;}}while(state!='Q');}void menu() //显示菜单函数{std::cout<<"===========HuffmanCoding===========\n";std::cout<<"input \t\t do\n";std::cout<<"I \t\tInit_HUffTree\n"; //初始化huffmantreestd::cout<<"C \t\tCoding\n"; //对ToBeTran.txt文件中的字符进行编码到CodeFile.txt中std::cout<<"D \t\tUnCoding\n"; //对CodeFile.txt中的01序列进行解码到TextFile.txtstd::cout<<"P \t\tPrintTree\n"; //打印哈夫曼树std::cout<<"Q \t\tquit\n";std::cout<<"请初始化哈夫曼树再执行后面的操作\n";}int inputHuff() //输入各个字母及其权值{int i=1,n=0;int ww[28];char cc[28];while(1){std::cout<<"input the letter(input '#' to stop):";cc[i]=std::cin.get();fflush(stdin);if(cc[i]=='#')break;std::cout<<"input the weight:";std::cin>>ww[i];fflush(stdin);n++;i++;}w=(int *)malloc(sizeof(int)*(n+1));c=(char *)malloc(sizeof(char)*(n+1));for(i=0;i<n+1;i++){w[i]=ww[i];c[i]=cc[i];}return n;}void HuffmanTree(Huff &HT,int *w,int n) //初始化哈夫曼树{int m,i;m=n*2-1;HT=(struct HuffmanTree *)malloc(sizeof(struct HuffmanTree)*(m+1));HT[0].lchild=0;HT[0].parent=0;HT[0].rchild=0;HT[0].weight=0;for(i=1;i<m;i++){HT[i].weight=i<=n?w[i]:0;HT[i].lchild=HT[i].rchild=HT[i].parent=0;}for(i=n+1;i<=m;i++){Select(HT,i);HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;HT[s1].parent=HT[s2].parent=i;}}void Select(struct HuffmanTree HT[],int i) //在HT[1..i-1]中选择parent为0且weight为最小的两个结点{int j;for(j=1;j<i;j++){if(HT[j].parent ==0){s1=j;s2=j;goto flag;}}flag: for(j=s1+1;j<i;j++){if(HT[j].parent==0){if(HT[s1].weight >=HT[j].weight){s2=s1;s1=j;}if(HT[s2].weight>HT[j].weight&&j!=s1)s2=j;if(s1==s2)s2=j;}}}void Print_tree(int n,Huff HT) //以凹入法的形式打印树{unsigned char T[100][100];int tt[100][100];int i,j,m=0;FILE *fp;Convert_tree(HT,T,tt,0,&m,2*n-1); //将内存中的赫夫曼树转换成凹凸表形式的树，存于数组T中if((fp=fopen("treeprint.txt","wb+"))==NULL)printf("Open file treeprint.txt error!\n");printf("\n以凹凸表形式打印已建好的赫夫曼树：\n");for(i=1;i<=2*n-1;i++){for (j=0;T[i][j]!=0;j++){if(T[i][j]==' ') {printf(" ");fputc(T[i][j],fp);}else{printf("%d",tt[i][j]);fprintf(fp,"%d\n\n\n",tt[i][j]);} }printf("\n");}fclose(fp);printf("\n此字符形式的哈夫曼树已写入文件treeprint.txt中.\n\n");printf("\n文件treeprint.txt的打开方式要为写字板，若打开方式为记事本，则无法显示凹凸表的形式\n");}void Convert_tree(Huff HT,unsigned char T[100][100],int tt[100][100],int s,int *i,int j) //将内存中的赫夫曼树转换成凹凸表形式的树，存于数组T中{int k,l;l=++(*i);for(k=0;k<s;k++)T[l][k]=' ';T[l][k]='#';tt[l][k]=HT[j].weight;if(HT[j].lchild)Convert_tree(HT,T,tt,s+1,i,HT[j].lchild);if(HT[j].rchild)Convert_tree(HT,T,tt,s+1,i,HT[j].rchild);T[l][++k]='\0';}void coding(int n) //对文件ToBeTran.txt编码到CodeFile.txt{FILE *fp1;Huff HT;HuffmanTree(HT,w,n);visite(HT,2*n-1,2,0);fflush(stdin);translatef("ToBeTran.txt","CodeFile.txt",n);fp1=fopen("CodeFile.txt","r");printf("\n编码已写入文件treeprint.txt中.\n");fclose(fp1);}void decoding(int n) //对CodeFile.txt中的01序列进行解码到TextFile.txt{FILE *fp1,*fp2;Huff HT;HuffmanTree(HT,w,n);fp1=fopen("CodeFile.txt","r");fp2=fopen("TextFile.txt","w");while(uncodef(fp1,fp2,HT,2*n-1));printf("\n");printf("\n解码已写入文件TextFile.txt中.\n");fclose(fp1);fclose(fp2);}void visite(Huff HT,int i,int flag,int rear)//通过递归调用visite()函数，得到各个字母的编码，存储于全局变量code[][]中{int j=0,k=0;if(flag==0){stack[rear]='0';rear++;}else if(flag==1){stack[rear]='1';rear++;}if(HT[i].lchild==0){for(j=0;j<rear;j++){code[i][j]=stack[j];}code[i][j]='#';rear--;return;}visite(HT,HT[i].lchild,0,rear);visite(HT,HT[i].rchild,1,rear);k=rear;for(j=0;j<k;j++){code[i][j]=stack[j];}code[i][j]='#';rear--;return;}void translatef(char *scource,char *save,int n)//读取文件中的字母序列，并根据code[][]将其转换成01序列输出{FILE *fp1,*fp2;char p=' ';int i=0,j=0,k=0;fp1=fopen(scource,"r");fp2=fopen(save,"w");p=fgetc(fp1);printf("\n得到的编码为:\n");while(p!=EOF){for(i=0;i<=n;i++){if(c[i]==p){for(j=0;j<N&&code[i][j]!='#';j++){fputc(code[i][j],fp2);putchar(code[i][j]);k++;if(k>=50){k=0;putchar('\n');}}}}p=fgetc(fp1);}fclose(fp1);fclose(fp2);}bool uncodef(FILE *fp1,FILE *fp2,Huff HT,int n)//通过对树的访问，把文件中01序列转换成一个字母输出。