最近完成了数据结构课程设计，被分到的题目是《哈夫曼编码和解码》，现在在这篇博文里分享一下自己的成果。
我在设计时，在网上参考了很多老师和前辈的算法和代码，向他们表示感谢！他们的成果给了我很多启示和帮助。另外，自己的成品中也还有很多不完善的地方，欢迎批评指正。
课题：哈夫曼编码与解码 C++代码实现
（1）统计某电文中字符出现的频率（假设电文中只含有大小写英文字母，以及逗号和点号）；
（2）把字符出现的频率作为权值建立哈夫曼树，进行哈夫曼编码，并输出每个字符的编码结果；
（3）对电文进行哈夫曼编码；
（4）把电文的哈夫曼编码进行译码，输出对应电文的内容。
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <ctype.h>
#define MAX 999999 //一个极大值
#define NUM 10 //存储哈夫曼树每个结点
typedef struct Node {
char ch;
int weight; //权值
int parent;
int lchild,rchild;
}HFNode;
//存储每个字符及其哈夫曼编码
typedef struct {
char ch;
char code[NUM];
}HFCharCode; HFNode HT[*-]; //哈夫曼树结构体
HFCharCode HCD[]; //哈夫曼编码结构体
int LeafNum; //叶子结点数
int NodeNum; //所有结点数
char EnterStr[MAX]; //输入的待编码电文
char EnterCode[MAX]; //输入的待解码密文
char RealStr[MAX]; //密文解码后的电文
int AllWeight[]; //存储所有28个字符的权值 void Statistics();
void CreateHFTree();
void SelectMin(int &min1, int &min2);
void CreateHFCode();
void ReverseStr(char *str);
void EncodeStr();
void DecodeHFCode(); int main() {
printf("****** 哈夫曼编码与解码 ******\n\n");
printf("*** 输入一串字符串 ***\n");
scanf("%s", EnterStr);
getchar();
Statistics();
CreateHFTree();
CreateHFCode();
EncodeStr();
printf("\n*** 输入想解码的内容 ***\n");
scanf("%s", EnterCode);
getchar();
DecodeHFCode();
return ;
} //统计每个字符权值
void Statistics() {
int len = strlen(EnterStr);
for(int i = ; i <= ; i++)
AllWeight[i] = ;
for(int j = ; j <= len - ; j++) {
if(isalpha(EnterStr[j])) {
EnterStr[j] = tolower(EnterStr[j]);
AllWeight[EnterStr[j]-'a']++;
}
else if((int)EnterStr[j] == )
AllWeight[]++;
else if((int)EnterStr[j] == )
AllWeight[]++;
else {
printf("\n输入不符合要求!\n\n");
exit(-);
}
}
int i = , j = ;
for( ; i <= ; i++) {
if(AllWeight[i] != ) {
HT[j].weight = AllWeight[i];
HT[j].ch = i+'a';
j++;
}
}
if(AllWeight[i] != ) {
HT[j].weight = AllWeight[i];
HT[j].ch = ',';
j++;
i++;
}
if(AllWeight[i] != ) {
HT[j].weight = AllWeight[i];
HT[j].ch = '.';
}
printf("\n*** 打印每个字符的权值 ***\n");
int n = ;
for(int i = ; i <= ; i++) {
if(AllWeight[i] != ) {
n++;
if(i <= )
putchar('a'+i);
else if(i == )
printf(",");
else
printf(".");
printf(": %d\n", AllWeight[i]);
}
}
LeafNum = n;
NodeNum = *LeafNum-;
} //构造哈夫曼树
void CreateHFTree() {
int i;
for(i = ; i <= LeafNum-; i++) {
HT[i].parent = -;
HT[i].lchild = -;
HT[i].rchild = -;
HT[i].weight = HT[i].weight;
}
for(; i <= NodeNum-; i++) {
HT[i].parent = -;
HT[i].lchild = -;
HT[i].rchild = -;
HT[i].weight = MAX;
}
int min1, min2;
for(i = LeafNum; i <= NodeNum-; i++) {
SelectMin(min1, min2);
HT[min1].parent = i;
HT[min2].parent = i;
HT[i].lchild = min1;
HT[i].rchild = min2;
HT[i].weight = HT[min1].weight + HT[min2].weight;
}
// printf("\n*** 打印哈夫曼树 ***\n");
// for(int i = 0; i <= NodeNum-1; i++) {
// printf("序号:%d 字符:%c 权值:%d 双亲:%d 左孩:%d 右孩:%d\n", i, HT[i].ch, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
// }
}
//找到两个权值最小的二叉树的序号
void SelectMin(int &min1, int &min2) {
int i = ;
int temp;
int wetmin1, wetmin2;
while(HT[i].parent != -)
i++;
wetmin1 = HT[i].weight;
min1 = i;
i++;
while(HT[i].parent != -)
i++;
wetmin2 = HT[i].weight;
min2 = i;
i++;
if(wetmin1 > wetmin2) {
temp = wetmin2;
wetmin2 = wetmin1;
wetmin1 = temp;
temp = min2;
min2 = min1;
min1 = temp;
}
for(; i <= NodeNum-; i++) {
if(HT[i].weight < wetmin1 && HT[i].parent == -) {
wetmin2 = wetmin1;
wetmin1 = HT[i].weight;
min2 = min1;
min1 = i;
} else if(HT[i].weight < wetmin2 && HT[i].parent == -) {
wetmin2 = HT[i].weight;
min2 = i;
}
}
} //进行哈夫曼编码
void CreateHFCode() {
int i, j, len;
for(i = ; i <= LeafNum-; i++) {
len = ;
j = i;
HCD[i].ch = HT[j].ch;
while(HT[j].parent != -) { //不是根节点
if(HT[HT[j].parent].lchild == j) { //是双亲结点的左孩子
HCD[i].code[len++] = ''+; //加上字符0
}else //是右孩子
HCD[i].code[len++] = ''+; //加上字符1
j = HT[j].parent; //往上遍历
}
HCD[i].code[len] = '\0'; //字符串末尾
ReverseStr(HCD[i].code);
}
printf("\n*** 打印每个字符的编码 ***\n");
for(int i = ; i <= LeafNum-; i++)
printf("%c: %s\n", HT[i].ch, HCD[i].code);
}
//将一个字符串反转
void ReverseStr(char *str) {
int i, j;
char c;
for(i = , j = strlen(str)-; i < j; i++, j--) {
c = str[i];
str[i] = str[j];
str[j] = c;
}
} //哈夫曼编码
void EncodeStr() {
int len = strlen(EnterStr);
printf("\n*** 编码结果 ***\n");
for(int i = ; i <= len-; i++) {
for(int j = ; j <= LeafNum-; j++) {
if(EnterStr[i] == HCD[j].ch)
printf("%s", HCD[j].code);
}
}
printf("\n");
} //哈夫曼解码
void DecodeHFCode() {
int k = NodeNum-; //根结点序号, 开始时一定在最后一个
int len = , i = ;
while(EnterCode[i]) {
if(EnterCode[i] == ''+)
k = HT[k].lchild;
else if(EnterCode[i] == ''+)
k = HT[k].rchild;
else {
printf("\n错误! 密文中仅能含有1和0!\n\n");
exit(-);
}
if(HT[k].lchild == - && HT[k].rchild == -) {
RealStr[len++] = HT[k].ch;
k = NodeNum-;
}
i++;
}
RealStr[len] = '\0';
if(k == NodeNum-) {
printf("\n*** 解码结果 ***\n%s\n\n", RealStr);
exit();
}
printf("\n错误! 部分密文无法解密!\n\n");
exit(-);
}