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

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

2、對(duì)文件中的字符進(jìn)行哈夫曼編碼，并存儲(chǔ)入字符編碼文件；.根據(jù)字符編碼文件對(duì)文本文件內(nèi)容進(jìn)行編碼；.根據(jù)字符編碼文件和已編碼文件的內(nèi)容進(jìn)行譯碼；5.能夠輸出原文、編碼表、文本文件編碼、譯文。三、測(cè)試數(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

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

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

5、HuffmanT 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)對(duì)文件編碼。Void DecdingHuffmanT(HuffmanT T, HuffmanCode H)根據(jù)Huf

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

7、、哈夫曼編碼表的存儲(chǔ)結(jié)構(gòu)： 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 結(jié)構(gòu)*/ typedef struct char ch;int weight;int lchild;int rchild;int parent;THNODE;typedef THNODE HuffmanTMAX_N;/*Huffman 編碼表結(jié)構(gòu)*

8、/ typedef struct char ch;char bitsMAX_C + 1;CodeNode;/右子/雙親/存儲(chǔ)字符/字符編碼位串/定義最大字符數(shù)/定義最大Huffman節(jié)點(diǎn)個(gè)數(shù)/字符/字符權(quán)重左子/右子/雙親/存儲(chǔ)字符/字符編碼位串typedef CodeNode HuffmanCodeMAX_C;HuffmanCode H;/* 全局變量 */int n;/指示待編譯文件的字長(zhǎng)char filename20;/*初始化Huffman樹*/void InitHT(HuffmanT T) int i;for (i = 0; i MAX_N; i+) Ti.ch = 0;Ti.wei

9、ght = 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) & (Tj

10、.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)計(jì)輸入文件的字符及其權(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 Cr

12、eatHT(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) int

13、 c;int p;int i;int start;char cdN;/指示T中孩子的位置/指示T中雙親的位置/指示編碼在cd中的位置for (i = 0; i = 0)cdstart = (Tp.lchildc = p;strcpy(Hi.bits, &cdstart);/依次求葉子的編碼/讀入葉子Ti對(duì)應(yīng)的字符/編碼起始位置的初值/從葉子Ti開始回溯/直到回溯到Tc是樹根位置 =c) ? 0 : 1;/復(fù)制臨時(shí)編碼到編碼表中/臨時(shí)存放編碼/*對(duì)文件編碼，將結(jié)果保存到codefile.txt中*/void EncodingHuffmanT(HuffmanT T, HuffmanCode H)

14、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 fail!n, encodefile); exit(1

15、);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 != 0) templ = Hj.bitsl;l+；in

16、t 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 葉子個(gè)數(shù)FILE *fp,*fp1;char ch,ch120,ch220;printf(Input encode file name:);scanf(%s”,

17、chi);printf(Input decode file name:);scanf(%s”, ch2);fp = fopen(ch1, rb);fpl = fopen(ch2, wb);/根據(jù)Huffman樹對(duì)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)/若編碼為。，則找此結(jié)點(diǎn)的左子樹；i = Ti.lchild;if (ch = 1)/若編碼為1,則

18、找此結(jié)點(diǎn)的右子樹；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 (fp = fopen(treeprint.txt”, wb) = NULL) pr

19、intf(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 saved in treeprint.txtnn);/*打印Huffman編碼表*

20、/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.ch, Hi.bits);fclose(fp);printf(nHuffman tr

21、ee code saved in codeprint.txt!nn);/*主菜單*/void MainMenue() fflush( stdin );printf(n* Main 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 file.*n)printf(*5. Decoding Huffman file.*n)prin

22、tf(*6. Exit.*n)printf(*n)t-x -i s 1- t s iprintfi*n/*主函數(shù)開始*/int main()int flag = 1; char ch10; HuffmanT T;HuffmanCode H; InitHT(T);while ( flag ) /定義Huffman樹/定義Huffman編碼表/初始化Huffman樹MainMenue();printf(Please input your choice(16):);gets( ch );switch (ch0)case 1CreatHT(T);break;case 2PrintHuffmanH(T,

23、 H);break;case 3PrintHuffmanT(T);break;case 4EncodingHuffmanT(T, H);break;case 5DecodingHuffmanT(T, H);break;case 6exit(1);default:printf(Input error!n);break;return 0;八、測(cè)試情況程序的測(cè)試結(jié)果如下:| decodefile.txt -記事本文件（F）蠲（E）瑚（。）鬲（V）落- 一In its medical literature, the Food and Drug Adinini strati on states that

24、 hot water coinfortable enoughfor washing hands is not hot enough to kill bacteria, but is more effective than cold water because itremoves oils from the hand that can harbor bacteria.:1011010:1011011:110，:1011101.:101111000： 10111101D： 10111110F： 10111111I： 11100100a： 1001b： 00010c： 10101d： 01111e：

25、 1111f： 111000g： 101100h： 0110i： 0100M 1H001011： 10100m： 00011n: 0000o: 1000r： 0101S： 11101t： 001U： 01110L 1011100W： 1110011Huffman tree code saued in codeprint.txt?建立哈夫曼樹、打印編碼表正確。Leaf8tweight of theHuffman tree is below：:2: 40r -2.:1A： 1 D： 1F：1 I:1 a：21b： 6 c: 8d：7 e:21 f:54 h： 13i15k： 11： 7n： 6 n

26、: 1218r： 15s : 11t： 26 u： 6u2w： 3Leaf&weightoftheHuffmantree saved in treeprint.txt打印權(quán)重表正確。Matin Menue *otxxoo(oo(oooooooooo TOC o 1-5 h z 1. Load to be dealt f ile.*J*2.Show Huffmancode list.*J*3.Show Huffmanweight list.*4. Encoding Huffman file.*J*5.Decoding Huffman file.*k*6.Exit.*mt-Please input

27、 90ur choice”： 4Input encode file name: encodefile.txtEncoding file has saved into encodefile.txtf* Main Menue TOC o 1-5 h z J*1.Load to be dealt f ile.*J*2.Show Huffman code list.*X3.Show Huffman weight list.*4. Encoding Huffman file.*J*5.Decoding Huffman file.*k*6.Exit.*M-M*Please input pour choic

28、e: 5 Input encode file name: encodefile.txt Input decode file name: decodefile.txt Decoding accomplished?The result has saue input decodefile.txt.二encodefile.txt -記事本莫件(F) 好(E)悟式(吃查看(V)竟氤而111001000000110010000111101110000111111011110100101011001101001101010001 000011111010110010010111001011111101110

29、111000101101111110101111111000100001111110100100000111111010111110010101110101100110101111010111100011010000000100111010010101100100101001000000011011101001100100111111110111000101101001001110011010000011101110011100100111110101110101011000000111110001000010100110010001010100111111011110000100001110

30、101100011010110111011010111000100001011101110011100111101011001000000101100110011010010000011111110111001001110111000001000001110011010000011101111000010000111010110001101100011000110111001010100101001010011000010100110101001111101010100100110111011100001001110001110010011101110000111000010111111101

31、111111000111000111110101001010010111001111110001011010010000110101011000101000111111011100111001001111101011100001011111010110010111011101111111001000011011011101101001011111000111000101110011111110111010000100101001110111011100001011000000111100010110111111001101001000001111110001011010010011101010110010000110011010010101000101000010111000010100110101001111101010100100110111100哈夫曼編碼正確。| decodefile.txt -記事本I 口 回In its medical literature, the Food and Drug Administra