``哈夫曼树是二叉树的一种特别应用，哈夫曼树仍然是一颗二叉树，只是其满足一定条件（带权最短路径二叉树）

1-求字符串中字母出现概率

2，对该字符串中出现的字符进行频度统计
3，根据频度统计，完成哈夫曼树
4，根据哈夫曼树得到每一个字符的哈夫曼编码
5，将原字符串中的每一个字符，与其相对应的哈夫曼编码代替，得到结果
6，将结果还原成原字符串

2-初始化并创建一棵哈夫曼树

3-进行初步的哈夫曼编码

4-初步的哈夫曼解码

#include <stdio.h> #include <malloc.h> #include <string.h> #include "mec.h" #
include "huffman.h" FREQ *getFreq(const char *str, int *count); FREQ *getFreq(
const char *str, int *count) { FREQ *result = NULL; int alpha[256] = {0}; int
index; int alphaCount = 0; int i = 0; for(index = 0; str[index]; index++) { ++
alpha[str[index]]; } for(index = 0; index < 256; index++) { if(alpha[index] > 0)
{ alphaCount++; } } *count = alphaCount; result = (FREQ *)calloc(sizeof(FREQ),
alphaCount); for(index = 0; index < 256; index++) { if(alpha[index] > 0) {
result[i].ch = index; result[i++].freq = alpha[index]; } } return result; } void
showFreq(const FREQ *freq, int count); void showFreq(const FREQ *freq, int count
) { int i; printf("字符及其频度如下\n"); for(i = 0; i < count; i++) { printf("%c %d\n",
freq[i].ch, freq[i].freq); } } HUFFMAN *initHuffmanTable(const FREQ *freq, const
int count, int *hufIndex); HUFFMAN *initHuffmanTable(const FREQ *freq, const int
count, int *hufIndex) { HUFFMAN *hufTab = NULL; int index; hufTab = (HUFFMAN *)
calloc(sizeof(HUFFMAN), 2*count - 1); for(index = 0; index < count; index++) {
hufTab[index].freq = freq[index]; hufTab[index].left = freq[index].right = -1;
hufTab[index].visited = FALSE; hufTab[index].code = (char *)calloc(sizeof(char),
count); hufIndex[freq[index].ch] = index; } return hufTab; } void showHuffTree(
const HUFFMAN *huf, const int count); void showHuffTree(const HUFFMAN *huf,
const int count) { int i; int ch; printf("%-5s%-5c%-5d%-7d%-7d%-5s%s\n", "下标",
"字符", "频度", "左孩子", "右孩子", "访问", "编码"); for (i = 0; i < 2*count - 1; i++) { ch =
huf[i].freq.ch; printf("%-5d%-5c%-5d%-7d%-7d%-5s%s\n", i, ch == 0 ? '#' : ch,
huf[i].freq.freq, huf[i].left, huf[i].right, huf[i].visited ? "√" ："×", huf[i].
code== NULL ? "无" : huf[i].code); } void findMIn(HUFFMAN *huf, int count); void
findMin(HUFFMAN *huf, int count) { int minIndex = -1; int index; for(index = 0;
index< count; index ++) { if(FALSE == huf[index].visited && (minIndex == -1 ||
huf[index].freq.freq < huf[minIndex].freq.freq)) { minIndex = index; } } huf[
minIndex].visited = TRUE; return minIndex; } void makeHuffmanTable(HUFFMAN *huf,
int count); void makeHuffmanTable(HUFFMAN *huf, int count) { int left; int right
; int i; for(i = 0; i < count - 1; i++) { left = findMin(huf, count + i); right
= findMin(huf, count + i); huf[count + i].freq.ch = '#'; huf[count + i].freq.
freq= huf[left].freq.freq +huf[right].freq.freq; huf[count + i].left = left; huf
[count + i].right = right; huf[count + i].visited = FALSE } } void
destoryHuffmanTable(HUFFMAN *huf, int count); void destoryHuffmanTable(HUFFMAN *
huf, int count) { int i; for(i = 0; i < count; i++) { free(huf[i].code); } free(
huf); } void makeHuffmanCode(HUFFMAN *huf, int root, char *code, int index);
void makeHuffmanCode(HUFFMAN *huf, int root, char *code, int index) { if(-1 ==
huf[root].left) { code[index] = 0; strcpy(huf[root].root, code); return; } code[
index] = '0'; makeHuffmanCode(huf, huf[root].left, code, index+1); code[index] =
'1'; makeHuffmanCode(huf, huf[root].right, code, index+1); } int getBitsCount(
HUFFMAN*huf, int count) { int cnt; int i; for(i = 0; i < count; i++) { cnt +=
strlen(huf[i].code) * huf[i].freq.freq; } return cnt; } char *codding(const char
*str, HUFFMAN *huf, int count, int *hufIndex) { int index; int i; char *result =
NULL; result = (char *)calloc(sizeof(char), getBitsCount(huf, count) + 1);
printf("对字符串[%s]编码结果为:n", str); for(index = 0; str[index]; index++) { strcat(
result, huf[hufIndex[str[index]]].code); } return result; } void encodding(const
char *code, HUFFMAN *huf, int count) { int index = 0; int root = 2 * (count - 1)
; int bitCount; printf("解码结果为：\n"); bitCount = getBitsCount(huf, count); while(
index<= bitCount) { if(-1 == huf[root].left) { printf("%c", huf[root].freq.ch);
root= 2 * (count - 1) { break; } continue; } root = '1' == code[index] ? huf[
root].right : huf[root].left; index++; } printf("\n"); } int main(int argc, char
const *argv[]) { FREQ *freq = NULL; HUFFMAN *hufTab = NULL; char str[80]; int
alphaCount; char code[256] = {0}; int hufIndex[256] = {0}; char *res; printf(
"请输入一个字符串\n"); gets(str); freq = getFreq(str, &alphaCount); showFreq(freq,
alphaCount); hufTab = initHuffmanTable(freq, alphaCount, hufIndex);
makeHuffmanTable(hufTab, alphaCount); makeHuffmanCode(hufTab, 2*(alphaCount - 1)
, code, 0); showHuffTree(hufTab, alphaCount); res = codding(str, hufTab,
alphaCount, hufIndex); printf("字符串[%s]的编码结果为：\n %s\n", str, res); encodding(res,
hufTab, alphaCount); free(freq); destoryHuffmanTable(hufTab, alphaCount); free(
res); return 0; }

GitHub

Gitee