`` Huffman tree is a special application of binary tree , Huffman tree is still a binary tree , Only it meets certain conditions （ Weighted shortest path binary tree ）
1- Find the probability of letters in string
Here, we try to get each letter and its number of times in a string composed of English letters
requirement analysis ：1, Enter a string from the keyboard
2, Statistics the frequency of characters in the string
3, According to frequency statistics , Complete the Huffman tree
4, According to the Huffman tree, the Huffman code of each character is obtained
5, Each character in the original string , The corresponding Huffman code replacement , Get the results
6, Restore the result to the original string
Here we first implement the simplest method to calculate the frequency of each character in the string
In this way, the frequency analysis of characters in the string is completed , Add the display function to complete this function
2- Initialize and create a Huffman tree
3- Carry on the preliminary Huffman coding
After obtaining the frequency of each character in a string and generating its corresponding Huffman tree , Next, code , That is, each character is converted into its corresponding Huffman code , Get one from 1 and 0 String composed of , there 1 and 0 Replace it with a byte first , This is also a method of encryption
Because of the addition of new content , The contents of initializing and displaying the Huffman table also need to be changed
Modified showhufftree Add a new print value , Namely code
The next step is to display the result of the encoding , Converts a string to a 1 0 String composed of , Each character corresponds to several characters 1 0
Add a function to destroy
4- Preliminary Huffman decoding
This completes the encoding and decoding of a string
#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(" The characters and their frequency are as follows \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", " subscript ",
" character ", " Frequency ", " Left child ", " Right child ", " visit ", " code "); 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 ? " nothing " : 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(" For Strings [%s] The encoding result is :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(" The decoding result is ：\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(
" Please enter a string \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(" character string [%s] The result of encoding is ：\n %s\n", str, res); encodding(res,
hufTab, alphaCount); free(freq); destoryHuffmanTable(hufTab, alphaCount); free(
res); return 0; }
Technology
Daily Recommendation