哈夫曼編碼譯碼器

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

2、）。其中文件操作版的具體實現為：能夠實現對26個小寫字母外加空格進行哈夫曼編碼，并能夠對一整篇文章（有小寫字母和空格組成）進行加密，生成密碼文件。最后根據生成的密碼翻譯出原文并存檔。在使用程序時，使用者只需要對ToBetran文件進行原文的輸入（使用小寫字母或空格），加密和解密功能由程序自主來完成。程序運行的過程中會輸出進行編碼的26個小寫字母和空格（字符型），并輸出其對應的權值（整型）。還輸出字符的編碼及生成的密文。最后輸出解密后的原文。鍵盤操作版為：要求從鍵盤輸入字符集和字符的權值，大部分字符均可輸入，需要各個字符的權值不能相同。利用輸入的權值建立哈夫曼樹，得到每個字符的前綴編碼。輸入字符

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

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

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

6、,HuffmanCode HC,int *w,int n,char *a) 指針a指向輸入的字符集，指針w指向字符集的度，n為字符集的大小。注：具體程序中加入了輸出各個字符的哈夫曼編碼的功能，在流程圖沒有顯示。沒畫完下面還有喲！詳細代碼：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(字符的個數過少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)詳細設計：首先通過一個循環(huán)找出當前數組中weight最小的一個。記錄下它的序號。也是一和一樣的循環(huán)和算法。加上一個if語句，如果循環(huán)到與第一次序號一樣的那次，就continue跳過這次比較。將得到的權值最小的兩個傳到s1和是s2指向的地址。這就是哈夫曼樹的構造和生成哈夫曼編碼的過程。詳細代碼：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)此函數為加密函數。該加密函數的流程圖如下：該功能的實現就是通過一個簡單的查找，通過字符與字符的哈夫曼編碼在不同數組的對應關系，進行加密。Input儲存輸入的字符串。Lo為輸入的字符串長度，n為原字符集的字符個數。詳細代碼如下：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);三、運行測試菜單界面：構造哈夫曼樹：編碼：譯碼：密鑰：譯碼測試：四、總結經過幾天的設計與編碼我們小組終于完成了兩個不同的版本的哈夫曼編碼譯碼器。雖然兩個系統(tǒng)大部分的算法

12、相同，但是也算我們的嘗試。美中不足的是我們沒能把兩個版本的系統(tǒng)融合起來。開發(fā)過程中遇到的最大的問題就是輸入輸出流的問題。因為是從鍵盤輸入數據的所以難免會遇到這種問題。我通過輸入流的過濾解決了此問題。通過這幾天的實驗，加深了我對哈夫曼樹的理解，也加強了自己的動手能力。數據結構這門課程還有很多很多的東西，我們仍應該繼續(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(字符的個數過少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;/根結點的位置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(請輸入字符名和度數中間以空格隔開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);/構建哈夫曼樹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