哈夫曼算法及其應(yīng)用

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

2、進(jìn)行哈夫曼編碼，并存儲入字符編碼文件；根據(jù)字符編碼文件對文本文件內(nèi)容進(jìn)行編碼；根據(jù)字符編碼文件和已編碼文件的內(nèi)容進(jìn)行譯碼；能夠輸出原文、編碼表、文本文件編碼、譯文。三、測試數(shù)據(jù)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 ）根據(jù)給定的n 個權(quán)值 W1， W2， W3Wn 構(gòu)成 n 棵二叉樹的集合T1 ， T2 ，Tn，其中 Ti 中只有一個權(quán)值為Wi 的根結(jié)點，左右子樹均為空。）在F 中選取兩棵根結(jié)點的權(quán)值最小的樹作為左、右子樹一構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點的權(quán)值為左、右子樹上根結(jié)點的權(quán)值之和。）在F 中刪除這兩棵中權(quán)值最小的樹，同時將新得到的二叉樹加入F 中。）重復(fù)2） 3）直到 F 中僅剩一棵樹為止，這棵樹就是哈夫曼樹。、哈夫曼編碼算法：通過從哈夫曼樹根結(jié)點開始，對左子樹分

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

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

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

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

8、d;/右子int parent;/THNODE;typedef THNODE HuffmanTMAX_N;/*Huffman 編碼表結(jié)構(gòu)*/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;/* 找到權(quán)重最小的葉子*/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)計輸入文件的字符及其權(quán)重并存放到樹T*/for (i = 0; i MAX_C; i+)if (ai != 0)Tj.ch = (unsigned char)i;Tj+.weight = (unsigned int)ai;n = j;/* 構(gòu)造 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;/* 根據(jù) 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 對應(yīng)的字符編碼起始位置的初值從葉子 Ti 開始回溯直到回溯到Tc 是樹根位置1;復(fù)制臨時編碼到編碼表中/* 對文件編碼，將結(jié)果保存到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);/* 根據(jù) Huffman 編碼、譯碼*/void DecodingHuffmanT(HuffmanT T, HuffmanCode H) int i; /指示 Huffman tree 葉子個數(shù)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);/ 根據(jù) 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，則找此結(jié)點

18、的左子樹；i = Ti.lchild;if (ch = 1)/若編碼為，則找此結(jié)點的右子樹；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 權(quán)重表 */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);/* 主函數(shù)開始*/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;八、測試情況程序的測試結(jié)果如下：建立哈夫曼樹、打印編碼表正確。打印權(quán)重表正確。哈夫曼編碼正確。哈夫曼譯碼正確，退出正確。九、參考文獻(xiàn)、嚴(yán)蔚敏，數(shù)據(jù)結(jié)構(gòu)C 語言 ，清華大學(xué)出版社。、譚浩強(qiáng)， c 語言程序設(shè)計，清華大學(xué)出版社。小結(jié)課程