Hawwmanzi

Huffmann binary tree source code:

A string is given, and the character is encoded according to the frequency displayed in each character in the statistical string, then the original string is encoded, and the encoded content is output.

--data structure

#include

#define max_node 1024

#define max_weight 4096

Typedef struct haffmantreenode {

CHAR CH, CODE [15];

Int weight;

INT PARENT, LCHILD, RCHILD;

} Htnode, * hatree;

Typedef struct {

HTNode Arr [MAX_NODE];

Int total

} Htree;

/ * Frequency of statistical characters * /

INT statistic_char (char * text, htree * t) {

INT I, J;

Int text_len = strlen (text);

T-> Total = 0;

For (i = 0; i

For (j = 0; j total; j ) IF (t-> arr [j] .ch == text [i]) {

T-> Arr [J] .weight ;

Break;

}

IF (j == t-> Total) {

T-> Arr [T-> Total] .CH = text [i];

T-> Arr [T-> Total] .weight = 1;

T-> Total ;

}

}

Printf ("Char Frequence / N");

For (i = 0; i Total; i )

Printf ("'% c'% d / n", t-> arr [i] .ch, t-> arr [i] .weight);

Printf ("/ n");

Return T-> Total

}

INT CREATE_HTREE (HTREE * T)

{

INT I;

INT TOTAL_NODE = T-> Total * 2 - 1;

INT min1, min2; / * Minimum two nodes * /

INT min1_i, min2_i; / * The minimum node corresponding to the number * /

INT Leaves = T-> Total

For (i = 0; i

T-> Arr [i] .parent = -1;

T-> Arr [i] .rchild = -1;

T-> Arr [i] .lchild = -1;

}

While (T-> Total

min1 = min2 = max_weight;

For (i = 0; i Total; i ) {/ * for each node * /

IF (t-> arr [i] .parent == -1 / * Node is not included * /

&& t-> arr [i] .weight

IF (t-> arr [i] .weight

MIN2_I = min1_i; min2 = min1;

Min1_i = i; min1 = t-> arr [i] .weight;}

Else

{

Min2_i = i; min2 = t-> arr [i] .weight;

}

}

}

T-> Arr [T-> Total] .weight = min1 min2;

T-> Arr [T-> Total] .parent = -1;

T-> Arr [T-> Total] .lchild = min1_i;

T-> Arr [T-> Total] .rchild = min2_i;

T-> Arr [min1_i] .parent = t-> Total

T-> Arr [min2_i] .parent = t-> Total

T-> Arr [T-> Total] .CH = '';

T-> Total ;

}

Return 0;

}

/ * Code to Hawman Tree * /

Void Coding (htree * t, int head_i, char * code)

{

IF (Head_i == -1) return;

IF (t-> arr [head_i] .lchild == -1 && t-> arr [head_i] .rchild == -1) {

STRCPY (T-> Arr [Head_i] .code, code);

Printf ("'% c':% s / n", t-> arr [head_i] .ch, t-> arr [head_i] .code);

}

Else {

INT LEN = Strlen (CODE);

STRCAT (CODE, "0");

Coding (t, t-> arr [head_i] .lchild, code);

Code [len] = '1';

Coding (t, t-> arr [head_i] .rchild, code);

Code [len] = '/ 0';

}

}

/ * Print tree * /

Void print_htree_ldr (htree * t, int head_i, int desip, int * path)

{

INT I;

IF (Head_i == -1) return;

Path [Deep] = 0;

Print_htree_ldr (t, t-> arr [head_i] .lchild, deep 1, path);

IF (deEP) Printf ("");

For (i = 1; i

INT DIR = PATH [I] == PATH [I-1];

IF (t-> arr [head_i] .lchild == -1 && t-> arr [head_i] .rchild == -1)

Printf ("% s -% d '% c' / n", DIR? "┌": "└",

T-> Arr [Head_i] .weight, t-> arr [head_i] .ch);

Else if (Head_i! = T-> Total-1)

Printf ("% s% 02d ┤ / N", DIR? "┌": "└" ", t-> arr [head_i] .weight); Else

Printf ("% 02d ┤ / n", t-> arr [head_i] .weight);

Path [Deep] = 1;

Print_htree_ldr (t, t-> arr [head_i] .rchild, deep 1, path);

}

/ * Code the character * /

Void code_string (char * text, htree * t)

{

INT I, J, TEXT_LEN = Strlen (Text);

INT n = 0;

For (i = 0; i

Char ch = text [i];

For (j = 0; j Total; J ) IF (CH == T-> Arr [J] .CH) {

Printf ("% s", t-> arr [j] .code);

N = Strlen (t-> arr [j] .code);

Break;

}

}

Printf ("/ N% D Chars, Total Len =% D / N", TEXT_LEN, N);

}

Int main (int Argc, char * argv [])

{

HTree T;

Char text [128] = "AbaaaAeeeeaAacccccaaAaccdea";

CHAR CODE [128] = ""

INT path [16] = {0};

Statistic_char (Text, & T);

CREATE_HTREE (& T);

Print_htree_ldr (& T, T. Total-1, 0, PATH);

Coding (& T, T. Total-1, Code);

Code_String (Text, & T);

Return 0;

}

Output results:

Char frequence'a '13'b' 1'e '4'c' 6'd '1

┌── 6 'c' ┌ - 12 ┤ │ │ ┌── 1 'b' │ │ ┌─02 ┤ │ │ │ └── 1 'D' │ └─06 ┤ │ └── 4 'E' 25 ┤ └── 13 'a'att': 00 ': 0100'd': 0101'e ': 011'a': 11 0100 1 1 1 1 011 011 011 1 1 00 00 00 00 1 1 1 1 00 00 0101 011 1