一：问题描述
【问题描述】
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。
【任务要求】
一个完整的系统应具有以下功能：
1) I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
2) E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
3) D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
【测试数据】
用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。
| 字符 | 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 | 1 |
二：大致思路
1.构建哈夫曼树
有n个字母待建树，申请p[2n-1]个结构体数组空间，将各个字母及其权值存入结构体数组，将数组按照权值进行排序，每次选取最小的两个构建哈夫曼树，每次从上次选择的下一个开始选择，即第一次p[0],p[1]则第二次p[2],p[3]，以此类推，每次生成的从p[n+1]开始存入，直至数组就剩下一个元素，即为根节点。
2.编码
从叶子结点（带权字母即叶子结点，从1步骤的结构体数组那里入手，需要判断一下是否为叶子结点）开始向上回溯即寻找父节点，若为父节点左子树编码为‘0’字符，反之为‘1’字符，建个数组从最后一位往前存入直至父节点为空即根节点，直至结构体数组最后一个元素。然后将存储的字母的编码和待编码的字符串进行比对，将字符串译码为01结构，编码完成。
3.译码
将01结构的编码从根节点开始译码，0往左子树遍历1往右子树，直至叶节点，译码出一个字母，然后再从根节点开始，循环操作直至所有都译码完成。
三：具体实现
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; typedef struct node { char ch[2]; int weight; char ldata,rdata; node *lchild,*rchild,*parent; }*huffman; typedef struct encoding { char ch[2]; char *data; }*encode1; void paixu(huffman *p,int m) { huffman temp; for(int i=0;i<m-1;i++) { for(int j=i+1;j<m;j++) { if(p[i]->weight>p[j]->weight) { temp=p[i]; p[i]=p[j]; p[j]=temp; } } } } huffman* Read(int n) //读取英文字母 { huffman *huff; FILE *fp; huff=new huffman[2*n-1]; for(int i=0;i<2*n-1;i++) { huff[i]=new node; huff[i]->lchild=huff[i]->rchild=NULL; } if((fp=fopen("hfmTree.txt","w"))==NULL) {cout<<"文件打开失败!";exit(0);} cout<<"please input the letter:"<<endl; for(int i=0;i<n;i++) { huff[i]->ch[0]=cin.get(); if(huff[i]->ch[0]==' ') huff[i]->ch[0]=cin.get(); cin>>huff[i]->weight; cin.get(); huff[i]->ch[1]=' '; fprintf(fp,"%s%d ",huff[i]->ch,huff[i]->weight); } cout<<"hfmTree.txt文件写入完成!"<<endl; fclose(fp); return huff; } node* Crhuffman(huffman* p,int n,int *n1) //创建哈夫曼树 { int m=n; for(int i=0;i<2*n-1;i+=2) { if((m-1)!=i) { paixu(p,m); p[m]->weight=p[i]->weight+p[i+1]->weight; p[m]->lchild=p[i]; p[m]->rchild=p[i+1]; p[i]->parent=p[m]; p[i+1]->parent=p[m]; m+=1; } else {p[m-1]->parent=NULL;break;} } *n1=m; return p[m-1]; } int Code(huffman *p,int n,int t,char *c,int c1,char *c2) //哈弗曼编码 { huffman q; FILE *fp; q=new node; int k=0,k1=t-1,kk=0; encode1 *encode; encode=new encode1[t]; for(int i=0;i<t;i++) { encode[i]=new encoding; encode[i]->data=new char[t]; } for(int i=0;i<t;i++) { for(int j=0;j<t;j++) { encode[i]->data[j]='a'; } } for(int i=0;i<n;i++) { if(p[i]->lchild==NULL&&p[i]->rchild==NULL) { q=p[i]; encode[k]->ch[0]=p[i]->ch[0]; while(q->parent!=NULL) { if(q->parent->lchild==q) encode[k]->data[k1]='0'; else encode[k]->data[k1]='1'; q=q->parent; k1=k1-1; } k+=1; k1=t-1; } } if((fp=fopen("CodeFile.txt","w"))==NULL) {cout<<"文件打开失败!"<<endl;exit(0);} for(int i=0;i<t;i++) { encode[i]->ch[1]=' '; fprintf(fp,"%s:",encode[i]->ch); for(int j=0;j<t;j++) { if(encode[i]->data[j]!='a') { fprintf(fp,"%c",encode[i]->data[j]); if(j==t-1) fprintf(fp," "); } } } for(int i=0;i<c1;i++)//编码 { for(int j=0;j<t;j++) { if(c[i]==encode[j]->ch[0]) for(int k2=0;k2<t;k2++) { if(encode[j]->data[k2]!='a') { c2[kk]=encode[j]->data[k2]; kk+=1; } } } } c2[kk]=' '; fprintf(fp,"#题目所给英文编码: %s",c2); cout<<"CodeFile文件写入完成!"<<endl; fclose(fp); return kk; } int Readtxt(char *c) //读取英文字符串 { int m=0; FILE *fp; cout<<"请输入需要编码的大写英文:"<<endl; if((fp=fopen("ToBeTran.txt","w"))==NULL) {cout<<"文件打开失败!";exit(0);} for(int i=0;;i++) { c[i]=cin.get(); if(c[i]==' ') {c[i]=' ';break;} m+=1; } fprintf(fp,"%s",c); fclose(fp); cout<<"ToBeTran.txt文件写入完成!"<<endl; return m; } void Initialization(huffman **p,node **p1,int &n,int &n1) //初始化 { cout<<"请输入待插入英文字母个数:"<<endl; cin>>n; *p=Read(n); *p1=Crhuffman(*p,n,&n1); } void Encoding(int &c1,char **c,char **c2,int n,int n1,huffman *p) //编码 { c1=Readtxt(*c); Code(p,n1,n,*c,c1,*c2); } void Decoding(node *p1,char *c) //译码 { int k=0,i=0; FILE *fp; node *p=p1; if((fp=fopen("TextFile.txt","w"))==NULL) {cout<<"文件打开失败!";exit(0);} while(c[i]!=' ') { while(c[i]!=' ') { if(c[i]=='0') { p=p->lchild; if(p->lchild==NULL&&p->rchild==NULL) {i++;break;} } else { p=p->rchild; if(p->lchild==NULL&&p->rchild==NULL) {i++;break;} } i++; } fprintf(fp,"%s",p->ch);p=p1; } fclose(fp);cout<<"TextFile.txt文件写入完成!"<<endl; } void Print() //打印 { FILE *fp,*fp1; char ch[1000]; if((fp=fopen("CodeFile.txt","r"))==NULL) {cout<<"文件打开失败!"<<endl;exit(0);} if((fp1=fopen("CodePrint.txt","w"))==NULL) {cout<<"文件打开失败!"<<endl;exit(0);} while(!feof(fp)) { fscanf(fp,"%s",ch); if(ch[0]=='#') { cout<<ch<<endl; fscanf(fp,"%s",ch); fprintf(fp1,"%s",ch); } cout<<ch<<endl; } fclose(fp); fclose(fp1); } void Tree_printing(node *p1) { FILE *fp; if((fp=fopen("TreePrint.txt","a"))==NULL) {cout<<"文件打开失败!"<<endl;exit(0);} if(p1) { if(p1->ch[0]==NULL) { cout<<"空"<<p1->weight<<" "; fprintf(fp,"空%d ",p1->weight); } else { cout<<p1->ch[0]<<p1->weight<<" "; fprintf(fp,"%c%d ",p1->ch[0],p1->weight); } Tree_printing(p1->lchild); Tree_printing(p1->rchild); } } void homepage() { cout<<"****************************************************************************"<<endl; cout<<" 1.Initialization()&&Encoding() //初始化并编码 "<<endl; cout<<" 2.Decoding() //译码 "<<endl; cout<<" 3.Print() //打印代码文件 "<<endl; cout<<" 4.Tree_printing() //打印哈夫曼树 "<<endl; cout<<" 5.Confirm exit //确认退出 "<<endl; cout<<"****************************************************************************"<<endl; cout<<"请选择需要的操作："<<endl; } void display() { int N;huffman *p,i=0; node *p1; encode1 *q; char *c,*c2; c=new char[100]; c2=new char[1000]; int n,n1,c1,n2; homepage(); cin>>N; while(1) { // system("cls"); if(N==1) { Initialization(&p,&p1,n,n1); Encoding(c1,&c,&c2,n,n1,p); i+=1; } else if(N==2) { if(i==0) {cout<<"操作不合法，请重新输入！"<<endl;} else {Decoding(p1,c2);i+=1;} } else if(N==3) { if(i==0) {cout<<"操作不合法，请重新输入！"<<endl;} else {cout<<" ";Print();i+=1;} } else if(N==4) { if(i==0) {cout<<"操作不合法，请重新输入！"<<endl;} else {Tree_printing(p1);i+=1;cout<<endl;} } else if(N==5) exit(0); else printf("输入不合法,请重新输入！ "); homepage(); cin>>N; } } int main() { display(); }
四：运行结果
具体编译码结果可以查看生成的编码文件以及译码文件
五：总结
1.字母以字符形式写入文件时会乱码，不能用%c，可以改为%s整体写入，注意字符数组末尾要加‘ ’转为字符串。
2.将指针传入函数，想改变指针的值即传入的指针再调用完后改变，即如test（p）(main 函数里的),void test(int **p)(main函数外的),需要设二级指针，即指向指针的指针，指针也是变量，和普通变量一样，只不过是地址类型，而且可以访问指针所存地址里的东西。
3.结构体数组即每个元素都是结构体，指向结构体的二级指针即二级指针元素是一级指针，一级指针元素是结构体类型数据。