哈夫曼編碼譯碼器

1、目錄系統(tǒng)開發(fā)的背景二、系統(tǒng)分析與設(shè)計(jì)系統(tǒng)功能要求 系統(tǒng)模塊結(jié)構(gòu)設(shè)計(jì)三、系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)哈夫曼樹的定義四、系統(tǒng)測試測試 MAIN_FORM() 函數(shù) 四)五)測試結(jié)果如下 測試結(jié)果如下 測試結(jié)果如下測試 VOID HFMCODIN(GHFMTREE&HT,HFMCOD&EHC,INT N) 函數(shù)，測試的結(jié)果 測試編碼函數(shù)， 測試譯碼函數(shù)， 測試退出函數(shù)，五、總結(jié)實(shí)驗(yàn)心得)六、附件源代碼)哈夫曼編譯碼16系統(tǒng)開發(fā)的背景隨著計(jì)算機(jī)的應(yīng)用越來越普遍，它的應(yīng)用早已不局限于簡單的數(shù)值運(yùn)算，而涉及到問題的分析、數(shù)據(jù)結(jié)構(gòu)框架的設(shè)計(jì)以及設(shè)計(jì)最短路線等復(fù)雜的非數(shù)值處理和操作。為了確保能夠更好的保存機(jī)密性文件、安全

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

3、e中讀入）,對文件 ToBeTran 中的正文進(jìn)行編碼,然后將結(jié)果存入文件 CodeFile 中。3、譯碼：利用已建好的哈夫曼樹將文件 CodeFile 中的代碼進(jìn)行譯碼,結(jié)果存入文件 TextFile 中。4、退出。系統(tǒng)模塊結(jié)構(gòu)設(shè)計(jì)通過對此功能的分析，哈夫曼編碼/譯碼器的功能如圖1所示。圖1哈夫曼編碼/譯碼器的功能圖通過上圖的功能分析，把整個系統(tǒng)劃分為 4個模塊:1、初始化，該模塊主要實(shí)現(xiàn)：哈夫曼二叉樹的定義以及哈夫曼二叉樹的建立，借助函數(shù)void hfmcoding ()來實(shí)現(xiàn);2、編碼，該模塊主要實(shí)現(xiàn)：把輸入的字符和代碼以二進(jìn)制的形式存儲起來，借助函數(shù)void hfmcoding ()來

4、實(shí)現(xiàn);3、譯碼，該模塊主要實(shí)現(xiàn)：把以二進(jìn)制形式存儲起來的代碼，轉(zhuǎn)換成字符的形式并輸出，借助函數(shù)來實(shí)現(xiàn);4、退出。三、系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)(一) 哈夫曼樹的定義1.哈夫曼樹節(jié)點(diǎn)的數(shù)據(jù)類型定義為:typ edef struct/char ch;int weight;/int paren t,lchild,rchild;ht no de,*hfmtree;赫夫曼樹的結(jié)構(gòu)體權(quán)值2.所實(shí)現(xiàn)的功能函數(shù)如下1)、void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈夫曼樹，處理InputHuffman(Huffman Hfm)函數(shù)得到的數(shù)據(jù)，按照哈夫曼規(guī)則建立2叉樹。

5、此函數(shù)塊調(diào)用了 Select ()函數(shù)。2) 、 void Select(hfmtree&HT,int a,int *p1,int *p2)/Select函數(shù)，選出HT樹到a為止，權(quán)值最小且p are nt為0的2 個節(jié)點(diǎn)3) 、int main()主函數(shù)：利用已建好的哈夫曼樹(如不在內(nèi)存，則從文件 hfmtree.txt中讀入)對文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile.txt 中。如果正文中沒有要編碼的字符，則鍵盤讀入并存儲到ToBeTran文件中。讀入ToBeTran中將要編碼的內(nèi)容，將編碼好的哈夫曼編碼存儲 到 CodeFile 中。4) 、Encoding編碼功能：對

6、輸入字符進(jìn)行編碼5) 、Decoding譯碼功能：利用已建好的哈夫曼樹將文件codefile.txt 中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile.dat 中。6) .主函數(shù)的簡要說明，主函數(shù)主要設(shè)計(jì)的是一個分支語句，讓用戶 挑選所實(shí)現(xiàn)的功能。使用鏈樹存儲，然后分別調(diào)用統(tǒng)計(jì)頻數(shù)函數(shù)，排序函數(shù)，建立哈夫 曼函數(shù)，編碼函數(shù)，譯碼函數(shù)來實(shí)現(xiàn)功能。四、系統(tǒng)測試(一) 測試 main_form()函數(shù) 測試該函數(shù)使用的測試方法，測試的具體步驟，測試用例的選取，測試的結(jié)果。赫夫號彎歳碼器： 爲(wèi)碼 * 3.55 0 逋出圖1哈夫曼編碼/譯碼界面測試 void hfmcoding(hfmtree&HT,hf

7、mcode &HC,int n)函數(shù)，測試的結(jié)果BMW MWM MWM MWM 疋KMIfKKWMUWWWMMWMWWMWMMWMW 貝淇皿皿 赫夫臺編有護(hù)譯碼器2 編碼3準(zhǔn)碼MM 口 M HM W0 逋也 t F 二 D D D D Q D 4X1114 自心自自心自2息 帖 隍 毘 層 思 圏 E 2ses Kriii? 5 1 2 3 4- 5 t 蜜于第魯?shù)诘诘?0 i;rr4rr5wf;rrf;tr4#r4dr4;rr 1 主月士月立目圭曰土月士島士冃土冃:驟步6的-n 一：公 f*j 4 Ln G00 ii i L B 14圖2哈夫曼樹的初始化測試編碼函數(shù)，測試結(jié)果如下圖3哈夫曼的

8、編碼測試譯碼函數(shù)，測試結(jié)果如下WWMWWMXM馬碼碼岀 曼 i 2 3 0 夫&謹(jǐn)輸A您宴操作的步黑=薛碼為：Wiend薛初結(jié)顛 字特已經(jīng)存入Textfile,txt件中!圖4哈夫曼譯碼（三） 測試退出函數(shù)，測試結(jié)果如下圖5哈夫曼編碼/譯碼系統(tǒng)的退出五、總結(jié)（實(shí)驗(yàn)心得）系統(tǒng)完成了利用哈夫曼樹對字符的編碼和譯碼之間的轉(zhuǎn)換，它能利用 哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時間，并且 降低傳輸成本的功能。此系統(tǒng)不能打印代碼文件（Print），不能打印哈夫曼樹（Tree Printing）。并且不能將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示 在終端上。我的收獲是，通過今年

9、對數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)和這次的課程設(shè)計(jì)，使 我了解到計(jì)算機(jī)的應(yīng)用在人類的現(xiàn)實(shí)生活中已經(jīng)越來越普遍，它的應(yīng)用早 已不局限于簡單的數(shù)值運(yùn)算，而涉及到問題的分析、數(shù)據(jù)結(jié)構(gòu)框架的設(shè)計(jì) 以及設(shè)計(jì)最短路線等復(fù)雜的非數(shù)值處理和操作。六、附件（源代碼）#include#include#include#include typedef struct / char ch; int weight; / int parent,lchild,rchild;htnode,*hfmtree; typedef char *hfmcode;赫夫曼樹的結(jié)構(gòu)體權(quán)值/代碼void Select(hfmtree &HT,int a,int *

10、p1,int *p2) /Select 權(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)for(j=1;j=a;+j)if(HTj.parent=0&x!=j) y=j; break;for(i=j+1;i=a;+i)函數(shù)，選出HT樹到a為止,if(HTi.weighty)*p1=y;/選出次小的節(jié)點(diǎn)*p2=x; else*p1=x;*p2=y;

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

12、()!=n)continue;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)/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

13、=(hfmcode)malloc(n+1)*sizeof(char *); / cd=(char *)malloc(n*sizeof(char); cdn-1=0;/給 n 個字符編碼for(i=1;i=n;+i)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,h100

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

15、編碼 / 譯碼器printf(printf(n);printf( 請輸入您要操作的步驟： );scanf(%d,&m);if(m=1)/初始化赫夫曼樹printf( 請輸入字符個數(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(else if(m=2)CodeFile.txt

16、中哈夫曼樹已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入 hfmTree.txt 文件中 !n);/進(jìn)行編碼，并將字符放入 ToBeTran.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);if(fp=fopen(CodeFile,w)=NULL)printf(cant open file!n); return 1;for

17、(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);讀入 CodeFile.

18、txt 中的編碼進(jìn)行譯碼，將譯出來的字符放入else if(m=3) /Textfile.txt 中 fp=fopen(CodeFile,w); if(fp=fopen(CodeFile,w)=NULL) printf(cant open file!n); return 1;fclose(fp); fp=fopen(Textfile,w); if(fp=fopen(Textfile,w)=NULL)printf(cant open file!n); return 1;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(strcmp(HCi,hl)=0)k