哈夫曼樹編碼實(shí)驗(yàn)報(bào)告

1、共享知識(shí)分享快樂河里士省數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題 目：.哈夫曼編碼/譯碼學(xué) 院數(shù)學(xué)與信息科學(xué)學(xué)院學(xué)科門類理科專業(yè)數(shù)學(xué)類學(xué)號(hào)2013433033姓名田娟2014年12月30日目錄一、需求分析1 .程序的功能32 .輸入輸出的要求33 .測(cè)試數(shù)據(jù)3二、概要設(shè)計(jì)1 .本程序所用的抽象數(shù)據(jù)類型的定義32 .主程序模塊33 .主模塊的流程及各子模塊的主要功能44 .模塊之間的層次關(guān)系4三、詳細(xì)設(shè)計(jì)1 .采用c語(yǔ)言定義相關(guān)的數(shù)據(jù)類型42 . 偽碼算法5四、調(diào)試分析1.調(diào)試中遇到的問題及對(duì)問題的解決方法15五、使用說明及測(cè)試結(jié)果1 .建立哈夫曼樹，輸入葉子結(jié)點(diǎn)個(gè)數(shù)，權(quán)值，字符集152 .編碼153 .譯碼16

2、4 .顯示碼文165 .顯示哈夫曼樹16六、源程序一、需求分析1 .程序的功能；哈夫曼編碼是一種應(yīng)用廣泛而有效的數(shù)據(jù)壓縮技術(shù)。利用哈夫曼編碼進(jìn)行通 信可以大大提高信道利用率，加快信息傳輸速度，降低傳輸成本。數(shù)據(jù)壓縮的過 程稱為編碼，解壓縮的過程稱為譯碼。進(jìn)行信息傳遞時(shí)，發(fā)送端通過一個(gè)編碼系 統(tǒng)對(duì)待傳數(shù)據(jù)(明文)預(yù)先編碼，而接收端將傳來(lái)的數(shù)據(jù)(密文)進(jìn)行譯碼。2 .輸入輸出的要求；：2.1 .構(gòu)造哈夫曼樹及哈夫曼編碼：從終端讀入字符集大小n、n個(gè)字符以及n個(gè)對(duì)應(yīng)的權(quán)值，建立哈夫曼樹；利用已經(jīng)建好的哈夫曼樹求每個(gè)葉結(jié)點(diǎn)的哈夫 曼編碼，并保存。2.2 編碼：利用已構(gòu)造的哈夫曼編碼對(duì)“明文”文件中的正

3、文進(jìn)行編碼，然 后將結(jié)果存入“密文”文件中。23 譯碼：將“密文”文件中的 0、1代碼序列進(jìn)行譯碼。2.4 .打印“密文”文件：將文件以緊湊格式顯示在終端上，每行30個(gè)代碼; 同時(shí)，將此字符形式的編碼文件保存。25打印哈夫曼樹及哈夫曼編碼：將已在內(nèi)存中的哈夫曼樹以凹入表形式 顯示在終端上，同時(shí)將每個(gè)字符的哈夫曼編碼顯示出來(lái)；并保存到文件。3 .測(cè)試數(shù)據(jù)。3.1 令葉子結(jié)點(diǎn)個(gè)數(shù)N為4,權(quán)值集合為1,3,5,7,字符集合為A,B,C,D, 且字符集與權(quán)值集合一一對(duì)應(yīng)。3.2 請(qǐng)自行選定一段英文文本，統(tǒng)計(jì)給出的字符集，實(shí)際統(tǒng)計(jì)字符的頻度， 建立哈夫曼樹，構(gòu)造哈夫曼編碼，并實(shí)現(xiàn)其編碼和譯碼。二、概要設(shè)

4、計(jì)1 .本程序所用的抽象數(shù)據(jù)類型的定義；class HuffmanTree/哈夫曼樹private:HuffmanNode *Node; /Node口 存放哈夫曼樹int LeafNum;/哈夫曼樹的葉子個(gè)數(shù)，也是源碼個(gè)數(shù)2 .主程序模塊main()2.2 建立哈夫曼樹函數(shù)/函數(shù)功能：建立哈夫曼樹void HuffmanTree二CreateHuffmanTree()2.3 函數(shù)功能：為哈夫曼樹編碼void HuffmanTree二Encoder。2.4 函數(shù)功能：對(duì)哈夫曼樹進(jìn)行譯碼void HuffmanTree二Decoder。2.5 輸出碼文函數(shù)/函數(shù)功能：從文件中輸出哈夫曼樹的碼文vo

5、id HuffmanTree二PrintCodeFile（）2.6 函數(shù)功能：用凹入法輸出哈夫曼樹void HuffmanTree二PrintHuffmanTree_aoru(int T,int layer)3 .主模塊的流程及各子模塊的主要功能;哈夫曼編碼/譯碼 系統(tǒng)建立哈夫曼樹顯示碼文顯示哈夫曼樹顯示哈夫曼樹基本功能分析4 .模塊之間的層次關(guān)系。 初始化：從鍵盤接收字符集大小n,以及n個(gè)字符和n個(gè)權(quán)值。 建立哈夫曼樹：構(gòu)造哈夫曼樹，即將 HNode數(shù)組中的各個(gè)位置的各個(gè)域 都添上相關(guān)的值，并將這個(gè)結(jié)構(gòu)體數(shù)組存于文件HTree.txt中。構(gòu)造哈夫曼編碼：為從文件HTree.txt中讀入相關(guān)的

6、字符信息進(jìn)行哈夫曼 編碼，然后將結(jié)果存入HNode.txt中，同時(shí)將字符與0、1代碼用的 對(duì)應(yīng)關(guān) 系打印到屏幕上。 編碼：利用已構(gòu)造的哈夫曼編碼（HNode.txt）對(duì)文件SourceFile.txt （明 文）中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile.txt （密文）中。譯碼：將文件CodeFile.txt （密文）中的代碼按照中建立的編碼規(guī)則將 其翻譯成 字符集中字符所組成的字符串形式，進(jìn)行譯碼，結(jié)果存 入文件 TextFile.txt （明文）中。（如果正確，TextFile.txt 的內(nèi)容與 SourceFile.txt 的內(nèi)容 一致） 顯示哈夫曼樹：從HNode數(shù)組中讀入

7、相關(guān)的結(jié)點(diǎn)信息，以凹入表方式將 各個(gè)結(jié)點(diǎn)以及葉子結(jié)點(diǎn)的權(quán)值和左分支上的0和右分支上的三、詳細(xì)設(shè)計(jì)1 .采用c語(yǔ)言定義相關(guān)的數(shù)據(jù)類型； 結(jié)點(diǎn)的類型定義描述如下：struct HuffmanNode/哈夫曼樹的一個(gè)結(jié)點(diǎn)int weight;int parent;int lchild,rchild;char sourcecode;std二string code;class HuffmanTree/哈夫曼樹private:HuffmanNode *Node; /Node口 存放哈夫曼樹 int LeafNum;2 .偽碼算法public:HuffmanTree();HuffmanTree();void

8、 CreateHuffmanTree();void CreateHuffmanTreeFromKeyboard();void CreateHuffmanTreeFromFile();void Encoder。；void Decoder。；void PrintCodeFile();void PrintHuffmanTree();void PrintHuffmanTree_aoru(int T,int layer=1);一/構(gòu)造函數(shù)/函數(shù)功能：初始化哈夫曼樹HuffmanTree:HuffmanTree()Node=NULL;LeafNum=0;/函數(shù)功能：將哈夫曼的數(shù)組的空間釋放/參數(shù)返回值：無(wú)

9、HuffmanTree:HuffmanTree() delete口 Node;/建立哈夫曼樹函數(shù)/函數(shù)功能：建立哈夫曼樹void HuffmanTree二CreateHuffmanTree()char Choose;coutChoose;if(Choose=2) CreateHuffmanTreeFromKeyboard();choose=2else /從哈夫曼樹文件hfmTree.dat中讀入信息并建立哈夫曼樹CreateHuffmanTreeFromFile();/函數(shù)功能：從鍵盤建立哈夫曼樹void HuffmanTree二CreateHuffmanTreeFromKeyboard()

10、int Num;coutNum;if (Num=1) cout無(wú)法建立少于2個(gè)葉子結(jié)點(diǎn)的哈夫曼樹。nn; return;LeafNum=Num;Node=new HuffmanNode2*Num-1;for(int i=0;iNum;i+) /讀入哈夫曼樹的葉子結(jié)點(diǎn)信息cout請(qǐng)輸入第i+1個(gè)字符值;getchar();Nodei.sourcecode=getchar(); /源文的字符存入字符數(shù)組 Info口 getchar();coutNodei.weight; / 源文的字符權(quán)重存入 Node.weightNodei.parent=-1;Nodei.lchild=-1;Nodei.rch

11、ild=-1;Nodei.code=0;for(int j=Num;j2*Num-1;j+) /循環(huán)建立哈夫曼樹內(nèi)部結(jié)點(diǎn)int pos1,pos2;int max1,max2;pos2=pos1=j;max2=max1=numeric_limits二max();/在所有子樹的根結(jié)點(diǎn)中，選權(quán)重最小的兩個(gè)根結(jié)點(diǎn)，posl最后應(yīng)指向權(quán)重最小的根結(jié)點(diǎn)的下標(biāo)for(int k=j-1;k=0;k-) if (Nodek.parent=-1)/如果是某棵子樹的根結(jié)點(diǎn)if (Nodek.weightmax1) 發(fā)現(xiàn)比當(dāng)前最大值還大的權(quán)重max2=max1;max1=Nodek.weight;pos2=pos

12、1;pos1=k;elseif(Nodek.weightmax2) /發(fā)現(xiàn)比當(dāng)前次大值還大的次大權(quán)重max2=Nodek.weight;pos2=k;/if (Nodej.parent=-1) /for/在下標(biāo)i處新構(gòu)造一個(gè)哈夫曼樹的內(nèi)部結(jié)點(diǎn)，其左、右孩子就是以上posh pos2所指向的結(jié)點(diǎn)Nodepos1.parent=j;Nodepos2.parent=j;Nodej.lchild=pos1;Nodej.rchild=pos2;Nodej.parent=-1;Nodej.weight=Nodepos1.weight+Nodepos2.weight; /for/產(chǎn)生所有葉子結(jié)點(diǎn)中字符的編碼

13、for (int m=0;mNum;m+) /產(chǎn)生 Nodei.sourcecode 的編碼，存入 Nodei.code 中int j=m;intj1;while(Nodej.parent!=-1) 從葉結(jié)點(diǎn)開始往根結(jié)點(diǎn)走，每往上走一層，就產(chǎn)生一位編碼存入code口j1=Nodej.parent;if(Nodej1.lchild=j)Nodem.code.insert(0,0);elseNodem.code.insert(0,1);j=j1;cout哈夫曼樹已成功構(gòu)造完成。n;char ch;coutch;if (ch!=y&ch!=Y) return;ofstream fop;fop.ope

14、n(hfmTree.dat,ios二out|ios二binary|ios:trunc);附丁 開文件if(fop.fail() coutn哈夫曼樹文件打開失敗，無(wú)法將哈夫曼樹寫入hfmTree.dat文件。n; return;fop.write(char*)&Num,sizeof(Num); /先寫入哈夫曼樹的葉子結(jié)點(diǎn)個(gè)數(shù)for(int n=0;n2*Num-1;n+) /最后寫入哈夫曼樹的各個(gè)結(jié)點(diǎn)(存儲(chǔ)在Node口1fop.write(char*)&Noden,sizeof(Noden);flush(cout);fop.close(); /關(guān)閉文件coutn哈夫曼樹已成功寫入hfmTree.

15、dat文件。n;/從文件建立哈夫曼樹函數(shù)/函數(shù)功能：從文件建立哈夫曼樹void HuffmanTree二CreateHuffmanTreeFromFile()ifstream fip;fip.open(hfmTree.dat,ios:binary|ios:in);if(fip.fail() cout哈夫曼樹文件hfmTree.dat打開失敗，無(wú)法建立哈夫曼樹。n;return;fip.read(char*)&LeafNum,sizeof(LeafNum);if (LeafNum=1) cout哈夫曼樹文件中的數(shù)據(jù)有誤，葉子結(jié)點(diǎn)個(gè)數(shù)少于2個(gè)，無(wú)法建立哈夫曼樹。n;fip.close();retu

16、rn;Node=new HuffmanNode2*LeafNum-1;for(int i=0;i2*LeafNum-1;i+)fip.read(char*)&Nodei,sizeof(Nodei);fip.close();cout哈夫曼樹已從文件成功構(gòu)造完成。n;/編碼函數(shù)/函數(shù)功能：為哈夫曼樹編碼void HuffmanTree二Encoder。if(Node=NULL) 內(nèi)存沒有哈夫曼樹，則從哈夫曼樹文件hfmTree.dat中讀入信息并建立哈夫曼樹CreateHuffmanTreeFromFile();if (LeafNum=1) cout內(nèi)存無(wú)哈夫曼樹。操作撤銷。nn;return;

17、/ifchar *SourceText;/讓用戶選擇源文是從鍵盤輸入，還是從源文文件ToBeTran.txt中讀入char Choose;coutChoose;if(Choose=1) ifstream fip1(ToBeTran.txt);if(fip1.fail() cout源文文件打開失??！無(wú)法繼續(xù)執(zhí)行。n”;return;char ch;int k=0;while(fip1.get(ch) k+;fip1.close();SourceText=new chark+1;ifstream fip2(ToBeTran.txt);k=0;while(fip2.get(ch) SourceTex

18、tk+=ch;fip2.close();SourceText止0;else string SourceBuff;cin.ignore();cout”請(qǐng)輸入需要編碼的源文(接回車鍵結(jié)束):n;getline(cin,SourceBuff,n);int k=0;while(SourceBuffk!=0) k+; SourceText=new chark+1; k=0;while(SourceBuffk!=0) SourceTextk=SourceBuffk; k+;SourceText止0;cout需編碼的源文為：;coutSourceTextendl;ofstream fop(CodeFile.

19、dat,ios:trunc);打開碼文存放文件int k=0;while(SourceTextk!=0)/源文用中從第一個(gè)字符開始逐個(gè)編碼 int i; for(i=0;iLeafNum;i+)/找到當(dāng)前要編碼的源文的字符在哈夫曼樹Node口中的下標(biāo) if(Nodei.sourcecode=SourceTextk) /將對(duì)應(yīng)編碼寫入碼文文件fop=LeafNum) cout源文中存在不可編碼的字符。無(wú)法繼續(xù)執(zhí)行。nendl; fop.close(); return;k+;fop.close();cout已完成編碼，碼文已寫入文件CodeFile.dat中。nn;/函數(shù)功能：對(duì)哈夫曼樹進(jìn)行譯碼

20、void HuffmanTree二Decoder。/如果內(nèi)存沒有哈夫曼樹，則從哈夫曼樹文件hfmTree.dat中讀入信息并建立哈夫 曼樹if(Node=NULL)CreateHuffmanTreeFromFile();if (LeafNum=1) cout內(nèi)存無(wú)哈夫曼樹。操作撤銷。nn;return;ifstream fip1(CodeFile.dat);if(fip1.fail() cout沒有碼文，無(wú)法譯碼。n;return;char* CodeStr;int k=0;char ch;while(fip1.get(ch)k+;fip1.close();CodeStr=new chark+

21、1;ifstream fip2(CodeFile.dat);k=0;while(fip2.get(ch)CodeStrk+=ch;fip2.close();CodeStrk=0;cout經(jīng)譯碼得到的源文為：;ofstream fop(TextFile.dat);int j=LeafNum*2-1-1;int i=0;while(CodeStri!=0) /下行到哈夫曼樹的葉子結(jié)點(diǎn)處，則譯出葉子結(jié)點(diǎn)對(duì)應(yīng)的源文字符if(CodeStri=0)j=Nodej.lchild;elsej=Nodej.rchild;if(Nodej.rchild=-1) /因?yàn)楣蚵鼧錄]有度為1的結(jié)點(diǎn)，所以此條件等同于N

22、odej為葉結(jié)點(diǎn)coutNodej.sourcecode;fopNodej.sourcecode;j=LeafNum*2-1-1;i+；fop.close();coutn譯碼成功且已存到文件TextFile.dat中。nn;/輸出碼文函數(shù)/函數(shù)功能：從文件中輸出哈夫曼樹的碼文void HuffmanTree二PrintCodeFile()char ch;int i=1;ifstream fip(CodeFile.dat);ofstream fop(CodePrin.dat);if(fip.fail()cout沒有碼文文件，無(wú)法顯示碼文文件內(nèi)容。n”;return;while(fip.get(c

23、h)coutch;fopch;if(i=50)coutendl;fopendl;i=0;i+;coutendl;fopendl;fip.close();fop.close();/輸出函數(shù)/函數(shù)功能：從內(nèi)存或文件中直接輸出哈夫曼樹void HuffmanTree二PrintHuffmanTree()if(Node=NULL)CreateHuffmanTreeFromFile();if (LeafNum=1) cout內(nèi)存無(wú)哈夫曼樹。操作撤銷。nn;return;ofstream fop(TreePrint.dat,ios_base:trunc);fop.close();PrintHuffmanT

24、ree_aoru(2*LeafNum-1-1);return;/凹入法輸出函數(shù)/函數(shù)功能：用凹入法輸出哈夫曼樹void HuffmanTree二PrintHuffmanTree_aoru(int T,int layer)if (T!=-1)PrintHuffmanTree_aoru(NodeT.lchild,layer+1);ofstream fop(TreePrint.dat,ios_base二app);coutendl;fopendl;for (int i=0;ilayer*5;i+) cout”;fop;if (NodeT.lchild=-1)coutNodeT.sourcecodeNodeT.weight(NodeT.code)endl;fopNodeT.sourcecodeNodeT.weight(NodeT.code)endl;else coutNodeT.weightendl;fopNodeT.weightendl;fop.close();PrintHuffmanTree_aoru(NodeT.rchild,layer+1);.int main()HuffmanTree huftree; char Choose;while(1)coutn*哈夫曼編碼/ 譯碼*肝；cout*1.建立哈夫曼樹*n;cout*2.編碼*n;co