最近完成了数据结构课程设计，被分到的题目是《哈夫曼编码和解码》，现在在这篇博文里分享一下自己的成果。
我在设计时，在网上参考了很多老师和前辈的算法和代码，向他们表示感谢！他们的成果给了我很多启示和帮助。另外，自己的成品中也还有很多不完善的地方，欢迎批评指正。
课题：哈夫曼编码与解码 C++代码实现
（1）统计某电文中字符出现的频率（假设电文中只含有大小写英文字母，以及逗号和点号）；
（2）把字符出现的频率作为权值建立哈夫曼树，进行哈夫曼编码，并输出每个字符的编码结果；（3）对电文进行哈夫曼编码；（4）把电文的哈夫曼编码进行译码，输出对应电文的内容。
1 #include2 #include 3 #include 4 #include 5 #include 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 else102 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; //加上字符0185 }else //是右孩子186 HCD[i].code[len++] = '0'+1; //加上字符1187 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 }