哈夫曼编码和译码 基本要求： 输入为：一段英文或中文的文章（原文） 对输入的文章构造哈夫曼树生成对应的编码 输出为：原文所对应的编码（译文） 根据已经生成的编码表，输入任意的译文可以得到对应的原文
哈夫曼树的定义：给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
首先先构造一棵哈夫曼树，在构造哈夫曼树的算法中，需要选择根权值最小和次小的树进行合并
//建立哈夫曼树编码表 void HuffmanTree::CreatHuffmanTree(int a[],char b[],int n) { int m=2*n-1; nodes= new HuffmanTreeNode[2*n-1];//开辟数组空间 for(int i=0;i<n;i++) //初始化结点为-1 { nodes[i].weight=a[i]; //函数头定义的权值数组a[] nodes[i].leftChild=-1; nodes[i].rightChild=-1; nodes[i].parent=-1; } for(i=n; i<m;i++) { int r1=0,r2=0; select(r1,r2,i); //合并两个根权值最小的树 nodes[r1].parent=nodes[r2].parent=i; nodes[i].leftChild=r1; nodes[i].rightChild=r2; nodes[i].parent=-1; nodes[i].weight=nodes[r1].weight+nodes[r2].weight; } //查找两个权值最小的树 void HuffmanTree::select(int &r1,int &r2,int n) { r1=r2=-1; for(int i=0; i<n; i++) if(nodes[i].parent==-1) //找权值最小的双亲节点 if(r1==-1) r1=i; else if(nodes[r1].weight<nodes[i].weight) { r2=r1;//r2等于次小的 r1=i;//r1等于最大的 } else if(r2==-1||nodes[i].weight<nodes[r2].weight)//找权值第二小的结点 r2=i; } ```cpp 在这里插入代码片建立编码表，根据每一根分支是左还是右，确定相应位编码是0还是1（此代码为左0右1），从叶子节点出发逆向到根结点，将编码倒转使之成为正确的编码
//建立编码表 void HuffmanTree::CreatHuffmanTree(int a[],char b[],int n) { codes=new HuffmanCode[n]; for( i=0; i<n; i++) { codes[i].data=b[i];//将编码后的结果储存在b数组中 int q=i; int p=nodes[i].parent;//p指向结点i的双亲 int k=0; while(p!=-1)//逆向求码 { if(q==nodes[p].leftChild) codes[i].code[k]='0'; //左0 else codes[i].code[k]='1'; //右1 k++;//向下往上查找双亲 q=p; p=nodes[q].parent; } codes[i].code[k]='\0'; recall(codes[i].code,k); //字符串整合，倒转 cout<<codes[i].data<<"的编码是："<<codes[i].code<<endl; } } //倒转字符串 void HuffmanTree::recall(char c[],int L) { L=0; char temp; while(c[L+1]!='\0')//获取当前编码的长度 { L++; } for(int i=0;i<=L/2;i++)//交换位置 { temp=c[i]; c[i]=c[L-i]; c[L-i]=temp; } }有了哈夫曼树的编码，即可进行编码和译码
//编码 void HuffmanTree::Encode(char *c, char *s,int n) { while(*c!='\0') { for(int i=0;i<=n-1;i++) //遍历查找编码 { if(*c==codes[i].data) { strcat(s,codes[i].code);//复制连接字符串 break; } } c++; } cout<<"编码结果为："<<s<<endl; } //译码 void HuffmanTree::Decode(char *s, char *d,int n) { int z=2*n-2; char *p=d; while(*s!='\0')//编码的逆过程 { while(nodes[z].leftChild!=-1) { if(*s=='0') //如果*s==0，给根结点的左孩子的下标值赋值z并把左孩子作为新的根结点 z=nodes[z].leftChild;//左0 else if(*s=='1') z=nodes[z].rightChild;//右1 s++; } *d=codes[z].data;//译码后的结果赋值给指针*d d++; } cout<<endl<<"译码结果为："<<p<<endl; }主要函数就是以上，下面将程序变得完整一点，使其成为可运行的程序 主函数如下：
void main() { HuffmanTree HT; //system("color b0"); //system("color f4"); cout<<"---------------------------------------"<<endl; cout<<" 欢迎使用哈夫曼编码系统 "<<endl; cout<<"---------------------------------------"<<endl; cout<<" 请输入英文段落： "<<endl; char *A1=new char[50];//定义字符指针，开辟空间设置字符长度 char *B1=new char[50]; *B1='\0';//字符串结束标志 gets(A1);//得到从键盘输入的字符串A1 int n = HT.sumweight(A1);//计算A1字符串的频率 char *A2=new char[50]; for(int i=0;i<=49;i++) *(A2+i)='\0'; //到A2+1个字符结束 cout<<"按任意字符继续。"<<endl; getch(); HT.menu(); while(true) { int w; cin>>w; switch(w) { case 1: HT.CreatHuffmanTree(I,H,n); getch(); cout<<"按任意字符继续。"<<endl; //system("cls");可选择清屏或不清屏 HT.menu(); break; case 2: HT.Encode(A1,B1,n); cout<<"按任意字符继续。"<<endl; getch(); //system("cls"); HT.menu(); break; case 3: gets(B1); cout<<endl<<"请输入想要翻译的一串二进制编码："<<endl; gets(B1); HT.Decode(B1,A2,n); cout<<"按任意字符继续。"<<endl; getch(); //system("cls"); HT.menu(); break; case 4: cout << endl; cout << "退出成功！" << endl; exit(0); break; default: cout<<"选择失败，请重新选择！"<<endl; cout<<endl; break; } } }哈夫曼树是带权路径长度最小的树，所以将一段英文里出现字符的频率作为权值来计算
//计算字符出现的频率 int HuffmanTree::sumweight(char *pl) { char *sweight=pl; int i=0; H[0]=*sweight; I[0]=0; while(*sweight!='\0') { for(int j=0;j<=i;j++) { if(H[j]==*sweight) { I[j]++; break; } } if(j>i) { i++; H[i]=*sweight; I[i]=1; } sweight++; } cout<<endl<<"统计次数："<<endl; for(int j=0;j<=i;j++) cout<<"字符"<<H[j]<<"的频率为"<<I[j]<<endl; return i+1; }至此，程序基本已经完善，剩下的函数成员以及结构体可在调试时自行加上。
