哈夫曼編碼譯碼器

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

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

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

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

5、*Hfmcode; /動態(tài)分配數(shù)組存儲哈弗曼編碼表沈陽航空航天大學(xué)課程設(shè)計報告 4 第 3 章 詳細(xì)設(shè)計3.1 功能流程功能流程此流程圖為構(gòu)造哈夫曼樹的過程，輸入字符的次數(shù)為權(quán)值對每個結(jié)點(diǎn)賦值，構(gòu)造哈夫曼樹，如圖 3.1 開開始始以以讀讀入入字字符符次次數(shù)數(shù)對對各各結(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 流程圖流程圖沈陽航空航天大學(xué)課程設(shè)計報告 5 此流程圖（圖 3.2）為對字符進(jìn)行哈夫曼編碼的過程，將字符轉(zhuǎn)化為哈夫曼編碼。 開開始始i i

6、= =n n第第一一個個字字符符，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é)束束將將得得到到的的編編碼碼存存儲儲Y YY YY YN NN NN圖圖 3.2 字符編碼模塊流程圖字符編碼模塊流程圖沈陽航空航天大學(xué)課程設(shè)計報告 6 沈陽航空航天大學(xué)課程設(shè)計報告 7 第 4 章 系統(tǒng)實現(xiàn)4.1 錯誤分析錯誤分析在此程序調(diào)試過程中主要遇到以下幾類問題：1、本程序運(yùn)用了對文件進(jìn)行操作，一定要注意在操作文件是文件的位置，我在做次程序是就是因為操作的文件位置錯了導(dǎo)致程序無法正常運(yùn)行。

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

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

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

10、 函數(shù)，選出 HT 樹到 a 為止，權(quán)值最小且 parent 為 0 的 2 個節(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)沈陽航空航天大學(xué)課程設(shè)計報告 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;void Hfmcoding

11、(Hfmtree &HT,Hfmcode &HC,int n) /構(gòu)建赫夫曼樹 HT，并求出 n沈陽航空航天大學(xué)課程設(shè)計報告 13 個字符的赫夫曼編碼 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 個葉子結(jié)點(diǎn)printf(請輸入第%d 字符信息和權(quán)值：,i);scanf(%c%d,&z,&w);while(getchar()!=n)continue;HTi.ch=z;HTi.weight=

12、w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i=m;+i) /初始化其余的結(jié)點(diǎn)HTi.ch=0;沈陽航空航天大學(xué)課程設(shè)計報告 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.weight+HTp2.weight;HC=(Hfmcode)malloc(

13、n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1=0; /-從葉子到根逆向給出每個字符的哈夫曼編碼-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; 沈陽航空航天大學(xué)課程設(shè)計報告 17 for(i=1;i=n;i+)output_file(HTi.

14、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(請輸入字符：);gets(str);output_file.open(A.txt);if(!output_file)coutcant oen file!endl;output_filestrendl;output_file.close();output_file.open(B.txt);if(!output_file)coutcant oen

15、file!endl;for(i=0;istrlen(str);i+)for(j=0;j=n;+j)if(HTj.ch=stri)沈陽航空航天大學(xué)課程設(shè)計報告 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;input_file.close(); else if(choice=3) /

16、讀入 B.txt 中的編碼進(jìn)行譯碼，將譯出來的字符放入 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)沈陽航空航天大學(xué)課程設(shè)計報告 19 coutcant oen file!endl;k=0;while(hk!=0) /先用編碼中的前幾個和字符的編碼相比較，然后往后移for(i=1;i=n;i+)l=k;for(j=0;jstrlen(HCi);j+,l+)hlj=h

17、l;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;沈陽航空航天大學(xué)課程設(shè)計報告 20 input_file.close();printf(譯碼結(jié)束，字符已經(jīng)存入 Textfile.txt 文件中!n); else if(choice=4) exit(0); else /如果選了選項之外的就讓用戶重新選擇printf(您沒

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