哈夫曼編碼與譯碼報(bào)告

1、用哈夫曼樹(shù)對(duì)字符串進(jìn)行編碼譯碼一、設(shè)計(jì)思想程序要求：利用哈夫曼樹(shù)對(duì)字符串進(jìn)行編碼,要求每個(gè)字符有自己唯一的編碼。將得到的一串字串譯成0、1編碼后存到一個(gè)文件夾中，然后再?gòu)倪@個(gè)文件夾中讀出這串編碼進(jìn)行解碼。實(shí)現(xiàn)方法：輸入一串字符，要求字符的區(qū)間為大寫(xiě)的26個(gè)英文字母， 將獲得的串字符用計(jì)算權(quán)值的函數(shù)（jsquanzhi()）進(jìn)行字符統(tǒng)計(jì)，統(tǒng)計(jì)出現(xiàn)的字符種數(shù)以及每種字符出現(xiàn)的次數(shù)， 將該種字符出現(xiàn)的次數(shù)作為它的權(quán)值。將出現(xiàn)的字符的權(quán)值和該字符依次分別賦給兩個(gè)結(jié)構(gòu)體HT和HC，利用HT（節(jié)點(diǎn)）權(quán)值的大小建立哈夫曼樹(shù)，首先用選擇函數(shù)select（）函數(shù)選擇兩個(gè)權(quán)值最小的字符作為葉子節(jié)點(diǎn)，創(chuàng)建一個(gè)新的節(jié)

2、點(diǎn)作為這兩個(gè)葉節(jié)點(diǎn)的父節(jié)點(diǎn)，被選中的節(jié)點(diǎn)給他的HTi.parent賦值是他下次不再被選中，父節(jié)點(diǎn)的權(quán)值為，子節(jié)點(diǎn)的權(quán)值之和。然后將該將父節(jié)點(diǎn)放入篩選區(qū)中，再進(jìn)行選擇（被選過(guò)的不再被使用），直到所有的節(jié)點(diǎn)都被使用，這樣一個(gè)哈夫曼樹(shù)就被建立了。根據(jù)每個(gè)字符在哈夫曼書(shū)中的位置來(lái)編譯每個(gè)字符的0、1密文代碼，從葉節(jié)點(diǎn)判斷該葉節(jié)點(diǎn)是其父節(jié)點(diǎn)的左右字左字為0，右子為1，在判斷父節(jié)點(diǎn)是上級(jí)父節(jié)點(diǎn)的左右子直至根節(jié)點(diǎn)，將生成的0、1字符串按所表示的字符倒序存入HC相應(yīng)的字符的bins數(shù)組。重新一個(gè)一個(gè)字符的讀取輸入的字符串，按照字符出現(xiàn)的順序?qū)⑺D(zhuǎn)為0、1代碼并存到一個(gè)txt文件夾中去。解碼時(shí)從文件夾中，一個(gè)一

3、個(gè)字符的讀出那串0、1代碼賦給一個(gè)臨時(shí)字符串cd，用該字符串與每個(gè)字符的HCi.bins密文比較，直到與一個(gè)字符的密文相同時(shí)，譯出該字符，將字符存放在臨時(shí)字符數(shù)組tempstr中，清空臨時(shí)字符串繼續(xù)讀取0、1代碼進(jìn)行翻譯，直至文件密文結(jié)束為止。于是就得到了原先被加密的那串字符串。二、算法流程圖 說(shuō)明：將的的字符串進(jìn)行字符種類級(jí)每種字符出現(xiàn)頻率的統(tǒng)計(jì)i+;圖1計(jì)算字符權(quán)值及字符種類算法是j+;strj=i+64; quanj=quantempi;結(jié)束i<27?quantempi=0?k=getstri-64;quantempk+( quantemp為int型數(shù)組開(kāi)始值都為0)i+;i=1,

4、j=0判斷getstri是否為26個(gè)大寫(xiě)字母開(kāi)始獲得輸入的字符串getstr，i=0。i+;否否是否是說(shuō)明：利用選擇排序，選擇節(jié)點(diǎn)權(quán)值最小的兩個(gè)節(jié)點(diǎn)，構(gòu)建一個(gè)子樹(shù)，將該樹(shù)的根節(jié)點(diǎn)再放入選擇區(qū)，重復(fù)該操作，直至用完所有節(jié)點(diǎn)完成哈夫曼數(shù)的搭建。圖2 構(gòu)建哈夫曼樹(shù)算法選擇權(quán)值最小的兩個(gè)節(jié)點(diǎn)將下標(biāo)賦給s1,s2.HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;i+結(jié)束是·i=num+1i<=2*num-1?HTi.weight=quanii=1;(num

5、為字符的種類)開(kāi)始將所有的幾點(diǎn)的父節(jié)點(diǎn)和子節(jié)點(diǎn)權(quán)值賦成0i<=num否是否說(shuō)明：利用每個(gè)字符在哈夫曼樹(shù)中的位子，得到每個(gè)字符的0、1密文編碼。再將字符串按字符密文進(jìn)行編譯，然后存入文件夾中。圖3 利用哈夫曼樹(shù)加密算法否否是HTc.parent>0cd-start=(HTp.lchild=c)?'0':'1' c= HTc.parent;i+start=num; c=i開(kāi)始i=0;cdnum='0'將stri的值依次賦給HCi.chi<=num;strcpy(HCi.bits,&cdstart); HCi.len=num-

6、start;i+結(jié)束否打開(kāi)codefile.txt文件,獲得字符串str指針，i=0；HCi.ch=*str?i<=num;將HCi.bitsj存進(jìn)文件是否是否是說(shuō)明：從文件夾中讀出密文，和HCi.bis中的密文進(jìn)行比較譯出字符，存入臨時(shí)數(shù)組。待譯碼結(jié)束后，輸出字符串。strk=HCj.ch;cjs=1;k+;strk='0'break;j+strcmp(HCj.bits,cd)=0j<=numi+結(jié)束開(kāi)始(i<num)&&(cjs=0)&&(!feof(fp)打開(kāi)文件夾codefile.txt, cjs=0, i=0!feof

7、(fp)圖4 解密算法cdi=''cdi+1='0'cdi=fgetc(fp);j=1;三、源代碼/ hafuman.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。/#include "stdafx.h"#include "stdlib.h"#include "string.h"#include "stdio.h"#define n 100/葉節(jié)點(diǎn)的個(gè)數(shù)小等于n#define m 2*n-1/總結(jié)點(diǎn)的個(gè)數(shù)為m=2*n-1int num;/定義一個(gè)全局變量用于存放字符種類個(gè)數(shù)typedef

8、struct/結(jié)構(gòu)體用于存放樹(shù)節(jié)點(diǎn)包括節(jié)點(diǎn)的父節(jié)點(diǎn)、左子、右子以及權(quán)值 int weight;int parent,lchild,rchild;HTNode;typedef HTNode HafumanTreem+1;/重命名HTNodetypedef struct/結(jié)構(gòu)體由于存放每個(gè)字符的密文和長(zhǎng)度char ch;char bits10;int len;CodeNode;typedef CodeNode HafumanCoden+1;/重命名CodeNodeint _tmain(int argc, _TCHAR* argv)int quan27;/聲明一個(gè)數(shù)組用以存放26字符的權(quán)值char

9、getstr300,str27;/聲明兩個(gè)字符串?dāng)?shù)組一個(gè)用于存輸入一個(gè)由于存放輸入中含有的字符char *s;/聲明一個(gè)char型指針用于指向字符HafumanTree HT;/聲明m+1個(gè)樹(shù)節(jié)點(diǎn)HafumanCode HC;/聲明n+1個(gè)codeint jisuanquan(char *s,int quan,char str);/聲明需要調(diào)用的函數(shù)void gjhafumantree(HafumanTree HT,HafumanCode HC,int quan,char str);void Hafumanencode(HafumanTree HT,HafumanCode HC);void c

10、oding(HafumanCode HC,char *str);char *decode(HafumanCode HC);printf("請(qǐng)輸入要加密的字符串：n");gets(getstr);/獲得輸入的字符串num=jisuanquan(getstr,quan,str);/統(tǒng)計(jì)字符串中含有字符種類個(gè)數(shù)/printf("%dn",num);gjhafumantree(HT,HC,quan,str);/根據(jù)字符權(quán)值構(gòu)建哈夫曼樹(shù)Hafumanencode(HT,HC);/根據(jù)哈夫曼樹(shù)確定每個(gè)字符的codecoding(HC,getstr);/將字符串譯碼存

11、入文件夾s=decode(HC);/將暗文解碼printf("解密為：n");printf("%sn",s);system("pause");return 0;/函數(shù)int jisuanquan(char *s,int quan,char str)/計(jì)算字符串中字符權(quán)值char *p; int i,j,k,quantemp27; for(i=1;i<27;i+)/將所有字符的權(quán)值賦成0 quantempi=0; for(p=s;*p!='0'p+)/判斷字符串是否結(jié)束 if(*p>='A'&

12、amp;&*p<='Z')/判斷字符是否為26字母k=*p-64;/看是26個(gè)字符中的哪個(gè)字符quantempk+;/字符權(quán)值加1 j=0; for(i=1,j=0;i<27;i+)if(quantempi!=0)j+;/用于統(tǒng)計(jì)字符種類個(gè)數(shù)strj=i+64;/str按字母表順序存儲(chǔ)出現(xiàn)過(guò)的字符quanj=quantempi; return j;void select(HafumanTree HT,int k,int *s1,int*s2)/選擇權(quán)值最小的兩個(gè)int i,j; int min1=9999;/聲明一個(gè)int類型的數(shù)值min1，賦個(gè)較大的輸給它

13、 for(i=1;i<=k;i+)/選擇權(quán)值最小的一個(gè)節(jié)點(diǎn)（且該節(jié)點(diǎn)無(wú)父節(jié)點(diǎn)） if(HTi.weight<min1)&&(HTi.parent=0) j=i;min1=HTi.weight; *s1=j; min1=9999; for(i=1;i<=k;i+) if(HTi.weight<min1)&&(HTi.parent=0)&&(i!=*s1)/選擇權(quán)值最小的一個(gè)節(jié)點(diǎn)（且該節(jié)點(diǎn)無(wú)父節(jié)點(diǎn)） j=i;min1=HTi.weight; *s2=j;void gjhafumantree(HafumanTree HT,Haf

14、umanCode HC,int quan,char str) /構(gòu)建哈夫曼樹(shù)int i,s1,s2; for(i=1;i<2*num-1;i+)/將所有的節(jié)點(diǎn)賦空 HTi.lchild=0;HTi.rchild=0; HTi.parent=0;HTi.weight=0; for(i=1;i<=num;i+)/將num個(gè)字符的權(quán)值賦給num葉節(jié)點(diǎn) HTi.weight=quani; for(i=1;i<=num;i+)/將num個(gè)字符賦給codenode HCi.ch=stri; i=1; while(i<=num) printf("=%c=%d=n"

15、,HCi.ch,quani);i+;/輸出每個(gè)字符的及其權(quán)值 for(i=num+1;i<=2*num-1;i+) select(HT,i-1,&s1,&s2);/選擇兩個(gè)權(quán)值最小的葉節(jié)點(diǎn)HTs1.parent=i;HTs2.parent=i;/兩個(gè)節(jié)點(diǎn)指向同一父節(jié)點(diǎn) HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/父節(jié)點(diǎn)的權(quán)值為子節(jié)點(diǎn)相加（父節(jié)點(diǎn)繼續(xù)放入選擇區(qū)） void Hafumanencode(HafumanTree HT,HafumanCode HC)int c,p,i;char c

16、dn;/臨時(shí)數(shù)組用于記錄字符在哈夫曼樹(shù)的位置int start;cdnum='0'/給cd賦個(gè)結(jié)束符for(i=1;i<=num;i+)start=num; c=i; while(p=HTc.parent)>0)/根據(jù)節(jié)點(diǎn)是其父節(jié)點(diǎn)的左右子來(lái)記錄它的位置 cd-start=(HTp.lchild=c)?'0':'1' c=p;/將父節(jié)點(diǎn)轉(zhuǎn)為子節(jié)點(diǎn) strcpy(HCi.bits,&cdstart);/將得到的0、1字串存入結(jié)構(gòu)體HC printf("%c:%sn",HCi.ch,HCi.bits); HCi

17、.len=num-start;/求每個(gè)字符0、1編碼長(zhǎng)度void coding(HafumanCode HC,char *str)/根據(jù)哈夫曼樹(shù)確定每個(gè)字符的0、1代碼codeint i,j;FILE *fp;/聲明一個(gè)文件夾指針fp=fopen("codefile.txt","w");/打開(kāi)文件夾codefileprintf("密文為：n");while(*str)/字符串未結(jié)束時(shí)for(i=1;i<=num;i+)if(HCi.ch=*str)/判斷字符是否在Codenode中存在for(j=0;j<HCi.len;j

18、+)/將codenode中該字符的1、0代碼存入文件夾 fputc(HCi.bitsj,fp);printf("%s",HCi.bits);break; str+;/字符后移printf("n");fclose(fp);char *decode(HafumanCode HC)FILE *fp;char tempstr9999;char *p;static char cdn+1;/char型數(shù)組用于存放從文件夾中讀取的1、0代碼int i,j,k=0,jsjs;fp=fopen("codefile.txt","r")

19、;while(!feof(fp)/當(dāng)文件夾讀取沒(méi)有結(jié)束jsjs=0;/判讀一個(gè)字符是否譯碼結(jié)束for(i=0;(i<num)&&(jsjs=0)&&(!feof(fp);i+)/當(dāng)一個(gè)字符未譯完并且文件未讀取結(jié)束 cdi=' 'cdi+1='0'/讓cd賦成空格cdi=fgetc(fp);/讀取文件夾中的一個(gè)字符for(j=1;j<=num;j+) if(strcmp(HCj.bits,cd)=0)/看cd的字符串是否等于Codenode中的某個(gè)密文tempstrk=HCj.ch;jsjs=1;printf("

20、;=%s=",HCj.bits);k+;break;/將譯出的字符賦給臨時(shí)字符串tempstr,標(biāo)記一個(gè)字符譯碼結(jié)束jsjs賦1，跳出循環(huán)tempstrk='0'/賦給臨時(shí)字符串一個(gè)結(jié)束標(biāo)志p=tempstr;/char型指針指向臨時(shí)字符串return p;四、運(yùn)行結(jié)果圖5 哈夫曼編碼與譯碼運(yùn)行結(jié)果圖五、遇到的問(wèn)題及解決這部分我主要遇到了如下兩個(gè)問(wèn)題，其內(nèi)容與解決方法如下所列：l 當(dāng)我寫(xiě)完程序，輸入一段字符串讓程序進(jìn)行譯碼和解碼是出現(xiàn)了一個(gè)問(wèn)題，譯出的結(jié)果不是想要的結(jié)果，但結(jié)果又有一定規(guī)律，就是結(jié)果中的字符都在明文中出現(xiàn)過(guò)，可是字符數(shù)量明顯比明文中的要少很多。首先我認(rèn)

21、為為題可能出現(xiàn)在我將明文加密后的存儲(chǔ)階段，于是我在程序?qū)?、1代碼存入codeflie.txt文件前，先將臨時(shí)存儲(chǔ)字符串?dāng)?shù)組內(nèi)容輸出，結(jié)果發(fā)現(xiàn)沒(méi)有問(wèn)題，于是我又在，譯碼階段將從codeflie.txt讀出的內(nèi)容逐字輸出發(fā)現(xiàn)結(jié)果和存入的一樣。輸入和輸出都一樣。問(wèn)題不是出現(xiàn)在存儲(chǔ)上，于是我想到問(wèn)題可能出現(xiàn)在，我將0、1編碼轉(zhuǎn)成明文的時(shí)。于是我認(rèn)真的看了看我的decode函數(shù)，添加了些輔助輸出，發(fā)現(xiàn)有寫(xiě)編碼不是原先的一個(gè)字符的譯文，有的是兩個(gè)字符的譯文譯成了一個(gè)字符。于是我又輸進(jìn)一段字符將暗文帶入函數(shù)計(jì)算，發(fā)現(xiàn)問(wèn)題出在但一出一個(gè)字符后，我的一個(gè)循環(huán)并沒(méi)有終止，而是繼續(xù)向cd數(shù)組中添加，1和0；直至cd的長(zhǎng)度超過(guò)num時(shí)才結(jié)束，而下次調(diào)用該循環(huán)式，前面會(huì)有幾個(gè)1、0沒(méi)有被編譯。所以導(dǎo)致了以上的錯(cuò)誤，于是我在函數(shù)中聲明了一個(gè)變量jsjs（計(jì)算結(jié)束），用它在譯完一個(gè)字符是讓函數(shù)跳出循環(huán)。于是問(wèn)題得到了解決。l 第二個(gè)問(wèn)題再之前就出現(xiàn)了只不過(guò)他和前一個(gè)問(wèn)題沒(méi)有多大的聯(lián)系，就是在輸出明文結(jié)果是字符串的結(jié)尾變成了: 燙燙燙燙燙燙燙燙燙燙燙燙燙燙燙燙燙。一開(kāi)始我認(rèn)為他和第一個(gè)問(wèn)題是一個(gè)問(wèn)題，是存儲(chǔ)或者譯碼出錯(cuò)了，但是但第一個(gè)問(wèn)題解決后他依然存在。于是我才確定