【哈夫曼树的应用】根据报文创建哈夫曼编码

要传输一则报文内容如下：

“AAAAAAAAAAAAAAABBBBBBBBBCCCCCCCCDDDDDDDDDDDDEEEEEEEEEEFFFFF”

请为这段报文设计哈夫曼编码，并输出每个字符的哈夫曼编码。

思路：将问题分解为四个功能函数，逐个解决

#include <stdio.h> #include <string.h> #include <malloc.h> #define MAXLEAF 50 #define MAXNODE MAXLEAF*2-1 typedef struct Node{ char node; int bits[MAXLEAF]; int weight; int parent, lchild, rchild; }HTNode; HTNode ht[MAXNODE]; //输入字符串 void InputString(char s[]) { printf("/*\n\t若想输入测试样例，则输入“1 ”\n"); printf("\t测试样例为题目要求：AAAAAAAAAAAAAAABBBBBBBBBCCCCCCCCDDDDDDDDDDDDEEEEEEEEEEFFFFF\n/*\n\n\n\n"); printf("请输入报文："); scanf("%s",s); if(strcmp(s,"1") == 0) { strcpy(s,"AAAAAAAAAAAAAAABBBBBBBBBCCCCCCCCDDDDDDDDDDDDEEEEEEEEEEFFFFF"); } } //获取权重 void GetWeight(char s[], int &n) { int i, j; for(i = 0;i < strlen(s);i++) { if(i == 0) { HTNode ht1; ht1.node = s[i]; ht1.weight = 1; ht1.lchild = -1; ht1.rchild = -1; ht1.parent = 0; ht[n++] = ht1; } else { for(j = 0;j < n;j++) { if(s[i] == ht[j].node) { ht[j].weight++; break; } } if(j == n) { HTNode ht1; ht1.node = s[i]; ht1.weight = 1; ht1.lchild = -1; ht1.rchild = -1; ht1.parent = 0; ht[n++] = ht1; } } } //打印出现次数 printf("\n出现次数为：\n"); for(j = 0;j < n;j++) { printf("%c -> %d\n",ht[j].node,ht[j].weight); } } //构造哈夫曼树 void CreatHuffmanTree(char s[], int &n) { int i, m = n; int min1, min1_weight; int min2, min2_weight; while(m < 2*n-1) { min1_weight = strlen(s); min2_weight = strlen(s); for(i = 0;i < m;i++) { if(ht[i].parent==0 && min1_weight > ht[i].weight) { min1_weight = ht[i].weight; min1 = i; } } for(i = 0;i < m;i++) { if(ht[i].parent==0 && min2_weight > ht[i].weight && i!=min1) { min2_weight = ht[i].weight; min2 = i; } } ht[m].parent = 0; ht[m].lchild = min1; ht[m].rchild = min2; ht[m].weight = min1_weight+min2_weight; ht[min1].parent = min1_weight + min2_weight; ht[min2].parent = min1_weight + min2_weight; m++; } n = m; } //打印编码 void Print(int n) { int i, pos, j; int a = 1; printf("\n该报文的哈夫曼编码为：\n"); for(i = 0;i < (n+1)/2;i++) { pos = i; a = 1; while(ht[pos].parent!=0) { if(ht[pos].weight < ht[pos].parent-ht[pos].weight) { ht[i].bits[a++] = 0; } else if(ht[pos].weight == ht[pos].parent-ht[pos].weight) { for(j = 0;j < n;j++) { if(ht[pos].parent==ht[j].weight && (ht[j].lchild==pos||ht[j].rchild==pos)) break; } if(pos == ht[j].lchild) ht[i].bits[a++] = 0; else ht[i].bits[a++] = 1; } else ht[i].bits[a++] = 1; for(j = 0;j < n;j++) { if(ht[pos].parent==ht[j].weight && (ht[j].lchild==pos||ht[j].rchild==pos)) { pos = j; break; } } } ht[i].bits[0] = a; } for(i = 0;i < (n+1)/2;i++) { int j; printf("%c -> ",ht[i].node); //从根结点到叶节点创建哈夫曼编码 for(j = ht[i].bits[0]-1;j > 0;j--) { printf("%d ",ht[i].bits[j]); } printf("\n"); } } //主函数 int main() { int n = 0; char s[MAXNODE]; InputString(s);//输入字符串 GetWeight(s,n);//获取权值 CreatHuffmanTree(s,n);//创建哈夫曼树 Print(n);//打印 }

运行结果截图： 其实一开始的样例很容易做，但随便输了一串aabbccdd之后发现有重复的数字，所以就花了时间来改进，啊继续写报告了（疯狂嚎叫）