




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 家電制造行業(yè)職業(yè)健康與安全咨詢項(xiàng)目成果
- 全球化視角下的臺(tái)風(fēng)預(yù)警偏航技術(shù)融合發(fā)展
- 2025至2030中國汽車導(dǎo)航行業(yè)項(xiàng)目調(diào)研及市場(chǎng)前景預(yù)測(cè)評(píng)估報(bào)告
- 2025至2030中國冰皮月餅行業(yè)發(fā)展趨勢(shì)分析與未來投資戰(zhàn)略咨詢研究報(bào)告
- 2025至2030中國自動(dòng)行尾包裝行業(yè)市場(chǎng)占有率及投資前景評(píng)估規(guī)劃報(bào)告
- 2025至2030中國自動(dòng)水果切片機(jī)行業(yè)市場(chǎng)深度研究及發(fā)展前景投資可行性分析報(bào)告
- 2025至2030中國臀部和膝蓋重建行業(yè)市場(chǎng)深度研究及發(fā)展前景投資可行性分析報(bào)告
- 節(jié)能型油分離器設(shè)計(jì)與優(yōu)化研究
- 2025至2030中國腳手架板行業(yè)深度研究及發(fā)展前景投資評(píng)估分析
- 2025至2030中國胰腺內(nèi)分泌腫瘤藥物行業(yè)市場(chǎng)占有率及投資前景評(píng)估規(guī)劃報(bào)告
- (高清版)DB11∕T 2429-2025 補(bǔ)充耕地質(zhì)量調(diào)查與評(píng)價(jià)技術(shù)規(guī)范
- 湖北省襄陽市2024-2025學(xué)年高一下學(xué)期7月期末統(tǒng)一調(diào)研測(cè)試地理試卷
- 機(jī)場(chǎng)行李安檢安全培訓(xùn)心得體會(huì)
- 建筑施工企業(yè)2025年半年業(yè)績總結(jié)和下半年工作計(jì)劃
- 昭通設(shè)備裝卸方案(3篇)
- 2025年天津市中考英語試卷(含標(biāo)準(zhǔn)答案及解析)
- 2025至2030中國港口航道工程行業(yè)深度研究及發(fā)展前景投資評(píng)估分析
- 單元復(fù)習(xí)AB卷:第二十八章 圓(A卷-中檔卷)解析版
- 建筑工程項(xiàng)目參與證明(8篇)
- 疏通經(jīng)絡(luò)課件
- 2025至2030中國桃膠行業(yè)發(fā)展分析及產(chǎn)業(yè)運(yùn)行態(tài)勢(shì)及投資規(guī)劃深度研究報(bào)告
評(píng)論
0/150
提交評(píng)論