添加注释版本:
/* cout<<i<<endl<<" 结点 | data | weight | lchild | rchild | parent "<<endl; for(int i=1;i<=m;++i) { cout<<i<<" | "<<HT[i].data<<" | "<<HT[i].weight<<" | "<<HT[i].lchild<<" | "<<HT[i].rchild<<" | "<<HT[i].parent<<endl; } */ #include<iostream> #include<stdio.h> #include<string> #include<cstring> #include<algorithm> #define MAX 0x3f3f3f3f using namespace std; typedef struct { char data; int weight; int parent; int lchild; int rchild; bool tag; }Huffnode,*HuffmanTree; typedef struct { string *code;//存放字符的编码 char *data;//存放字符 int num;//存放一共有多少字符 }HuffmanCode; void DisplayHuffmanCode(HuffmanCode &HC,int n) { for(int i=0;i<n;++i) { cout<<HC.code[i]<<endl; } } void Select(HuffmanTree &HT,int index, int &s1, int &s2) { int min1=MAX; int min2=MAX; for(int i=1;i<=index;++i) { if(HT[i].parent==0&&HT[i].tag) { if(HT[i].weight<min1) { s1=i; min1=HT[i].weight; } } } HT[s1].tag=0;//表明此节点已经被选中过 for(int i=1;i<=index;++i) { if(HT[i].parent==0&&HT[i].tag) { if(HT[i].weight<min2) { s2=i; min2=HT[i].weight; } } } HT[s2].tag=0; } void CreatHuffmanTree(HuffmanTree &HT,int n) { /*n:待编码数有多少*/ if(n<=1)return; int m=2*n-1; //计算节点个数 HT=new Huffnode[m+1];//0号单元未用,HT[m]表示根结点,从1开始存放数据 //初始化哈夫曼表 for(int i=1;i<=m;++i) { HT[i].lchild=0; HT[i].rchild=0; HT[i].parent=0; HT[i].tag=1; HT[i].data='\0'; } //依次输入待编码的数据的权重 cout<<"请依次输入每一个字和它的权重:"<<endl; for(int i=1;i<=n;++i) { scanf("%c",&HT[i].data); getchar(); scanf("%d",&HT[i].weight); getchar(); // cin>>HT[i].data>>HT[i].weight; } //构造 Huffman树 int s1,s2; for(int i=n+1;i<=m;++i) { Select(HT,i-1,s1,s2); //在已经有数据的哈夫曼节点中,选择两个双亲域为0,且权值最小的结点 //并返回它们在HT中的序号s1和s2 HT[s1].parent=i; HT[s2].parent=i; //表示从F中删除s1,s2 HT[i].lchild=s1; HT[i].rchild=s2; //s1,s2分别作为i的左右孩子 HT[i].weight=HT[s1].weight + HT[s2].weight; //i 的权值为左右孩子权值之和 } cout<<" 结点 | data | weight | lchild | rchild | parent "<<endl; for(int i=1;i<=m;++i) { cout<<i<<" | "<<HT[i].data<<" | "<<HT[i].weight<<" | "<<HT[i].lchild<<" | "<<HT[i].rchild<<" | "<<HT[i].parent<<endl; } } //根据创建的哈夫曼树,从叶子到根逆向求每个字符的赫夫曼编码,存储在编码表HC中 void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n) { /*n:代表编码个数*/ HC.code=new string[n+1]; //分配n个指向字符串的指针 HC.data=new char[n+1]; HC.num=n+1;//从1开始存 for(int i=1; i<=n; ++i) { //逐个字符求赫夫曼编码 int c=i; //哈夫曼表的下标 int f=HT[i].parent; string cd=""; while(f!=0) { //从叶子结点开始向上回溯,直到根结点 if (HT[f].lchild==c) { cd+="0"; //结点c是f的左孩子,则生成代码0 } else { cd+="1"; //结点c是f的右孩子,则生成代码1 } c=f; //跟新孩子,找上一代 f=HT[f].parent; //继续向上回溯 } reverse(cd.begin(),cd.end()); HC.code[i]=cd; //将求得的编码从临时空间cd复制到HC的当前行中 // cout<<cd<<endl; } cout<<"当前的哈夫曼编码表为:"<<endl; for(int i=1;i<=n;++i) { HC.data[i]=HT[i].data; cout<<i<<" | "<<HC.data[i]<<" | "<<HC.code[i]<<endl; } } void Encoding(HuffmanCode HC,string str) { cout<<"编码结果为:"<<endl; for(int i=0;i<str.length();++i) { for(int j=1;j<=HC.num;++j) { // cout<<"\nHC.data[j]==str[i]"<<HC.data[j]<<" "<<str[i]<<endl; if(HC.data[j]==str[i]) { cout<<HC.code[j]; break; } } } } void Decoding(HuffmanCode HC,string str) { cout<<"解码结果为:"<<endl; string temp=""; int postion=0; for(int i=0;i<str.length();) { for(int j=1;j<=HC.num;++j) { int k=0; // cout<<"\n当前查找的是:"<<HC.code[j]; for(;k<HC.code[j].length();++k) { // cout<<" HC.code[j][k]!=str[i] "<<HC.code[j][k]<<","<<str[i+k]; if(HC.code[j][k]!=str[i+k]) { break; } } // cout<<" k="<<k<<endl; if(k==HC.code[j].length()) { i+=HC.code[j].length(); cout<<HC.data[j]; break; } } } } int main() { HuffmanTree HT; HuffmanCode HC; //构造赫夫曼树,输出各字符的赫夫曼编码 cout<<"\n请输入编码的个数:"<<endl; int n=0; cin>>n; getchar(); CreatHuffmanTree(HT,n); CreatHuffmanCode(HT,HC,n); // 编码:输入字符序列,输出对应的赫码序列。 cout<<"\n请输入要编码的字符:"<<endl; string e_str=""; getline(cin,e_str); Encoding(HC,e_str); // cout<<e_str<<endl; // 译码:输入赫夫曼码序列,输出原始字符代码。 cout<<"\n请输入要解码的字符:"<<endl; string d_str=""; getline(cin,d_str); Decoding(HC,d_str); }View Code
未加注释清爽版:
1 #include<iostream> 2 #include<stdio.h> 3 #include<string> 4 #include<cstring> 5 #include<algorithm> 6 #define MAX 0x3f3f3f3f 7 using namespace std; 8 9 typedef struct 10 { 11 char data; 12 int weight; 13 int parent; 14 int lchild; 15 int rchild; 16 bool tag; 17 }Huffnode,*HuffmanTree; 18 typedef struct 19 { 20 string *code; 21 char *data; 22 int num; 23 }HuffmanCode; 24 void DisplayHuffmanCode(HuffmanCode &HC,int n) 25 { 26 for(int i=0;i<n;++i) 27 { 28 cout<<HC.code[i]<<endl; 29 } 30 } 31 void Select(HuffmanTree &HT,int index, int &s1, int &s2) 32 { 33 int min1=MAX; 34 int min2=MAX; 35 for(int i=1;i<=index;++i) 36 { 37 if(HT[i].parent==0&&HT[i].tag) 38 { 39 if(HT[i].weight<min1) 40 { 41 s1=i; 42 min1=HT[i].weight; 43 } 44 } 45 } 46 HT[s1].tag=0; 47 for(int i=1;i<=index;++i) 48 { 49 if(HT[i].parent==0&&HT[i].tag) 50 { 51 if(HT[i].weight<min2) 52 { 53 s2=i; 54 min2=HT[i].weight; 55 } 56 } 57 } 58 HT[s2].tag=0; 59 } 60 void CreatHuffmanTree(HuffmanTree &HT,int n) 61 { 62 if(n<=1)return; 63 int m=2*n-1; 64 HT=new Huffnode[m+1]; 65 66 for(int i=1;i<=m;++i) 67 { 68 HT[i].lchild=0; 69 HT[i].rchild=0; 70 HT[i].parent=0; 71 HT[i].tag=1; 72 HT[i].data='\0'; 73 } 74 cout<<"请依次输入每一个字和它的权重:"<<endl; 75 for(int i=1;i<=n;++i) 76 { 77 scanf("%c",&HT[i].data); 78 getchar(); 79 scanf("%d",&HT[i].weight); 80 getchar(); 81 } 82 83 int s1,s2; 84 for(int i=n+1;i<=m;++i) 85 { 86 Select(HT,i-1,s1,s2); 87 HT[s1].parent=i; 88 HT[s2].parent=i; 89 HT[i].lchild=s1; 90 HT[i].rchild=s2; 91 HT[i].weight=HT[s1].weight + HT[s2].weight; 92 } 93 } 94 void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n) 95 { 96 97 HC.code=new string[n+1]; 98 HC.data=new char[n+1]; 99 HC.num=n+1; 100 101 for(int i=1; i<=n; ++i) 102 { 103 int c=i; 104 int f=HT[i].parent; 105 string cd=""; 106 while(f!=0) 107 { 108 if (HT[f].lchild==c) 109 { 110 cd+="0"; 111 } 112 else 113 { 114 cd+="1"; 115 } 116 c=f; 117 f=HT[f].parent; 118 } 119 reverse(cd.begin(),cd.end()); 120 HC.code[i]=cd; 121 } 122 cout<<"当前的哈夫曼编码表为:"<<endl; 123 for(int i=1;i<=n;++i) 124 { 125 HC.data[i]=HT[i].data; 126 cout<<i<<" | "<<HC.data[i]<<" | "<<HC.code[i]<<endl; 127 128 } 129 } 130 void Encoding(HuffmanCode HC,string str) 131 { 132 cout<<"编码结果为:"<<endl; 133 for(int i=0;i<str.length();++i) 134 { 135 for(int j=1;j<=HC.num;++j) 136 { 137 if(HC.data[j]==str[i]) 138 { 139 cout<<HC.code[j]; 140 break; 141 } 142 } 143 144 } 145 } 146 void Decoding(HuffmanCode HC,string str) 147 { 148 cout<<"解码结果为:"<<endl; 149 string temp=""; 150 int postion=0; 151 for(int i=0;i<str.length();) 152 { 153 for(int j=1;j<=HC.num;++j) 154 { 155 int k=0; 156 for(;k<HC.code[j].length();++k) 157 { 158 if(HC.code[j][k]!=str[i+k]) 159 { 160 break; 161 } 162 } 163 if(k==HC.code[j].length()) 164 { 165 i+=HC.code[j].length(); 166 cout<<HC.data[j]; 167 break; 168 } 169 } 170 } 171 } 172 int main() 173 { 174 HuffmanTree HT; 175 HuffmanCode HC; 176 //构造赫夫曼树,输出各字符的赫夫曼编码 177 cout<<"\n请输入编码的个数:"<<endl; 178 int n=0; 179 cin>>n; 180 getchar(); 181 CreatHuffmanTree(HT,n); 182 CreatHuffmanCode(HT,HC,n); 183 // 编码:输入字符序列,输出对应的赫码序列。 184 cout<<"\n请输入要编码的字符:"<<endl; 185 string e_str=""; 186 getline(cin,e_str); 187 Encoding(HC,e_str); 188 // 译码:输入赫夫曼码序列,输出原始字符代码。 189 cout<<"\n请输入要解码的字符:"<<endl; 190 string d_str=""; 191 getline(cin,d_str); 192 Decoding(HC,d_str); 193 194 }
测试样例:
输入:
27
输入:
186 a 64 b 13 c 22 d 32 e 103 f 21 g 15 h 47 i 57 j 1 k 5 l 32 m 20 n 56 o 63 P 15 q 1 r 48 s 51 t 80 u 23 v 8 w 18 x 1 y 16 z 1View Code
输入:
you are bad gay but laolao is not
输入:
1000111001000011111010001001011110000010101011011110000110101000111111000000000111011111011110101001101111010100111101110011111011010011101
输出: