哈夫曼編碼譯碼

1、哈夫曼編碼/譯碼 一、【實(shí)驗(yàn)內(nèi)容】【問(wèn)題描述】 利用哈夫曼編碼進(jìn)行住處通訊可以大大提高信道利用率,縮短住處傳輸時(shí)間,降低成本,但是,這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)將傳輸?shù)臄?shù)據(jù)預(yù)先編碼,在接收端通過(guò)一個(gè)譯碼系統(tǒng)對(duì)傳來(lái)的數(shù)據(jù)進(jìn)行譯碼(復(fù)原),對(duì)于雙向傳輸信息的信道,每端都一個(gè)完整的編碼譯碼系統(tǒng),試為這樣的住處收發(fā)站寫一個(gè)哈夫曼友的編碼譯碼系統(tǒng).【基本要求】：一個(gè)完整的系統(tǒng)應(yīng)以下功能:(1) I. 初始化(Initialization)。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值,建立哈夫曼樹,并將它存放在文件hfmTree中.(2) E. 編碼(Encoding)。利用已建立好的哈夫曼樹（如不

2、在內(nèi)存，則從文件hfmTree中讀入），對(duì)文件ToBeTran中的正文進(jìn)行編碼,然后將結(jié)果代碼存(傳輸)到文件CodeFile中.(3) D. 譯碼(Decoding)。利用已建好的哈夫曼樹,對(duì)傳輸?shù)竭_(dá)的CodeFile中的數(shù)據(jù)代碼進(jìn)行譯碼,將譯碼結(jié)果存入文件TextFile中. (4) P. 印文件代碼(Print)。將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件CodePrin中。 (5) T. 印哈夫曼樹(TreePrinting)。將已在內(nèi)存中的哈夫曼樹以直觀的方式(樹或凹入表的形式)顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件Tr

3、eePrint中。測(cè)試數(shù)據(jù)：(1)利用教科書例6-2中的數(shù)據(jù)調(diào)試程序。(2)用下表給出的字符集和頻度的計(jì)數(shù)據(jù)建立哈曼樹,并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”.。字符 A B C D E F G H I J K L M頻數(shù)186 64 13 22 32 103 21 15 47 57 1 5 32 20字符N O P Q R S T U V W X Y Z頻數(shù)57 63 15 1 48 51 80 23 8 18 1 16 1 二、實(shí)驗(yàn)?zāi)康臉湫徒Y(jié)構(gòu)是一種應(yīng)用極為廣泛的非線性數(shù)據(jù)結(jié)構(gòu),也是本課程的重點(diǎn)內(nèi)容,哈夫曼樹(最優(yōu)二叉樹)是樹型結(jié)構(gòu)的典型應(yīng)用

4、,本次實(shí)驗(yàn)突出了數(shù)據(jù)結(jié)構(gòu)加操作的程序設(shè)計(jì)觀點(diǎn),希望能根據(jù)樹型結(jié)構(gòu)的非線性特點(diǎn),熟悉各種存儲(chǔ)結(jié)構(gòu)的特性,達(dá)到如何應(yīng)用樹型結(jié)構(gòu)的非線性特點(diǎn),熟悉各種存儲(chǔ)結(jié)構(gòu)的特性,達(dá)到如何應(yīng)用樹型結(jié)構(gòu)解決具體問(wèn)題的目的.三、實(shí)驗(yàn)文檔： 哈夫曼編碼/譯碼一、需求分析1、利用哈夫曼編碼進(jìn)行信息通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（既可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。本次設(shè)計(jì)就是為這樣的信息收發(fā)站寫的一個(gè)哈夫曼的編/譯碼器。本實(shí)驗(yàn)要求：2、本演示程序中，用戶可以輸入

5、鍵盤中的任意字符，長(zhǎng)度為任意長(zhǎng)，字符輸入順序不限，且允許出現(xiàn)重碼3、演示程序以用戶與計(jì)算機(jī)的對(duì)話方式執(zhí)行，即在計(jì)算機(jī)終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運(yùn)算命令，相應(yīng)的輸入數(shù)據(jù)（可慮去輸入中的非法字符）和運(yùn)算結(jié)果顯示在其后。4、本演示程序中，當(dāng)用戶選擇的功能錯(cuò)誤時(shí)，系統(tǒng)會(huì)輸出相應(yīng)的提示。5、在本系統(tǒng)中，用戶可以對(duì)任意長(zhǎng)的字符串可進(jìn)行編碼/譯碼。6、程序執(zhí)行的命令包括：1) 初始化(I)2) 編碼(E)3) 譯碼(D) 4) 印代碼文件(P)5) 印哈夫曼樹(T)6) 退出(Q)、測(cè)試數(shù)據(jù)：（）利用教科書例6-2中的數(shù)據(jù)調(diào)試程序。（）用下表給出的字符集和頻度的計(jì)數(shù)據(jù)建立

6、哈曼樹,并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”.。字符 A B C D E F G H I J K L M頻數(shù)186 64 13 22 32 103 21 15 47 57 1 5 32 20字符N O P Q R S T U V W X Y Z頻數(shù)57 63 15 1 48 51 80 23 8 18 1 16 1 二、概要設(shè)計(jì)為實(shí)現(xiàn)上述程序功能，應(yīng)以指針存儲(chǔ)結(jié)點(diǎn)。為此，需要定義一個(gè)抽象數(shù)據(jù)類型。1. 抽象數(shù)據(jù)類型定義為：ADT HuffmanTree數(shù)據(jù)對(duì)象：D=ai| aiCharSet,i=1,2,n, n0數(shù)據(jù)關(guān)系：R= ai-1, a

7、iD, ai-1ai ,i=2，3，n基本操作P：HuffmanTree(); 構(gòu)造函數(shù) HuffmanTree(); 析構(gòu)函數(shù)Initialization(int WeightNum);操作結(jié)果：構(gòu)造哈夫曼樹。Encoder()初始條件：哈夫曼樹已存在或者哈夫曼樹已存到文件中。操作結(jié)果：對(duì)字符串進(jìn)行編碼Decoder();初始條件：哈夫曼樹已存在且已編碼。操作結(jié)果：對(duì)二進(jìn)制串進(jìn)行譯碼Print()初始條件：編碼文件已存在。操作結(jié)果：把已保存好的編碼文件顯示在屏幕TreePrinting()初始條件：哈夫曼樹已存在。操作結(jié)果：將已在內(nèi)存中的哈夫曼樹以直觀的方式顯示在終端上2.本程序包含三個(gè)模塊

8、：1)主程序模塊：void main() 初始化；do 接受命令； 處理命令；while(“命令”=”退出”)2)、建樹模塊實(shí)現(xiàn)定義的抽象數(shù)據(jù)類型3)、編/譯碼模塊實(shí)現(xiàn)字符串的編/譯碼各模塊之間的調(diào)用關(guān)系如下： 主程序模塊 建樹模塊 編/譯碼模塊三、詳細(xì)設(shè)計(jì)程序代碼如下/ 程序名：HuffmanTree.h/ 程序功能：哈夫曼樹類的頭文件(并用其來(lái)實(shí)現(xiàn)編/譯碼)/ 作者：劉偉高/ 日期：2006.11.27/ 版本：1.0/對(duì)應(yīng)類實(shí)現(xiàn)文件: HuffmanTree.cpp/對(duì)應(yīng)主程序文件: main.cpp#include#include#includeusing namespace std;

9、struct HuffmanNode /定義哈夫曼樹各結(jié)點(diǎn)int weight; /存放結(jié)點(diǎn)的權(quán)值，假設(shè)只考慮處理權(quán)值為整數(shù)的情況int parent; /記錄結(jié)點(diǎn)父親位置，-1表示為根結(jié)點(diǎn)，否則表示為非根結(jié)點(diǎn)int lchild,rchild; /分別存放該結(jié)點(diǎn)的左、右孩子的所在單元的編號(hào);class HuffmanTree /建立哈夫曼樹類private:HuffmanNode *Node; /哈夫曼樹中結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)char *Info; /用來(lái)保存各字符信息int LeafNum; /樹中的葉子結(jié)點(diǎn)總數(shù)public:HuffmanTree(); /構(gòu)造函數(shù)HuffmanTree();

10、/析構(gòu)函數(shù)void Initialization(int WeightNum); /初始化函數(shù)：根據(jù)WeightNum個(gè)權(quán)值建立一棵哈夫曼樹void Encoder(); /編碼函數(shù)：利用構(gòu)造好的哈夫曼樹對(duì)字符進(jìn)行編碼void Decoder(); /譯碼函數(shù)：對(duì)二進(jìn)制串進(jìn)行譯碼void Print(); /印文件函數(shù)：把已保存好的編碼文件顯示在屏幕void TreePrinting(); /印哈夫曼樹函數(shù)：將已在內(nèi)存中的哈夫曼樹以直觀的方式顯示在終端上;/ 程序名：HuffmanTree.cpp/ 程序功能：實(shí)現(xiàn)哈夫曼樹類的源文件(并用其來(lái)實(shí)現(xiàn)編/譯碼)/ 作者：劉偉高/ 日期：2006.1

11、1.27/ 版本：1.0#includeHuffmanTree.h#includeusing namespace std;/ 構(gòu)造函數(shù)/ 函數(shù)功能：將結(jié)點(diǎn)指針初始化為NULL/ 函數(shù)參數(shù)：無(wú)/ 參數(shù)返回值：無(wú)HuffmanTree:HuffmanTree()Node=NULL; /將樹結(jié)點(diǎn)初始化為空 Info=NULL; /將字符數(shù)組初始化為空LeafNum=0; /將葉子數(shù)初始化為0/ 析構(gòu)函數(shù)/ 函數(shù)功能：將所有結(jié)點(diǎn)的空間釋放/ 函數(shù)參數(shù)：無(wú)/ 參數(shù)返回值：無(wú)HuffmanTree:HuffmanTree()delete Node; /釋放結(jié)點(diǎn)空間delete Info; /釋放字符存儲(chǔ)空

12、間/ 初始化函數(shù)/ 函數(shù)功能：從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值,/ 建立哈夫曼樹,并將它存放在文件hfmTree中./ 函數(shù)參數(shù)：int WeightNum表示代碼個(gè)數(shù)/ 參數(shù)返回值：無(wú) void HuffmanTree:Initialization(int WeightNum) /初始化int i,j,pos1,pos2,max1,max2; /Node=new HuffmanNode2*WeightNum-1; /WeightNum權(quán)值對(duì)應(yīng)的哈夫曼樹中的結(jié)點(diǎn)總數(shù)為2*WeightNum-1個(gè)Info=new char2*WeightNum-1;for(i=0;iWeightN

13、um;i+)cout請(qǐng)輸入第i+1個(gè)字符值;getchar(); /丟棄字符t與nInfoi=getchar(); /輸入一個(gè)字符,主要是考慮輸入空格而采用這種形式的getchar();coutNodei.weight; /輸入權(quán)值Nodei.parent=-1; /為根結(jié)點(diǎn)Nodei.lchild=-1; /無(wú)左孩子Nodei.rchild=-1; /無(wú)右孩子for(i=WeightNum;i2*WeightNum-1;i+) /表示需做WeightNum-1次合并pos1=-1;pos2=-1; /分別用來(lái)存放當(dāng)前最小值和次小值的所在單元編號(hào) max1=32767; /32767為整型數(shù)的

14、最大值 max2=32767; /分別用來(lái)存放當(dāng)前找到的最小值和次小值 for(j=0;ji;j+) /在跟節(jié)點(diǎn)中選出權(quán)值最小的兩個(gè)if(Nodej.parent=-1) /是否為根結(jié)點(diǎn)if(Nodej.weightmax1) /是否比最小值要小 max2=max1; /原最小值變?yōu)榇涡≈祄ax1=Nodej.weight; /存放最小值pos2=pos1; /修改次小值所在單元編號(hào)pos1=j; /修改最小值所在單元編號(hào)elseif(Nodej.weightmax2) /比原最小值大但比原次小值要小max2=Nodej.weight; /存放次小值pos2=j; /修改次小值所在的單元編號(hào)

15、/forNodepos1.parent=i; /修改父親位置Nodepos2.parent=i;Nodei.lchild=pos1; /修改兒子位置Nodei.rchild=pos2;Nodei.parent=-1; /表示新結(jié)點(diǎn)應(yīng)該是根結(jié)點(diǎn)Nodei.weight=Nodepos1.weight+Nodepos2.weight; /forLeafNum=WeightNum;char ch;coutch;if(ch=y|ch=Y)ofstream fop; /以二進(jìn)制方式打開hfmTree.dat文件，并當(dāng)重新運(yùn)行時(shí)覆蓋原文件fop.open(hfmTree.dat,ios:out|ios:b

16、inary|ios:trunc);if(fop.fail() /文件打開失敗cout文件打開失敗！n;fop.write(char*)&WeightNum,sizeof(WeightNum); /寫入WeightNumfor(i=0;iWeightNum;i+) /把各字符信息寫入文件fop.write(char*)&Infoi,sizeof(Infoi);flush(cout);for(i=0;i2*WeightNum-1;i+) /把個(gè)節(jié)點(diǎn)內(nèi)容寫入文件fop.write(char*)&Nodei,sizeof(Nodei);flush(cout);fop.close(); /關(guān)閉文件cou

17、t哈夫曼樹已構(gòu)造完成。n;/Initialization/ 編碼函數(shù)/ 函數(shù)功能：利用已建立好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），/ 對(duì)文件ToBeTran中的正文進(jìn)行編碼,然后將結(jié)果代碼存(傳輸)到文件CodeFile中./ 函數(shù)參數(shù)：無(wú)/ 參數(shù)返回值：無(wú)void HuffmanTree:Encoder()if(Node=NULL) /哈夫曼樹不在內(nèi)存，從文件hfmTree中讀入ifstream fip; /以二進(jìn)制方式打開hfmTree.dat文件fip.open(hfmTree.dat,ios:binary|ios:in);if(fip.fail() /文件打開失敗c

18、out文件打開失敗！n;return; /結(jié)束本函數(shù)fip.read(char*)&LeafNum,sizeof(LeafNum); /讀取葉子數(shù)Info=new charLeafNum; Node=new HuffmanNode2*LeafNum-1;for(int i=0;iLeafNum;i+) /讀取字符信息fip.read(char*)&Infoi,sizeof(Infoi);for(i=0;i2*LeafNum-1;i+) /讀取結(jié)點(diǎn)信息fip.read(char*)&Nodei,sizeof(Nodei);char *Tree; /用于存儲(chǔ)需編碼內(nèi)容int i=0,num;cha

19、r Choose; /讓用戶選擇讀取文件或重新輸入需編碼內(nèi)容coutChoose;if(Choose=1) /讀取文件ToBeTran.txtifstream fip1(ToBeTran.txt);if(fip1.fail() /文件不存在cout文件打開失敗!n;return; /結(jié)束本函數(shù)char ch;int k=0;while(fip1.get(ch) k+; /計(jì)算CodeFile中代碼長(zhǎng)度 fip1.close(); Tree=new chark+1;ifstream fip2(ToBeTran.txt);k=0; while(fip2.get(ch)Treek=ch; /讀取文件

20、內(nèi)容，并存到Tree中k+;fip2.close();Treek=0; /結(jié)束標(biāo)志cout需編碼內(nèi)容為:;coutTreeendl;/if(Choose=1)else /Choose!=1,重新輸入string tree; /用于輸入需編碼內(nèi)容，由于string類對(duì)象可以輸入任意長(zhǎng)度， /所以先利用這個(gè)對(duì)象輸入，再轉(zhuǎn)存在Tree中 cin.ignore();cout請(qǐng)輸入需要編碼的內(nèi)容(可輸入任意長(zhǎng)，結(jié)束時(shí)請(qǐng)按2下回車):n;getline(cin,tree,n); /輸入任意長(zhǎng)字符串， /getline以回車(n)作為結(jié)束符，第一次按回車表示字符串結(jié)束，第二次按回車才開始輸出。while(t

21、reei!=0)i+;num=i; /計(jì)算tree長(zhǎng)度i=0;Tree=new charnum+1;while(treei!=0) /將tree中的字符轉(zhuǎn)存到Tree中Treei=treei;i+; Treei=0; /結(jié)束標(biāo)志符ofstream fop(CodeFile.dat,ios:trunc); /存儲(chǔ)編碼后的代碼,并覆蓋原文件i=0;int k=0;char *code;code=new charLeafNum; /為所產(chǎn)生編碼分配容量為L(zhǎng)eafNum的存儲(chǔ)空間 /因?yàn)椴坏乳L(zhǎng)編碼中最長(zhǎng)的編碼一定不會(huì)超過(guò)要求編碼的字符個(gè)數(shù)while(Treek!=0) /對(duì)每一個(gè)字符編碼int j,s

22、tart=0;for(i=0;iLeafNum;i+)if(Infoi=Treek) /求出該文字所在單元的編號(hào)break; j=i;while(Nodej.parent!=-1) /結(jié)點(diǎn)j非樹根j=Nodej.parent; /非結(jié)點(diǎn)j的雙親結(jié)點(diǎn)if(Nodej.lchild=i) /是左子樹，則生成代碼0codestart+=0;else /是右子樹，則生成代碼1codestart+=1;i=j;codestart=0; /置串結(jié)束符 for(i=0;istart/2;i+) /對(duì)二進(jìn)制序列進(jìn)行逆置j=codei;codei=codestart-i-1;codestart-i-1=j; i

23、=0;while(codei!=0) /存儲(chǔ)代碼fopcodei;i+;k+;fop.close();cout已編碼！且存到文件CodeFile.dat中！nn; /Encode/ 譯碼函數(shù)/ 函數(shù)功能：利用已建好的哈夫曼樹,對(duì)傳輸?shù)竭_(dá)的CodeFile中的數(shù)據(jù)代碼進(jìn)行譯碼,/ 將譯碼結(jié)果存入文件TextFile中./ 函數(shù)參數(shù)：無(wú)/ 參數(shù)返回值：無(wú)void HuffmanTree:Decoder()int i=0,k=0;int j=LeafNum*2-1-1; /表示從根結(jié)點(diǎn)開始往下搜索char* BitStr;ifstream fip1(CodeFile.dat); /利用已建好的哈夫曼

24、樹將文件CodeFile中的代碼進(jìn)行譯碼if(fip1.fail() /文件打開失敗，還未編碼cout 請(qǐng)先編碼！n;return;cout經(jīng)譯碼,原內(nèi)容為:;char ch;while(fip1.get(ch) k+; /計(jì)算CodeFile中代碼長(zhǎng)度f(wàn)ip1.close(); BitStr=new chark+1;ifstream fip2(CodeFile.dat);k=0;while(fip2.get(ch)BitStrk=ch; /讀取文件內(nèi)容k+;fip2.close(); BitStrk=0; /結(jié)束標(biāo)志符if(Node=NULL) /還未建哈夫曼樹 cout請(qǐng)先編碼!n; re

25、turn;ofstream fop(TextFile.dat); /將字符形式的編碼文件寫入文件CodePrin中while(BitStri!=0)if(BitStri=0)j=Nodej.lchild; /往左走elsej=Nodej.rchild; /往右走if(Nodej.rchild=-1) /到達(dá)葉子結(jié)點(diǎn)coutInfoj; /輸出葉子結(jié)點(diǎn)對(duì)應(yīng)的字符j=LeafNum*2-1-1; /表示重新從根結(jié)點(diǎn)開始往下搜索fopInfoj; /存入文件/if、i+;/whilefop.close();coutn譯碼成功且已存到文件TextFile.dat中！nn;/Decoder/ 印文件代碼

26、函數(shù)/ 函數(shù)功能：將文件CodeFile以緊湊格式顯示在終端上，/ 每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件CodePrin中。/ 函數(shù)參數(shù)：無(wú)/ 參數(shù)返回值：無(wú)void HuffmanTree:Print()char ch;int i=1;ifstream fip(CodeFile.dat); /讀取文件ofstream fop(CodePrin.dat); /存儲(chǔ)文件if(fip.fail()cout沒(méi)有文件，請(qǐng)先編碼！n;return;while(fip.get(ch)coutch; /讀取文件內(nèi)容fopch; /存到文件中if(i=50) /每行輸出50個(gè)字符coutendl

27、;i=0;i+;coutendl;fip.close(); /關(guān)閉CodeFile.dat文件fop.close(); /關(guān)閉CodePrin.dat文件/ 印哈夫曼樹函數(shù)/ 函數(shù)功能：將已在內(nèi)存中的哈夫曼樹以直觀的方式(樹或凹入表的形式)顯示在終端上，/ 同時(shí)將此字符形式的哈夫曼樹寫入文件TreePrint中。/ 函數(shù)參數(shù)：無(wú)/ 參數(shù)返回值：無(wú)void HuffmanTree:TreePrinting()if(Node=NULL) /未建立哈夫曼樹cout請(qǐng)先建立哈夫曼樹！n;return;ofstream fop(TreePrint.dat);cout結(jié)點(diǎn)位置(權(quán)值) 編碼 左孩子 編碼右

28、孩子(表示葉子)n;fop結(jié)點(diǎn)位置(權(quán)值) 編碼 左孩子 編碼LeafNum-1;i-) /輸出哈夫曼樹couti(Nodei.weight)-1-Nodei.lchild(NodeNodei.lchild.weight)-0-Nodei.rchild(NodeNodei.rchild.weight)endl;fopi(Nodei.weight)-1-Nodei.lchild(NodeNodei.lchild.weight)-0-Nodei.rchild(NodeNodei.rchild.weight)=0;i-)couti:Nodei.weight(Infoi)-n;fopi:Nodei.w

29、eight(Infoi)-n;/ 程序名：main.cpp/ 程序功能：主函數(shù)源文件/ 作者：劉偉高/ 日期：2006.11.27/ 版本：1.0#includeHuffmanTree.h#include#include/ 主函數(shù)/參數(shù)返回值：無(wú)int main()cout 歡迎使用哈夫曼碼的編/譯碼系統(tǒng)!n;cout 劉偉高n;cout 版權(quán)所有,盜版必究n; cout在此系統(tǒng)中可以進(jìn)行以下操作:n;cout(1) 初始化(I);n;cout(2) 編碼(E);n;cout(3) 譯碼(D);n;cout(4) 印代碼文件(P);n;cout(5) 印哈夫曼樹(T)n;cout(6) 退出(

30、Q)nn;HuffmanTree huftree; /定義哈夫曼樹對(duì)象int weight;char Choose;while(1)coutChoose;switch(Choose)case I:case i:coutweight;huftree.Initialization(weight); /初始化哈夫曼樹break;case E:case e:huftree.Encoder();break;case D:case d:huftree.Decoder();break;case P:case p:huftree.Print();break;case T:case t:huftree.TreePrinting();break;case Q:case q:coutn *感謝使用本系統(tǒng)!*nn; sys