哈夫曼編碼與譯碼報告要點

---、設(shè)計思想程序要求：利用哈夫曼樹對字符串進(jìn)行編碼,要求每個字符有自己唯一的編碼。將得到的一串字串譯成0、1編碼后存到一個文件夾中，然后再從這個文件夾中讀出這串編碼進(jìn)行解碼。實現(xiàn)方法：輸入一串字符，要求字符的區(qū)間為大寫的26個英文字母，將獲得的串字符用計算權(quán)值的函數(shù)（jsquanzhi（））進(jìn)行字符統(tǒng)計，統(tǒng)計出現(xiàn)的字符種數(shù)以及每種字符出現(xiàn)的次數(shù)，將該種字符出現(xiàn)的次數(shù)作為它的權(quán)值。將出現(xiàn)的字符的權(quán)值和該字符依次分別賦給兩個結(jié)構(gòu)體HT和HC，利用HT（節(jié)點）權(quán)值的大小建立哈夫曼樹，首先用選擇函數(shù)select（）函數(shù)選擇兩個權(quán)值最小的字符作為葉子節(jié)點，創(chuàng)建一個新的節(jié)點作為這兩個葉節(jié)點的父節(jié)點，被選中的節(jié)點給他的HT[i].parent賦值是他下次不再被選中，父節(jié)點的權(quán)值為，子節(jié)點的權(quán)值之和。然后將該將父節(jié)點放入篩選區(qū)中，再進(jìn)行選擇（被選過的不再被使用），直到所有的節(jié)點都被使用，這樣一個哈夫曼樹就被建立了。根據(jù)每個字符在哈夫曼書中的位置來編譯每個字符的0、1密文代碼，從葉節(jié)點判斷該葉節(jié)點是其父節(jié)點的左右字左字為‘0’，右子為‘1’，在判斷父節(jié)點是上級父節(jié)點的左右子直至根節(jié)點，將生成的0、1字符串按所表示的字符倒序存入HC相應(yīng)的字符的bins口數(shù)組。重新一個一個字符的讀取輸入的字符串，按照字符出現(xiàn)的順序?qū)⑺D(zhuǎn)為0、1代碼并存到一個txt文件夾中去。解碼時從文件夾中，一個一個字符的讀出那串0、1代碼賦給一個臨時字符串cd口，用該字符串與每個字符的HC[i].bins密文比較，直到與一個字符的密文相同時，譯出該字符，將字符存放在臨時字符數(shù)組tempstr口中，清空臨時字符串繼續(xù)讀取0、1代碼進(jìn)行翻譯，直至文件密文結(jié)束為止。于是就得到了原先被加密的那串字符串。二、算法流程圖圖1計算字符權(quán)值及字符種類算法說明：將的的字符串進(jìn)行字符種類級每種字符出現(xiàn)頻率的統(tǒng)計圖2構(gòu)建哈夫曼樹算法說明：利用選擇排序，選擇節(jié)點權(quán)值最小的兩個節(jié)點，構(gòu)建一個子樹，將該樹的根節(jié)點再放入選擇區(qū)，重復(fù)該操作，直至用完所有節(jié)點完成哈夫曼數(shù)的搭建。

圖3利用哈夫曼樹加密算法說明：利用每個字符在哈夫曼樹中的位子，得到每個字符的0、1密文編碼。再將字符串按字符密文進(jìn)行編譯，然后存入文件夾中。圖4解密算法說明：從文件夾中讀出密文，和HC[i].bis中的密文進(jìn)行比較譯出字符，存入臨時數(shù)組。待譯碼結(jié)束后，輸出字符串。#definen100#definen100#definem2*n-1intnum;〃重命名HTNode//結(jié)構(gòu)體由于存放每個字符的密文和長度〃重命名CodeNode//聲明一個數(shù)組用以存放26字符的權(quán)值型指針用于指向字符三、源代碼//hafuman.cpp:定義控制臺應(yīng)用程序的入口點。//#include"stdafx.h"#include"stdlib.h"#include"string.h"#include"stdio.h"〃葉節(jié)點的個數(shù)小等于n〃總結(jié)點的個數(shù)為m=2*n-1//定義一個全局變量用于存放字符種類個數(shù)//結(jié)構(gòu)體用于存放樹節(jié)點包括節(jié)點的父節(jié)點、左子、右子以及權(quán)值//結(jié)構(gòu)體用于存放樹節(jié)點包括節(jié)點的父節(jié)點、左子、右子以及權(quán)值{intweight;intparent,lchild,rchild;}HTNode;typedefHTNodeHafumanTree[m+1];typedefstruct{charch;charbits[10];intlen;}CodeNode;typedefCodeNodeHafumanCode[n+1];int_tmain(intargc,_TCHAR*argv[]){intquan[27];chargetstr[300],str[27];//聲明兩個字符串?dāng)?shù)組一個用于存輸入一個由于存放輸入中含有的字符char*s;//聲明一個charHafumanTreeHT;//聲明m+1個樹節(jié)點HafumanCodeHC;//聲明n+1個codeintjisuanquan(char*s,intquan[],charstr[]);//聲明需要調(diào)用的函數(shù)voidgjhafumantree(HafumanTreeHT,HafumanCodeHC,intquan[],charstr[]);voidHafumanencode(HafumanTreeHT,HafumanCodeHC);voidcoding(HafumanCodeHC,char*str);char*decode(HafumanCodeHC);printf("請輸入要加密的字符串:\n");gets(getstr);num=jisuanquan(getstr,quan,str);//printf("%d\n",num);gjhafumantree(HT,HC,quan,str);Hafumanencode(HT,HC);coding(HC,getstr);s=decode(HC);printf("解密為:\n");printf("%s\n",s);system("pause");return0;}

//獲得輸入的字符串//統(tǒng)計字符串中含有字符種類個數(shù)//根據(jù)字符權(quán)值構(gòu)建哈夫曼樹〃根據(jù)哈夫曼樹確定每個字符的code//將字符串譯碼存入文件夾//將暗文解碼//函數(shù)intjisuanquan(char*s,intquan[],charstr[]){char*p;inti,j,k,quantemp[27];for(i=1;i<27;i++){quantemp[i]=0;}for(p=s;*p!='\0';p++){if(*p>='A'&&*p<='Z'){k=*p-64;quantemp[k]++;}}j=0;for(i=1,j=0;i<27;i++){if(quantemp[i]!=0){j++;str[j]=i+64;quan[j]=quantemp[i];}}returnj;}//計算字符串中字符權(quán)值//將所有字符的權(quán)值賦成0//判斷字符串是否結(jié)束//判斷字符是否為26字母//看是26個字符中的哪個字符//字符權(quán)值加1//用于統(tǒng)計字符種類個數(shù)//str按字母表順序存儲出現(xiàn)過的字符////將所有的節(jié)點賦空//將num個字符的權(quán)值賦給num葉節(jié)點//將num個字符賦給codenode//輸出每個字符的及其權(quán)值//選擇兩個權(quán)值最小的葉節(jié)點//兩個節(jié)點指向同一父節(jié)點voidselect(HafumanTreeHT,intk,int*s1,int*s2)//選擇權(quán)值最小的兩個{inti,j;intmin1=9999;〃聲明一個int類型的數(shù)值mini,賦個較大的輸給它for(i=1;i<=k;i++)//選擇權(quán)值最小的一個節(jié)點(且該節(jié)點無父節(jié)點){if((HT[i].weight<min1)&&(HT[i].parent==0)){j=i;min1=HT[i].weight;}}*s1=j;min1=9999;for(i=1;i<=k;i++){if((HT[i].weight<min1)&&(HT[i].parent==0)&&(i!=*s1))//選擇權(quán)值最小的一個節(jié)點(且該節(jié)點無父節(jié)點){j=i;min1=HT[i].weight;}}*s2=j;}voidgjhafumantree(HafumanTreeHT,HafumanCodeHC,intquan[],charstr[])//構(gòu)建哈夫曼樹{inti,s1,s2;for(i=1;i<2*num-1;i++){HT[i].lchild=0;HT[i].rchild=0;HT[i].parent=0;HT[i].weight=0;}for(i=1;i<=num;i++){HT[i].weight=quan[i];}for(i=1;i<=num;i++){HC[i].ch=str[i];}i=1;while(i<=num){printf("===%c===%d===\n",HC[i].ch,quan[i]);i++;}for(i=num+1;i<=2*num-1;i++){select(HT,i-1,&s1,&s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;//父節(jié)點的權(quán)值為子節(jié)點相加（父節(jié)點繼續(xù)放入選擇區(qū)）

voidHafumanencode(HafumanTreeHT,HafumanCodeHC){intc,p,i;charcd[n];intstart;charcd[n];intstart;cd[num]='\0';for(i=1;i<=num;i++){start=num;c=i;while((p=HT[c].parent)>0){cd[--start]=(HT[p].lchild==c)?'0':'1';c=p;}strcpy(HC[i].bits,&cd[start]);printf("%c:%s\n",HC[i].ch,HC[i].bits);HC[i].len=num-start;}}//臨時數(shù)組用于記錄字符在哈夫曼樹的位置〃給cd賦個結(jié)束符//根據(jù)節(jié)點是其父節(jié)點的左右子來記錄它的位置//將父節(jié)點轉(zhuǎn)為子節(jié)點〃將得到的0、1字串存入結(jié)構(gòu)體HC//求每個字符0、1編碼長度voidcoding(HafumanCodeHC,char*str){inti,j;FILE*fp;fp=fopen("codefile.txt","w");printfvoidcoding(HafumanCodeHC,char*str){inti,j;FILE*fp;fp=fopen("codefile.txt","w");printf("密文為:\n");while(*str){for(i=1;i<=num;i++){if(HC[i].ch==*str){for(j=0;j<HC[i].len;j++){fputc(HC[i].bits[j],fp);}printf("%s",HC[i].bits);break;〃根據(jù)哈夫曼樹確定每個字符的0、1代碼code//聲明一個文件夾指針〃打開文件夾codefile//字符串未結(jié)束時〃判斷字符是否在Codenode中存在〃將codenode中該字符的1、0代碼存入文件夾}}str++;//字符后移}printf("\n");fclose(fp);}char*decode(HafumanCodeHC){FILE*fp;chartempstr[9999];char*p;staticcharcd[n+1];char*decode(HafumanCodeHC){FILE*fp;chartempstr[9999];char*p;staticcharcd[n+1];inti,j,k=0,jsjs;fp=fopen("codefile.txt","r");//char型數(shù)組用于存放從文件夾中讀取的1、0代碼while(!feof(fp)){jsjs=0;for(i=0;(i<num)&&(jsjs==0)&&(!feof(fp));i++){cd[i]='';cd[i+1]='\0';cd[i]=fgetc(fp);//當(dāng)文件夾讀取沒有結(jié)束//判讀一個字符是否譯碼結(jié)束//當(dāng)一個字符未譯完并且文件未讀取結(jié)束〃讓cd口賦成空格//讀取文件夾中的一個字符for(j=1;j<=num;j++){if(strcmp(HC[j].bits,cd)==0)〃看cd口的字符串是否等于Codenode中的某個密文{tempstr[k]=HC[j].ch;jsjs=1;printf("=%s=",HC[j].bits);k++;break;}〃將譯出的字符賦給臨時字符串tempstr口，標(biāo)記一個字符譯碼結(jié)束jsjs賦1,跳出循環(huán)}}}tempstr[k]='\0';//賦給臨時字符串一個結(jié)束標(biāo)志p=tempstr;//char型指針指向臨時字符串returnp;}四、運行結(jié)果>HI:\Users\Sen\documerts\visualstudio2010\Projects\hafuman\Debug\hafuman.eMe情輸入要加密的字符串：JKDSFHGKJDHGKFJDHFKJHKDJSHBKJDFKJHKDJSHFKJDHKJHKJDSFHGEURVUBCZ輸入密密文氐其權(quán)宿：C：101000D：100E：101001F：010G：10111H：110J:lllK：00R：101010s：0111U：1010ilU：101100V：101101密文為：11100100011101011010111001111001101011100010111100110010001111100010011101111100110100111100010001111100010011101111100100011110011000111110001111000111010110101111010011011001010101011011010110110110100001100解密為：JKDSFHGKJDHGKFJDHFKJHKDJSHBKJDFKJHKDJSHFKJDHKJHKJDSFHGEHRYUBCZ請按任意鍵繼續(xù)...?圖5哈夫曼編碼與譯碼運行結(jié)果圖五、遇到的問題及解決這部分我主要遇到了如下兩個問題，其內(nèi)容與解決方法如下所列：當(dāng)我寫完程序，輸入一段字符串讓程序進(jìn)行譯碼和解碼是出現(xiàn)了一個問題，譯出的結(jié)果不是想要的結(jié)果，但結(jié)果又有一定規(guī)律，就是結(jié)果中的字符都在明文中出現(xiàn)過，可是字符數(shù)量明顯比明文中的要少很多。首先我認(rèn)為為題可能出現(xiàn)在我將明文加密后的存儲階段，于是我在程序?qū)?、1代碼存入codeflie.txt文件前，先將臨時存儲字符串?dāng)?shù)組內(nèi)容輸出，結(jié)果發(fā)現(xiàn)沒有問題，于是我又在，譯碼階段將從codeflie.txt讀出的內(nèi)容逐字輸出發(fā)現(xiàn)結(jié)果和存入的一樣。輸入和輸出都一樣。問題不是出現(xiàn)在存儲上，于是我想到問題可能出現(xiàn)在，我將0、1編碼轉(zhuǎn)成明文的時。于是我認(rèn)真的看了看我的decode函數(shù)，添加了些輔助輸出，發(fā)現(xiàn)有寫編碼不是原先的一個字符的譯文，有的是兩個字符的譯文譯成了一個字符。于是我又輸進(jìn)一段字符將暗文帶入函數(shù)計算，發(fā)現(xiàn)問題出在但一出一個字符后，我的一個循環(huán)并沒有終止，而是繼續(xù)向cd口數(shù)組中添加，1和0；直至cd口的長度超過num時才結(jié)束，而下次調(diào)用該循環(huán)式，前面會有幾個1、0沒有被編譯。所以導(dǎo)致了以上的錯誤，于是我在函數(shù)中聲明了一個變量jsjs（計算結(jié)束），用它在譯完一個字符是讓函數(shù)跳出循環(huán)。于是問題得到了解決。第二個問題再之前就出現(xiàn)了只不過他和前一個問題沒有多大的聯(lián)系，就是在輸出明文結(jié)果是字符串的結(jié)尾變成了:燙燙燙燙燙燙燙燙燙燙燙燙燙燙燙燙燙…………。一開始我認(rèn)為他和第一個問題是一個問題，是存儲或者譯碼出錯了，但是但第一個問題解決后他依然存在。于是我才確定這是另外的一個問題。根據(jù)以晚的經(jīng)驗出現(xiàn)這種情況的原因就幾種，存儲