哈夫曼编解码（C语言）

示例

输入：

helllllllo

生成码表：

a:00010010

b:00010011

c:00010100

d:00010101

e:001

f:00010110

g:00010111

h:010

i:00011000

j:00011001

k:00011010

l:1

m:00011011

n:00011100

o:011

p:00011101

q:00011110

r:00011111

s:0000000

t:0000001

u:0000010

v:0000011

w:0000100

x:0000101

y:0000110

z:0000111

编码结果：

0100011111111011

解码结果：

helllllllo

代码实现

#include<stdio.h>#include<stdlib.h>#include<string.h>#define maxsize 1000 /* 编码函数中，被编译的字符串的最大长度 */#define max 1000 /* 最大字符的个数 */typedef struct {char data; /* 数据域 */int weight; /* 权值域 */int parent;int left;int right;} huffNode;typedef struct {char code[max]; // 存放哈夫曼编码int start;} huffCode;huffNode *initFrequency(int count[]) // 初始化带权结点{static huffNode ht[2 * max];ht[0].weight = 27; /* 字符个数 */ht[1].data = ' ';ht[1].weight = count[26]; // spacefor (int i = 1; i <= 27; i++) {ht[i].data = (char) ('a' + i - 1);ht[i].weight = count[i - 1];}return ht;}void buildTree(huffNode *ht) {/* m1为最小权值，x1为其在ht中的下标；m2为第二小权值，x2为其下标 */int i, k, x1, x2, n, m1, m2;n = ht[0].weight;for (i = 1; i <= 2 * n - 1; i++)ht[i].parent = ht[i].left = ht[i].right = 0; /* 对ht的parent，left，right域进行初始化 */for (i = n + 1; i <= 2 * n - 1; i++) {m1 = m2 = 10000; /* m1，m2初值无限大 */x1 = x2 = 0;/* x1, x2初值为0 */for (k = 1; k <= i - 1; k++) {/* k为可以进行比较的结点的下标 */if (ht[k].parent == 0) {/* 当前结点的父结点不存在时 */if (ht[k].weight < m1) /* 当前结点的权值比最小权值还小时 */{m2 = m1;x2 = x1;m1 = ht[k].weight;x1 = k;} else if (ht[k].weight < m2) {/* 当前结点的权值比最小权值大但比第二最小权值小时 */m2 = ht[k].weight;x2 = k;}}}ht[x1].parent = i;ht[x2].parent = i;ht[i].weight = ht[x1].weight + ht[x2].weight;ht[i].left = x1;ht[i].right = x2;}}huffCode *printHuffmanCode(huffNode *hNode) {static huffCode hCode[max];huffCode d;int i, n, c, f, k, x;n = hNode[0].weight;for (i = 1; i <= n; i++) {d.start = n + 1;c = i;f = hNode[i].parent;while (f != 0) {if (hNode[f].left == c) d.code[--d.start] = '0';else d.code[--d.start] = '1';c = f;f = hNode[f].parent;}hCode[i] = d;}printf("huffman code table:\n");for (i = 1; i <= n; i++) {printf("%c:", hNode[i].data);x = hCode[i].start;for (k = x; k <= n; k++) {printf("%c", hCode[i].code[k]);}printf("\n");}return hCode;}huffCode *encoding(huffCode *hCode, huffNode *hNode) {int i, j, n, m, k, x;char in[maxsize], out[2 * maxsize];int count[27] = {0};m = 0;printf("input a string:");getchar();gets(in);n = strlen(in);for (i = 0; i < n; i++) {if (in[i] >= 'a' && in[i] < 'z') {count[in[i] - 'a']++;}if (in[i] == ' ')count[26]++;if (in[i] == '0') break;}hNode = initFrequency(count);buildTree(hNode);hCode = printHuffmanCode(hNode);for (i = 0; i < n; i++) {for (j = 1; j <= hNode[0].weight; j++) {if (in[i] == hNode[j].data) {x = hCode[j].start;for (k = x; k <= hNode[0].weight; k++) {out[m++] = hCode[j].code[k];}}}}printf("\nThe encoding result is:\n");for (i = 0; i < m; i++) {printf("%c", out[i]);}return hNode;}void decoding(huffCode hcd[], huffNode ht[]) {int i, j, n, k, x, m, w;char in[maxsize * 2], out[maxsize];printf("\nenter huffman code:\n");scanf("%s", in);n = strlen(in);i = 0;m = 0;while (i < n) {for (j = 1; j <= ht[0].weight; j++) {x = hcd[j].start;for (k = x, w = i; k <= ht[0].weight; k++, w++) {if (in[w] != hcd[j].code[k]) {break;}}if (k > ht[0].weight) {out[m++] = ht[j].data;break;}}i = w;}for (i = 0; i < m; i++) {printf("%c", out[i]);}}int main() {int select;huffNode *hNode;huffCode *hCode;do {printf("\n\n");printf("--------------------------Menu-----------------------------\n");printf("1. input string\n");printf("2. input code\n");printf("-----------------------------------------------------------\n\n");printf("choose 1 or 2: ");scanf("%d", &select);if (select == 1) {hNode = encoding(hCode, hNode);} else if (select == 2) {hCode = printHuffmanCode(hNode);decoding(hCode, hNode);} else {printf("No such option. Exit.\n");exit(1);}} while (1);}