首页 > > 程序设计 > C/C++ >

哈夫曼编码与解码的C++实现：建立哈夫曼树、进行…

2018-06-17 21:27:45来源：未知阅读 ()

　　最近完成了数据结构课程设计，被分到的题目是《哈夫曼编码和解码》，现在在这篇博文里分享一下自己的成果。

　　我在设计时，在网上参考了很多老师和前辈的算法和代码，向他们表示感谢！他们的成果给了我很多启示和帮助。另外，自己的成品中也还有很多不完善的地方，欢迎批评指正。

课题：哈夫曼编码与解码 C++代码实现

（1）统计某电文中字符出现的频率（假设电文中只含有大小写英文字母，以及逗号和点号）；
（2）把字符出现的频率作为权值建立哈夫曼树，进行哈夫曼编码，并输出每个字符的编码结果；
（3）对电文进行哈夫曼编码；
（4）把电文的哈夫曼编码进行译码，输出对应电文的内容。

  1 #include <stdlib.h>
  2 #include <stdio.h>
  3 #include <malloc.h>
  4 #include <string.h>
  5 #include <ctype.h>
  6 #define MAX 999999 //一个极大值
  7 #define NUM 10
  8 
  9 //存储哈夫曼树每个结点
 10 typedef struct Node {
 11     char ch;
 12     int weight; //权值
 13     int parent;
 14     int lchild,rchild;
 15 }HFNode;
 16 //存储每个字符及其哈夫曼编码
 17 typedef struct {
 18     char ch;
 19     char code[NUM];
 20 }HFCharCode;
 21 
 22 HFNode HT[28*2-1]; //哈夫曼树结构体
 23 HFCharCode HCD[28]; //哈夫曼编码结构体
 24 int LeafNum; //叶子结点数
 25 int NodeNum; //所有结点数
 26 char EnterStr[MAX]; //输入的待编码电文
 27 char EnterCode[MAX]; //输入的待解码密文
 28 char RealStr[MAX]; //密文解码后的电文
 29 int AllWeight[28]; //存储所有28个字符的权值
 30 
 31 void Statistics();
 32 void CreateHFTree();
 33     void SelectMin(int &min1, int &min2);
 34 void CreateHFCode();
 35     void ReverseStr(char *str);
 36 void EncodeStr();
 37 void DecodeHFCode();
 38 
 39 int main() {
 40     printf("****** 哈夫曼编码与解码 ******\n\n");
 41     printf("*** 输入一串字符串 ***\n");
 42     scanf("%s", EnterStr);
 43     getchar();
 44     Statistics();
 45     CreateHFTree();
 46     CreateHFCode();
 47     EncodeStr();
 48     printf("\n*** 输入想解码的内容 ***\n");
 49     scanf("%s", EnterCode);
 50     getchar();
 51     DecodeHFCode();
 52     return 0;
 53 }
 54 
 55 //统计每个字符权值
 56 void Statistics() {
 57     int len = strlen(EnterStr);
 58     for(int i = 0; i <= 27; i++)
 59         AllWeight[i] = 0;
 60     for(int j = 0; j <= len - 1; j++) {
 61         if(isalpha(EnterStr[j])) {
 62             EnterStr[j] = tolower(EnterStr[j]);
 63             AllWeight[EnterStr[j]-'a']++;
 64         }
 65         else if((int)EnterStr[j] == 44)
 66             AllWeight[26]++;
 67         else if((int)EnterStr[j] == 46)
 68             AllWeight[27]++;
 69         else {
 70             printf("\n输入不符合要求!\n\n");
 71             exit(-1);
 72         }
 73     }
 74     int i = 0, j = 0;
 75     for( ; i <= 25; i++) {
 76         if(AllWeight[i] != 0) {
 77                 HT[j].weight  = AllWeight[i];
 78                 HT[j].ch = i+'a';
 79                 j++;
 80         }
 81     }
 82     if(AllWeight[i] != 0) {
 83             HT[j].weight = AllWeight[i];
 84             HT[j].ch = ',';
 85             j++;
 86             i++;
 87     }
 88     if(AllWeight[i] != 0) {
 89             HT[j].weight = AllWeight[i];
 90             HT[j].ch = '.';
 91     }
 92     printf("\n*** 打印每个字符的权值 ***\n");
 93     int n = 0;
 94     for(int i = 0; i <= 27; i++) {
 95         if(AllWeight[i] != 0) {
 96             n++;
 97             if(i <= 25)
 98                 putchar('a'+i);
 99             else if(i == 26)
100                 printf(",");
101             else
102                 printf(".");
103             printf(": %d\n", AllWeight[i]);
104         }
105     }
106     LeafNum = n;
107     NodeNum = 2*LeafNum-1;
108 }
109 
110 //构造哈夫曼树
111 void CreateHFTree() {
112     int i;
113     for(i = 0; i <= LeafNum-1; i++) {
114         HT[i].parent = -1;
115         HT[i].lchild = -1;
116         HT[i].rchild = -1;
117         HT[i].weight = HT[i].weight;
118     }
119     for(; i <= NodeNum-1; i++) {
120         HT[i].parent = -1;
121         HT[i].lchild = -1;
122         HT[i].rchild = -1;
123         HT[i].weight = MAX;
124     }
125     int min1, min2;
126     for(i = LeafNum; i <= NodeNum-1; i++) {
127         SelectMin(min1, min2);
128         HT[min1].parent = i;
129         HT[min2].parent = i;
130         HT[i].lchild = min1;
131         HT[i].rchild = min2;
132         HT[i].weight = HT[min1].weight + HT[min2].weight;
133     }
134     // printf("\n*** 打印哈夫曼树 ***\n");
135     // for(int i = 0; i <= NodeNum-1; i++) {
136     //     printf("序号:%d 字符:%c 权值:%d 双亲:%d 左孩:%d 右孩:%d\n", i, HT[i].ch, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
137     // }
138 }
139     //找到两个权值最小的二叉树的序号
140     void SelectMin(int &min1, int &min2) {
141         int i = 0;
142         int temp;
143         int wetmin1, wetmin2;
144         while(HT[i].parent != -1) 
145             i++;
146         wetmin1 = HT[i].weight;
147         min1 = i;
148         i++;
149         while(HT[i].parent != -1) 
150             i++;
151         wetmin2 = HT[i].weight;
152         min2 = i;
153         i++;
154         if(wetmin1 > wetmin2) {
155             temp = wetmin2;
156             wetmin2 = wetmin1;
157             wetmin1 = temp;
158             temp = min2;
159             min2 = min1;
160             min1 = temp;
161         }
162         for(; i <= NodeNum-1; i++) {
163             if(HT[i].weight < wetmin1 && HT[i].parent == -1) {
164                 wetmin2 = wetmin1;
165                 wetmin1 = HT[i].weight;
166                 min2 = min1;
167                 min1 = i;
168             } else if(HT[i].weight < wetmin2 && HT[i].parent == -1) {
169                 wetmin2 = HT[i].weight;
170                 min2 = i;
171             }
172         }
173     }
174 
175 //进行哈夫曼编码
176 void CreateHFCode() {
177     int i, j, len; 
178     for(i = 0; i <= LeafNum-1; i++) {  
179         len = 0;  
180         j = i;
181         HCD[i].ch = HT[j].ch;
182         while(HT[j].parent != -1) {  //不是根节点
183             if(HT[HT[j].parent].lchild == j) {  //是双亲结点的左孩子
184                 HCD[i].code[len++] = '0'+0;  //加上字符0
185             }else  //是右孩子
186                 HCD[i].code[len++] = '0'+1;  //加上字符1
187             j = HT[j].parent;  //往上遍历
188         }
189         HCD[i].code[len] = '\0'; //字符串末尾 
190         ReverseStr(HCD[i].code); 
191     }
192     printf("\n*** 打印每个字符的编码 ***\n");
193     for(int i = 0; i <= LeafNum-1; i++)
194         printf("%c: %s\n", HT[i].ch, HCD[i].code);
195 }
196     //将一个字符串反转  
197     void ReverseStr(char *str) {  
198         int i, j;  
199         char c;  
200         for(i = 0, j = strlen(str)-1; i < j; i++, j--) {  
201             c = str[i];  
202             str[i] = str[j];  
203             str[j] = c;  
204         }
205     }
206 
207 //哈夫曼编码
208 void EncodeStr() {
209     int len = strlen(EnterStr);
210     printf("\n*** 编码结果 ***\n");
211     for(int i = 0; i <= len-1; i++) {
212         for(int j = 0; j <= LeafNum-1; j++) {
213             if(EnterStr[i] == HCD[j].ch)
214                 printf("%s", HCD[j].code);
215         }
216     }
217     printf("\n");
218 }
219 
220 //哈夫曼解码
221 void DecodeHFCode() {
222     int k = NodeNum-1; //根结点序号, 开始时一定在最后一个
223     int len = 0, i = 0;  
224     while(EnterCode[i]) {  
225         if(EnterCode[i] == '0'+0)  
226             k = HT[k].lchild;  
227         else if(EnterCode[i] == '0'+1)  
228             k = HT[k].rchild;  
229         else {
230             printf("\n错误! 密文中仅能含有1和0!\n\n");
231             exit(-1);
232         }  
233         if(HT[k].lchild == -1 && HT[k].rchild == -1) {  
234             RealStr[len++] = HT[k].ch;
235             k = NodeNum-1;
236         }  
237         i++;  
238     }
239     RealStr[len] = '\0';
240     if(k == NodeNum-1) {     
241         printf("\n*** 解码结果 ***\n%s\n\n", RealStr);
242         exit(0);
243     }
244     printf("\n错误! 部分密文无法解密!\n\n");
245     exit(-1);  
246 }