哈夫曼樹實驗報告

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

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

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

4、曼 編碼就是從根結點到相應葉子結點所經(jīng)過得路徑上各分支所組成得0、1序列，因此先得到得分支代碼為所求編碼得低位碼，后得到得分支代碼位所求編碼得高位碼，所以設計如下數(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ù))設計( 1)、初始化功能模塊。此功能模塊得功能為從鍵盤接收字符集大小 n ，以及 n 個字符與 n 個權值。(2) 、建立哈夫曼樹得功能模塊。此模塊功能為使用 1 中得到得數(shù)據(jù)按照教材中

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

6、以及葉子此模塊功能為從HuffNo d e數(shù)組中讀入相關得結點信息結點得權值與左分支上得0 與右分支上得 1 畫出來。)及分析1、實驗主要代碼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*結點結構體*/ 結點內(nèi)容* / 結點權值*/* 編碼結構體*/in t b i tM AXBI T ; in t sta r t ;HCodeT y p e; *創(chuàng)建哈夫曼樹*/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;<"請輸入第"<< i + 1<v"個權值"? c in> > HFMTre ei 、weig h t;? co ut<<”請輸入對應字符"<<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)建哈夫曼樹成功！ u v <en d l;void Haffma n Code (HNodeType HFMTree口,H C odeT y p e Huff Code口 ,int n) /* 構建 哈夫曼編碼*/? 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 ;請湎