哈夫曼編碼和譯碼系統(tǒng)(附源代碼)

1、實(shí)訓(xùn)報(bào)告題 目： 哈夫曼編碼和譯碼系統(tǒng)院 系： 專 業(yè)： 姓 名： 學(xué) 號(hào)： 指導(dǎo)教師： 日 期： 目錄一. 需求分析····································2二. 概要設(shè)計(jì)（1） 建立哈夫曼樹 、編碼

2、83;·····················3（2） 字符匹配···························

3、······3（3） 哈夫曼樹遍歷·····························3三. 詳細(xì)設(shè)計(jì)及編碼實(shí)現(xiàn)···········

4、···············3四. 流程圖（1） 總流程圖································

5、83;15（2） 編碼實(shí)現(xiàn)流程圖···························16（3） 譯碼實(shí)現(xiàn)流程圖··················&

6、#183;········17五. 調(diào)試分析 （1）計(jì)算權(quán)值···································18 （1）生成哈夫曼樹，建立編碼表&#

7、183;··················18 （3）將輸入字符編碼·····························1

8、9 （4）輸入新的字符串，進(jìn)行譯碼···················19 （5）輸入新的二進(jìn)制數(shù)將其譯為字符 ··············20 六. 系統(tǒng)維護(hù)·········

9、·····························20七實(shí)驗(yàn)總結(jié)····················

10、;··················20八. 源代碼······························

11、83;·········21一需求分析1問題描述：在傳送電文時(shí)，人們總是希望傳送時(shí)間盡可能短，這就是要求使電文代碼長(zhǎng)度盡可能短。利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)能夠?qū)Υ齻鬏敂?shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每段都需要一個(gè)完整的編/譯系統(tǒng)。所以為這樣的信息收發(fā)站寫一個(gè)哈夫曼的編譯碼系統(tǒng)。2打開一篇英文文章，統(tǒng)計(jì)該文章中每個(gè)字符出現(xiàn)的次數(shù)，然后以它們作為權(quán)值，對(duì)每一個(gè)字符進(jìn)行編

12、碼，編碼完成后再對(duì)其編碼進(jìn)行譯碼。 問題補(bǔ)充：1. 從硬盤的一個(gè)文件里讀出一段英語(yǔ)文章。2. 統(tǒng)計(jì)這篇文章中的每個(gè)字符出現(xiàn)的次數(shù)。3. 以字符出現(xiàn)字?jǐn)?shù)作為權(quán)值，構(gòu)建哈夫曼樹，并將哈夫曼樹的存儲(chǔ) 結(jié)構(gòu)的初態(tài)和終態(tài)進(jìn)行輸出。 4. 對(duì)每個(gè)字符進(jìn)行編碼并將所編碼寫入文件然后對(duì)所編碼進(jìn)行編譯。 3這個(gè)哈夫曼編碼譯碼主要是以英文字母輸入進(jìn)行編碼與編譯，編碼譯碼過程由系統(tǒng)自動(dòng)完成，人工操作部分就是電文的錄入，和編譯出來時(shí)的讀操作。二概要設(shè)計(jì)本程序主要用到了三個(gè)算法。(1)哈夫曼樹建立、編碼在初始化(I)的過程中間，要用輸入的字符和權(quán)值建立哈夫曼樹并求得哈夫曼編碼。先將輸入的字符和權(quán)值存放到一個(gè)結(jié)構(gòu)體數(shù)組中

13、，建立哈夫曼樹，將計(jì)算所得的哈夫曼編碼存儲(chǔ)到另一個(gè)結(jié)構(gòu)體數(shù)組中。(2)串的匹配在編碼(D)的過程中間，要對(duì)已經(jīng)編碼過的代碼譯碼，可利用循環(huán)，將代碼中的與哈夫曼編碼的長(zhǎng)度相同的串與這個(gè)哈夫曼編碼比較(3)哈夫曼遍歷 在印哈夫曼樹(T)的中，因?yàn)楣蚵鼧湟彩嵌鏄?，所以就要利用二叉樹的先序遍歷將哈夫曼樹輸出。三詳細(xì)設(shè)計(jì)及編碼實(shí)現(xiàn)構(gòu)造哈夫曼樹的方法如下：   初始化：每個(gè)字符就是一個(gè)結(jié)點(diǎn)，字符的頻度就是結(jié)點(diǎn)的權(quán)；     1、將結(jié)點(diǎn)按頻度從小到大排序；     2、選取頻度最小的兩個(gè)結(jié)點(diǎn)，以它們?yōu)閮鹤?，?gòu)造出一個(gè)新的結(jié)點(diǎn)；新結(jié)點(diǎn)的權(quán)值就是它兩個(gè)兒子的

14、權(quán)值之和；構(gòu)造之后，從原來的結(jié)點(diǎn)序列里刪除剛才選出的那兩個(gè)結(jié)點(diǎn)，但同時(shí)將新生成的結(jié)點(diǎn)加進(jìn)去；     3、如果結(jié)點(diǎn)序列里只剩下一個(gè)結(jié)點(diǎn)，表示構(gòu)造完畢，退出。否則回到第一步。編碼：     上面已經(jīng)生成了樹，接著就該對(duì)該樹進(jìn)行編碼了。     可以假定，對(duì)某個(gè)結(jié)點(diǎn)而言，其左孩子在當(dāng)前階段的編碼為0，右孩子的編碼為1。這樣就可以通過“樹的遍歷”的方式來生成字符編碼對(duì)照表。  來到這里，基本上艱苦的已經(jīng)完成了，對(duì)某個(gè)具體的字符串編碼和解碼就只是簡(jiǎn)單的“查表替換”的工作了。   譯碼：     

15、0;   譯碼也是個(gè)簡(jiǎn)單的查表-替換過程。如果利用該種編碼發(fā)送字符串，則它的“字符編碼”對(duì)應(yīng)表也必須發(fā)送過去，不然對(duì)方是不知道怎么解碼的。         對(duì)給出的一串編碼，從左向右，將編碼組合起來并查表，“一旦”找到有匹配的字符，則馬上將當(dāng)前的編碼替換為對(duì)應(yīng)的字符。         因?yàn)樵摼幋a是不會(huì)出現(xiàn)”某一個(gè)字符的編碼是另一個(gè)字符編碼的綴”這種情況的，也就是不會(huì)出現(xiàn)類似于“A   00   B   0010”   這樣的情況，所以譯碼出來的字符串是唯一的，而且就

16、是原來進(jìn)行編碼的那一個(gè)。代碼如下：（1）求頻率遍歷過程：int Frequent(char *p)char *pt2=p;int i=0;ch0=*pt2;freq0=0;while(*pt2!='0')for(int j=0;j<=i;j+) /在ch0chi中遍歷是否有*pt2if(chj=*pt2)freqj+;break;if(j>i) /遍歷結(jié)束，該字符目前頻度為1，跳至下一個(gè)字符i+;chi=*pt2;freqi=1;pt2+;cout<<endl<<"統(tǒng)計(jì)權(quán)值："<<endl;for(int j=

17、0;j<=i;j+)cout<<"字符"<<chj<<"的權(quán)值為"<<freqj<<endl;return i+1;（2） 預(yù)程序處理及結(jié)構(gòu)體定義：#include <iostream>#include <string>using namespace std;struct HNode int weight;int parent;int LChild;int RChild;struct HCode / 哈夫曼編碼表char data;char code100;clas

18、s Huffmanprivate:HNode* HTree;HCode* HCodeTable;int SentenceLen; /編碼前長(zhǎng)度int CodeLen; /編碼后長(zhǎng)度protected:void SelectMin(int&x,int&y,int start,int end); / 從1-i中選取權(quán)值最小的兩個(gè)結(jié)點(diǎn)（x,y為游標(biāo)）void Reverse(char *,int); / 將編碼字符逆置public:void Init(int a,int n);void CreateTable(char b,int n);void Encode(char *c, ch

19、ar *s,int n); void Decode(char *s, char *d,int n);Huffman();（3） 主函數(shù)main：void main()Huffman obj;char *sentence1=new char500;char *code01=new char1000;*code01='0'cout<<"n 請(qǐng)輸入所需文章:"<<endl;gets(sentence1);int n=Frequent(sentence1);char *sentence2=new char500;char *sentence3

20、=new char500;for(int i=0;i<=499;i+)*(sentence3+i)='0'char *code02=new char1000;*code02='0'cout<<"*"<<endl<<" 菜單:"<<endl<<" 1.建立編碼表nn 2.編碼nn 3.編碼新字符串nn 4.譯碼新編碼串nn 5.退出n*"<<endl;cout<<"nn請(qǐng)選擇菜單：n*"<&

21、lt;endl;int w;bool tag=1;while(tag) /菜單設(shè)計(jì) 6 tag=0,結(jié)束菜單cin>>w;switch(w)case 1:obj.Init(freq,n);obj.CreateTable(ch,n);cout<<"nn請(qǐng)選擇菜單：n*"<<endl;break;case 2:obj.Encode(sentence1,code01,n);cout<<"nn請(qǐng)選擇菜單：n*"<<endl;break;case 3:gets(sentence2);cout<<

22、;endl<<"請(qǐng)根據(jù)已編碼字符再輸入一句話："<<endl;gets(sentence2);obj.Encode(sentence2,code02,n);cout<<"nn請(qǐng)選擇菜單：n*"<<endl;break;case 4:gets(code01);cout<<endl<<"請(qǐng)根據(jù)編碼表輸入一個(gè)編碼后的編碼串："<<endl;gets(code01);obj.Decode(code01,sentence3,n);cout<<&quo

23、t;nn請(qǐng)選擇菜單：n*"<<endl;break;case 5:tag=0;break;default: cout<<"選擇錯(cuò)誤，請(qǐng)重新選擇！"<<endl;cout<<endl;break;（4） 初始化并創(chuàng)建哈夫曼樹：void Huffman:Init(int a,int n)int x=0,y=0;HTree= new HNode2*n-1;for(int i=0;i<n;i+) HTreei.weight=ai; /根據(jù)權(quán)重?cái)?shù)組a初始化哈夫曼樹HTreei.LChild=-1; /初始化HTreei.

24、RChild=-1; /初始化HTreei.parent=-1; /初始化for(i=n; i<2*n-1;i+) /開始建哈夫曼樹SelectMin(x,y,0,i); / 從1-i中選出2個(gè)權(quán)值最小的結(jié)點(diǎn)HTreex.parent=HTreey.parent=i;HTreei.weight=HTreex.weight+HTreey.weight;HTreei.LChild=x;HTreei.RChild=y;HTreei.parent=-1; / 節(jié)點(diǎn)無(wú)數(shù)據(jù)void Huffman:CreateTable(char b,int n)cout<<endl<<&q

25、uot;打印編碼表："<<endl;HCodeTable=new HCoden; / 生成編碼表for(int i=0; i<n; i+)HCodeTablei.data=bi;int child=i;int parent=HTreei.parent;int k=0;while(parent!=-1)if(child=HTreeparent.LChild)HCodeTablei.codek='0' /左孩子標(biāo)0elseHCodeTablei.codek='1' /右孩子標(biāo)1k+;child=parent;parent=HTreechi

26、ld.parent;HCodeTablei.codek='0'Reverse(HCodeTablei.code,k-1+1);cout<<HCodeTablei.data<<"的編碼是："<<HCodeTablei.code<<endl;（5） 編碼：void Huffman:Encode(char *c, char *s,int n) /編碼SentenceLen=strlen(c);while(*c!='0') /字符串是否為空for(int i=0;i<=n-1;i+)if(*c=H

27、CodeTablei.data) /如果有值strcat(s,HCodeTablei.code);break;c+;CodeLen=strlen(s);cout<<endl<<"編碼后結(jié)果："<<s<<endl;（6） 譯碼：void Huffman:Decode(char *s, char *d,int n) /譯碼 s為編碼串，d為譯碼后的字符串char *pd=d; /存儲(chǔ)當(dāng)前指針位置，方便最后輸出。while(*s!='0')int parent=2*n-2; /根結(jié)點(diǎn)在HTree中的下標(biāo)while(H

28、Treeparent.LChild!=-1) /判斷有無(wú)節(jié)點(diǎn)if(*s='0') parent=HTreeparent.LChild;elseparent=HTreeparent.RChild;s+;*d=HCodeTableparent.data;d+;cout<<endl<<"譯碼后結(jié)果："<<pd<<endl;4 流程圖 總流程圖Huffman_Tree()CharCodeFile()LoadeCode()LoadHuffman()Show_HuffCode()CharCode()InitHuffman(

29、)strlen()WrightHuffman1()CharWeight()Huffman_Code()HuffmanMenu()Hencode() 編碼實(shí)現(xiàn)流程圖結(jié)束c+SentenceLen=strlen(c) c+CodeLen=strlen(s)if(*c=HCodeTablei.data)開始將字符存入哈夫曼樹結(jié)構(gòu)體數(shù)組的字符單元 譯碼實(shí)現(xiàn)流程圖開始Root指向節(jié)點(diǎn)P!=rootCodei=0p->LChild=NULL&p->RChild=NULLP=p->LChildSk+=strjP=root結(jié)束P=p->RChild五、調(diào)試分析：1.統(tǒng)計(jì)權(quán)值：2

30、. 生成哈夫曼樹，建立編碼表3.將輸入字符編碼4. 輸入新的字符串，進(jìn)行編碼5.輸入任意譯文可以得到原文六、系統(tǒng)維護(hù)經(jīng)測(cè)試與調(diào)試確認(rèn)軟件無(wú)錯(cuò)時(shí)，開發(fā)就告一段落，這時(shí)可以交付軟件供用戶使用，但是在軟件的使用過程中還會(huì)面臨更加漫長(zhǎng)的工作，即軟件維護(hù)。一般維護(hù)的工作有：更改使用中發(fā)現(xiàn)的錯(cuò)誤；為適應(yīng)實(shí)際環(huán)境而對(duì)程序進(jìn)行修改；為滿足新的需求而對(duì)程序作必要的改進(jìn)等等。七、實(shí)驗(yàn)總結(jié)通過簡(jiǎn)單哈夫曼編碼和譯碼的設(shè)計(jì)與實(shí)現(xiàn)來掌握樹型結(jié)構(gòu)，學(xué)會(huì)用順序表作為哈夫曼樹的存儲(chǔ)結(jié)構(gòu)。所編程序的各個(gè)模塊比較清晰，分塊編寫程序，然后在整個(gè)程序中對(duì)各子模塊函數(shù)進(jìn)行調(diào)用，是編寫程序的重點(diǎn)。執(zhí)行過程、比較順利。 實(shí)現(xiàn)哈夫曼樹的建立及

31、哈弗曼編碼的構(gòu)造上學(xué)到不少細(xì)節(jié)問題解決的方法，積累了獨(dú)立思考問題和解決問題的些許能力。程序編寫要特別注意細(xì)節(jié)問題，善用指針，做到合理真卻。 但是在實(shí)驗(yàn)過程中，遇到了很多問題，在編寫程序之前沒有仔細(xì)的分析實(shí)驗(yàn)的目的和要求就動(dòng)手做實(shí)驗(yàn)，導(dǎo)致走了很多彎路，而且總是卡住。另外在哈夫曼編碼時(shí)，考慮的不夠周到，這也是由于認(rèn)識(shí)不夠全面。 程序雖然最終實(shí)現(xiàn)了特定的功能，但就編寫效率，算法優(yōu)化，程序執(zhí)行效率方面還的有很大的提高！學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)就是提高時(shí)間效率，降低空間復(fù)雜度。 實(shí)訓(xùn)是迅速提高教學(xué)要求的主要手段，所以，在今后要多動(dòng)手，動(dòng)腦，為自己的成功做好堅(jiān)實(shí)的根基。我相信未來一定會(huì)做的越來越好。驗(yàn)收的時(shí)候設(shè)備出了

32、點(diǎn)小故障，沒能很好的順利驗(yàn)收，下次會(huì)好好注意。8. 源代碼#include <iostream>#include <string>using namespace std;struct HNode int weight;int parent;int LChild;int RChild;struct HCode / 哈夫曼編碼表char data;char code100;class Huffmanprivate:HNode* HTree;HCode* HCodeTable;int SentenceLen; /編碼前長(zhǎng)度int CodeLen; /編碼后長(zhǎng)度protecte

33、d:void SelectMin(int&x,int&y,int start,int end); / 從1-i中選取權(quán)值最小的兩個(gè)結(jié)點(diǎn)（x,y為游標(biāo)）void Reverse(char *,int); / 將編碼字符逆置public:void Init(int a,int n);void CreateTable(char b,int n);void Encode(char *c, char *s,int n); void Decode(char *s, char *d,int n);Huffman();void Huffman:Init(int a,int n)int x=0,

34、y=0;HTree= new HNode2*n-1;for(int i=0;i<n;i+) HTreei.weight=ai; /根據(jù)權(quán)重?cái)?shù)組a初始化哈夫曼樹HTreei.LChild=-1; /初始化HTreei.RChild=-1; /初始化HTreei.parent=-1; /初始化for(i=n; i<2*n-1;i+) /開始建哈夫曼樹SelectMin(x,y,0,i); / 從1-i中選出2個(gè)權(quán)值最小的結(jié)點(diǎn)HTreex.parent=HTreey.parent=i;HTreei.weight=HTreex.weight+HTreey.weight;HTreei.LCh

35、ild=x;HTreei.RChild=y;HTreei.parent=-1; / 節(jié)點(diǎn)無(wú)數(shù)據(jù)void Huffman:CreateTable(char b,int n)cout<<endl<<"打印編碼表："<<endl;HCodeTable=new HCoden; / 生成編碼表for(int i=0; i<n; i+)HCodeTablei.data=bi;int child=i;int parent=HTreei.parent;int k=0;while(parent!=-1)if(child=HTreeparent.LCh

36、ild)HCodeTablei.codek='0' /左孩子標(biāo)0elseHCodeTablei.codek='1' /右孩子標(biāo)1k+;child=parent;parent=HTreechild.parent;HCodeTablei.codek='0'Reverse(HCodeTablei.code,k);cout<<HCodeTablei.data<<"的編碼是："<<HCodeTablei.code<<endl;void Huffman:Encode(char *c, cha

37、r *s,int n) /編碼SentenceLen=strlen(c);while(*c!='0') /字符串是否為空for(int i=0;i<=n-1;i+)if(*c=HCodeTablei.data) /如果有值strcat(s,HCodeTablei.code);break;c+;CodeLen=strlen(s);cout<<endl<<"編碼后結(jié)果："<<s<<endl;void Huffman:Decode(char *s, char *d,int n) /譯碼 s為編碼串，d為譯碼后的

38、字符串char *pd=d; /存儲(chǔ)當(dāng)前指針位置，方便最后輸出。while(*s!='0')int parent=2*n-2; /根結(jié)點(diǎn)在HTree中的下標(biāo)while(HTreeparent.LChild!=-1) /判斷有無(wú)節(jié)點(diǎn)if(*s='0') parent=HTreeparent.LChild;elseparent=HTreeparent.RChild;s+;*d=HCodeTableparent.data;d+;cout<<endl<<"譯碼后結(jié)果："<<pd<<endl;void H

39、uffman:SelectMin(int &x,int &y,int n1,int n2)/從下標(biāo)n1開始到n2-1的結(jié)點(diǎn)中找出沒分配父結(jié)點(diǎn)的最小的兩個(gè)，x，y分別為其下標(biāo)，x更小if(n2-n1<1)throw "error"x=-1;y=-1; /x,y為游標(biāo)，初始值為-1for(int i=n1; i<n2; i+)if(HTreei.parent=-1) /未分配父結(jié)點(diǎn)if(x=-1)x=i;else if(y=-1)if(HTreex.weight<HTreei.weight) /x,y中x的權(quán)值更小y=i;elsey=x;x=i

40、;else if(HTreei.weight<HTreex.weight) /x,y中x的權(quán)值更小y=x;x=i;else if(HTreei.weight<HTreey.weight)y=i;void Huffman:Reverse(char *c,int len) / 字符逆置for(int i=0;i<=len/2-1;i+)char temp=*(c+i);*(c+i)=*(c+len-1-i);*(c+len-1-i)=temp;char ch50;int freq50=0;int Frequent(char *p); /統(tǒng)計(jì)字符串p各字符出現(xiàn)的頻率（權(quán)值）void main()Huffman obj;char *sentence1=new char500;char *code01=new char1000;*code01='0'cout<<"n 請(qǐng)輸入所需文章:"<<endl;gets(sentence1);int n=Frequent(sentence1);char *sentence2=new char500;char *sentence3=new char500;for(int i=0;i<=499;i+)*(sentence3+i)=&#