哈夫曼樹編碼實驗報告

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

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

3、用已構(gòu)造的哈夫曼編碼對“明文”文件中的正文進行編碼，然后將結(jié)果存入“密文”文件中。2.3 譯碼：將“密文”文件中的0、1 代碼序列進行譯碼。2.4 打印“密文”文件：將文件以緊湊格式顯示在終端上，每行 30 個代碼；同時，將此字符形式的編碼文件保存。2.5 打印哈夫曼樹及哈夫曼編碼：將已在內(nèi)存中的哈夫曼樹以凹入表形式顯示在終端上，同時將每個字符的哈夫曼編碼顯示出來；并保存到文件。3測試數(shù)據(jù)。3.1. 令葉子結(jié)點個數(shù) n為 4， 權(quán)值集合為 1,3,5,7， 字符集合為 a,b,c,d ，且字符集與權(quán)值集合一一對應(yīng)。3.2. 請自行選定一段英文文本，統(tǒng)計給出的字符集，實際統(tǒng)計字符的頻度，建立哈夫

4、曼樹，構(gòu)造哈夫曼編碼，并實現(xiàn)其編碼和譯碼。二、概要設(shè)計1本程序所用的抽象數(shù)據(jù)類型的定義；class huffmantree /哈夫曼樹 private: huffmannode *node; /node存放哈夫曼樹 int leafnum; /哈夫曼樹的葉子個數(shù)，也是源碼個數(shù)2. 主程序模塊main() 2.2 建立哈夫曼樹函數(shù)/ 函數(shù)功能：建立哈夫曼樹void huffmantree:createhuffmantree() 2.3 函數(shù)功能：為哈夫曼樹編碼void huffmantree:encoder() 2.4 函數(shù)功能：對哈夫曼樹進行譯碼void huffmantree:decoder

5、() 2.5 輸出碼文函數(shù)/ 函數(shù)功能：從文件中輸出哈夫曼樹的碼文. . void huffmantree:printcodefile() 2.6 函數(shù)功能：用凹入法輸出哈夫曼樹void huffmantree:printhuffmantree_aoru(int t,int layer) 3主模塊的流程及各子模塊的主要功能；基本功能分析4模塊之間的層次關(guān)系。 初始化：從鍵盤接收字符集大小n，以及 n 個字符和 n 個權(quán)值。 建立哈夫曼樹：構(gòu)造哈夫曼樹，即將hnode數(shù)組中的各個位置的各個域都添上相關(guān)的值，并將這個結(jié)構(gòu)體數(shù)組存于文件htree.txt中。 構(gòu)造哈夫曼編碼：為從文件htree.tx

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

7、相關(guān)的結(jié)點信息，以凹入表方式將各個結(jié)點以及葉子結(jié)點的權(quán)值和左分支上的0 和右分支上的三、詳細設(shè)計1采用 c 語言定義相關(guān)的數(shù)據(jù)類型；結(jié)點的類型定義描述如下：struct huffmannode /哈夫曼樹的一個結(jié)點 哈夫曼編碼/譯碼系統(tǒng)建立哈夫曼樹編碼顯示碼文譯碼顯示哈夫曼樹顯示哈夫曼樹. . int weight; int parent; int lchild,rchild; char sourcecode; std:string code; ; class huffmantree /哈夫曼樹 private: huffmannode *node; /node存放哈夫曼樹 int leafn

8、um; 2. 偽碼算法public: huffmantree(); huffmantree(); void 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ù)功能：初始化哈夫曼樹huffm

9、antree:huffmantree() node=null; leafnum=0; / 函數(shù)功能：將哈夫曼的數(shù)組的空間釋放/ 參數(shù)返回值：無huffmantree:huffmantree() delete node; / 建立哈夫曼樹函數(shù)/ 函數(shù)功能：建立哈夫曼樹void huffmantree:createhuffmantree() . . char choose; coutchoose; if(choose=2) createhuffmantreefromkeyboard(); /choose=2 else /從哈夫曼樹文件 hfmtree.dat 中讀入信息并建立哈夫曼樹 create

10、huffmantreefromfile(); / 函數(shù)功能：從鍵盤建立哈夫曼樹void huffmantree:createhuffmantreefromkeyboard() int num; coutnum; if (num=1) cout無法建立少于 2 個葉子結(jié)點的哈夫曼樹。 nn; return; leafnum=num; node=new huffmannode2*num-1; for(int i=0;inum;i+) /讀入哈夫曼樹的葉子結(jié)點信息 cout請輸入第 i+1 個字符值 ; getchar(); nodei.sourcecode=getchar(); /源文的字符存入字

11、符數(shù)組info getchar(); coutnodei.weight; /源文的字符權(quán)重存入node.weight nodei.parent=-1; nodei.lchild=-1; nodei.rchild=-1; nodei.code=0; for(int j=num;j2*num-1;j+) /循環(huán)建立哈夫曼樹內(nèi)部結(jié)點 int pos1,pos2; int max1,max2; pos2=pos1=j; max2=max1=numeric_limits:max( ); /在所有子樹的根結(jié)點中，選權(quán)重最小的兩個根結(jié)點，pos1 最后應(yīng)指向權(quán)重最小的根結(jié)點的下標(biāo)for(int k=j-1;

12、k=0;k-) if (nodek.parent=-1)/如果是某棵子樹的根結(jié)點. . if (nodek.weightmax1) /發(fā)現(xiàn)比當(dāng)前最大值還大的權(quán)重 max2=max1; max1=nodek.weight; pos2=pos1; pos1=k; else if(nodek.weightmax2) /發(fā)現(xiàn)比當(dāng)前次大值還大的次大權(quán)重 max2=nodek.weight; pos2=k; /if (nodej.parent=-1) /for / 在下標(biāo) i 處新構(gòu)造一個哈夫曼樹的內(nèi)部結(jié)點，其左、右孩子就是以上pos1、pos2 所指向的結(jié)點 nodepos1.parent=j; nod

13、epos2.parent=j; nodej.lchild=pos1; nodej.rchild=pos2; nodej.parent=-1; nodej.weight=nodepos1.weight+nodepos2.weight; /for /產(chǎn)生所有葉子結(jié)點中字符的編碼 for (int m=0;mnum;m+) /產(chǎn)生 nodei.sourcecode的編碼，存入 nodei.code中 int j=m; int j1; while(nodej.parent!=-1) / 從葉結(jié)點開始往根結(jié)點走，每往上走一層，就產(chǎn)生一位編碼存入code j1=nodej.parent; if(nodej

14、1.lchild=j) nodem.code.insert(0,0); else nodem.code.insert(0,1); j=j1; cout 哈夫曼樹已成功構(gòu)造完成。n; char ch; coutch; . . if (ch!=y&ch!=y) return; ofstream fop; fop.open(hfmtree.dat,ios:out|ios:binary|ios:trunc); /打開文件 if(fop.fail() coutn哈夫曼樹文件打開失敗， 無法將哈夫曼樹寫入hfmtree.dat 文件。n; return; fop.write(char*)&

15、num,sizeof(num); /先寫入哈夫曼樹的葉子結(jié)點個數(shù) for(int n=0;n2*num-1;n+) /最后寫入哈夫曼樹的各個結(jié)點（存儲在node 中） fop.write(char*)&noden,sizeof(noden); flush(cout); fop.close(); /關(guān)閉文件 coutn哈夫曼樹已成功寫入hfmtree.dat 文件。 n; / 從文件建立哈夫曼樹函數(shù)/ 函數(shù)功能：從文件建立哈夫曼樹void huffmantree:createhuffmantreefromfile() ifstream fip; fip.open(hfmtree.dat,

16、ios:binary|ios:in); if(fip.fail() cout哈夫曼樹文件 hfmtree.dat打開失敗，無法建立哈夫曼樹。n; return; fip.read(char*)&leafnum,sizeof(leafnum); if (leafnum=1) cout哈夫曼樹文件中的數(shù)據(jù)有誤， 葉子結(jié)點個數(shù)少于2 個，無法建立哈夫曼樹。 n; fip.close(); return; node=new huffmannode2*leafnum-1; for(int i=0;i2*leafnum-1;i+) fip.read(char*)&nodei,sizeof(

17、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)存無哈夫曼樹。操作撤銷。nn; return; /if char *sourcetext; /讓用戶選擇源文是從鍵盤輸入， 還是從源文文件 tobetran.txt中讀入 char choose; co

18、utchoose; if(choose=1) ifstream fip1(tobetran.txt); if(fip1.fail() cout源文文件打開失敗 ! 無法繼續(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) sourcetextk+=ch; fip2.close(); sourcetextk=0; else string sourcebuf

19、f; cin.ignore(); cout請輸入需要編碼的源文 ( 按回車鍵結(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+; sourcetextk=0; cout 需編碼的源文為： ; coutsourcetextendl; ofstream fop(codefile.dat,ios:trunc); /打開碼文存放文件 int k=0;

20、while(sourcetextk!=0) /源文串中從第一個字符開始逐個編碼 int i; for(i=0;ileafnum;i+) /找到當(dāng)前要編碼的源文的字符在哈夫曼樹node 中的下標(biāo) if(nodei.sourcecode=sourcetextk) /將對應(yīng)編碼寫入碼文文件 fop=leafnum) cout源文中存在不可編碼的字符。無法繼續(xù)執(zhí)行。nendl; fop.close(); return; k+; fop.close(); cout 已完成編碼，碼文已寫入文件codefile.dat中。nn; / 函數(shù)功能：對哈夫曼樹進行譯碼void huffmantree:decode

21、r() / 如果內(nèi)存沒有哈夫曼樹， 則從哈夫曼樹文件 hfmtree.dat中讀入信息并建立哈夫曼樹 if(node=null) . . createhuffmantreefromfile(); if (leafnum=1) cout內(nèi)存無哈夫曼樹。操作撤銷。nn; return; ifstream fip1(codefile.dat); if(fip1.fail() cout沒有碼文，無法譯碼。 n; return; char* codestr; int k=0; char ch; while(fip1.get(ch) k+; fip1.close(); codestr=new chark+

22、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é)點處，則譯出葉子結(jié)點對應(yīng)的源文字符 if(codestri=0) j=nodej.lchild; else j=nodej.rchild; if(nodej.rchild=-1) /因為哈夫曼樹

23、沒有度為1 的結(jié)點，所以此條件等同于 nodej 為葉結(jié)點 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沒有碼

24、文文件，無法顯示碼文文件內(nèi)容。n; return; while(fip.get(ch) 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)存無哈夫曼樹。操作撤銷。nn; return; ofst

25、ream fop(treeprint.dat,ios_base:trunc); fop.close(); printhuffmantree_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+) cou