哈夫曼樹(shù)實(shí)驗(yàn)報(bào)告

1、計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告班級(jí) 2 0 14級(jí)計(jì)算機(jī) 1班 學(xué)號(hào) 2 0 1 44 1 38021姓名 張建華 成績(jī)實(shí)驗(yàn)項(xiàng)目簡(jiǎn)單哈夫曼贏"7譯碼得設(shè)計(jì)與實(shí)現(xiàn)實(shí)驗(yàn)日期2 016、1、5一、實(shí)驗(yàn)?zāi)康帽緦?shí)驗(yàn)得目得就是進(jìn)一步理解哈夫曼樹(shù)得邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)，進(jìn)一步提高使用理論知識(shí)指導(dǎo)解決實(shí)際 問(wèn)題得能力。二、實(shí)驗(yàn)問(wèn)題描述利用哈夫曼編碼進(jìn)行通信可以大大提高彳t道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但就是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)得數(shù)據(jù)進(jìn)行譯碼 ，此實(shí)驗(yàn)即設(shè)計(jì)這樣得一個(gè)簡(jiǎn)單編/碼系統(tǒng)。系統(tǒng)應(yīng)該具有如下得幾個(gè)功能：1、接收原始數(shù)據(jù)。從終端讀入字

2、符集大小n,以及n個(gè)字符與n個(gè)權(quán)值，建立哈夫曼樹(shù)，并將它存于文件 hfmt ree、d a t 中。2、編碼。?利用已建好得哈夫曼樹(shù)（如不在內(nèi)存，則從文件hfmtree、da t中讀入），對(duì)文件中得正文進(jìn)行編碼，然后將結(jié)果存入文件 code中。3、譯碼。利用已建好得哈夫曼樹(shù)將文件code中得代碼進(jìn)行譯碼，結(jié)果存入文件t e x t中。4、打印編碼規(guī)則。即字符與編碼得一一對(duì)應(yīng)關(guān)系。5、打印哈夫曼樹(shù)，將已在內(nèi)存中得哈夫曼樹(shù)以直觀得方式顯示在終端上。三、實(shí)驗(yàn)步驟1、實(shí)驗(yàn)問(wèn)題分析1、構(gòu)造哈夫曼樹(shù)時(shí)使用靜態(tài)鏈表作為哈夫曼樹(shù)得存儲(chǔ)。在構(gòu)造哈夫曼樹(shù)時(shí)，設(shè)計(jì)一個(gè)結(jié)構(gòu)體數(shù)組H uffNode保存哈夫曼樹(shù)中各結(jié)點(diǎn)

3、得信息 ，根 據(jù)二叉樹(shù)得性質(zhì)可知，具有n個(gè)葉子結(jié)點(diǎn)得哈夫曼樹(shù)共有 2n-1個(gè)結(jié)點(diǎn)，所以數(shù)組HuffN。d e得大小設(shè)置為2 n 1,描述結(jié)點(diǎn)得數(shù)據(jù)類型為：Typedef strc u t? Int weight ; /* 結(jié)點(diǎn)權(quán)值*/I n t parent;I n t lchild;I nt r chil d ;HNod e T y pe;2、求哈夫曼編碼時(shí)使用一維結(jié)構(gòu)數(shù)組Hu f fCode作為哈夫曼編碼信息得存儲(chǔ)。求哈夫曼編碼，實(shí)質(zhì)上就就是在已建立得哈夫曼樹(shù)中，從葉子結(jié)點(diǎn)開(kāi)始，沿結(jié)點(diǎn)得雙親鏈域回退到根結(jié)點(diǎn)，沒(méi)回退一步，就走過(guò)了哈夫曼樹(shù)得一個(gè)分支，從而得到一位哈夫曼碼值，由于一個(gè)字符得哈夫

4、曼 編碼就是從根結(jié)點(diǎn)到相應(yīng)葉子結(jié)點(diǎn)所經(jīng)過(guò)得路徑上各分支所組成得0、1序列，因此先得到得分支代碼為所求編碼得低位碼，后得到得分支代碼位所求編碼得高位碼，所以設(shè)計(jì)如下數(shù)據(jù)類型：#defi n e MAX BIT 10T y pedef struct Int bitMAXB I T;? Int s tart; H Cod e Type;3、文件 h f m tree、dat、code 與 text 。2、功能(函數(shù))設(shè)計(jì)( 1)、初始化功能模塊。此功能模塊得功能為從鍵盤接收字符集大小 n ，以及 n 個(gè)字符與 n 個(gè)權(quán)值。(2) 、建立哈夫曼樹(shù)得功能模塊。此模塊功能為使用 1 中得到得數(shù)據(jù)按照教材中

5、得構(gòu)造哈夫曼樹(shù)得算法構(gòu)造哈夫曼樹(shù),即將Huff Node數(shù)組中得各個(gè)位置得各個(gè)域都添上相關(guān)得值，并將這個(gè)結(jié)構(gòu)體數(shù)組存于文件hfmtree、dat中。(3) 、建立哈夫曼編碼得功能模塊。此模塊功能為從文件hfmtree 、 dat 中讀入相關(guān)得字符信息進(jìn)行哈夫曼編碼,然后將結(jié)果存入code中,同時(shí)將字符與0、1代碼串得一一對(duì)應(yīng)關(guān)系打印到屏幕上。(4) 、譯碼得功能模塊。此模塊功能為接收需要譯碼得 0、 1 代碼串,按照3 中建立得編碼規(guī)則將其翻譯成字符集中字符所組成得字符串形式，存入文件t e x t ,同時(shí)將翻譯得結(jié)果在屏幕上打印輸出。(5 )、打印哈夫曼樹(shù)得功能模塊。,以圖形得方式將各個(gè)結(jié)點(diǎn)

6、以及葉子此模塊功能為從HuffNo d e數(shù)組中讀入相關(guān)得結(jié)點(diǎn)信息結(jié)點(diǎn)得權(quán)值與左分支上得0 與右分支上得 1 畫出來(lái)。)及分析1、實(shí)驗(yàn)主要代碼t y pedef s true tstring hfm str;? int we i ght;int parent ；i nt 1 c h ild;int r child; HN o d eT y p e;typ e def st r uct*結(jié)點(diǎn)結(jié)構(gòu)體*/ 結(jié)點(diǎn)內(nèi)容* / 結(jié)點(diǎn)權(quán)值*/* 編碼結(jié)構(gòu)體*/in t b i tM AXBI T ; in t sta r t ;HCodeT y p e; *創(chuàng)建哈夫曼樹(shù)*/v oid C re a t e

7、_Hu f fMTree(HNodeTyp e HFMTre e 口,int n) ? in tml, x1,m2,x2 ;? i n t i,j;? f o r( i =0; i <2 *n- 1 ;i+ )? HFM Treei 、h f ms tr=""HFMT r e e i 、we ight=0 ;? H FMTr eei 、par e nt = - 1;HF M Tr e e ： i、lchild=-1;HFM T re e i 、r c h i ld=-1 ;? f or (i=0 ; i<n;i+ +)?<<e n d l;cout&

8、lt;<"請(qǐng)輸入第"<< i + 1<v"個(gè)權(quán)值"? c in> > HFMTre ei 、weig h t;? co ut<<”請(qǐng)輸入對(duì)應(yīng)字符"<<e ndl;? cin> > HFM T r ee i、h f mst r;?f or ( i = 0 ; i<n 1;i+ )? x1=x2=MAX VALUE;? ml =m2= 0;for(j = 0;j<n+ i ;j + +)? ? i f(H F MTreej 、parent=-1&&H

9、FMT r ee j 、w eigh t <x1) ?x 2 = x 1;? ? ? m2=m1;? x 1 = HF M T re e j > weig h t;m 1=j;? ? ? else i f (H FMTr eej 、p arent =-1&&HFMTr e e j 、wei g h t<x2) ?x2=HFMTree j 、weight ;? m2=j ；? HFMTr eem1、p arent= n + i ;HFMTre e m2、pa r e n t =n+i ;? ? HF MTree n + i 、we ig h t = H FMTr

10、 e em1、weight+H F MTreem2、weight ;? HF MT re e n+i 、1 ch i 1 d= ml ;? H F MTre en+i 、r c hild=m 2 ;? c o u t v”創(chuàng)建哈夫曼樹(shù)成功！ u v <en d l;void Haffma n Code (HNodeType HFMTree口,H C odeT y p e Huff Code口 ,int n) /* 構(gòu)建 哈夫曼編碼*/? HCo deType c d;i n t i,j, c ,p;for(i = 0;i<n ; i+) cd 、 start=n 1； c= i ;

11、p=HFMTreec 、parent ;w h i 1 e ( p!=- 1 )i f (HFMTr ee p、lchild = = c) cd 、 bitcd 、 start=0 ；el bitcd 、 start=1;c d > s tar t -;c =p；p =HFM Tree c 、par ent;fo r (j=cd、sta r t+1;j < n;j+)HuffCod e i 、b i tj = c d、bitj;Huff Code i 、start = cd、star t ;v o id d e cod e i n g ( c har s t ring,H Nod

12、eType HFMTr e e , i n t n) /* 解碼 * /int i , t mp=0 ,code102 4 ;int m =2*n-1;c h ar *n u mp;cha r n um1 0 24;for ( i = 0 ; i<s t rl e n (strin g) ; i + +)i f(stringi = ='0')numi =0;elsen u m i =1;i =0;nump=&nun 0;w h ile(nump<( & num st r 1 e n ( s tring) )? tmp = m-1;wh i le( (HFMTree tmp、lc h i 1 d! =- 1)&&( H FMT ree t mp、rchild! =- 1)?if(*n u mp= =0)?tmp=HFMTree tmp 卜 1 c h i ld ;?e lsetmp=HFMT r eet m p、rch i ld;n ump+ +;cout v<HFMTreet m p、h fms t r;cou t << e n d 1 ;請(qǐng)湎