哈夫曼编码应用

问题描述

​ 给定字符串  
    
    
，将每个不同的字符的哈夫曼编码表示并输出其哈夫曼编码

     


     


  ，并再将其哈夫曼编码还原回字符串

分析一下

构建哈夫曼树

​ 使用静态链表 




 




 
，先将所有的结点关系全部清零  

   

   

，再进行结点和相应权值的赋值

     

     

 ，遍历后n-1个结点 (新根)  




  




  ，从n个结点中选两个最小的权值了合成一棵树  


  


  


，并将新根加入到比较结点中(并将这两棵树标记以及结合
     
     
，不再进行下次的比较)
   




   




   ，最后后合成一颗哈夫曼树

哈夫曼编码

​ 在这里用到了一个大数组嵌套一个小数组 



 



 


，大数组I的功能是存放每一个结点的哈夫曼编码           ，小数组中存放每一个结点的没有个哈夫曼编码的反码

​ 从叶子结点分别向根出发即可

    




    




   ，若该结点时双亲结点的左孩子












，则记0            ，反之记为1

     



     



   ，记录在一个记录数组中直到该结点没有双亲(根结点)











，每遍历完一个结点后将记录数组复制到对应的小数组中    
    
  。并及时清空记录数组进行下次使用   


     


     
。

​ 在输出方面使用了多重的for循环  
    
    
，依次遍字符串

     


     


  ，将字符串的每一个字符与结点进行比较 




 




 
，若相等则输出对应的(该结点)的哈夫曼编码  

   

   

，最后再用一数组接收

     

     

 ，以便后续的使用

解码

​ 依次遍历没有过哈夫曼遍历  




  




  ，从根结点出发  


  


  


，遇0向左
     
     
，遇1则右
   




   




   ，若到了叶子（无左孩子或无右孩子） 



 



 


，则输出



 




 




。并将更新结点值

看看代码吧

必没问题！！！(有问题就用个dev吧...)

#include<iostream> #define Max_S 1000000 #define MaxSize 100 using namespace std; //静态链表 typedef struct TreeNode{ char data; int weight; int parent,lchild,rchild; }HTNode, *HuffmanTree; //编码数组 typedef struct{ int HC[MaxSize]; }info,*Info;//一个大数组套一个小数组 //=========================================================== //一些串和二叉树的算法 //求串长 int Strstrlen(char a[]){ int i = 1; for(;a[i] !=\0;){ i++; } return i; } //字符串赋值 void StrAssige(char(&S)[MaxSize+1],char a[]){ S[0] = Strstrlen(a); for(int i = 1;i <= Strstrlen(a);i++){ S[i] = a[i-1]; } } //求深度 int qiushendu(HuffmanTree t,int root){ if(root == 0) return 0; if(t[root].lchild == 0&&t[root].rchild == 0) return 1; return (max(qiushendu(t,t[root].lchild),qiushendu(t,t[root].rchild)) + 1); } //================================================================== //获取两个最小值 int *Select(HuffmanTree HT,int n){ int s1,s2;////最小值与极小值 int mmin = Max_S;//先等于无穷大 int min = Max_S; for(int i = 1;i <= n;i++){ if(HT[i].parent != 0) continue;//双亲不为零代表已经构成新树           ，应去除 else{ if(mmin >= HT[i].weight){//最小的 min = mmin ; s2 = s1; mmin = HT[i].weight; s1 = i; }else if(min >= HT[i].weight){//次小的 min = HT[i].weight; s2 = i; } } } //若最小值相等

    




    




   ，则浅(先遍历的)树的序号在前 int S1 = qiushendu(HT,s1); int S2 = qiushendu(HT,s2); if(S1 >= S2){ int temp; temp = s1; s1 = s2; s2 = temp;//交换顺序 } //用数组存放最小值和次小值 int a[3] = {0,s1,s2}; return a; } //=========================================================================== //构建哈夫曼树 void CreatHuffmanTree(HuffmanTree &HT,char *huf,int *wei,int n){ int s1,s2;//最小值与极小值 if(n <= 1){ cout << "抱歉












，您输入的结点数不符合逻辑"; return; } int m = 2*n-1;//总结点树 HT = new HTNode[m+1];//放弃下标为零的数组 //先遍历前n个数,初始化 for(int i = 1;i <= m;i++){//全部初始化为零 HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0; } //赋结点  
    
    
、权值 for(int i;i <= n;i++){ HT[i].data = huf[i];//结点 HT[i].weight = wei[(int)huf[i]];//权值 } //遍历后n+1个            ，新根 for(int i = n+1;i <= m;i++){ //找出最小额两个结点 int *a;//获取s1和s2 a = Select(HT,i-1);//在n个数中找 s1 = a[1]; s2 = a[2]; //更新各个数值 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; } } //================================================= //哈夫曼树编码化

     



     



   ，并输出 void HuffmanCode(HuffmanTree HT,info* I, int n){ int lchild,rchilg,parent,copyparent;//左孩子值











，有孩子子  
    
    
，双亲值

     


     


  ，类双亲值(永远是双亲值值的孩子 




 




 
，但不知是左孩子右) int jilv[100];//记录数组每个结点的编码(0/1)  

   

   

，算深度即可无需大开 for(int i = 1;i <= n;i++){//依次遍历叶子结点 int n = 0;//记录数 //初始化各个双亲值 copyparent = i; parent = HT[i].parent; while(parent != 0&&copyparent != 0){//两个双亲都不为零 if(HT[parent].lchild == copyparent){//结点的双亲的左孩子与他的序号相等

     

     

 ，记为零 jilv[++n] = 0; }else{ jilv[++n] = 1; } copyparent = parent;//更新类双亲 parent = HT[parent].parent;//更新双亲 } I[i].HC[0] = jilv[0] = n;//第一个字符的总编码数 for(int m = 1;m <= jilv[0];m++)//将第一个字符的所有编码复制到第一个存在数组中去 I[i].HC[m] = jilv[m]; //输出 cout << HT[i].data << ":"; for(int m = jilv[0];m >=1;m--){//反向输出 cout << I[i].HC[m]; jilv[m] = 0;//记录数组清空 } cout << endl; jilv[0] = 0;//记录数组清零 } } //完整输出哈夫曼编码 int *printHuf(char *h,char *huf,info* I){ static int hufman[MaxSize+1]; int mum = 0; for(int i = 1;i <= h[0];i++){//遍历原数组 for(int j = 1;j <= huf[0];j++){//遍历结点 if(h[i] == huf[j]){//如果相等 for(int m = I[j].HC[0];m >=1;m--){//反向输出 cout << I[j].HC[m]; hufman[++mum] = I[j].HC[m]; } } } } hufman[0] = mum; return hufman; } //================================================================================== //哈夫曼解码  




  




  ，并输出 void HuffmanDeCode(int * HufMan,HuffmanTree HT,int n){ HuffmanTree p = HT; int lchild,rchid,r,m = 2*n-1; for(int i = 1;i <= HufMan[0];i++){//遍历每一个哈夫曼编码 //与0向左  


  


  


，由1向右 if(HufMan[i] == 0){ m = p[m].lchild; }else{ m = p[m].rchild; } //若无孩子则直接输出(没有度为一的数)
     
     
，并更新根结点和m的值 if(p[m].lchild == 0||p[m].rchild == 0){ cout << p[m].data; p = HT; m = 2*n- 1; } } } int main(){ int wei[1000] = {0};//权值数组 char huf[MaxSize+1];//哈夫曼结点数组 char a[MaxSize+1];//赋值串 char h[MaxSize+1];//要编译的字符串 cout << "请输入要编码的字符:"; gets(a); StrAssige(h,a); //赋结点

     


     


  、权值 for(int i = 1,n = 0;i <=h[0];i++){ wei[(int)h[i]]++;//权值++ if(wei[(int)h[i]] == 1){//第一次遇到的不同得字符 huf[++n] = h[i];//结点确定 } huf[0] = n;//总结点数 } //哈夫曼树 HuffmanTree HT; //创建哈夫曼树 CreatHuffmanTree(HT,huf,wei,huf[0]); //====================================================================================== //将字符串哈夫曼编码化,并输出每个结点的哈夫曼编码 info *I = new info[huf[0]];//就是一个大数组
   




   




   ，大数组存放每一个字符的哈夫曼编码 



 



 


，小数组存放每一位的 HuffmanCode(HT,I,huf[0]); //输出完整的哈夫曼编码 ,并捕获 int* HufMan; cout << "获得的哈夫曼编码为："; HufMan = printHuf(h,huf,I); cout << endl; //================================================================================== //解码哈夫曼编码 cout << "该哈夫曼编码的解码为："; HuffmanDeCode(HufMan,HT,huf[0]); cout <<endl; return 0; }