哈夫曼译码

1000(ms)

10000(kb)

1997 / 4186

通常要求根据给定的编码本对密文进行解码。现已给定相应字符的哈夫曼编码，要求根据编码对密文进行解码。（建立哈夫曼树以及编码、主函数等都已经给出，你只需要填写译码函数void ccode(haffnode  hafftree[],int n)即可。

const int maxvalue=100;

const int maxbit=100;

const int maxn=100;

 #include "iostream"

#include "stdio.h"

#include "stdlib.h"

using namespace std;

struct haffnode

{

 char ch; 

int weight; 

int flag; 

int parent;

 int leftchild; 

int rightchild;

};

struct code

{ 

int bit[maxn];

 int start;

 int weight; 

char ch;

}; 

void haffman(int weight[],char text[],int n,haffnode hafftree[])

{ 

int j,m1,m2,x1,x2,i; 

for(i=0;i< 2*n-1;i++) 

{ 

if(i < n) 

{ 

hafftree[i].weight=weight[i]; 

hafftree[i].

ch=text[i];

 } 

else

 { 

hafftree[i].weight=0; 

hafftree[i].ch='#'; 

} 

hafftree[i].parent=0;

 hafftree[i].flag=0;

 hafftree[i].leftchild=-1;

 hafftree[i].rightchild=-1;

 } 

for(i=0;i< n-1;i++) 

{ 

m1=m2=maxvalue;

 x1=x2=0; 

for(j=0;j< n+i;j++) 

{ 

if(hafftree[j].weight< m1&&hafftree[j].flag==0) 

{ 

m2=m1;

 x2=x1;

 m1=hafftree[j].weight;

 x1=j; 

} 

else if(hafftree[j].weight< m2&&hafftree[j].flag==0)

 { 

m2=hafftree[j].weight; x2=j;

 } 

} 

hafftree[x1].parent=n+i; 

hafftree[x2].parent=n+i;

 hafftree[x1].flag=1; 

hafftree[x2].flag=1; 

hafftree[n+i].weight=hafftree[x1].weight+hafftree[x2].weight; 

hafftree[n+i].leftchild=x1; hafftree[n+i].rightchild=x2;

 } 

} 

void haffmancode(haffnode hafftree[],int n,code haffcode[])

{ 

code cd; int i,j; int child,parent;

 for( i=0;i< n;i++)

 { 

cd.start=n-1; 

cd.weight=hafftree[i].weight; 

cd.ch=hafftree[i].ch; 

child=i; 

parent=hafftree[child].parent; 

while(parent!=0)

 { 

if(hafftree[parent].leftchild==child) 

cd.bit[cd.start]=0; 

else cd.bit[cd.start]=1; 

cd.start--; 

child=parent; 

parent=hafftree[child].parent; 

} 

for(j=cd.start+1;j< n;j++) 

haffcode[i].bit[j]=cd.bit[j];

 haffcode[i].start=cd.start;

 haffcode[i].weight=cd.weight; 

haffcode[i].ch=cd.ch;

 } 

} 

void ccode(haffnode hafftree[],int n)

{ }

 int main( )

{ 

int n=8; 

int weight[]={5,29,7,8,14,23,3,11};

 char text[]={'a','b','c','d','e','f','g','h'}; 

haffnode myhafftree[maxvalue]; 

code myhaffcode[maxvalue];

 haffman(weight,text,n,myhafftree);

 haffmancode(myhafftree,n,myhaffcode); 

ccode(myhafftree,n); 

return 0;

}

输入

根据哈夫曼树编码表，针对字符串做好的编码结果。

输出

对每一行需要解码的串，进行解码，并输出解码后的结果。

样例输入

000100011011101110

样例输出

aabcc 

 

1 const int maxvalue=100;  2 const int maxbit=100;  3 const int maxn=100;  4 #include "iostream"  5 #include "stdio.h"  6 #include "stdlib.h"  7 #include "string.h"   8 using namespace std;  9 struct haffnode 10 { 11     char ch; 12     int weight; 13     int flag; 14     int parent; 15     int leftchild; 16     int rightchild; 17 }; 18 struct code 19 { 20     int bit[maxn]; 21     int start; 22     int weight; 23     char ch; 24 }; 25 void haffman(int weight[],char text[],int n,haffnode hafftree[]) 26 { 27     int j,m1,m2,x1,x2,i; 28     for(i=0; i< 2*n-1; i++) 29     { 30         if(i < n) 31         { 32             hafftree[i].weight=weight[i]; 33             hafftree[i]. 34             ch=text[i]; 35         } 36         else 37         { 38             hafftree[i].weight=0; 39             hafftree[i].ch='#'; 40         } 41         hafftree[i].parent=0; 42         hafftree[i].flag=0; 43         hafftree[i].leftchild=-1; 44         hafftree[i].rightchild=-1; 45     } 46     for(i=0; i< n-1; i++) 47     { 48         m1=m2=maxvalue; 49         x1=x2=0; 50         for(j=0; j< n+i; j++) 51         { 52             if(hafftree[j].weight< m1&&hafftree[j].flag==0) 53             { 54                 m2=m1; 55                 x2=x1; 56                 m1=hafftree[j].weight; 57                 x1=j; 58             } 59             else if(hafftree[j].weight< m2&&hafftree[j].flag==0) 60             { 61                 m2=hafftree[j].weight; 62                 x2=j; 63             } 64         } 65         hafftree[x1].parent=n+i; 66         hafftree[x2].parent=n+i; 67         hafftree[x1].flag=1; 68         hafftree[x2].flag=1; 69         hafftree[n+i].weight=hafftree[x1].weight+hafftree[x2].weight; 70         hafftree[n+i].leftchild=x1; 71         hafftree[n+i].rightchild=x2; 72     } 73 } 74 void haffmancode(haffnode hafftree[],int n,code haffcode[]) 75 { 76     code cd; 77     int i,j; 78     int child,parent; 79     for( i=0; i< n; i++) 80     { 81         cd.start=n-1; 82         cd.weight=hafftree[i].weight; 83         cd.ch=hafftree[i].ch; 84         child=i; 85         parent=hafftree[child].parent; 86         while(parent!=0) 87         { 88             if(hafftree[parent].leftchild==child) 89                 cd.bit[cd.start]=0; 90             else 91                 cd.bit[cd.start]=1; 92             cd.start--; 93             child=parent; 94             parent=hafftree[child].parent; 95         } 96         for(j=cd.start+1; j< n; j++) 97             haffcode[i].bit[j]=cd.bit[j]; 98         haffcode[i].start=cd.start; 99         haffcode[i].weight=cd.weight;100         haffcode[i].ch=cd.ch;101     }102 }103 void ccode(haffnode hafftree[],int n)104 {105     int i,j=0,m=2*n-1;106     char b[maxn];107     memset(b,'\0',sizeof(b));108     i=m-1;                      109     scanf("%s",b);110     while(b[j]!='\0')111     {112         if(b[j]=='0')113             i=hafftree[i].leftchild;              114         else115             i=hafftree[i].rightchild;              116         if(hafftree[i].leftchild==-1)         117         {118             printf("%c",hafftree[i].ch);119             i=m-1;      120         }121         j++;122     }123 }124 int main( )125 {126     int n=8;127     int weight[]= {
   5,29,7,8,14,23,3,11};128     char text[]= {
   'a','b','c','d','e','f','g','h'};129     haffnode myhafftree[maxvalue];130     code myhaffcode[maxvalue];131     haffman(weight,text,n,myhafftree);132     haffmancode(myhafftree,n,myhaffcode);133     ccode(myhafftree,n);134     return 0;135 }