哈夫曼樹(shù)的課程設(shè)計(jì)報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告書(shū)題目： 哈夫曼編碼/譯碼器 班級(jí)： 學(xué)號(hào)： 姓名： 田 歡 指導(dǎo)教師： 龔 丹 周期： 2011-12-19至2011-12-23 成績(jī)： 年 月 日專心-專注-專業(yè)一、課程設(shè)計(jì)的目的與要求 （一）課程設(shè)計(jì)目的與任務(wù)（參考已發(fā)文檔自行編輯，但不少于100字）設(shè)計(jì)一個(gè)利用哈夫曼算法的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理以下項(xiàng)目，直到選擇退出為止。利用哈夫曼樹(shù)編碼問(wèn)題基本原理的應(yīng)用，撐握對(duì)樹(shù)的不同存儲(chǔ)結(jié)構(gòu)的定義和算法描述。學(xué)會(huì)構(gòu)造哈夫曼樹(shù)和哈夫曼編碼等主要算法。（二）題目要求1) 將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt，位于執(zhí)

2、行程序的當(dāng)前目錄中) 2) 分別采用動(dòng)態(tài)和靜態(tài)存儲(chǔ)結(jié)構(gòu)3) 初始化：鍵盤輸入字符集大小n、n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)；4) 編碼：利用建好的哈夫曼樹(shù)生成哈夫曼編碼；5) 輸出編碼；6) 設(shè)字符集及頻度如下表：字符 空格 A B C D E F G H I J K L M頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 1二、設(shè)計(jì)正文1 系統(tǒng)分析（1）定義一個(gè)變量名為HTNo

3、de的結(jié)構(gòu)體，用該結(jié)構(gòu)體中的char data、int weight、int parent、int lchild、int rchild分別表示哈夫曼樹(shù)中每個(gè)結(jié)點(diǎn)的權(quán)值、權(quán)重、雙親結(jié)點(diǎn)、左孩子、右孩子，再定義一個(gè)HTNode類型的數(shù)組ht30存放哈夫曼樹(shù)；另外定義一個(gè)變量名為HCode的結(jié)構(gòu)體，采用HCode類型變量的cdstartcdn存放當(dāng)前結(jié)點(diǎn)的哈夫曼編碼、最后定義一個(gè)HCode類型的數(shù)組hcd30的數(shù)組用于存放當(dāng)前葉子結(jié)點(diǎn)hti的哈夫曼編碼。（2）編寫CodeInput(n,ht)函數(shù)并在函數(shù)中設(shè)置一個(gè)for(i=0;n;+)循環(huán)，首先輸入n個(gè)字符，再利用函數(shù)中的for(i=0;<

4、n;+)循環(huán)實(shí)現(xiàn)對(duì)這n個(gè)字符的權(quán)值的輸入。（3）編寫CreateHT(ht,n)函數(shù)來(lái)構(gòu)造一棵哈夫曼樹(shù)，首先用一個(gè)for(i=0;<2*n-1;+)循環(huán)將所有2n-1個(gè)結(jié)點(diǎn)的parent、lchild、rchild域均置初值為-1；再用一個(gè)for(i=n;<2*n-1;+)循環(huán)來(lái)構(gòu)造哈夫曼樹(shù)，在該循環(huán)中首先令lnode和rnode為最小權(quán)值的兩個(gè)結(jié)點(diǎn)位置且其域值均為-1，再用一個(gè)for(k=0;<=i-1;k+)循環(huán)在數(shù)組ht30中尋找權(quán)值最小的兩個(gè)結(jié)點(diǎn)并且只能在尚未構(gòu)造二叉樹(shù)的結(jié)點(diǎn)中查找，由于只能在尚未構(gòu)造二叉樹(shù)的結(jié)點(diǎn)中查找，因此在for(k=0;k<=i-1;k+)

5、循環(huán)中加入一個(gè)if(htk.parent=-1)語(yǔ)句來(lái)判斷結(jié)點(diǎn)lnode和rnode是否已經(jīng)在二叉樹(shù)中，如果結(jié)點(diǎn)lnode和rnode在二叉樹(shù)中，則結(jié)點(diǎn)lnode和rnode的parent的值為其雙親結(jié)點(diǎn)在數(shù)組ht30中的序號(hào)就不會(huì)為-1了，在查找到htlnode和htrnode后將他們作為hti的左右子樹(shù)，htlnode和htrnode的雙親結(jié)點(diǎn)置為hti，且hti.weight=htlnode.weight+ht rnode.weight。如此處理下去，直到所2n-1個(gè)結(jié)點(diǎn)處理完畢。（4）編寫CreateHCode(ht,hcd,n)函數(shù)來(lái)求哈夫曼編碼，由于求哈夫曼編碼只需求葉子結(jié)點(diǎn)的哈夫

6、曼編碼。對(duì)于當(dāng)前葉子結(jié)點(diǎn)hti，首先將對(duì)應(yīng)的哈夫曼編碼hcdi的start域值置初值n，找其雙親結(jié)點(diǎn)htf，若當(dāng)前結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子結(jié)點(diǎn)，則在hcdi的cd數(shù)組中添加0，若當(dāng)前結(jié)點(diǎn)是雙親的右孩子結(jié)點(diǎn)，則在hcdi的cd數(shù)組中添加1，將start域減1。再對(duì)雙親結(jié)點(diǎn)進(jìn)行同樣的操作，直到無(wú)雙親結(jié)點(diǎn)為止，最后讓start指向哈夫曼編碼最開(kāi)始字符。因此在函數(shù)中設(shè)置一個(gè)for(i=0;i<n;i+)循環(huán)，在循環(huán)中設(shè)置一個(gè)while(f!=-1)循環(huán)語(yǔ)句來(lái)判斷循環(huán)是否到了根結(jié)點(diǎn)，再在while(f!=-1)中設(shè)置一個(gè)if(htf.lchild=c)語(yǔ)句來(lái)判斷該處理左孩子結(jié)點(diǎn)還是該處理右孩子結(jié)點(diǎn)。

7、最后用這個(gè)for(i=0;i<n;i+)循環(huán)來(lái)根據(jù)哈夫曼樹(shù)求出哈夫曼編碼。（5）最后編寫CodeOutput(n,hcd)函數(shù)，首先利用for(i=0;i<n;i+)循環(huán)和for(j=hcdi.start;j<=n;j+)循環(huán)來(lái)實(shí)現(xiàn)所有字符的哈夫曼編碼的輸出；再利用for(i=0;i<n;i+)循環(huán)和for(j=hcdi.start;j<=n;j+)循環(huán)來(lái)實(shí)現(xiàn)每個(gè)字符的序號(hào)和哈夫曼編碼的輸出。2 功能詳細(xì)描述及框圖（1）主函數(shù)流程圖如圖2.1Int I,f,c;i+Hc.start+;multiplexi=0hc.start=n;c=i;i<nf!=-1圖2

8、.2哈夫曼編碼算法流程圖Int i;scanf(“%d”,&htt.wei+i<n結(jié)束開(kāi)始圖2.1主函數(shù)流程圖（2）哈夫曼編碼算法流程圖，如圖2.2（3）構(gòu)造樹(shù)函數(shù)流程圖，如圖2.3Int k,lnode,mode;Hti.parent=hti.childi+i=nHtlnode,parent=i;Min1=min2=32767Multiplexi=0;i<2*2*n-1i<2*n-1i+圖2.3構(gòu)造樹(shù)函數(shù)流程圖3、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)31抽象數(shù)據(jù)類型定義（1）樹(shù)的抽象數(shù)據(jù)類型定義32模塊劃分本程序包括三個(gè)模塊：（1）主程序模塊void main()初始化；構(gòu)造哈夫曼樹(shù)；求哈

9、夫曼編碼；哈夫曼編碼輸出；（2）哈夫曼模塊實(shí)現(xiàn)哈夫曼樹(shù)的抽象數(shù)據(jù)類型（3）求哈夫曼編碼模塊實(shí)現(xiàn)求哈夫曼編碼算法的數(shù)據(jù)類型4、主要功能邏輯過(guò)程和實(shí)現(xiàn)算法41數(shù)據(jù)類型的定義（1）哈夫曼樹(shù)類型typedef struct/構(gòu)造樹(shù) char data;/結(jié)點(diǎn)權(quán)值 int weight;/權(quán)重 int parent;/雙親結(jié)點(diǎn) int lchild;/左孩子 int rchild;/右孩子 HTNode; HTNode ht30;（2）求哈夫曼編碼類型typedef struct char cd30;/存放當(dāng)前結(jié)點(diǎn)的哈弗曼編碼 int start;/cdstartcdn存放哈弗曼碼 HCode; HCo

10、de hcd30;42主要模塊的算法描述（1）主函數(shù)int main() int n; printf("請(qǐng)輸入要輸入的字符數(shù)量n:");/讀入字符的個(gè)數(shù) while(scanf("%d",&n),n!=-1)/初始化 printf("請(qǐng)輸入n個(gè)字符和n個(gè)權(quán)值n"); CodeInput(n,ht);/輸入數(shù)據(jù)函數(shù)，將讀入n個(gè)字符和權(quán)重 CreateHT(ht,n);/構(gòu)造哈弗曼樹(shù) CreateHCode(ht,hcd,n);/哈弗曼編碼算法 CodeOutput(n,hcd);/打印哈弗曼編碼將打印出編碼，和每一個(gè)字符的編碼

11、return 0;（2）構(gòu)造哈夫曼樹(shù)void CreateHT(HTNode ht,int n)/構(gòu)造一棵哈夫曼樹(shù) int i,k,lnode,rnode; int min1,min2; for (i=0;i<2*n-1;i+)/所有結(jié)點(diǎn)的相關(guān)域置初值-1 hti.parent=hti.lchild=hti.rchild=-1; for (i=n;i<2*n-1;i+)/構(gòu)造哈弗曼樹(shù) min1=min2=32767;/lnode和rnode為最小權(quán)值的兩個(gè)結(jié)點(diǎn)位置 lnode=rnode=-1; for (k=0;k<=i-1; k+)/在ht中查找權(quán)值的最小的兩個(gè)結(jié)點(diǎn) if

12、 (htk.parent=-1)/只在未構(gòu)造的二叉樹(shù)結(jié)點(diǎn)中查找 if (htk.weight<min1) min2=min1;rnode=lnode; min1=htk.weight; lnode=k; else if (htk.weight<min2) min2=htk.weight; rnode=k; htlnode.parent=i; htrnode.parent=i; hti.weight=htlnode.weight+htrnode.weight; hti.lchild=lnode; hti.rchild=rnode;/ht為雙親結(jié)點(diǎn) （3）利用哈夫曼編碼算法哈夫曼編碼v

13、oid CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for(i=0; i<n; i+)/根據(jù)哈弗曼樹(shù)求哈弗曼編碼 hc.start=n; c=i; f=hti.parent; while (f!=-1)/循環(huán)知道樹(shù)的根結(jié)點(diǎn) if(htf.lchild=c) hc.cdhc.start-='0'/處理左孩子結(jié)點(diǎn) else hc.cdhc.start-='1'/處理右孩子結(jié)點(diǎn) c=f; f=htf.parent; hc.start+;/start指向哈弗曼編碼最開(kāi)始的位置 hcdi=h

14、c; 5、界面設(shè)計(jì)6、系統(tǒng)測(cè)試測(cè)試數(shù)據(jù)及結(jié)果如下： 結(jié)果分析：首先確定要輸入的字符數(shù)量n為8，然后分別輸入這8個(gè)字符和這8個(gè)字符的權(quán)值，且輸入的這8個(gè)字符分別為B、C、D、E、F、G、H、I而這8個(gè)字符對(duì)應(yīng)的權(quán)值分別為13、22、32、103、21、15、47、57。其次根據(jù)輸出的結(jié)果可知：所有字符的哈夫曼為011。其中序號(hào)0表示字符B，其哈夫曼編碼為0010；序號(hào)1表示字符C，其哈夫曼編碼為110；序號(hào)2表示字符D，其哈夫曼編碼為010；序號(hào)3表示字符E，其哈夫曼編碼為0011；序號(hào)4表示字符F，其哈夫曼編碼為111；序號(hào)5表示字符G，其哈夫曼編碼為10；序號(hào)6表示字符H，其哈夫曼編碼為00

15、0；序號(hào)7表字符I，其哈夫曼編碼為011，這個(gè)8個(gè)字符 對(duì)應(yīng)的哈夫曼樹(shù)如圖6.1。04F1 C6 H3E101010107 I2 D0110 B5 G01圖6.1構(gòu)造哈夫曼樹(shù)及哈夫曼編碼三、小組成員分工說(shuō)明獨(dú)立完成四、課程設(shè)計(jì)總結(jié)或結(jié)論1 課程設(shè)計(jì)過(guò)程中出現(xiàn)的技術(shù)難點(diǎn)和解決方法：1.1技術(shù)難點(diǎn)。（1） 輸入的字符個(gè)數(shù)不確定，可跟據(jù)情況輸入。（2） 哈夫曼樹(shù)的類型。（3） 哈夫曼編碼類型。（4） 構(gòu)造哈夫曼樹(shù)算法。（5） 計(jì)算哈夫曼編碼算法。1.2解決方法。（1）通過(guò)向老師虛心學(xué)習(xí)請(qǐng)教.（2）和同學(xué)們細(xì)心交流，認(rèn)真討論。（3）上網(wǎng)參考，吸取別人的精華。2 課程設(shè)計(jì)期間的主要收獲：通過(guò)這次課程設(shè)計(jì)使我充分的理解了用哈夫曼樹(shù)再編碼問(wèn)題中基本原理的應(yīng)用，知道了樹(shù)的不同存儲(chǔ)結(jié)構(gòu)的定義和算法描述，同時(shí)也學(xué)會(huì)了編寫簡(jiǎn)單的哈夫曼編碼問(wèn)題的程序。雖然此次的程序不是很完備，但是總體還是一個(gè)比較能體現(xiàn)數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)的程序，當(dāng)然只是相對(duì)于我這個(gè)學(xué)者來(lái)說(shuō)。在剛開(kāi)始