版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告書題目: 哈夫曼編碼/譯碼器 班級(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)目,直到選擇退出為止。利用哈夫曼樹編碼問題基本原理的應(yīng)用,撐握對(duì)樹的不同存儲(chǔ)結(jié)構(gòu)的定義和算法描述。學(xué)會(huì)構(gòu)造哈夫曼樹和哈夫曼編碼等主要算法。(二)題目要求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)值,建立哈夫曼樹;4) 編碼:利用建好的哈夫曼樹生成哈夫曼編碼;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分別表示哈夫曼樹中每個(gè)結(jié)點(diǎn)的權(quán)值、權(quán)重、雙親結(jié)點(diǎn)、左孩子、右孩子,再定義一個(gè)HTNode類型的數(shù)組ht30存放哈夫曼樹;另外定義一個(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ù)來構(gòu)造一棵哈夫曼樹,首先用一個(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)來構(gòu)造哈夫曼樹,在該循環(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)造二叉樹的結(jié)點(diǎn)中查找,由于只能在尚未構(gòu)造二叉樹的結(jié)點(diǎn)中查找,因此在for(k=0;k<=i-1;k+)
5、循環(huán)中加入一個(gè)if(htk.parent=-1)語(yǔ)句來判斷結(jié)點(diǎn)lnode和rnode是否已經(jīng)在二叉樹中,如果結(jié)點(diǎn)lnode和rnode在二叉樹中,則結(jié)點(diǎn)lnode和rnode的parent的值為其雙親結(jié)點(diǎn)在數(shù)組ht30中的序號(hào)就不會(huì)為-1了,在查找到htlnode和htrnode后將他們作為hti的左右子樹,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ù)來求哈夫曼編碼,由于求哈夫曼編碼只需求葉子結(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)行同樣的操作,直到無雙親結(jié)點(diǎn)為止,最后讓start指向哈夫曼編碼最開始字符。因此在函數(shù)中設(shè)置一個(gè)for(i=0;i<n;i+)循環(huán),在循環(huán)中設(shè)置一個(gè)while(f!=-1)循環(huán)語(yǔ)句來判斷循環(huán)是否到了根結(jié)點(diǎn),再在while(f!=-1)中設(shè)置一個(gè)if(htf.lchild=c)語(yǔ)句來判斷該處理左孩子結(jié)點(diǎn)還是該處理右孩子結(jié)點(diǎn)。
7、最后用這個(gè)for(i=0;i<n;i+)循環(huán)來根據(jù)哈夫曼樹求出哈夫曼編碼。(5)最后編寫CodeOutput(n,hcd)函數(shù),首先利用for(i=0;i<n;i+)循環(huán)和for(j=hcdi.start;j<=n;j+)循環(huán)來實(shí)現(xiàn)所有字符的哈夫曼編碼的輸出;再利用for(i=0;i<n;i+)循環(huán)和for(j=hcdi.start;j<=n;j+)循環(huán)來實(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é)束開始圖2.1主函數(shù)流程圖(2)哈夫曼編碼算法流程圖,如圖2.2(3)構(gòu)造樹函數(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ù)流程圖3、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)31抽象數(shù)據(jù)類型定義(1)樹的抽象數(shù)據(jù)類型定義32模塊劃分本程序包括三個(gè)模塊:(1)主程序模塊void main()初始化;構(gòu)造哈夫曼樹;求哈
9、夫曼編碼;哈夫曼編碼輸出;(2)哈夫曼模塊實(shí)現(xiàn)哈夫曼樹的抽象數(shù)據(jù)類型(3)求哈夫曼編碼模塊實(shí)現(xiàn)求哈夫曼編碼算法的數(shù)據(jù)類型4、主要功能邏輯過程和實(shí)現(xiàn)算法41數(shù)據(jù)類型的定義(1)哈夫曼樹類型typedef struct/構(gòu)造樹 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)造哈弗曼樹 CreateHCode(ht,hcd,n);/哈弗曼編碼算法 CodeOutput(n,hcd);/打印哈弗曼編碼將打印出編碼,和每一個(gè)字符的編碼
11、return 0;(2)構(gòu)造哈夫曼樹void CreateHT(HTNode ht,int n)/構(gòu)造一棵哈夫曼樹 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)造哈弗曼樹 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)造的二叉樹結(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ù)哈弗曼樹求哈弗曼編碼 hc.start=n; c=i; f=hti.parent; while (f!=-1)/循環(huán)知道樹的根結(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指向哈弗曼編碼最開始的位置 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)的哈夫曼樹如圖6.1。04F1 C6 H3E101010107 I2 D0110 B5 G01圖6.1構(gòu)造哈夫曼樹及哈夫曼編碼三、小組成員分工說明獨(dú)立完成四、課程設(shè)計(jì)總結(jié)或結(jié)論1 課程設(shè)計(jì)過程中出現(xiàn)的技術(shù)難點(diǎn)和解決方法:1.1技術(shù)難點(diǎn)。(1) 輸入的字符個(gè)數(shù)不確定,可跟據(jù)情況輸入。(2) 哈夫曼樹的類型。(3) 哈夫曼編碼類型。(4) 構(gòu)造哈夫曼樹算法。(5) 計(jì)算哈夫曼編碼算法。1.2解決方法。(1)通過向老師虛心學(xué)習(xí)請(qǐng)教.(2)和同學(xué)們細(xì)心交流,認(rèn)真討論。(3)上網(wǎng)參考,吸取別人的精華。2 課程設(shè)計(jì)期間的主要收獲:通過這次課程設(shè)計(jì)使我充分的理解了用哈夫曼樹再編碼問題中基本原理的應(yīng)用,知道了樹的不同存儲(chǔ)結(jié)構(gòu)的定義和算法描述,同時(shí)也學(xué)會(huì)了編寫簡(jiǎn)單的哈夫曼編碼問題的程序。雖然此次的程序不是很完備,但是總體還是一個(gè)比較能體現(xiàn)數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)的程序,當(dāng)然只是相對(duì)于我這個(gè)學(xué)者來說。在剛開始
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年物業(yè)與業(yè)主社區(qū)養(yǎng)老服務(wù)體系合同3篇
- 二零二五版高速公路監(jiān)控系統(tǒng)集成采購(gòu)與安裝合同2篇
- 2025版定制化鐵藝工程勞務(wù)分包服務(wù)合同3篇
- 安徽省高三上學(xué)期校聯(lián)考化學(xué)試卷及答案(含答案解析)
- 二零二五年度木地板產(chǎn)品回收與再利用合同3篇
- 動(dòng)漫產(chǎn)業(yè)法律法規(guī)與版權(quán)保護(hù)考核試卷
- 城市規(guī)劃與城市能源結(jié)構(gòu)調(diào)整考核試卷
- 塑料加工過程中的物料管理與優(yōu)化考核試卷
- 二零二五版養(yǎng)老設(shè)施建設(shè)項(xiàng)目合伙承包合同樣本3篇
- 2025年度某某酒店電梯設(shè)施維護(hù)保養(yǎng)合同2篇
- 勞務(wù)協(xié)議范本模板
- 2025大巴車租車合同范文
- 老年上消化道出血急診診療專家共識(shí)2024
- 人教版(2024)數(shù)學(xué)七年級(jí)上冊(cè)期末測(cè)試卷(含答案)
- 2024年國(guó)家保密培訓(xùn)
- 磚廠承包合同簽訂轉(zhuǎn)讓合同
- 思政課國(guó)內(nèi)外研究現(xiàn)狀分析
- 皮膚感染的護(hù)理診斷與護(hù)理措施
- 2023年公務(wù)員多省聯(lián)考《申論》題(廣西B卷)
- EPC總承包項(xiàng)目中的質(zhì)量管理體系
- 高中物理考試成績(jī)分析報(bào)告
評(píng)論
0/150
提交評(píng)論