數(shù)據(jù)結構實驗報告-赫夫曼編碼算法

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

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

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

4、不同字符在該字符串中出現(xiàn)的次數(shù)，字符要區(qū)分大小寫；（2）實現(xiàn)赫夫曼樹的構建算法；（3）遍歷赫夫曼生成每個字符的二進制編碼；（4）顯示輸出每個字母的編碼。七、實驗器材（設備、元器件）：PC機一臺，裝有C或C+語言集成開發(fā)環(huán)境。八、數(shù)據(jù)結構與程序：#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)計

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("為權重數(shù)組分配空間失??！n&

16、quot;);exit(0);pch = (char *)malloc(nchar);if( !pch )printf("為字符數(shù)組（字典）分配空間失??！n");exit(0);k = 0;for(i = 0; i < 128; +i)if( tokensi > 0 )pwghtk = tokensi;pchk = (char)i; /強制類型轉換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ù)結構實驗/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