1、數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計報告書題目哈夫曼編碼/譯碼器班級：學(xué)號：姓名：田歡 指導(dǎo)教師：龔丹周期：2011-12-19 至 2011-12-23成績：1_SI年月日來源：網(wǎng)絡(luò)轉(zhuǎn)載、課程設(shè)計的目的與要求(一) 課程設(shè)計目的與任務(wù)(參考已發(fā)文檔自行編輯，但不少于100 字)設(shè)計一個利用哈夫曼算法的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理以下項目，直到選擇退出為止。利用哈夫曼樹編碼問題基本原理的應(yīng)用， 撐握對樹的不同存儲結(jié)構(gòu)的定義和算法描述。學(xué)會構(gòu)造哈夫曼樹和哈夫 曼編碼等主要算法。(二) 題目要求1) 將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt,位于執(zhí)行程序的當 前目錄中)2) 分別采用動態(tài)和靜態(tài)存儲

2、結(jié)構(gòu)3) 初始化：鍵盤輸入字符集大小n、n個字符和n個權(quán)值，建立哈夫 曼樹；4) 編碼：利用建好的哈夫曼樹生成哈夫曼編碼；5) 輸出編碼；6) 設(shè)字符集及頻度如下表：字符空格 ABCDEFGHIJKLM頻度 1866413223210321154757153220字符 NOPQRSTUVWXYZ頻度 5763151485180238181161二、設(shè)計正文1系統(tǒng)分析(1) 定義一個變量名為HTNode!勺結(jié)構(gòu)體，用該結(jié)構(gòu)體中的chardata、intweight、intparent 、intlchild、intrchild分別表示哈夫曼樹中每個結(jié)點的權(quán)值、權(quán)重、雙親結(jié)點、左孩子、右孩子，再定義

3、 一個HTNode類型的數(shù)組ht30存放哈夫曼樹；另外定義一個變量名為 HCode勺結(jié)構(gòu)體，采用HCode類型變量的cdstartcdn存放當前結(jié)點的哈夫曼編碼、最后定義一個 HCode類型的數(shù)組hcd30的數(shù)組用于存 放當前葉子結(jié)點hti的哈夫曼編碼。(2) 編寫CodeInput(n,ht) 函數(shù)并在函數(shù)中設(shè)置一個 for(i=0;n;+)循環(huán)，首先輸入n個字符，再利用函數(shù)中的for(i=0;n;+)循環(huán)實現(xiàn)對這n個字符的權(quán)值的輸入。(3) 編寫CreateHT(ht,n)函數(shù)來構(gòu)造一棵哈夫曼樹，首先用一個for(i=0;2* n-1;+)循環(huán)將所有 2n-1 個結(jié)點的 pare nt、l

4、child 、rchild域均置初值為-1 ;再用一個for(i=n;2*n-1;+)循環(huán)來構(gòu)造哈夫曼樹，在該循環(huán)中首先令lnode和rnode為最小權(quán)值的兩個結(jié)點位置且其域值 均為-1，再用一個for(k=0;=i-1;k+)循環(huán)在數(shù)組ht30中尋找權(quán)值最小的兩個結(jié)點并且只能在尚未構(gòu)造二叉樹的結(jié)點中查找，由于只能在尚 未構(gòu)造二叉樹的結(jié)點中查找，因此在for(k=0;k=i-1;k+)循環(huán)中加入一個if(htk.pare nt=-1)語句來判斷結(jié)點In ode和rnode是否已經(jīng)在二叉樹中，如果結(jié)點In ode和rnode在二叉樹中，則結(jié)點In ode和rnode 的parent的值為其雙親結(jié)

5、點在數(shù)組ht30中的序號就不會為-1 了，在 查找到htlnode和htrnode后將他們作為hti的左右子樹， ht In ode和htrnode的雙親結(jié)點置為hti，且 hti.weight=htl node.weight+htrnode.weight。如此處理下去，直到所2n-1個結(jié)點處理完畢。(4) 編寫CreateHCode(ht,hcd,n)函數(shù)來求哈夫曼編碼，由于求哈夫曼編碼只需求葉子結(jié)點的哈夫曼編碼。對于當前葉子結(jié)點hti，首先將對應(yīng)的哈夫曼編碼hcdi的start域值置初值n，找其雙親結(jié)點 htf，若當前結(jié)點是雙親結(jié)點的左孩子結(jié)點，則在hcdi的cd數(shù)組中添加0,若當前結(jié)點是

6、雙親的右孩子結(jié)點，則在hcdi的cd數(shù)組中添加 1，將start域減1。再對雙親結(jié)點進行同樣的操作，直到無雙親結(jié)點為 止，最后讓start指向哈夫曼編碼最開始字符。因此在函數(shù)中設(shè)置一個 for(i=0;in;i+)循環(huán)，在循環(huán)中設(shè)置一個while(f!=-1) 循環(huán)語句來判斷循環(huán)是否到了根結(jié)點，再在while(f!=-1)中設(shè)置一個if(htf.lchild=c)語句來判斷該處理左孩子結(jié)點還是該處理右孩子結(jié)點。最后用這個for(i=0;in;i+)循環(huán)來根據(jù)哈夫曼樹求出哈夫曼編碼。(5) 最后編寫 CodeOutput(n,hcd)函數(shù)，首先利用 for(i=0;in;i+)循環(huán)和for(j=

7、hcdi.start;j=n;j+)循環(huán)來實現(xiàn)所有字符的哈夫曼編碼的輸出；再利用for(i=0;in;i+)循環(huán)和for(j=hcdi.start;j=n;j+)循環(huán)來實現(xiàn)每個字符的序號和哈夫曼編碼的輸出。2功能詳細描述及框圖I(1)主函數(shù)流程圖如圖2.1來源：網(wǎng)絡(luò)轉(zhuǎn)載開始seanf( %d”,&htt.we1 rInti;11In tl,f,c;i=0Jk.i+hc.start=n ;c=i;multiplex結(jié)束圖2.1主函數(shù)流程圖I r-Hc.start+;i+圖2.2哈夫曼編碼算法流程圖(2) 哈夫曼編碼算法流程圖，如圖2.2(3) 構(gòu)造樹函數(shù)流程圖，如圖2.3圖2.3構(gòu)造樹函數(shù)流程圖

8、3、數(shù)據(jù)結(jié)構(gòu)設(shè)計3. 1抽象數(shù)據(jù)類型定義(1) 樹的抽象數(shù)據(jù)類型定義3. 2模塊劃分本程序包括三個模塊：(1) 主程序模塊voidmai n()初始化；構(gòu)造哈夫曼樹；求哈夫曼編碼；哈夫曼編碼輸出；(2) 哈夫曼模塊實現(xiàn)哈夫曼樹的抽象數(shù)據(jù)類型(3) 求哈夫曼編碼模塊實現(xiàn)求哈夫曼編碼算法的數(shù)據(jù)類型4、主要功能邏輯過程和實現(xiàn)算法4. 1數(shù)據(jù)類型的定義(1) 哈夫曼樹類型typedefstruct構(gòu)造樹chardata;/ 結(jié)點權(quán)值 in tweight;/權(quán)重in tpare nt;雙親結(jié)點in tlchild;/左孩子in trchild;/右孩子HTNode;HTNodeht30;(2) 求哈夫

9、曼編碼類型typedefstructcharcd30;/存放當前結(jié)點的哈弗曼編碼in tstart;/cdstartcd n存放哈弗曼碼HCode;HCodehcd30;4. 2主要模塊的算法描述(1) 主函數(shù)in tma in()intn;prin tf(請輸入要輸入的字符數(shù)量n:);/讀入字符的個數(shù)while(sca nf(%d,&n), n!=-1)初始化printf( 請輸入n個字符和n個權(quán)值n);Codelnput(n,ht);輸入數(shù)據(jù)函數(shù)，將讀入n個字符和權(quán)重CreateHT(ht, n);構(gòu)造哈弗曼樹CreateHCode(ht,hcd, n);哈弗曼編碼算法CodeOutput

10、( n,hcd);打印哈弗曼編碼將打印出編碼，和每一個字符的編碼return。；(2) 構(gòu)造哈夫曼樹voidCreateHT(HTNodeht,i ntn)構(gòu)造一棵哈夫曼樹in ti,k ,lno de,r no de;in tmi n1,mi n2;for(i=0;i2*n-1;i+)所有結(jié)點的相關(guān)域置初值-1hti.pare nt=hti.lchild=hti.rchild=-1;for(i=n;i2* n-1;i+)構(gòu)造哈弗曼樹min仁min2=32767;/lnode和rnode為最小權(quán)值的兩個結(jié)點位置Ino de=r no de=-1;for(k=0;k=i-1;k+)在ht中查找權(quán)

11、值的最小的兩個結(jié)點if(htk.pare nt=-1)只在未構(gòu)造的二叉樹結(jié)點中查找if(htk.weightmi n1)min 2=mi n1;rno de=l no de;min 1=htk.weight; Ino de=k;elseif(htk.weightmi n2)mi n2=htk.weight;rnode=k;ht Ino de.pare nt=i;htr no de.pare nt=i; hti.weight=ht Ino de.weight+htr no de.weight; hti.lchild=l node;hti.rchild=rnode;/ht為雙親結(jié)點(3) 利用哈夫

12、曼編碼算法哈夫曼編碼 voidCreateHCode(HTNodeht,HCodehcd,i ntn)in ti,f,c;HCodehc;for(i=0;i n;i+)根據(jù)哈弗曼樹求哈弗曼編碼hc.start=n ;c=i;f=hti.pare nt;while(f!=-1)循環(huán)知道樹的根結(jié)點if(htf.lchild=c)hc.cdhc.start-=O;處理左孩子結(jié)點elsehc.cdhc.start-=1;處理右孩子結(jié)點c=f;f=htf.pare nt;hc.start+;/start指向哈弗曼編碼最開始的位置hcdi=hc;5、界面設(shè)計6、系統(tǒng)測試測試數(shù)據(jù)及結(jié)果如下：對應(yīng)的哈夫曼樹如

13、圖6.1 o圖6.1構(gòu)造哈夫曼樹及哈夫曼編三、 小組成員分工說明碼獨立完成四、課程設(shè)計總結(jié)或結(jié)論1課程設(shè)計過程中出現(xiàn)的技術(shù)難點和解決方法：1.1技術(shù)難點。（1）輸入的字符個數(shù)不確定，可跟據(jù)情況輸入。（2）哈夫曼樹的類型。（3）哈夫曼編碼類型。（4）構(gòu)造哈夫曼樹算法。（5）計算哈夫曼編碼算法。1.2解決方法。（1）通過向老師虛心學(xué)習(xí)請教（2）和同學(xué)們細心交流，認真討論。（3）上網(wǎng)參考，吸取別人的精華。2課程設(shè)計期間的主要收獲：通過這次課程設(shè)計使我充分的理解了用哈夫曼樹再編碼問題中基本 原理的應(yīng)用，知道了樹的不同存儲結(jié)構(gòu)的定義和算法描述，同時也學(xué)會 了編寫簡單的哈夫曼編碼問題的程序。雖然此次的程序不是很完備，但 是總體還是一個比較能體現(xiàn)數(shù)據(jù)結(jié)構(gòu)知識點的程序，當然只是相對于我 這個學(xué)者來說。在剛開始編程的時候，我感到很茫然，無從下手。但是 困難是可以解決的，只要通過努力，向老師虛心學(xué)習(xí)請教，