/ * ================================================================================================================================================================ ==== * /
/ * * /
/ * Huffman.c (pp) - a Huffman Arithmetic DemonStration * /
/ * smith_135@163.com * /
/ * QQ: 58101543 * /
/ * Version 0.9 * /
/ * CopyRight (c) meteor135 * /
/ * 2004.7.13 v0.10 * /
/ * 2004.11.19 v0.11 * /
/ * * /
/ * ================================================================================================================================================================ ==== * /
#include
#include
#include
#include
#include
/ * Tree structure and global structural pointer * /
Struct Node
{
INT NUM; / * Non-point number * /
Char C;
Int weight;
Int Parent;
Int lchild, rchild;
} * ht;
/ * Constant file name * /
Const char * TABLEFILENAME = "hfmtbl.txt";
Const char * sourcefilename = "srcText.txt";
Const char * codefilename = "hfmcode.txt";
Const char * decodefilename = "decodeText.txt";
Const char * treeviewFileName = "treView.txt"; / * Print format string constance * /
Const char * printformatstr = "% 4D% 13C% 13D% 13D% 13D% 13D / R / N";
/ * Read format string constance * /
Const char * readformatstr = "% D% C% D% D% D% D";
/ * Print Parameter Macro * /
#define print_Param (i) HT [(i)]. Num, HT [(i)]. C, HT [(i)]. weight, /
HT [(i)]. Parent, HT [(i)]. LCHILD, HT [(i)]. rChild
/ * Read parameter macro * /
#define read_param (i) & HT [(i)]. Num, & HT [(i)]. C, & HT [(i)]. weight, /
& HT [(I)]. Parent, & HT [(I)]. LCHILD, & HT [(i)]. rChild
/ * Print format and parameter macro * /
#define read_format_param (i) ReadFormatstr, Read_Param (i)
/ * Read format and parameter macro * /
#define print_format_param (i) PrintFormatstr, Print_Param (i)
/ ************************************************** *********** /
/ ** utility functions ** /
/ ************************************************** *********** /
/ * Memory swap function, used for structural variable exchange * /
Void Memswap (Void * BUF1, VOID * BUF2, SIZE_T BUFLEN)
{
IF (BUF1! = BUF2)
{
Void * p = malloc (buflen);
Memmove (P, BUF1, BUFLEN);
Memmove (BUF1, BUF2, BUFLEN);
Memmove (BUF2, P, BUFLEN);
Free (p);
}
}
/ * Print mesh * /
Void Printht (int from, int to)
{
INT I;
For (i = from; i <= to; i )
{
Printf (Print_Format_Param (i));
}
Printf ("/ n");
}
/ * Selection method sort * /
Void SelectSort (int from, int to)
{
INT I, J, K;
For (i = from; i { For (k = i, j = i 1; j <= to; j ) IF (HT [J] .weight K = J; IF (k! = i) MEMSWAP (& HT [K], & HT [I], SIZEOF (Struct Node); PRINTHT (from, to); } } / * Release HT * / Void free_ht () { IF (ht! = null) { Free (HT); HT = NULL; } } / * Save from the file read data to the global heap, the call party should remember the release * / Int ReadFromFile () { INT I; Int m; File * h; IF ((h = fopen (TableFileName, "R")) == NULL) { Printf ("Cannot Open% S / N", TableFileName); Getch (); Return 0; } Fscanf (h, "% d", & m); Free_ht (); HT = (struct node *) Calloc (m 1, sizeof (struct node)); // Printf ("% d / n", m); For (i = 1; i <= m; i ) { Fscanf (h, read_format_param (i)); // Printf (Print_Format_Param (i)); } Fclose (h); Return M; } / * Eat invalid spam * / void eatcharsuntilnewline () { While (getchar ()! = '/ n') CONTINUE; } / * Reissous by node sequence * / Void Sortbynum (Int M) { INT i = 0, J; SIZE_T LEN = SIZEOF (STRUCT NODE); For (i = 1; i { For (j = i 1; j <= m; j ) { IF (HT [J] .NUM == i) { MemSwap (& HT [I], & HT [J], LEN); Break; } } } } / ************************************************** *********** / / ** Command Instruction functions ** / / ************************************************** *********** / / * Initialize and write files * / void initialize () { INT i = 0, x = 0, y = 0, n, m; File * h; "" INPUT The Number of The Total Char N: "); Scanf ("% d", & n); Eatcharsuntilnewline (); M = 2 * n-1; HT = (struct node *) Calloc (m 1, sizeof (struct node)); / * Traverse the leaf node for initialization * / For (i = 1; i <= n; i ) { "" Input a char: "); Scanf ("% C", & HT [i] .c); Eatcharsuntilnewline (); "" "" " Scanf ("% D", & HT [i] .weight); Eatcharsuntilnewline (); HT [i] .num = i; } Printht (1, n); For (i = n 1; i <= m; i ) / * address branch * / { HT [i] .c = '$'; HT [i] .num = i; } Printht (n 1, m); / * Use the selection method to order the first to n elements from small to large sorts * / SelectSort (1, n); Printht (1, n); For (x = 1, i = n 1; i <= m; i , x = 2) { Y = x 1; HT [x] .parent = HT [y] .parent = i; HT [i] .lchild = HT [x] .num; HT [I] .rchild = HT [Y] .num; HT [i] .weight = HT [x] .weight HT [Y] .weight; / * Sorting * / Selectsort (1, i); } / * See the sorting effect * / Printht (1, m); Getch (); Sortbynum (m); / * View recovery serial number * / Printht (1, m); Getch (); / * Data writing files and outputs to the screen * / IF ((h = fopen (TableFileName, "WB")) == NULL) { Printf ("Cannot Open% S / N", TableFileName); Getch (); Return; } Printf ("The Huffmantree IS: / N"); Printf ("Number Character Weight Parent Lchild Rchild / N"); / * The first line is written to the number of data lines * / FPRINTF (h, "% d / r / n", m); / * Recycled to the screen output at the same time * / For (i = 1; i <= m; i ) { Printf (Print_Format_Param (i)); FPRINTF (H, Print_Format_Param (i)); } Free_ht (); Fclose (h); } / * Encoded and write file * / Void encode () { INT I, MM, C, F, START; CHAR WR, * CD = (char *) NULL, CH; Char ** hc = (char **) NULL; File * fp1, * fp2; INT m = readfromfile (); INT N = (m 1) / 2; IF (hc! = null) free (HC); HC = (char **) Calloc (N 1, Sizeof (char *)); IF (hc == null) return; IF (CD! = NULL) Free (CD); CD = (char *) Calloc (n, sizeof (char)); IF (cd == null) return; For (i = 1; i <= n; i ) { START = N-1; For (c = i, f = HT [i] .parent; f! = 0; c = f, f = HT [f] .parent) { /*CD [--start]='1' 1'-(ht[f].lchild==c ); * IF (ht [f] .lchild == c) CD [- start] = '0'; Else CD [- start] = '1'; } HC [I] = (char *) Malloc ((N-START) * SIZEOF (CHAR)); STRCPY (HC [I], & CD [Start]); } Free (CD); For (i = 1; i <= n; i ) Printf ("% C ----% S / N", HT [I] .C, HC [I]); Printf ("IF INPUT The File Tobetran Select A, Else Read from% s. / n", SourceFileName; Printf ("Please Input:"); Scanf ("% C", & WR); IF (WR == 'A' || WR == 'A') { IF ((fp1 = fopen (SourceFileName, "W ")) == null) { Printf ("Cannot open% S / N", SourceFileName); Getch (); Return; } Printf ("" please input the tobetran: (end with '#') / n "); CH = GetCh (); While (ch! = '#') { FPUTC (CH, FP1); PUTCHAR (CH); CH = GetCh (); } Rewind (fp1); Printf ("/ n"); } Else { IF ((fp1 = fopen (sourcefilename, "r") == null) { Printf ("Cannot open% S / N", SourceFileName); Getch (); Return; } } IF ((FP2 = FOPEN (CodeFileName, "W") == null) { Printf ("canNot open% s / n", codefilename); Getch (); Return; } While (! Feof (fp1)) { CH = FGETC (FP1); For (i = 1; i <= n; i ) IF (HT [I] .c == CH) For (mm = 0; HC [i] [mm]! = '/ 0'; mm ) { FPUTC (HC [I] [mm], FP2); Printf ("% C", HC [i] [mm]); } } Printf ("/ n"); For (i = 1; i <= n; i ) FPRINTF (FP1, "/ R / N% C ----% S", HT [I] .C, HC [I]); For (i = 1; i <= n; i ) FPRINTF (FP2, "/ R / N% S ----% C", HC [I], HT [I] .c); For (i = 1; i <= n; i ) { Free (HC [I]); } Free (hc); Free_ht (); Fclose (fp1); Fclose (FP2); } / * Decoding write files and outputs * / void decode () { File * codefilep, * textfilep; CHAR CH = '/ 0'; INT F; INT m = readfromfile (); f = m; IF (CodeFileP = Fopen (CodeFileName, "R")) == NULL) { Printf ("canNot open% s / n", codefilename); Getch (); Return; } IF ((TextFileP = FOPEN (DecodeFileName, "W")) == NULL) { Printf ("Cannot Open% S / N", DECodeFileName); Getch (); Return; } While (! feof (codefilep) && ch! = '/ n') { CH = FGETC (CodeFileP); IF (CH == '0') f = HT [f] .lchild; IF (CH == '1') f = HT [f] .rchild; IF (! HT [f] .lchild &&! HT [f] .rchild) { FPUTC (HT [F] .c, TextFileP); Printf ("% C", HT [f] .c); f = m; } } Free_ht (); Fclose (CodeFileP); Fclose (TextFileP); Printf ("/ n"); } / * Do not decode Huffman encoding in the direct output file * / Void PrintCode () { INT i = 0; CHAR CH = 0; FILE * CODEFILEP; IF (CodeFileP = Fopen (CodeFileName, "R")) == NULL) { Printf ("canNot open% s / n", codefilename); Getch (); Return; } While (! Feof (CodefileP) && ch! = '/ n') { IF (i == 50) { Printf ("/ n"); i = 0; } CH = FGETC (CodeFileP); Printf ("% C", CH); } Printf ("/ n"); Fclose (CodeFileP); } / * Output huffman tree * / Void Printtree () { INT I, K, TOP, P; INT * level, * stack; File * TreePrintFileP; INT m = readfromfile (); INT N = (m 1) / 2; IF (TreePrintFilep = FOPEN (TreeViewFileName, "W")) == NULL) { Printf ("Cannot Open% S / N", TreeViewFileName; Getch (); Return; } Printf ("The Huffmantree IS: / N"); FPrintf (TreePrintFilep, "The Huffmantree IS: / N"); Level = (int *) malloc (n * sizeof (int)); Stack = (int *) malloc (n * sizeof (int)); IF (M! = 0) { TOP = 1; Stack [TOP] = M; Level [TOP] = 3; While (TOP> 0) { P = stack [top]; K = level [TOP]; For (i = 1; i <= k; i ) { Printf (""); FPRINTF (TreePrintFileP, "); } Printf ("% d / n", HT [p] .weight); FPrintf (TreePrintFilep, "% D / N", HT [P] .weight); Top -; IF (ht [p] .rchild! = 0) { TOP ; Stack [TOP] = HT [P] .rchild; Level [TOP] = K 3; IF (ht [p] .lchild! = 0) { TOP ; Stack [TOP] = HT [P] .lchild; Level [TOP] = K 3; } } } Free (Level); Free (stack); Fclose (TreePrintFileP); } INT Prompt () { CHAR EN; Puts ("/ n ****************************************"); PUTS ("I / I --- Initialize E / E --- Encode P / P --- Print File's Code"); PUTS ("T / T - PRINT HFMTREE D / D --- Decode Q / Q --- Quit Program"); PUTS ("**************************************************************************"); Puts ("Please Choose A Menu Item and Press Enter to Continue."); Printf (">"); Scanf ("% C", & en); Eatcharsuntilnewline (); Return TOLOWER (EN); } void main () { While (1) { Switch (prompt ()) { Case 'I': INITIALIZE (); Break; Case 'E': ENCODE (); Break; Case 'd': Decode (); Break; Case 'P': PRINTCODE (); Break; Case 'T': PRINTTREE (); Break; Case 'Q': Free_ht (); Return; } } }
