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

共頁(yè)第頁(yè)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告班級(jí)2014級(jí)計(jì)算機(jī)1班學(xué)號(hào)20144138021姓名張建華成績(jī)實(shí)驗(yàn)項(xiàng)目簡(jiǎn)單哈夫曼編/譯碼的設(shè)計(jì)與實(shí)現(xiàn)實(shí)驗(yàn)日期2016.1.5一、實(shí)驗(yàn)?zāi)康谋緦?shí)驗(yàn)的目的是進(jìn)一步理解哈夫曼樹的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，進(jìn)一步提高使用理論知識(shí)指導(dǎo)解決實(shí)際問題的能力。二、實(shí)驗(yàn)問題描述利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼，此實(shí)驗(yàn)即設(shè)計(jì)這樣的一個(gè)簡(jiǎn)單編/碼系統(tǒng)。系統(tǒng)應(yīng)該具有如下的幾個(gè)功能：1、接收原始數(shù)據(jù)。 從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹，并將它存于文件hfmtree.dat中。2、編碼。 利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmtree.dat中讀入），對(duì)文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile.dat中。3、譯碼。利用已建好的哈夫曼樹將文件codefile.dat中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile.dat中。4、打印編碼規(guī)則。即字符與編碼的一一對(duì)應(yīng)關(guān)系。5、打印哈夫曼樹， 將已在內(nèi)存中的哈夫曼樹以直觀的方式顯示在終端上。三、實(shí)驗(yàn)步驟1、實(shí)驗(yàn)問題分析1、構(gòu)造哈夫曼樹時(shí)使用靜態(tài)鏈表作為哈夫曼樹的存儲(chǔ)。 在構(gòu)造哈夫曼樹時(shí)，設(shè)計(jì)一個(gè)結(jié)構(gòu)體數(shù)組HuffNode保存哈夫曼樹中各結(jié)點(diǎn)的信息，根據(jù)二叉樹的性質(zhì)可知，具有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有2n-1個(gè)結(jié)點(diǎn)，所以數(shù)組HuffNode的大小設(shè)置為2n-1，描述結(jié)點(diǎn)的數(shù)據(jù)類型為：Typedefstrcut{ Intweight；/*結(jié)點(diǎn)權(quán)值*/Intparent；Intlchild；Intrchild；}HNodeType；2、求哈夫曼編碼時(shí)使用一維結(jié)構(gòu)數(shù)組HuffCode作為哈夫曼編碼信息的存儲(chǔ)。 求哈夫曼編碼，實(shí)質(zhì)上就是在已建立的哈夫曼樹中，從葉子結(jié)點(diǎn)開始，沿結(jié)點(diǎn)的雙親鏈域回退到根結(jié)點(diǎn)，沒回退一步，就走過了哈夫曼樹的一個(gè)分支，從而得到一位哈夫曼碼值，由于一個(gè)字符的哈夫曼編碼是從根結(jié)點(diǎn)到相應(yīng)葉子結(jié)點(diǎn)所經(jīng)過的路徑上各分支所組成的0、1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼位所求編碼的高位碼，所以設(shè)計(jì)如下數(shù)據(jù)類型：#defineMAXBIT10Typedefstruct{ Intbit[MAXBIT]； Intstart；}HCodeType；3、文件hfmtree.dat、codefile.dat和textfile.dat。2、功能（函數(shù)）設(shè)計(jì)（1）、初始化功能模塊。 此功能模塊的功能為從鍵盤接收字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值。（2）、建立哈夫曼樹的功能模塊。此模塊功能為使用1中得到的數(shù)據(jù)按照教材中的構(gòu)造哈夫曼樹的算法構(gòu)造哈夫曼樹，即將HuffNode數(shù)組中的各個(gè)位置的各個(gè)域都添上相關(guān)的值，并將這個(gè)結(jié)構(gòu)體數(shù)組存于文件hfmtree.dat中。（3）、建立哈夫曼編碼的功能模塊。此模塊功能為從文件hfmtree.dat中讀入相關(guān)的字符信息進(jìn)行哈夫曼編碼，然后將結(jié)果存入codefile.dat中，同時(shí)將字符與0、1代碼串的一一對(duì)應(yīng)關(guān)系打印到屏幕上。（4）、譯碼的功能模塊。此模塊功能為接收需要譯碼的0、1代碼串，按照3中建立的編碼規(guī)則將其翻譯成字符集中字符所組成的字符串形式，存入文件textfile.dat，同時(shí)將翻譯的結(jié)果在屏幕上打印輸出。（5）、打印哈夫曼樹的功能模塊。 此模塊功能為從HuffNode數(shù)組中讀入相關(guān)的結(jié)點(diǎn)信息，以圖形的方式將各個(gè)結(jié)點(diǎn)以及葉子結(jié)點(diǎn)的權(quán)值和左分支上的0和右分支上的1畫出來。四、實(shí)驗(yàn)結(jié)果（程序）及分析1、實(shí)驗(yàn)主要代碼typedefstruct/*結(jié)點(diǎn)結(jié)構(gòu)體*/{ stringhfmstr;/*結(jié)點(diǎn)內(nèi)容*/ intweight;/*結(jié)點(diǎn)權(quán)值*/intparent;intlchild;intrchild;}HNodeType;typedefstruct/*編碼結(jié)構(gòu)體*/{intbit[MAXBIT];intstart;}HCodeType;void