哈夫曼编码--c语言实现

本文主要是介绍哈夫曼编码--c语言实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

// 库函数
# include<stdio.h>
# include<string.h>
# include<stdlib.h>// 创建结构体
typedef struct {double weight; // 权重char s; // 字符int parent, lchild, rchild; // 定义父亲和左右孩子
}HTNode, *HuffmanTree;// 函数定义
void Select(HuffmanTree ht, int j, int *m1, int *m2); // 找出权重最小的两个数void CreatHuffmanTree(HuffmanTree ht, int n); // 构建哈夫曼树void HuffmanCoding(HuffmanTree ht, char **hc, int n); // 哈夫曼编码void printHuffmanCode(HuffmanTree ht, char **hc, int index); // 打印哈夫曼编码void printEachCharacterCode(HuffmanTree ht, char **hc, int n);void HuffmanDecoding(HuffmanTree ht, int n, char *pwd); // 在生成的哈夫曼树中查询目标// 找出最小的两个数
void Select(HuffmanTree ht, int x, int *m1, int *m2) {double min1 = 999999;double min2 = 999999;int j;for(j = 1; j <= x; j++) {if(ht[j].weight < min1 && ht[j].parent == 0) {min1 = ht[j].weight;*m1 = j;}}int k;for(k = 1; k <= x; k++) {if(ht[k].weight < min2 && ht[k].parent == 0 && k != *m1) {min2 = ht[k].weight;*m2 = k;}}
}// 构造哈夫曼树, n 为用户主函数输入的字符个数
void CreatHuffmanTree(HuffmanTree ht, int n) {int i;for(i = n+1; i <= 2*n-1; i ++) {int m1, m2;Select(ht, i-1, &m1, &m2);// 从 n+1 开始创建新的根ht[i].weight = ht[m1].weight + ht[m2].weight;ht[i].lchild = m1;ht[i].rchild = m2;ht[i].parent = 0;ht[m1].parent = i;ht[m2].parent = i;}
}// 哈夫曼编码
void HuffmanCoding(HuffmanTree ht, char **hc, int n) {char *cd = (char*)malloc(n*sizeof(char)); // cd临时存放编码cd[n-1] = '\0';int now = 1;int p = 0;int start;int i = 0;while (i < n) {start = n-1;now = i+1;p = ht[now].parent;while (p != 0) {start--;if (ht[p].lchild == now) {cd[start] = '0';}else {cd[start] = '1';}now = p;p = ht[now].parent;}hc[i+1] = (char*)malloc((n-start)*sizeof(char));strcpy(hc[i+1], &cd[start]);i++;}
}// 先序打印
void printHuffmanCode(HuffmanTree ht, char **hc, int index) {// 递归输出先序序列if(ht[index].lchild == 0 && ht[index].rchild == 0) {printf("%c:%s\n", ht[index].s, hc[index]);return ;}printHuffmanCode(ht, hc, ht[index].lchild);printHuffmanCode(ht, hc, ht[index].rchild);
}// 生成哈夫曼树的目标
void HuffmanDecoding(HuffmanTree ht, int n, char *pwd) {printf("翻译结果:");int len = strlen(pwd); // 获取编码长度int i = 0;int node = 2*n-1;while (i < len) {if(pwd[i] == '0') {node = ht[node].lchild;i++;if(ht[node].lchild == 0 && ht[node].rchild == 0) {printf("%c", ht[node].s);node = 2*n-1;}}if(pwd[i] == '1') {node = ht[node].rchild;i++;if(ht[node].lchild == 0 && ht[node].rchild == 0) {printf("%c", ht[node].s);node = 2*n-1;}}}
}// 打印每个字符的哈夫曼编码
void printEachCharacterCode(HuffmanTree ht, char **hc, int n) {int i;for(i = 1; i <= n; i++) {if (ht[i].lchild == 0 && ht[i].rchild == 0) {printf("%c:%s\n", ht[i].s, hc[i]);}}
}int main() {printf("请输入要输入的字符数w：");int n;scanf("%d", &n);HuffmanTree ht = malloc((2 * n) * sizeof(HTNode));getchar();char *hc[n+1];// 初始化int i;for (i = 1; i <= n; i++) {printf("输入第%d个元素和它权重：", i);scanf("%c%lf", &ht[i].s, &ht[i].weight);getchar();ht[i].lchild = 0;ht[i].rchild = 0;ht[i].parent = 0;}// 创建二叉树CreatHuffmanTree(ht, n);// 编码HuffmanCoding(ht, hc, n);printf("打印哈夫曼编码\n");printEachCharacterCode(ht, hc, n);printf("递归打印哈夫曼编码\n");printHuffmanCode(ht, hc, 2*n-1);char pwd[9999];printf("输入正确编码：");scanf("%s", pwd);//译码HuffmanDecoding(ht,n,pwd);return 0;
}

输出结果：