哈夫曼編碼譯碼器

1、 目錄目錄一、一、系統(tǒng)開發(fā)的背景系統(tǒng)開發(fā)的背景.1二、系統(tǒng)分析與設(shè)計(jì)二、系統(tǒng)分析與設(shè)計(jì).1（一）（一）系統(tǒng)功能要求系統(tǒng)功能要求.1（二）（二）系統(tǒng)模塊結(jié)構(gòu)設(shè)計(jì)系統(tǒng)模塊結(jié)構(gòu)設(shè)計(jì).2三、系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)三、系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn).2（一）（一）哈夫曼樹的定義哈夫曼樹的定義.2四、系統(tǒng)測試四、系統(tǒng)測試.3（一）（一）測試測試MAINMAIN_ _FORMFORM()()函數(shù)函數(shù).3（二）（二）測試測試VOIDVOID HFMCODINGHFMCODING( (HFMTREEHFMTREE &HT,&HT,HFMCODEHFMCODE &HC,&HC,INTINT N N)

2、)函數(shù)，測試的結(jié)果函數(shù)，測試的結(jié)果.4（三）（三）測試編碼函數(shù)，測試結(jié)果如下測試編碼函數(shù)，測試結(jié)果如下.4（四）（四）測試譯碼函數(shù)，測試結(jié)果如下測試譯碼函數(shù)，測試結(jié)果如下.4（五）（五）測試退出函數(shù)，測試結(jié)果如下測試退出函數(shù)，測試結(jié)果如下.5五、總結(jié)（實(shí)驗(yàn)心得）五、總結(jié)（實(shí)驗(yàn)心得）.5六、附件（源代碼）六、附件（源代碼）.6 1哈夫曼編譯碼哈夫曼編譯碼一、一、 系統(tǒng)開發(fā)的系統(tǒng)開發(fā)的背景背景隨著計(jì)算機(jī)的應(yīng)用越來越普遍，它的應(yīng)用早已不局限于簡單的數(shù)值運(yùn)算，而涉及到問題的分析、數(shù)據(jù)結(jié)構(gòu)框架的設(shè)計(jì)以及設(shè)計(jì)最短路線等復(fù)雜的非數(shù)值處理和操作。 為了確保能夠更好的保存機(jī)密性文件、安全的傳送某一個(gè)重要的東西，

3、利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼器。因此我為這樣的信息收發(fā)站設(shè)計(jì)了一個(gè)簡單的哈夫曼的編碼/譯碼器。二、系統(tǒng)分析與設(shè)計(jì)二、系統(tǒng)分析與設(shè)計(jì)（一）（一） 系統(tǒng)功能要求系統(tǒng)功能要求一個(gè)完整的哈夫曼編碼/譯碼器應(yīng)具有以下功能：1、 初始化：從終端讀入字符集大小 n，以及 n 個(gè)字符和 n 個(gè)權(quán)值，建立哈夫曼樹，并將它存于文件 hfmTree 中。2、 編碼：利用以建好的哈夫曼樹（如不在內(nèi)存，則從文

4、件 hfmTree中讀入） ，對文件 ToBeTran 中的正文進(jìn)行編碼，然后將結(jié)果存入文件 CodeFile 中。3、 譯碼：利用已建好的哈夫曼樹將文件 CodeFile 中的代碼進(jìn)行譯碼，結(jié)果存入文件 TextFile 中。4、 退出。 2（二）（二）系統(tǒng)模塊結(jié)構(gòu)設(shè)計(jì)系統(tǒng)模塊結(jié)構(gòu)設(shè)計(jì)通過對此功能的分析，哈夫曼編碼/譯碼器的功能如圖 1 所示。哈夫曼編碼/譯碼器哈夫曼編碼/譯碼器1.初始化1.初始化2.編碼2.編碼3.譯碼3.譯碼0.退出0.退出圖 1 哈夫曼編碼/譯碼器的功能圖通過上圖的功能分析，把整個(gè)系統(tǒng)劃分為 4 個(gè)模塊：1、初始化，該模塊主要實(shí)現(xiàn)：哈夫曼二叉樹的定義以及哈夫曼二叉樹的

5、建立，借助函數(shù) void hfmcoding（）來實(shí)現(xiàn)；2、編碼，該模塊主要實(shí)現(xiàn)：把輸入的字符和代碼以二進(jìn)制的形式存儲起來，借助函數(shù) void hfmcoding（）來實(shí)現(xiàn)；3、譯碼，該模塊主要實(shí)現(xiàn)：把以二進(jìn)制形式存儲起來的代碼，轉(zhuǎn)換成字符的形式并輸出，借助函數(shù)來實(shí)現(xiàn)；4、退出。三、系統(tǒng)的設(shè)計(jì)三、系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)與實(shí)現(xiàn)（一）（一） 哈夫曼樹的定義哈夫曼樹的定義1.哈夫曼樹節(jié)點(diǎn)的數(shù)據(jù)類型定義為：typedef struct /赫夫曼樹的結(jié)構(gòu)體char ch;int weight; /權(quán)值int parent,lchild,rchild;htnode,*hfmtree;2.所實(shí)現(xiàn)的功能函數(shù)如下1）

6、 、void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈 3夫曼樹，處理 InputHuffman(Huffman Hfm)函數(shù)得到的數(shù)據(jù)，按照哈夫曼規(guī)則建立 2 叉樹。此函數(shù)塊調(diào)用了 Select（）函數(shù)。2)、void Select(hfmtree &HT,int a,int *p1,int *p2) /Select 函數(shù)，選出 HT 樹到 a 為止，權(quán)值最小且 parent 為 0 的 2個(gè)節(jié)點(diǎn)3)、 int main()主函數(shù)： 利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmtree.txt 中讀入）對文件中的正文

7、進(jìn)行編碼，然后將結(jié)果存入文件 codefile.txt 中。如果正文中沒有要編碼的字符，則鍵盤讀入并存儲到 ToBeTran 文件中。讀入 ToBeTran 中將要編碼的內(nèi)容，將編碼好的哈夫曼編碼存儲到 CodeFile 中。4)、Encoding 編碼功能：對輸入字符進(jìn)行編碼5)、Decoding譯碼功能： 利用已建好的哈夫曼樹將文件 codefile.txt 中的代碼進(jìn)行譯碼，結(jié)果存入文件 textfile.dat 中。6).主函數(shù)的簡要說明，主函數(shù)主要設(shè)計(jì)的是一個(gè)分支語句，讓用戶挑選所實(shí)現(xiàn)的功能。使用鏈樹存儲，然后分別調(diào)用統(tǒng)計(jì)頻數(shù)函數(shù)，排序函數(shù)，建立哈夫曼函數(shù)，編碼函數(shù)，譯碼函數(shù)來實(shí)現(xiàn)功

8、能。四、系統(tǒng)測試四、系統(tǒng)測試（一）（一） 測試測試 main_form()main_form()函數(shù)函數(shù)測試該函數(shù)使用的測試方法，測試的具體步驟，測試用例的選取，測試的結(jié)果。圖 1 哈夫曼編碼/譯碼界面 4（二）（二） 測試測試 voidvoid hfmcoding(hfmtreehfmcoding(hfmtree &HT,hfmcode&HT,hfmcode &HC,int&HC,int n)n)函函數(shù)，測試的結(jié)果數(shù)，測試的結(jié)果圖 2 哈夫曼樹的初始化（一）（一） 測試編碼函數(shù)，測試結(jié)果如下測試編碼函數(shù)，測試結(jié)果如下圖 3 哈夫曼的編碼（二）（二） 測試譯碼函

9、數(shù)，測試結(jié)果如下測試譯碼函數(shù)，測試結(jié)果如下 5圖 4 哈夫曼譯碼（三）（三） 測試退出函數(shù)，測試結(jié)果如下測試退出函數(shù)，測試結(jié)果如下圖 5 哈夫曼編碼/譯碼系統(tǒng)的退出五、總結(jié)五、總結(jié)（實(shí)驗(yàn)心得）（實(shí)驗(yàn)心得）系統(tǒng)完成了利用哈夫曼樹對字符的編碼和譯碼之間的轉(zhuǎn)換，它能利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，并且降低傳輸成本的功能。此系統(tǒng)不能打印代碼文件（Print） ，不能打印哈夫曼樹（Tree Printing） 。并且不能將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上。我的收獲是，通過今年對數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)和這次的課程設(shè)計(jì)，使我了解到計(jì)算機(jī)的應(yīng)用在人類的現(xiàn)實(shí)

10、生活中已經(jīng)越來越普遍，它的應(yīng)用早已不局限于簡單的數(shù)值運(yùn)算，而涉及到問題的分析、數(shù)據(jù)結(jié)構(gòu)框架的設(shè)計(jì)以及設(shè)計(jì)最短路線等復(fù)雜的非數(shù)值處理和操作。 6六、附件（源代碼）六、附件（源代碼）#include#include#include#include typedef struct /赫夫曼樹的結(jié)構(gòu)體char ch;int weight; /權(quán)值int parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode; /代碼void Select(hfmtree &HT,int a,int *p1,int *p2) /Select 函數(shù)，選出

11、 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)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)*p1=y; 7*p2=x;else*p1=x;*p2=y;void hfmcoding(hfmtree &

12、HT,hfmcode &HC,int n) /構(gòu)建赫夫曼樹 HT，并求出 n 個(gè)字符的赫夫曼編碼 HCint i,start,c,f,m,w; /w 中存放的是權(quán)值int p1,p2;char *cd,z; /z 中存放的是需要編碼的字符if(n=1)return;m=2*n-1; /哈弗曼樹中節(jié)點(diǎn)的個(gè)數(shù)HT=(hfmtree)malloc(m+1)*sizeof(htnode);for(i=1;i=n;+i) /初始化 n 個(gè)葉子結(jié)點(diǎn)printf(請輸入第%d 字符信息和權(quán)值：,i);scanf(%c%d,&z,&w);while(getchar()!=n)conti

13、nue;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;HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i=m;+i) /建立赫夫曼樹 8Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.weight;HC

14、=(hfmcode)malloc(n+1)*sizeof(char *); /cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;+i) /給 n 個(gè)字符編碼start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);int main()char code100,h1

15、00,hl100;int n,i,j,k,l,m; /m 中存放選擇序號，n 中存放char str100;hfmtree HT;hfmcode HC; /HC 中存放的是哈弗曼代碼FILE *fp;FILE *htmTree;FILE *ToBeTran;FILE *CodeFile;FILE *Textfile;printf(n); 9while(m!=0) /當(dāng) choice 的值不為 q 且不為 Q 時(shí)循環(huán)printf( *n);printf( * 赫夫曼編碼/譯碼器 *n); printf( * 1.初始化 *n);printf( * 2.編碼 *n);printf( * 3.譯碼

16、*n);printf( * 0.退出 *n);printf( *n);printf(n); printf(請輸入您要操作的步驟：);scanf(%d,&m); if(m=1) /初始化赫夫曼樹printf(請輸入字符個(gè)數(shù)：);scanf(%d,&n);hfmcoding(HT,HC,n);for(i=1;i=n;+i)printf(%c:,HTi);puts(HCi);fp=fopen(hfmTree,txt);if(fp=fopen(hfmTree,w)=NULL)printf(cant open file!n);return 1;fclose(fp);printf(哈夫曼樹

17、已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入 hfmTree.txt 文件中!n); else if(m=2) /進(jìn)行編碼，并將字符放入 ToBeTran.txt，碼值放入CodeFile.txt 中printf(請輸入字符：);scanf(%s,str);fp=fopen(ToBeTran,w);if(fp=fopen(ToBeTran,w)=NULL)printf(cant open file!n);return 1;fputs(str,fp);fclose(fp);fp=fopen(CodeFile,w); 10if(fp=fopen(CodeFile,w)=NULL)printf(cant open f

18、ile!n);return 1;for(i=0;istrlen(str);i+)for(j=0;j=n;+j)if(HTj.ch=stri)fputs(str,htmTree);break;fclose(fp);printf(n);printf(編碼完畢，并且已經(jīng)存入 CodeFile.txt 文件！n);fp=fopen(CodeFile,r); /從 CodeFile.txt 中讀入編碼，輸出在終端if(fp=fopen(CodeFile,r)=NULL)printf(cant open file!n);return 1;printf(編碼碼值為：%d,HTj);fclose(fp); else if(m=3) /讀入 CodeFile.txt 中的編碼進(jìn)行譯碼，將譯出來的字符放