哈夫曼編解碼（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

編碼結(jié)果：
0100011111111011

解碼結(jié)果：
helllllllo

代碼實(shí)現(xiàn)

#include<stdio.h> #include<stdlib.h> #include<string.h>#define maxsize 1000 /* 編碼函數(shù)中，被編譯的字符串的最大長度 */ #define max 1000 /* 最大字符的個(gè)數(shù) */typedef struct {char data; /* 數(shù)據(jù)域 */int weight; /* 權(quán)值域 */int parent;int left;int right; } huffNode;typedef struct {char code[max]; // 存放哈夫曼編碼int start; } huffCode;huffNode *initFrequency(int count[]) // 初始化帶權(quán)結(jié)點(diǎn) {static huffNode ht[2 * max];ht[0].weight = 27; /* 字符個(gè)數(shù) */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為最小權(quán)值，x1為其在ht中的下標(biāo)；m2為第二小權(quán)值，x2為其下標(biāo) */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; /* 對(duì)ht的parent，left，right域進(jìn)行初始化 */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為可以進(jìn)行比較的結(jié)點(diǎn)的下標(biāo) */if (ht[k].parent == 0) { /* 當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)不存在時(shí) */if (ht[k].weight < m1) /* 當(dāng)前結(jié)點(diǎn)的權(quán)值比最小權(quán)值還小時(shí) */{m2 = m1;x2 = x1;m1 = ht[k].weight;x1 = k;} else if (ht[k].weight < m2) { /* 當(dāng)前結(jié)點(diǎn)的權(quán)值比最小權(quán)值大但比第二最小權(quán)值小時(shí) */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); }

總結(jié)

以上是生活随笔為你收集整理的哈夫曼编解码（C语言）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。