哈夫曼算法及其應用

1、一、問題描述給定 n 個權值作為n 個葉子結點，構造一棵二叉樹，若帶權路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹。哈夫曼編碼是一種根據哈夫曼樹對文件進行編碼的方式。哈夫曼編碼是可變字長編碼的一種。本次課程設計是對一個已建文本文件，統(tǒng)計該文件中各字符頻率，對各字符進行Huffman 編碼， 將該文件翻譯成Huffman 編碼文件，再將Huffman 編碼文件翻譯成原文件。壓縮文件即讀文件，統(tǒng)計文件中的字符個數，對文件進行哈夫曼編碼和譯碼，并將編碼譯碼后的字符存儲在文件中。二、基本要求程序要求實現以下功能：統(tǒng)計文本文件中各字符的出現次數（涉及讀文件，統(tǒng)計字符個數）；對文件中的字符

2、進行哈夫曼編碼，并存儲入字符編碼文件；根據字符編碼文件對文本文件內容進行編碼；根據字符編碼文件和已編碼文件的內容進行譯碼；能夠輸出原文、編碼表、文本文件編碼、譯文。三、測試數據In its medical literature, the Food and Drug Administration states that hot water comfortable enough for washing hands is not hot enough to kill bacteria, but is more effective than cold water because itremoves o

3、ils from the hand that can harbor bacteria.四、算法思想、哈夫曼樹建立算法：1 ）根據給定的n 個權值 W1， W2， W3Wn 構成 n 棵二叉樹的集合T1 ， T2 ，Tn，其中 Ti 中只有一個權值為Wi 的根結點，左右子樹均為空。）在F 中選取兩棵根結點的權值最小的樹作為左、右子樹一構造一棵新的二叉樹，且置新的二叉樹的根結點的權值為左、右子樹上根結點的權值之和。）在F 中刪除這兩棵中權值最小的樹，同時將新得到的二叉樹加入F 中。）重復2） 3）直到 F 中僅剩一棵樹為止，這棵樹就是哈夫曼樹。、哈夫曼編碼算法：通過從哈夫曼樹根結點開始，對左子樹分

4、配代碼“1”，右子樹分配代碼“0”，一直到達葉子結點為止，然后將從樹根沿每條路徑到達葉子結點的代碼排列起來，便得到了哈夫曼編碼。3、對文件字符編碼算法：逐一讀取文件中字符，在哈夫曼編碼表查找對應字符，讀取其編碼并寫入文件，如此循環(huán)直至結束。4 、哈夫曼譯碼算法：根據編碼用的哈夫曼樹，從根結點出發(fā)，逐個讀入電文中的二進制碼；若代碼為“1 ”，則走左子樹的根結點，否則走向右子樹的根結點；一旦到達葉子結點，便譯出代碼所對應的字符。然后又重新從根結點開始繼續(xù)譯碼，直到二進制電文結束。五、模塊劃分Void InitHT(HuffmanT T)初始化 Huffman 樹。Void SelectMin(Hu

5、ffmanT T, int n, int &p1, int &p2)找到權重最小的葉子。Void LoadHuffmanFile(HuffmanT T)加載文件。Void CreatHT(HuffmanT T)構造Huffman 樹。Void CharSetHuffmanEncoding(HuffmanT T, HuffmanCode H)根據Huffman 樹求Huffman 編碼表。Void EncodingHuffmanT(HuffmanT T, HuffmanCode H)對文件編碼。Void DecdingHuffmanT(HuffmanT T, HuffmanCode H)根據 H

6、uffman 編碼、譯碼。Void PrintHuffmanT(HuffmanT T)打印Huffman 權重表。Void PrintHuffmanH(HuffmanT T, HuffmanCode H)打印Huffman 編碼表。Void MainMenue ()主菜單。提供相關的操作提示。Int main ()主函數。用個while 循環(huán)和 switch 選擇結構進行進行循環(huán)交互性操作。六、數據結構/(ADT)1 、哈夫曼樹的存儲結構：typedef struct char ch;/字符int weight;/字符權重int lchild;/左子int rchild;/右子int pare

7、nt;/ THNODE;2 、哈夫曼編碼表的存儲結構：typedef struct 雙親char ch;/存儲字符char bitsMAX_C + 1;/ CodeNode;七、源程序/Huffman.cpp 源代碼如下：#include #include #include 字符編碼位串#define MAX_C 256/定義最大字符數#define MAX_N 512/#define N 50/*Huffman Tree 結構 */typedef struct定義最大Huffman 節(jié)點個數 char ch;/字符int weight;/字符權重int lchild;/左子int rchil

8、d;/右子int parent;/THNODE;typedef THNODE HuffmanTMAX_N;/*Huffman 編碼表結構*/typedef struct雙親 char ch;/存儲字符char bitsMAX_C + 1;/CodeNode;字符編碼位串typedef CodeNode HuffmanCodeMAX_C;HuffmanCode H;指示待編譯文件的字長int n;/char filename20;/* 初始化 Huffman 樹 */void InitHT(HuffmanT T) int i;for (i = 0; i MAX_N; i+) Ti.ch = 0;

9、Ti.weight = 0;Ti.lchild = -1;Ti.rchild = -1;Ti.parent = -1;/* 找到權重最小的葉子*/void SelectMin(HuffmanT T, int n, int &p1, int &p2) int i;int j;for (i = 0; i 0)p1 = i;break;for (j = i + 1; j 0)p2 = j;break;for (i = 0; i Ti.weight) & (Ti.parent = -1) & (p2 != i) & (Ti.weight 0)p1 = i;for (j = 0; j Tj.weight

10、) & (Tj.parent = -1) & (p1 != j) & (Tj.weight 0)p2 = j;/*加載文件*/void LoadHuffmanFile(HuffmanT T) unsigned int i;int j = 0;char c;int aMAX_C;FILE *fp;printf(Input file name: );scanf(%s, filename);if (fp = fopen(filename, rb) = NULL) printf(Cant open %sn, filename);exit( 0 );for (i = 0; i MAX_C; i+)ai

11、= 0;fseek(fp, 0, SEEK_SET);while ( 1 )/( !feof(fp) )fread(&c, sizeof(unsigned char), 1, fp);if (feof(fp) break;a(unsigned int)c+;fclose(fp);/* 統(tǒng)計輸入文件的字符及其權重并存放到樹T*/for (i = 0; i MAX_C; i+)if (ai != 0)Tj.ch = (unsigned char)i;Tj+.weight = (unsigned int)ai;n = j;/* 構造 huffam 樹， T2 * n - 1 為其根 */ void

12、CreatHT(HuffmanT T)int i,p1,p2;LoadHuffmanFile(T);/加載被編碼文件for (i = n; i 2 * n - 1; i+) SelectMin(T, i - 1, p1, p2);Tp1.parent = Tp2.parent = i;Ti.lchild = p1;Ti.rchild = p2;Ti.weight = Tp1.weight + Tp2 .weight;/* 根據 Huffman T 求 Huffman 編碼表 H*/ void CharSetHuffmanEncoding(HuffmanT T, HuffmanCode H) T

13、OC o 1-5 h z int c;/int p;/int i;int start;/char cdN;/for (i = 0; i = 0) / cd-start = (Tp.lchild = c) ? 0 : c = p;strcpy(Hi.bits, &cdstart); /指示T 中孩子的位置指示T 中雙親的位置指示編碼在cd 中的位置臨時存放編碼依次求葉子的編碼讀入葉子Ti 對應的字符編碼起始位置的初值從葉子 Ti 開始回溯直到回溯到Tc 是樹根位置1;復制臨時編碼到編碼表中/* 對文件編碼，將結果保存到codefile.txt 中 */void EncodingHuffmanT(

14、HuffmanT T, HuffmanCode H) char c;FILE *in,*fp;int j,l;char encodefile20,tempMAX_C;if (in = fopen(filename, rb) = NULL) printf(Read %s fail!n, encodefile);exit(1);CharSetHuffmanEncoding(T, H);printf(Input encode file name: );gets( encodefile );if (fp = fopen(encodefile, wb) = NULL) printf(Write %s f

15、ail!n, encodefile); exit(1);fread(&c, sizeof(unsigned char), 1, in);fwrite(&c, sizeof(unsigned char), 1, fp);fseek(in, 0, SEEK_SET);fseek(fp, 0, SEEK_SET);while ( 1 )/( !feof( in ) fread(&c, sizeof(unsigned char), 1, in);if (feof(in) break;for (j = 0; j n; j+)if (c = Hj.ch) l = 0;while (Hj.bitsl !=

16、0) templ = Hj.bitsl; l+;int m = 0;while ( l- )fwrite(&tempm+, sizeof(unsigned char), 1, fp);fclose(fp);printf(Encoding file has saved into %s!n, encodefile);/* 根據 Huffman 編碼、譯碼*/void DecodingHuffmanT(HuffmanT T, HuffmanCode H) int i; /指示 Huffman tree 葉子個數FILE *fp,*fp1;char ch,ch120,ch220;printf(Inpu

17、t encode file name: );scanf(%s, ch1);printf(Input decode file name: );scanf(%s, ch2);fp = fopen(ch1, rb);fp1 = fopen(ch2, wb);/ 根據 Huffman 樹對 Huffman 編碼 譯碼 i = 2 * n - 2;fseek(fp, 0L, SEEK_SET);fseek(fp1, 0L, SEEK_SET);while (!feof(fp) fread(&ch, sizeof(unsigned char), 1, fp);if (ch = 0)/若編碼為o，則找此結點

18、的左子樹；i = Ti.lchild;if (ch = 1)/若編碼為，則找此結點的右子樹；i = Ti.rchild;if (i n) fwrite(&Ti.ch, sizeof(unsigned char), 1, fp1);i = 2 * n - 2;fclose(fp);fclose(fp1);printf(Decoding accomplished!nThe result has save input %s.n,ch2); getchar();/* 打印 Huffman 權重表 */void PrintHuffmanT(HuffmanT T) int i;FILE *fp;if (f

19、p = fopen(treeprint.txt, wb) = NULL) printf(Open treeprint.txt fail!n);exit(1);printf(nLeaf&weight of the Huffman tree is below:n);for (i = 0; i 0) printf(n);if (Ti.weight 0) fprintf(fp, %c:%d , Ti.ch, Ti.weight);printf(%c: %d , Ti.ch, Ti.weight);fclose(fp);printf(nLeaf&weight of the Huffman tree sa

20、ved in treeprint.txtnn);/* 打印 Huffman 編碼表 */void PrintHuffmanH(HuffmanT T, HuffmanCode H) int i;FILE *fp;CharSetHuffmanEncoding(T, H);if (fp = fopen(codeprint.txt, wb) = NULL) printf(Open codeprint.txt fail!n);exit(1);for (i = 0; i 0) printf(n);printf(%c: %sn, Ti.ch, Hi.bits);fprintf(fp, %c:%s , Ti.

21、ch, Hi.bits);fclose(fp);printf(nHuffman tree code saved in codeprint.txt!nn);/* 主菜單 */void MainMenue() fflush( stdin );printf(nMain Menue*n);printf(*n);printf(* 1. Load to be dealt file.*n);printf(* 2. Show Huffman code list.*n);printf(* 3. Show Huffman weight list. *n);printf(*4. Encoding Huffman f

22、ile.*n);printf(*5. Decoding Huffman file.*n);printf(* 6. Exit.*n);printf(*n);printf(*n);/* 主函數開始*/int main()int flag = 1;char ch10;定義Huffman 樹定義Huffman 編碼表初始化 Huffman 樹HuffmanT T;/HuffmanCode H; /InitHT(T);/while ( flag ) MainMenue();printf(Please input your choice(16): ); gets( ch );switch ( ch0 )c

23、ase 1: CreatHT(T);break;case 2: PrintHuffmanH(T, H); break;case 3: PrintHuffmanT(T); break;case 4: EncodingHuffmanT(T, H);break;case 5: DecodingHuffmanT(T, H);break;case 6: exit(1);default: printf(Input error!n); break;return 0;八、測試情況程序的測試結果如下：建立哈夫曼樹、打印編碼表正確。打印權重表正確。哈夫曼編碼正確。哈夫曼譯碼正確，退出正確。九、參考文獻、嚴蔚敏，數據結構C 語言 ，清華大學出版社。、譚浩強， c 語言程序設計，清華大學出版社。小結課程