哈夫曼編碼譯碼器

1、哈夫曼編碼譯碼器學(xué)院班級: 信息工程學(xué)院 軟件1501 指導(dǎo)教師: 朱俊武 小組成員: 劉洋 蔣佳燁 冀若含 本人學(xué)號: 151303107 報告書寫: 冀若含 學(xué)生成績: 目錄一、總體介紹03-04二、詳細(xì)設(shè)計(jì)04-11三、運(yùn)行測試11-12四、課設(shè)總結(jié)13-13五、附錄代碼13-19一、總體介紹1.1任務(wù)概述我們小組做了兩個版本，其中一個為文件操作版，另一個為鍵盤操作版。兩個版本都實(shí)現(xiàn)了哈夫曼編碼/譯碼操做。我主要負(fù)責(zé)的是構(gòu)造哈夫曼樹，給出各個字符的哈夫曼編碼，加密操做，整個鍵盤操作版系統(tǒng)的代碼重組、編輯。開發(fā)的過程中使用了Codelite、Dev、Vc等軟件。參考書籍為數(shù)據(jù)結(jié)構(gòu)（c語言版

2、）。其中文件操作版的具體實(shí)現(xiàn)為：能夠?qū)崿F(xiàn)對26個小寫字母外加空格進(jìn)行哈夫曼編碼，并能夠?qū)σ徽恼拢ㄓ行懽帜负涂崭窠M成）進(jìn)行加密，生成密碼文件。最后根據(jù)生成的密碼翻譯出原文并存檔。在使用程序時，使用者只需要對ToBetran文件進(jìn)行原文的輸入（使用小寫字母或空格），加密和解密功能由程序自主來完成。程序運(yùn)行的過程中會輸出進(jìn)行編碼的26個小寫字母和空格（字符型），并輸出其對應(yīng)的權(quán)值（整型）。還輸出字符的編碼及生成的密文。最后輸出解密后的原文。鍵盤操作版為：要求從鍵盤輸入字符集和字符的權(quán)值，大部分字符均可輸入，需要各個字符的權(quán)值不能相同。利用輸入的權(quán)值建立哈夫曼樹，得到每個字符的前綴編碼。輸入字符

3、串，程序?qū)ζ溥M(jìn)行加密。輸入密文（1010101.）對密文進(jìn)行解密。兩個版本都利用了哈夫曼樹解決問題，通過建立哈夫曼樹，得出每個字符的獨(dú)特前綴編碼，也就是密文，然后利用密文對明文進(jìn)行加密得到密文。密文轉(zhuǎn)換為明文則是通過對哈夫曼樹的遍歷。（之前想過字符串的匹配得到明文但是算法太為復(fù)雜）。1.2系統(tǒng)功能框圖本系統(tǒng)分為三個大的模塊：構(gòu)造哈夫曼樹，編碼，譯碼。1.3 功能難點(diǎn)本系統(tǒng)的實(shí)現(xiàn)難點(diǎn)在于哈夫曼樹的構(gòu)造。編碼、譯碼功能的實(shí)現(xiàn)都是基于哈夫曼樹的。二、詳細(xì)設(shè)計(jì)2.1哈夫曼樹的構(gòu)造哈夫曼樹，又稱最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹，有著廣泛的應(yīng)用。哈夫曼樹的構(gòu)造過程如下：1.初始化： 根據(jù)給定的n個權(quán)值w

4、1,w2,wn構(gòu)成n棵二叉樹的集合F=T1,T2,.,Tn，其中每棵二叉樹Ti中只有一個帶權(quán)wi的根節(jié)點(diǎn)，左右子樹均空。2. 找最小樹：在F中選擇兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且至新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹上根結(jié)點(diǎn)的權(quán)值之和。3. 刪除與加入：在F中刪除這兩棵樹，并將新的二叉樹加入F中。4. 判斷：重復(fù)前兩步（2和3），直到F中只含有一棵樹為止。該樹即為哈夫曼樹。2.2 代碼實(shí)現(xiàn)哈夫曼樹和哈夫曼編碼的儲存表示typedef structint weight;int parent,lchild,rchild;HTNode,*HuffmanTree;/動態(tài)分配數(shù)組

5、儲存哈夫曼樹typedef char* *HuffmanCode;/動態(tài)分配數(shù)組儲存哈夫曼編碼表void Select(HuffmanTree HT,int p,int *s1,int *s2)該函數(shù)的功能為：找出HT1.i-1中parent為0且weight最小的兩個結(jié)點(diǎn)，其序號為s1，s2。void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n,char *a)該函數(shù)的功能為構(gòu)造哈夫曼樹HT，并求出n個字符的哈夫曼編碼HC。以下為兩個函數(shù)的流程圖或詳細(xì)設(shè)計(jì)。void HuffmanCoding(HuffmanTree HT

6、,HuffmanCode HC,int *w,int n,char *a) 指針a指向輸入的字符集，指針w指向字符集的度，n為字符集的大小。注：具體程序中加入了輸出各個字符的哈夫曼編碼的功能，在流程圖沒有顯示。沒畫完下面還有喲！詳細(xì)代碼：void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n,char *a)int m=0;int c;int f;int start;char *cd;int *s1;int *s2;int i;s1=(int*)malloc(sizeof(int);s2=(int*)malloc(sizeof

7、(int);m=2*n-1;if(n=1)printf(字符的個數(shù)過少n);return;HuffmanTree p;p=HT;p+;for(i=1;iweight=*w;p-parent=0;p-lchild=0;p-rchild=0;for(;iweight=0;p-parent=0;p-lchild=0;p-rchild=0;for(i=n+1;i=m;+i)Select(HT,i-1,s1,s2);HT*s1.parent=i;HT*s2.parent=i;HTi.lchild=*s1;HTi.rchild=*s2;HTi.weight=HT*s1.weight+HT*s2.weigh

8、t;cd=(char *)malloc(n*sizeof(char);cdn-1=0;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;else cd-start=1;HCi=(char *)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);printf(%c ,*a);a+;printf(%sn,HCi);free(cd);void Select(HuffmanTree HT,int p,int *s1

9、,int *s2)詳細(xì)設(shè)計(jì)：首先通過一個循環(huán)找出當(dāng)前數(shù)組中weight最小的一個。記錄下它的序號。也是一和一樣的循環(huán)和算法。加上一個if語句，如果循環(huán)到與第一次序號一樣的那次，就continue跳過這次比較。將得到的權(quán)值最小的兩個傳到s1和是s2指向的地址。這就是哈夫曼樹的構(gòu)造和生成哈夫曼編碼的過程。詳細(xì)代碼：void Select(HuffmanTree HT,int p,int *s1,int *s2)/i為遍歷長度int i=1;int x=0;int y=0;int min=1000;int min1=1000;int v=1;*s1=1;*s2=1;for(i=1;iy)min=HT

10、i.weight;*s1=i;v=i;for(i=1;i=y)min1=HTi.weight;*s2=i;2.3 編碼（加密）void HuffmanEncryption(HuffmanCode HC,char *a,int n)此函數(shù)為加密函數(shù)。該加密函數(shù)的流程圖如下：該功能的實(shí)現(xiàn)就是通過一個簡單的查找，通過字符與字符的哈夫曼編碼在不同數(shù)組的對應(yīng)關(guān)系，進(jìn)行加密。Input儲存輸入的字符串。Lo為輸入的字符串長度，n為原字符集的字符個數(shù)。詳細(xì)代碼如下：void HuffmanEncryption(HuffmanCode HC,char *a,int n)char input100;int i=

11、0,j=0;char lu= ;int lo=0;/要加密的字符串的長度char c;printf(請輸入你要加密的字符串n);while(lu=getchar()!=n&lu!=EOF);c=getchar();while(c!=n)inputi=c;i+;c=getchar();lo=i;for(i=0;ilo;i+)for(j=0;jn;j+)if(inputi=aj)printf(%s,HCj+1);printf(n);三、運(yùn)行測試菜單界面：構(gòu)造哈夫曼樹：編碼：譯碼：密鑰：譯碼測試：四、總結(jié)經(jīng)過幾天的設(shè)計(jì)與編碼我們小組終于完成了兩個不同的版本的哈夫曼編碼譯碼器。雖然兩個系統(tǒng)大部分的算法

12、相同，但是也算我們的嘗試。美中不足的是我們沒能把兩個版本的系統(tǒng)融合起來。開發(fā)過程中遇到的最大的問題就是輸入輸出流的問題。因?yàn)槭菑逆I盤輸入數(shù)據(jù)的所以難免會遇到這種問題。我通過輸入流的過濾解決了此問題。通過這幾天的實(shí)驗(yàn)，加深了我對哈夫曼樹的理解，也加強(qiáng)了自己的動手能力。數(shù)據(jù)結(jié)構(gòu)這門課程還有很多很多的東西，我們?nèi)詰?yīng)該繼續(xù)努力。附錄全部代碼：#include #include #include #include typedef structint weight;int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char* *HuffmanCode

13、;void Select(HuffmanTree HT,int p,int *s1,int *s2)/i為遍歷長度，bigint i=1;int x=0;int y=0;int min=1000;int min1=1000;int v=1;*s1=1;*s2=1;for(i=1;iy)min=HTi.weight;*s1=i;v=i;for(i=1;i=y)min1=HTi.weight;*s2=i;void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n,char *a)int m=0;int c;int f;int star

14、t;char *cd;int *s1;int *s2;int i;s1=(int*)malloc(sizeof(int);s2=(int*)malloc(sizeof(int);m=2*n-1;if(n=1)printf(字符的個數(shù)過少n);return;HuffmanTree p;p=HT;p+;for(i=1;iweight=*w;p-parent=0;p-lchild=0;p-rchild=0;for(;iweight=0;p-parent=0;p-lchild=0;p-rchild=0;for(i=n+1;i=m;+i)Select(HT,i-1,s1,s2);HT*s1.parent

15、=i;HT*s2.parent=i;HTi.lchild=*s1;HTi.rchild=*s2;HTi.weight=HT*s1.weight+HT*s2.weight;cd=(char *)malloc(n*sizeof(char);cdn-1=0;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;else cd-start=1;HCi=(char *)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);

16、printf(%c ,*a);a+;printf(%sn,HCi);free(cd);void HuffmanEncryption(HuffmanCode HC,char *a,int n)char input100;int i=0,j=0;char lu= ;int lo=0;/要加密的字符串的長度char c;printf(請輸入你要加密的字符串n);while(lu=getchar()!=n&lu!=EOF);c=getchar();while(c!=n)inputi=c;i+;c=getchar();lo=i;for(i=0;ilo;i+)for(j=0;jn;j+)if(inputi

17、=aj)printf(%s,HCj+1);printf(n);void Huffmandeciphering(HuffmanCode HC,char *a,int n,HuffmanTree HT)/解密int input100=0;char c= ;int num=0;int m=1;int t=0;printf(請輸入你要解密的字符串n);int i=0;getchar();while(c!=n)c=getchar();inputi=(int)c-48;i+;num=i;for(i=1;t=0;i+)if(HTi.parent =0)t=i;/根結(jié)點(diǎn)的位置m=t;for(i=0;i: );

18、scanf(%c,&choice);switch(choice)case a:case A:system(cls);view();getchar();break;case b:case B:printf(請輸入字符集大小n);scanf(%d,&n);printf(請輸入字符名和度數(shù)中間以空格隔開n);for(i=0;in;i+)while(lu=getchar()!=n&lu!=EOF);scanf(%c %d,&inp,&inpt);*(a+i)=inp;*(w+i)=inpt;HuffmanCoding(HT,HC,w,n,a);/構(gòu)建哈夫曼樹getchar();break;case c:case C:HuffmanEncryption(HC,a,n);/加密break;case D:case d:Huffmandeciphering(HC,a,n,HT);/解密break;case F:case f:printf(你確定要初始化嗎Y or Nn);char yn;getchar();scanf(%c,&yn);if(yn=Y)free(a);free(w);free(HT);free(HC);lu= ;inp