哈夫曼編碼譯碼器

1、沈陽(yáng)航空航天大學(xué)課課 程程 設(shè)設(shè) 計(jì)計(jì) 報(bào)報(bào) 告告課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)題目：哈夫曼編碼哈夫曼編碼/ /譯碼器譯碼器院（系）：計(jì)算機(jī)學(xué)院專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班 級(jí)：學(xué) 號(hào)：姓 名：指導(dǎo)教師：沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 I 目錄目錄沈陽(yáng)航空航天大學(xué)沈陽(yáng)航空航天大學(xué).I第第 1 章章 概要設(shè)計(jì)概要設(shè)計(jì).11.1 題目的內(nèi)容與要求.11.2 總體結(jié)構(gòu).1第第 2 章章 算法分析算法分析.22.1 核心算法思想.22.2 算法結(jié)構(gòu)定義.2第第 3 章章 詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì).33.1 功能流程.3第第 4 章章 系統(tǒng)實(shí)現(xiàn)系統(tǒng)實(shí)現(xiàn).54.1 錯(cuò)誤分析.54.2 運(yùn)行結(jié)果

2、.5參考文獻(xiàn)參考文獻(xiàn).8附附 錄錄.9沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 1 第 1 章 概要設(shè)計(jì)1.1 題目的內(nèi)容與要求題目的內(nèi)容與要求內(nèi)容：設(shè)計(jì)一個(gè)利用哈夫曼算法的編碼和譯碼系統(tǒng)，可以接收從鍵盤輸入的字符集大小、字符和權(quán)值信息，創(chuàng)建哈夫曼樹生成哈夫曼編碼并能對(duì)其進(jìn)行解碼。要求：1存儲(chǔ)結(jié)構(gòu)自定；2將生成的哈夫曼編碼與等長(zhǎng)編碼進(jìn)行比較，判斷優(yōu)劣；3給出動(dòng)態(tài)演示過(guò)程（選作） 。1.2 總體結(jié)構(gòu)總體結(jié)構(gòu)本程序主要分為 3 個(gè)模塊（功能模塊圖見(jiàn)圖 1.1）：主模塊，編碼模塊，譯碼模塊。主模塊：程序的主體部分，分別調(diào)用各個(gè)模塊，實(shí)現(xiàn)各項(xiàng)功能。編碼模塊：對(duì)每個(gè)出現(xiàn)的字符進(jìn)行編碼。譯碼模塊：將已有編碼譯成字符，

3、使之可以直接被讀出。 哈哈夫夫曼曼編編碼碼/ /譯譯碼碼器器主主模模塊塊編編碼碼模模塊塊譯譯碼碼模模塊塊 圖圖 1.1 功能模塊圖功能模塊圖沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 2 沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 3 第 2 章 算法分析2.1 核心算法思想核心算法思想哈夫曼樹的建立由赫夫曼算法的定義可知，初始森林中共有 n 棵只含有根結(jié)點(diǎn)的二叉樹。算法的第二步是：將當(dāng)前森林中的兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹，合并成一棵新的二叉樹；每合并一次，森林中就減少一棵樹，產(chǎn)生一個(gè)新結(jié)點(diǎn)。顯然要進(jìn)行 n1 次合并，所以共產(chǎn)生 n1 個(gè)新結(jié)點(diǎn)，它們都是具有兩個(gè)孩子的分支結(jié)點(diǎn)。由此可知，最終求得的哈夫曼樹中一共有 2n1

4、 個(gè)結(jié)點(diǎn)，其中 n 個(gè)結(jié)點(diǎn)是初始森林的 n 個(gè)孤立結(jié)點(diǎn)。并且哈夫曼樹中沒(méi)有度數(shù)為 1 的分支結(jié)點(diǎn)。我們可以利用一個(gè)大小為 2n-1 的一維數(shù)組來(lái)存儲(chǔ)哈夫曼樹中的結(jié)點(diǎn)。哈夫曼編碼是可變字長(zhǎng)編碼。編碼時(shí)借助哈夫曼樹，也即帶權(quán)路徑長(zhǎng)度最小的二叉樹，來(lái)建立編碼。譯碼的基本思想是：讀文件中編碼，并與原先生成的赫夫曼編碼表比較，遇到相等時(shí)，即取出其對(duì)應(yīng)的字符存入一個(gè)新串中。2.2 算法結(jié)構(gòu)定義算法結(jié)構(gòu)定義結(jié)構(gòu)體存儲(chǔ)表示typedef struct int weight;int parent,lchild,rchild; Htnode,*Hfmtree; /動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹typedef char

5、*Hfmcode; /動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈弗曼編碼表沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 4 第 3 章 詳細(xì)設(shè)計(jì)3.1 功能流程功能流程此流程圖為構(gòu)造哈夫曼樹的過(guò)程，輸入字符的次數(shù)為權(quán)值對(duì)每個(gè)結(jié)點(diǎn)賦值，構(gòu)造哈夫曼樹，如圖 3.1 開開始始以以讀讀入入字字符符次次數(shù)數(shù)對(duì)對(duì)各各結(jié)結(jié)點(diǎn)點(diǎn)賦賦初初值值并并令令i=2n-1i i為為0 0找找出出根根結(jié)結(jié)點(diǎn)點(diǎn)權(quán)權(quán)值值最最小小和和次次小小樹樹s1,s2兩兩樹樹合合并并成成新新樹樹n+i結(jié)結(jié)束束i i減減1 1NY圖圖 3.1 流程圖流程圖沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 5 此流程圖（圖 3.2）為對(duì)字符進(jìn)行哈夫曼編碼的過(guò)程，將字符轉(zhuǎn)化為哈夫曼編碼。 開開始始i i

6、= =n n第第一一個(gè)個(gè)字字符符，i=1結(jié)結(jié)點(diǎn)點(diǎn)是是否否是是根根結(jié)結(jié)點(diǎn)點(diǎn)雙雙親親結(jié)結(jié)點(diǎn)點(diǎn)的的左左結(jié)結(jié)點(diǎn)點(diǎn)是是否否等等于于該該結(jié)結(jié)點(diǎn)點(diǎn)記記編編碼碼0 0記記編編碼碼1 1i i= =i i+ +1 1結(jié)結(jié)束束將將得得到到的的編編碼碼存存儲(chǔ)儲(chǔ)Y YY YY YN NN NN圖圖 3.2 字符編碼模塊流程圖字符編碼模塊流程圖沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 6 沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 7 第 4 章 系統(tǒng)實(shí)現(xiàn)4.1 錯(cuò)誤分析錯(cuò)誤分析在此程序調(diào)試過(guò)程中主要遇到以下幾類問(wèn)題：1、本程序運(yùn)用了對(duì)文件進(jìn)行操作，一定要注意在操作文件是文件的位置，我在做次程序是就是因?yàn)椴僮鞯奈募恢缅e(cuò)了導(dǎo)致程序無(wú)法正常運(yùn)行。

7、2、在函數(shù)內(nèi)部有時(shí)需要多定義參數(shù)，注意參數(shù)的作用域，而且注意傳引用調(diào)用和傳值調(diào)用的區(qū)別，不能不正確的修改實(shí)參的值，否則會(huì)導(dǎo)致程序運(yùn)行的錯(cuò)誤。3、本程序用到的外部函數(shù)較多，在調(diào)用時(shí)一定要注意傳入的參數(shù)是否符合函數(shù)的定義，而且位置也不能錯(cuò)，這是引用函數(shù)要注意的一點(diǎn)。4、剛開始時(shí)清屏函數(shù)運(yùn)用出錯(cuò)，導(dǎo)致操作界面消失，使用戶無(wú)法操作，因此，在使用一些函數(shù)是一定要注意。4.2 運(yùn)行結(jié)果運(yùn)行結(jié)果運(yùn)行程序首先出現(xiàn)界面圖，如圖 4.2 所示。 圖圖 4.1 界面圖界面圖選擇操作 1 后，輸入相應(yīng)的字符大小，字符和權(quán)值，生成哈夫曼樹。系統(tǒng)會(huì)顯示每個(gè)字符的哈夫曼編碼，如圖 4.2 所示。沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告

8、 8 圖圖 4.2 程序運(yùn)行截圖程序運(yùn)行截圖選擇操作 2 后，輸入字符串，系統(tǒng)會(huì)顯示對(duì)字符串進(jìn)行哈弗曼編碼得到的哈弗曼編碼，顯示以下界面（圖 4.3）供用戶選擇。 圖圖 4.3 程序運(yùn)行截圖程序運(yùn)行截圖選擇操作 3 后，系統(tǒng)會(huì)顯示用哈夫曼編碼翻譯成的字符，顯示以下界面（圖4.4）供用戶選擇 圖圖 4.44.4 程序運(yùn)行截圖程序運(yùn)行截圖選擇操作 4 后，退出系統(tǒng)，顯示以下界面（圖 4.5）沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 9 圖圖 4.5 程序運(yùn)行截圖程序運(yùn)行截圖沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 10 參考文獻(xiàn)1 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)(C 語(yǔ)言版).清華大學(xué)出版社，20072 譚浩強(qiáng).C 語(yǔ)言程序設(shè)計(jì)教程.

9、高等教育出版社，20063 蘇仕華.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì).機(jī)械工業(yè)出版社，2007沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 11 附 錄源程序如下：#include#include#include#include#includetypedef struct /赫夫曼樹的結(jié)構(gòu)體char ch;int weight; /權(quán)值int parent,lchild,rchild;Htnode,*Hfmtree; /動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹typedef char *Hfmcode; /動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼編碼表void Select(Hfmtree &HT,int a,int *s1,int *s2) /Se

10、lect 函數(shù)，選出 HT 樹到 a 為止，權(quán)值最小且 parent 為 0 的 2 個(gè)節(jié)點(diǎn)int i,j,x,y;for(j=1;j=a;+j)if(HTj.parent=0)x=j;break;for(i=j+1;i=a;+i)if(HTi.weightHTx.weight&HTi.parent=0)x=i; /選出最小的節(jié)點(diǎn)沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 12 for(j=1;j=a;+j)if(HTj.parent=0&x!=j)y=j;break;for(i=j+1;i=a;+i)if(HTi.weighty)*s1=y;*s2=x;else*s1=x;*s2=y;vo

11、id Hfmcoding(Hfmtree &HT,Hfmcode &HC,int n) /構(gòu)建赫夫曼樹 HT，并求出 n沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 13 個(gè)字符的赫夫曼編碼 HCint i,start,c,f,m,w;int p1,p2;char *cd,z;if(n=1)return;m=2*n-1;HT=(Hfmtree)malloc(m+1)*sizeof(Htnode);for(i=1;i=n;+i) /初始化 n 個(gè)葉子結(jié)點(diǎn)printf(請(qǐng)輸入第%d 字符信息和權(quán)值：,i);scanf(%c%d,&z,&w);while(getchar()!=n)c

12、ontinue;HTi.ch=z;HTi.weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i=m;+i) /初始化其余的結(jié)點(diǎn)HTi.ch=0;沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 14 HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i=m;+i) /建立赫夫曼樹Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.we

13、ight+HTp2.weight;HC=(Hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1=0; /-從葉子到根逆向給出每個(gè)字符的哈夫曼編碼-for(i=1;ichoice; if(choice=1) /初始化赫夫曼樹coutn;Hfmcoding(HT,HC,n);for(i=1;i=n;+i)coutHTi.ch:HCiendl;output_file.open(hfmTree.txt);if(!output_file)coutcant oen file!endl; 沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)

14、告 17 for(i=1;i=n;i+)output_file(HTi.chHCi);output_file.close();printf(赫夫曼樹已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入 hfmTree.txt 文件中!n); else if(choice=2) /進(jìn)行編碼，并將字符放入A.txt，碼值放入 B.txt 中printf(請(qǐng)輸入字符：);gets(str);output_file.open(A.txt);if(!output_file)coutcant oen file!endl;output_filestrendl;output_file.close();output_file.open(

15、B.txt);if(!output_file)coutcant oen file!endl;for(i=0;istrlen(str);i+)for(j=0;j=n;+j)if(HTj.ch=stri)沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 18 output_fileHCj;break;output_file.close();coutn;printf(編碼完畢，并且已經(jīng)存入 B.txt 文件！n);input_file.open(B.txt); /從 B.txt 中讀入編碼，輸出在終端if(!input_file)coutcant oen file!code;cout編碼碼值為：codeendl;inp

16、ut_file.close(); else if(choice=3) /讀入 B.txt 中的編碼進(jìn)行譯碼，將譯出來(lái)的字符放入 Textfile.txt 中input_file.open(B.txt);if(!input_file)coutcant oen file!h;input_file.close();output_file.open(Textfile.txt);if(!output_file)沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 19 coutcant oen file!endl;k=0;while(hk!=0) /先用編碼中的前幾個(gè)和字符的編碼相比較，然后往后移for(i=1;i=n;i+)

17、l=k;for(j=0;jstrlen(HCi);j+,l+)hlj=hl;hlj=0;if(strcmp(HCi,hl)=0)output_fileHTi.ch;k=k+strlen(HCi);break;output_file.close();input_file.open(Textfile.txt);if(!input_file)coutcant oen file!h; couthendl;沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 20 input_file.close();printf(譯碼結(jié)束，字符已經(jīng)存入 Textfile.txt 文件中!n); else if(choice=4) exit(

18、0); else /如果選了選項(xiàng)之外的就讓用戶重新選擇printf(您沒(méi)有輸入正確的步驟，請(qǐng)重新輸入！);沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 21 課程設(shè)計(jì)總結(jié)：課程設(shè)計(jì)總結(jié)：通過(guò)近兩周的課程設(shè)計(jì)使我對(duì)哈夫曼樹以及哈夫曼編碼譯碼有了更深的認(rèn)識(shí)和理解，也使我更加明白哈夫曼編碼譯碼在信息技術(shù)中的重要性和地位。在做課設(shè)的過(guò)程中我也遇到了很多問(wèn)題：開始的時(shí)候，代碼中有許多的錯(cuò)誤，特別是有一個(gè)“無(wú)法找到文件”的錯(cuò)誤讓我束手無(wú)策，最后還是屏蔽了定義的四個(gè)頭文件然后慢慢地改正錯(cuò)誤才讓我又看到了希望。然后在實(shí)現(xiàn)文章的讀入時(shí)，由于對(duì)文件不是太熟悉，只好翻開 C 語(yǔ)言和 C+語(yǔ)言書本仿照其模式編寫，但后來(lái)進(jìn)入了死循環(huán)，最后的解決方式是在 main 函數(shù)里有一個(gè)控制語(yǔ)句使用不正確。我們遇到問(wèn)題很正常，說(shuō)明我們掌握的知