數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-赫夫曼編碼算法

1、電 子 科 技 大 學(xué)實(shí) 驗(yàn) 報(bào) 告學(xué)生姓名：XXX 學(xué) 號(hào)：XXX 指導(dǎo)教師：XX實(shí)驗(yàn)地點(diǎn)：信軟樓306 實(shí)驗(yàn)時(shí)間：5月19日一、實(shí)驗(yàn)室名稱：軟件實(shí)驗(yàn)室 二、實(shí)驗(yàn)項(xiàng)目名稱：數(shù)據(jù)結(jié)構(gòu)與算法樹三、實(shí)驗(yàn)學(xué)時(shí)：4四、實(shí)驗(yàn)原理：霍夫曼編碼（Huffman Coding）是一種編碼方式，是一種用于無損數(shù)據(jù)壓縮的熵編碼（權(quán)編碼）算法。1952年，David A. Huffman在麻省理工攻讀博士時(shí)所發(fā)明的。在計(jì)算機(jī)數(shù)據(jù)處理中，霍夫曼編碼使用變長編碼表對(duì)源符號(hào)（如文件中的一個(gè)字母）進(jìn)行編碼，其中變長編碼表是通過一種評(píng)估來源符號(hào)出現(xiàn)機(jī)率的方法得到的，出現(xiàn)機(jī)率高的字母使用較短的編碼，反之出現(xiàn)機(jī)率低的則使用較長的

2、編碼，這便使編碼之后的字符串的平均長度、期望值降低，從而達(dá)到無損壓縮數(shù)據(jù)的目的。例如，在英文中，e的出現(xiàn)機(jī)率最高，而z的出現(xiàn)概率則最低。當(dāng)利用霍夫曼編碼對(duì)一篇英文進(jìn)行壓縮時(shí)，e極有可能用一個(gè)比特來表示，而z則可能花去25個(gè)比特（不是26）。用普通的表示方法時(shí)，每個(gè)英文字母均占用一個(gè)字節(jié)（byte），即8個(gè)比特。二者相比，e使用了一般編碼的1/8的長度，z則使用了3倍多。倘若我們能實(shí)現(xiàn)對(duì)于英文中各個(gè)字母出現(xiàn)概率的較準(zhǔn)確的估算，就可以大幅度提高無損壓縮的比例。霍夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長度最短的二叉樹。所謂樹的帶權(quán)路徑長度，就是樹中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長度（若根結(jié)點(diǎn)為

3、0層，葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度為葉結(jié)點(diǎn)的層數(shù)）。樹的路徑長度是從樹根到每一結(jié)點(diǎn)的路徑長度之和，記為WPL=(W1*L1+W2*L2+W3*L3+.+Wn*Ln)，N個(gè)權(quán)值Wi（i=1,2,.n）構(gòu)成一棵有N個(gè)葉結(jié)點(diǎn)的二叉樹，相應(yīng)的葉結(jié)點(diǎn)的路徑長度為Li（i=1,2,.n）?？梢宰C明霍夫曼樹的WPL是最小的。五、實(shí)驗(yàn)?zāi)康模罕緦?shí)驗(yàn)通過編程實(shí)現(xiàn)赫夫曼編碼算法，使學(xué)生掌握赫夫曼樹的構(gòu)造方法，理解樹這種數(shù)據(jù)結(jié)構(gòu)的應(yīng)用價(jià)值，并能熟練運(yùn)用C語言的指針實(shí)現(xiàn)構(gòu)建赫夫曼二叉樹，培養(yǎng)理論聯(lián)系實(shí)際和自主學(xué)習(xí)的能力，加強(qiáng)對(duì)數(shù)據(jù)結(jié)構(gòu)的原理理解，提高編程水平。六、實(shí)驗(yàn)內(nèi)容：（1）實(shí)現(xiàn)輸入的英文字符串輸入，并設(shè)計(jì)算法分別統(tǒng)計(jì)

4、不同字符在該字符串中出現(xiàn)的次數(shù)，字符要區(qū)分大小寫；（2）實(shí)現(xiàn)赫夫曼樹的構(gòu)建算法；（3）遍歷赫夫曼生成每個(gè)字符的二進(jìn)制編碼；（4）顯示輸出每個(gè)字母的編碼。七、實(shí)驗(yàn)器材（設(shè)備、元器件）：PC機(jī)一臺(tái)，裝有C或C+語言集成開發(fā)環(huán)境。八、數(shù)據(jù)結(jié)構(gòu)與程序：#include <stdio.h>#include <stdlib.h>#include <string.h>#define BUFFERSIZE 6000#define VERBAL 0#define DEBUG 1#define MAXVALUE 6000typedef struct hnode int weig

5、ht; int lchild, rchild, parent;THNode, * TpHTree;typedef struct huffman_code int weight; char * pcode;THCode, *TpHcodeTab;void select_subtree(TpHTree huffman,int n,int *subA,int *subB) int i, suba = -1, subb = -1,a = MAXVALUE,b = MAXVALUE; for(i = 0; i <= n; i+) if(huffmani.parent = -1) if( huffm

6、ani.weight < a ) a = huffmani.weight; subb = suba; suba = i; else if(huffmani.weight < b ) b = huffmani.weight; subb = i; *subA = suba; *subB = subb; return;TpHTree create_huffman_tree(int weights, int n ) TpHTree pht; int subA, subB,i, num=(2*n)-1; pht = ( TpHTree ) malloc( sizeof( THNode ) *

7、 num ); for( i = 0; i < num; +i ) phti.weight = weightsi; phti.lchild = -1; phti.rchild = -1; phti.parent = -1; for( i = n; i < num; +i ) select_subtree( pht, i-1, &subA, &subB ); phtsubA.parent = i; phtsubB.parent = i; phti.lchild = subA; phti.rchild = subB; phti.weight = phtsubA.weig

8、ht + phtsubB.weight; return pht;void output_huffman_tree(TpHTree pht, int n)int i; for (i=n+1;i<=2*n-1;i+) printf(" %d",phtphti.lchild.weight); printf(" %d",phti.weight); printf(" %dn",phtphti.rchild.weight); TpHcodeTab build_huffman_code_table(TpHTree pht, int n ) i

9、nt i, j, k, m, len; TpHcodeTab table = ( TpHcodeTab )malloc( sizeof( THCode ) * n); char * pch = (char *) malloc(n + 1 ); for( i = 0; i < n; +i ) m = n; j = i; k = phtj.parent; tablei.weight = phti.weight; while( k!= -1 ) if (phtk.lchild = j) pch-m = '0' else pch-m = '1' j = k; k

10、= phtj.parent; len = n - m + 1; tablei.pcode = ( char * )malloc( len ); strncpy( tablei.pcode, &pchm, strlen(&pchm) ); return table;char * encode_huffman(TpHcodeTab pht, char *msg, char *dict, int n) int i, j; long m, len, offset = 0; char * pch; pch = ( char * )malloc( BUFFERSIZE + 1 ); m =

11、 strlen(msg); for(i = 0; i < m; +i) for(j = 1; j <= n; +j) if(msgi = dictj) len = strlen(phtj.pcode); strncpy( &pchoffset, phtj.pcode, len); offset += len; break; return pch; char * decode_huffman(TpHTree pht, char *msg, char *dict, int n) int i, pos = 0, idx = 0; long len; char * pch; pch

12、 = ( char * )malloc( BUFFERSIZE + 1 ); len = strlen(msg); for(i = 0; i < len; ) idx = (2 * n) - 2; while ( idx >= n) if( msgi = '0') idx = phtidx.lchild; +i; else idx = phtidx.rchild; +i; pchpos = dictidx; pos+; return pch;void destroy_hctable(TpHcodeTab hcode_table, int n) int i; for(

13、i = 0; i < n; +i) if (hcode_tablei.pcode) free(hcode_tablei.pcode); free(hcode_table);long read_file(char* filename, char *message)long slen;FILE * pFile = NULL;pFile = fopen(filename, "r");if(!pFile)printf("read_file(): 打開文件%s失敗!n", filename);exit(0);elseprintf("read_fil

14、e(): 成功打開文件%s!n", filename);memset(message, 0, BUFFERSIZE);if( fgets( message, BUFFERSIZE-1, pFile ) = NULL)printf( "fgets errorn" );exit(0);elseprintf( "%s", message);slen = strlen(message);fclose(pFile);printf("read_file(): 成功讀入文件%s!n", filename);return slen;/ 統(tǒng)計(jì)

15、字符串text中字符出現(xiàn)的頻率int calc_freq(char text, int *freq, char *dict, long n)int i, k, nchar = 0;int * pwght;char * pch;int tokens128 = 0;for(i = 0; i < n; +i)tokenstexti+;for(i = 0; i < 128; i+)if( tokensi > 0 )nchar+;pwght = (int*)malloc(sizeof(int)*nchar);if( !pwght )printf("為權(quán)重?cái)?shù)組分配空間失?。&

16、quot;);exit(0);pch = (char *)malloc(nchar);if( !pch )printf("為字符數(shù)組（字典）分配空間失?。");exit(0);k = 0;for(i = 0; i < 128; +i)if( tokensi > 0 )pwghtk = tokensi;pchk = (char)i; /強(qiáng)制類型轉(zhuǎn)換k+;*freq = pwght;*dict = pch;return nchar;int main(int argc, char *argv)int i, nleaves = 0; long nmsg;char *

17、filename = "/Users/pro/Desktop/數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)/src/debug/love_letter.txt"TpHTree pht = NULL;TpHcodeTab hcode_table;char msgBUFFERSIZE;int *weights = NULL;char *dict = NULL;char *pcode = NULL;char *ptxt = NULL; nmsg = read_file(filename, msg);printf("%sn", msg); nleaves = calc_freq( msg, &

18、amp;weights, &dict, nmsg ); for(i = 0; i < nleaves; +i)printf("%d %c : %dn",i, dicti, weightsi);pht = create_huffman_tree( weights, nleaves ); output_huffman_tree(pht, nleaves); hcode_table = build_huffman_code_table( pht, nleaves ); printf("nHuffman編碼表如下：n"); pcode = encode_huffman(hcode_table, msg, dict, nleaves); printf("nHuffman編碼為：n%sn", pcode); ptxt = decode_huffman(pht, pcode, dict, nleaves); printf("n編碼的解碼為： n%sn",ptxt);d