哈夫曼編碼譯碼器

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

2、.9第 1 章 概要設計1.1 題目的內(nèi)容與要求題目的內(nèi)容與要求內(nèi)容：設計一個利用哈夫曼算法的編碼和譯碼系統(tǒng)，可以接收從鍵盤輸入的字符集大小、字符和權值信息，創(chuàng)建哈夫曼樹生成哈夫曼編碼并能對其進行解碼。要求：1存儲結構自定；2將生成的哈夫曼編碼與等長編碼進行比較，判斷優(yōu)劣；3給出動態(tài)演示過程（選作） 。1.2 總體結構總體結構本程序主要分為 3 個模塊（功能模塊圖見圖 1.1）：主模塊，編碼模塊，譯碼模塊。主模塊：程序的主體部分，分別調(diào)用各個模塊，實現(xiàn)各項功能。編碼模塊：對每個出現(xiàn)的字符進行編碼。譯碼模塊：將已有編碼譯成字符，使之可以直接被讀出。 哈哈夫夫曼曼編編碼碼/ /譯譯碼碼器器主主模模

3、塊塊編編碼碼模模塊塊譯譯碼碼模模塊塊 圖圖 1.1 功能模塊圖功能模塊圖第 2 章 算法分析2.1 核心算法思想核心算法思想哈夫曼樹的建立由赫夫曼算法的定義可知，初始森林中共有 n 棵只含有根結點的二叉樹。算法的第二步是：將當前森林中的兩棵根結點權值最小的二叉樹，合并成一棵新的二叉樹；每合并一次，森林中就減少一棵樹，產(chǎn)生一個新結點。顯然要進行 n1 次合并，所以共產(chǎn)生 n1 個新結點，它們都是具有兩個孩子的分支結點。由此可知，最終求得的哈夫曼樹中一共有 2n1 個結點，其中 n 個結點是初始森林的 n 個孤立結點。并且哈夫曼樹中沒有度數(shù)為 1 的分支結點。我們可以利用一個大小為 2n-1 的一

4、維數(shù)組來存儲哈夫曼樹中的結點。哈夫曼編碼是可變字長編碼。編碼時借助哈夫曼樹，也即帶權路徑長度最小的二叉樹，來建立編碼。譯碼的基本思想是：讀文件中編碼，并與原先生成的赫夫曼編碼表比較，遇到相等時，即取出其對應的字符存入一個新串中。2.2 算法結構定義算法結構定義結構體存儲表示typedef struct int weight;int parent,lchild,rchild; Htnode,*Hfmtree; /動態(tài)分配數(shù)組存儲哈夫曼樹typedef char *Hfmcode; /動態(tài)分配數(shù)組存儲哈弗曼編碼表第 3 章 詳細設計3.1 功能流程功能流程此流程圖為構造哈夫曼樹的過程，輸入字符的次

5、數(shù)為權值對每個結點賦值，構造哈夫曼樹，如圖 3.1 開開始始以以讀讀入入字字符符次次數(shù)數(shù)對對各各結結點點賦賦初初值值并并令令i=2n-1i i為為0 0找找出出根根結結點點權權值值最最小小和和次次小小樹樹s1,s2兩兩樹樹合合并并成成新新樹樹n+i結結束束i i減減1 1NY 圖圖 3.1 流程圖流程圖此流程圖（圖 3.2）為對字符進行哈夫曼編碼的過程，將字符轉化為哈夫曼編碼。 開開始始i i = =n n第第一一個個字字符符，i=1結結點點是是否否是是根根結結點點雙雙親親結結點點的的左左結結點點是是否否等等于于該該結結點點記記編編碼碼0 0記記編編碼碼1 1i i= =i i+ +1 1結結

6、束束將將得得到到的的編編碼碼存存儲儲Y YY YY YN NN NN 圖圖 3.2 字符編碼模塊流程圖字符編碼模塊流程圖第 4 章 系統(tǒng)實現(xiàn)4.1 錯誤分析錯誤分析在此程序調(diào)試過程中主要遇到以下幾類問題：1、本程序運用了對文件進行操作，一定要注意在操作文件是文件的位置，我在做次程序是就是因為操作的文件位置錯了導致程序無法正常運行。2、在函數(shù)內(nèi)部有時需要多定義參數(shù)，注意參數(shù)的作用域，而且注意傳引用調(diào)用和傳值調(diào)用的區(qū)別，不能不正確的修改實參的值，否則會導致程序運行的錯誤。3、本程序用到的外部函數(shù)較多，在調(diào)用時一定要注意傳入的參數(shù)是否符合函數(shù)的定義，而且位置也不能錯，這是引用函數(shù)要注意的一點。4、剛

7、開始時清屏函數(shù)運用出錯，導致操作界面消失，使用戶無法操作，因此，在使用一些函數(shù)是一定要注意。4.2 運行結果運行結果運行程序首先出現(xiàn)界面圖，如圖 4.2 所示。 圖圖 4.1 界面圖界面圖選擇操作 1 后，輸入相應的字符大小，字符和權值，生成哈夫曼樹。系統(tǒng)會顯示每個字符的哈夫曼編碼，如圖 4.2 所示。 圖圖 4.2 程序運行截圖程序運行截圖選擇操作 2 后，輸入字符串，系統(tǒng)會顯示對字符串進行哈弗曼編碼得到的哈弗曼編碼，顯示以下界面（圖 4.3）供用戶選擇。 圖圖 4.3 程序運行截圖程序運行截圖選擇操作 3 后，系統(tǒng)會顯示用哈夫曼編碼翻譯成的字符，顯示以下界面（圖4.4）供用戶選擇 圖圖 4

8、.44.4 程序運行截圖程序運行截圖選擇操作 4 后，退出系統(tǒng)，顯示以下界面（圖 4.5）圖圖 4.5 程序運行截圖程序運行截圖參考文獻1 嚴蔚敏.數(shù)據(jù)結構(C 語言版).清華大學出版社，20072 譚浩強.C 語言程序設計教程.高等教育出版社，20063 蘇仕華.數(shù)據(jù)結構課程設計.機械工業(yè)出版社，2007附 錄源程序如下：#include#include#include#include#includetypedef struct /赫夫曼樹的結構體char ch;int weight; /權值int parent,lchild,rchild;Htnode,*Hfmtree; /動態(tài)分配數(shù)組存

9、儲赫夫曼樹typedef char *Hfmcode; /動態(tài)分配數(shù)組存儲赫夫曼編碼表void Select(Hfmtree &HT,int a,int *s1,int *s2) /Select 函數(shù)，選出 HT 樹到 a 為止，權值最小且 parent 為 0 的 2 個節(jié)點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é)點for(j=1;j=a;+j)if(HTj.parent=0&x!=j)y=j;b

10、reak;for(i=j+1;i=a;+i)if(HTi.weighty)*s1=y;*s2=x;else*s1=x;*s2=y;void Hfmcoding(Hfmtree &HT,Hfmcode &HC,int n) /構建赫夫曼樹 HT，并求出 n個字符的赫夫曼編碼 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 個葉子結點printf(請輸入第%d 字符信息和權值：,i);scanf

11、(%c%d,&z,&w);while(getchar()!=n)continue;HTi.ch=z;HTi.weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i=m;+i) /初始化其余的結點HTi.ch=0;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=

12、HTp1.weight+HTp2.weight;HC=(Hfmcode)malloc(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; for(i=

13、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) /進行編碼，并將字符放入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(!

14、output_file)coutcant oen file!endl;for(i=0;istrlen(str);i+)for(j=0;j=n;+j)if(HTj.ch=stri)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(choi

15、ce=3) /讀入 B.txt 中的編碼進行譯碼，將譯出來的字符放入 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)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=hl;hlj=0;if(

16、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;input_file.close();printf(譯碼結束，字符已經(jīng)存入 Textfile.txt 文件中!n); else if(choice=4) exit(0); else /如果選了選項之外的就讓用戶重新選擇printf(您沒有輸入正確的步驟，請重新輸入！);課程設計總結：課程設計總結：通過近兩周的課程設計使我對哈夫曼樹以及哈夫曼編碼譯碼有了更深的認識和理解，也使我更加明白哈夫曼編碼譯碼在信息技術中的重要性和地位。在做課設的過程中我也遇到了很多問題：開始的時候，代碼中有許多的錯誤，特別是有一個“無法找到文件”的錯誤讓我束手無策，最后還是屏蔽了定義的四個頭文件然后慢慢地改正錯誤才讓我又看到了希望。然后在實現(xiàn)文章的讀入時，由于對文件不是太熟悉，只好翻開 C 語言和 C+語言書本仿照其模式編寫，但后來進入了死循環(huán)，最后的解決方式是在 main 函數(shù)里有一個控制語句使用不正確。我們遇到問題很正常，說明我們掌握的知識還是