Huffman tree and huffman encoding

// Huffman tree and huffman encoding

#include #include #include #include

#define overflow -1

TypedEf struct {char letter; int tent; int lchild; int rChild;} htnode, * huffmantree

Typedef char * * huffmancode;

Void SELECT (Huffmantree & HT, INT I, INT & S1, INT & S2) {/ * Select two trees in the forest, the root nodes, and the small number of times, * to record the subsidy of its root nodes into S1 and S2 * / int J, k; for (k = 1; k

For (j = 1; j

}

Void Huffmancoding (HuffmanTree & HT, Huffmancode & HC, CHAR * ZI, INT * W, INT N) {Huffmantree P;

INT M, I, S1, S2, F, C; Int iStart = 1; CHAR * CD; IF (n <= 1) Return; M = 2 * N-1; IF (! (ht = (ht = (ht = (ht = (ht = (ht =) Malloc (m 1) * sizeof (htnode)))))))))))) EXIT (OVERFLOW); for (p = HT 1, i = 1; i <= n; i, zi, p, w ) {/ * Generate independent forest * / p-> parent = NULL; P-> letter = * zi; p-> lchild = null; p-> rchild = null; p-> weight = * w;

For (; i <= m; i, p) {(* p) .weight = 0; (* p) .parent = 0; (* p) .lchild = 0; (* p) .rchild = 0;}

For (i = n 1; i <= m; i) {SELECT (HT, I-1, S1, S2); HT [S1] .Parent = i; HT [S2] .parent = i; HT [i] .lchild = S1; HT [i] .rchild = S2; HT [i] .weight = HT [S1] .weight HT [S2] .weight;} hc = (huffmancode) malloc ((n 1 * sizeof (char *)); cd = (char *) Malloc (N * sizeof (char)); / * Temporary Code storage * / CD [N-1] = '/ 0'; for (i = 1 i <= n; i) {iStart = n - 1; / * Press the generated Hafman tree to get the Hafman code * / for (c = i, f = HT [i] .parent; f! = 0; c = f, f = HT [f] .parent) IF (HT [f] .lchild == c) CD [- iStart] = '0'; Else CD [- iStart ] = '1'; HC [I] = (char *) Malloc ((n - iStart) * Sizeof (char)); strcpy (hc [i], & cd [iStart]);} free (CD);} void Main () {huffmantree ht; huffmancode hc; int I, j, yu; char zi [9] = {'a', 'b', 'c', 'd', 'e', ​​'f', 'g ',' H '}; int w [100]; char z; char C [100]; z =' a '; cout << Endl; for (i = 0; i <= 7; i ) {cout << "please input the weight" << z << ":"; cin >> w [i]; z ;} Huffmancoding (HT, HC, Zi, W, 8); cout << endl; cout << "char Weight huffmancode "<< Endl; for (i = 1; i <= 8; i ) cout << HT [i] .letter <<" << HT [i] .weight << "<< HC [i ] > c; cout << "The code is:"; for (i = 0; i

COUT << Endl; COUT << "Enter the code:"; cin >> C; j = strlen (c); yu = 15; i = 1; cout << "The text is:"; while (i <= j) {while (ht [] .lchild! = 0) / * Because it is a complete binary tree * / {if (C [i-1] ==0 ') {/ * uses hafman tree, will enter The current code (variable C is expressed) translated into text, description: Variable name C In program * / yU = HT [] .lchild; i ; continue;} if (c [i-1] == '1') { YU = HT [YU] .rchild; i ; contract;}} / * The character decoded by partial code is decoded, and the decoding of the following electric code * / cout << HT [] .letter; yu = 15;} cout << Endl;} // no error handling

Enter an example: please input the weight for a: 12 please input the weight for c: 23 Please Input The Weight for D: 23 please Input The Weight for E: 26 please input the weight for f: 267 please Input The Weight for G: 23 please Input The Weight for H: 67

char weight huffmancodeA 12 0001B 234 01C 6 0000D 23 1000E 26 001F 267 11G 23 1001H 67 101please input the text: ABCDEFGThe code is: 00010100001000001111001Enter the code: 00010100001000001111001The text is: ABCDEFGPress any key to continue