huffman(哈夫曼)樹編碼譯碼-課程設(shè)計報告

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計學(xué) 院： 信息科學(xué)與工程學(xué)院專 業(yè)： 計算機科學(xué)與技術(shù) 班 級： 計卓1601學(xué) 號： 學(xué)生姓名： 指導(dǎo)教師： 年 月 日題目名稱一、實驗內(nèi)容哈夫曼編碼譯碼系統(tǒng)【問題描述】用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼碼的編/譯碼系統(tǒng)。【基本要求】1）初始化。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹。2）編碼。利用已建好的哈夫曼樹

2、對輸入英文進行編碼，編碼結(jié)果存儲在數(shù)組中。3）譯碼。利用已建好的哈夫曼樹將數(shù)組中的代碼進行譯碼，結(jié)果存入一個字符數(shù)組。4）輸出編碼。將編碼結(jié)果顯示在終端上，每行50個代碼。5）輸出哈夫曼樹。將哈夫曼樹以直觀的方式（樹或凹入表形式）顯示出來?！緦崿F(xiàn)提示】用戶界面可以設(shè)計為“菜單”方式，再加上一個“退出”功能。請用戶鍵入一個選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“退出”為止。 參考教材P240-246 【選做內(nèi)容】將哈夫曼樹保存到文件中，編碼和譯碼的結(jié)果也分別存放在兩個文本文件中。二、數(shù)據(jù)結(jié)構(gòu)設(shè)計儲存結(jié)構(gòu)struct HNodeType /字符結(jié)構(gòu)體類型int weight;

3、/權(quán)int parent;/雙親位置int lchild;/左孩子int rchild;/右孩子char inf;/字符;struct HcodeType int bitMaxBit;/存儲編碼int start;/起始位置;三、算法設(shè)計1、在構(gòu)造哈夫曼樹時，設(shè)計一個結(jié)構(gòu)體數(shù)組HuffNode保存哈夫曼樹中各結(jié)點的信息，根據(jù)二叉樹的性質(zhì)可知，具有n個葉子結(jié)點的哈夫曼樹共有2n-1個結(jié)點，所以數(shù)組HuffNode的大小設(shè)置為2n-1。求哈夫曼編碼時使用一維結(jié)構(gòu)數(shù)組HuffCode作為哈夫曼編碼信息的存儲。求哈夫曼編碼實際上就是在已建立的哈夫曼樹中，從葉子結(jié)點開始，沿結(jié)點的父節(jié)點回退到根結(jié)點，每回

4、退一步，就走過了哈夫曼的一個分支，從而得到一位哈夫曼編碼值。由于一個字符的哈夫曼編碼就是從根結(jié)點到相應(yīng)葉子結(jié)點所經(jīng)過的路徑上各分支所組成的0、1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼為所求的高位2、初始化為從鍵盤接受字符集大小n，以及n個字符和n個權(quán)值。3、建立哈夫曼編碼為使用2中得到的數(shù)據(jù)按照教材中的構(gòu)造哈弗曼的算法構(gòu)造哈弗曼樹，即將HuffNode數(shù)組中的各個位置的各個域都填上相關(guān)的值，并將這個結(jié)構(gòu)體數(shù)組存于文件nodedata.dat中。void Creat_Haffmantree(int &n) /建樹并輸出樹n+;HNodeType *HaffNode=new

5、 HNodeType2*n-1;int i,j;int m1,m2,x1,x2;for(i=0; i2*n-1; i+) /賦初值HaffNodei.weight=0;HaffNodei.parent=-1;HaffNodei.lchild=-1;HaffNodei.rchild=-1;HaffNodei.inf=0; for(i=0; in-1; i+) /輸入字符及權(quán)值cout請輸入字符:HaffNodei.inf;cout請輸入該字符的權(quán)值:HaffNodei.weight;HaffNoden-1.inf= ;/最后一個為空格HaffNoden-1.weight=120;/空格權(quán)值for

6、(i=0; in-1; i+) /構(gòu)造哈夫曼樹m1=m2=Maxvalue;x1=x2=0;for(j=0; jn+i; j+) /找出最小和次小if(HaffNodej.parent=-1&HaffNodej.weightm1) m2=m1;x2=x1;m1=HaffNodej.weight;x1=j; else if(HaffNodej.parent=-1&HaffNodej.weightm2) m2=HaffNodej.weight;x2=j;/合并Huffman樹HaffNodex1.parent=n+i;HaffNodex2.parent=n+i;HaffNoden+i.weight

7、=HaffNodex1.weight+HaffNodex2.weight;HaffNoden+i.lchild=x1;HaffNoden+i.rchild=x2;HaffNoden+i.inf= ;/輸出樹cout顯示存儲的哈弗曼樹信息:endl;cout 權(quán)值 左孩子 右孩子 父節(jié)點endl;for(i=0; i2*n-1; i+) coutHaffNodei.inf ;coutsetiosflags(ios:right)setw(4)HaffNodei.weight ;coutsetiosflags(ios:right)setw(4)HaffNodei.lchild ;coutsetios

8、flags(ios:right)setw(4)HaffNodei.rchild ;coutsetiosflags(ios:right)setw(4)HaffNodei.parentendl;/寫入文件fstream outfile1;outfile1.open(E:nodedata.dat,ios:out|ios:trunc|ios:binary);/建立進行寫入的文件并清空之前數(shù)據(jù) if(!outfile1) /沒有創(chuàng)建成功則顯示相應(yīng)信息coutnodedata.dat文件不能打開endl;abort();for(i=0; i2*n-1; i+) /將內(nèi)存中從HaffNodei地址開始的si

9、zeof(HaffNodei)的內(nèi)容寫入文件中outfile1.write(char*)&HaffNodei,sizeof(HaffNodei);outfile1.close ();/關(guān)閉文件delete HaffNode;4、 編碼系統(tǒng)為從文件nodedata.dat中讀入相關(guān)的字符信息進行哈弗曼編碼，然后將結(jié)果存入code.dat中，同時將字符與0和1代碼串的一一對應(yīng)關(guān)系顯示到屏幕上。void HaffCode(int &n) /哈夫曼編碼HNodeType *HaffNode=new HNodeTypeMaxnode;/存儲樹HcodeType *HaffCode=new HcodeTy

10、peMaxleaf;/存儲編碼HcodeType cd;int i,j,c,p;fstream in(E:nodedata.dat,ios:in|ios:binary);/打開文件in.read(char*)HaffNode,(2*n-1)*sizeof(HNodeType);/從文件中讀取樹in.close();/關(guān)閉文件fstream outfile;outfile.open(E:codedata.dat,ios:out|ios:binary);/建立進行寫入的文件for(i=0; in; i+) /進行編碼 并向數(shù)組中從右向左寫入編碼cd.start=n-1;c=i;p=HaffNode

11、c.parent;while(p!=-1) if(HaffNodep.lchild=c)cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=p;p=HaffNodec.parent;for(j=cd.start+1; jn; j+)/ 向結(jié)構(gòu)體數(shù)組存儲編碼HaffCodei.bitj=cd.bitj; HaffCodei.start=cd.start;for(i=0; in; i+) /向文件中存取數(shù)據(jù)outfileHaffNodei.inf;for(j=HaffCodei.start+1; jn; j+)outfileHaffCodei.bit

12、j;cout字符信息-編碼信息endl;for(i=0; in; i+) coutHaffNodei.inf-;for(j=HaffCodei.start+1; jn; j+)/輸出編碼coutHaffCodei.bitj;/編碼信息01串coutendl; outfile.close ();/關(guān)閉文件cout請輸入要編碼的字符串,基本元素為（;for(i=0; in; i+)coutHaffNodei.inf,;cout)endl;char inf100;/定義輸入字符存放數(shù)組getchar();gets(inf);/讀取屏幕字符int f=strlen(inf);fstream outfi

13、le1;outfile1.open(E:code.dat,ios:out|ios:binary);/建立進行寫入的文件if(!outfile1) coutcode.dat文件不能打開!endl;abort(); else coutendl; cout字符串編碼后為:n;int num=0;for(int x=0; xf; x+) /輸出文本編碼for(i=0; in; i+) if(infx=HaffNodei.inf) for(j=HaffCodei.start+1; jn; j+) outfile1.write(char*)&HaffCodei.bitj,sizeof(HaffCodei.

14、bitj);coutHaffCodei.bitj;num+;if(num%50=0) coutendl; coutendl;coutendl;cout編譯后的代碼串已經(jīng)存入code.dat文件中!endl;coutendl;outfile1.close();delete HaffNode;delete HaffCode;5、 譯碼系統(tǒng)為接收需要譯碼的0、1代碼串，按照3中建立的編碼規(guī)則將其翻譯成字符集中字符所組成的字符串形式，存入文件textfile.dat，同時將翻譯的結(jié)果在屏幕上打印輸出。接受0、1代碼串有兩種形式，一種是直接輸入，一種是從文件中讀取。void decode( int &n

15、) int i;HNodeType *HaffNode=new HNodeType2*n-1;fstream infile1;infile1.open(E:nodedata.dat,ios:in|ios:binary);/打開文件if(!infile1) coutnodedata.dat文件不能打開endl;abort();for(i=0; i2*n-1; i+)/從文件里讀出Huffman樹infile1.read(char*)&HaffNodei,sizeof(HNodeType);infile1.close();/關(guān)閉int tempcode100;/定義一個數(shù)組存放01串int num

16、=0;for(i=0; i100; i+)/數(shù)組初始化tempcodei=-1;HcodeType *Code=new HcodeTypen;cout請選擇要做的操作：endl;cout4.輸入01串解碼endl;cout5.從文件中解碼q;while(q!=4&q!=5) coutq;switch(q) case 4: cout請輸入要解碼的0,1串(按2結(jié)束輸入）：a;if(a!=0&a!=1&a!=2)couta;if(a!=0&a!=1&a!=2)cout輸入錯誤，請重新輸入n; else break;if(a=0) tempcodei=0;else if(a=1)tempcodei=

17、1;else if(a=2) tempcodei=2;cout輸入的編碼為:n;for(i=0;inum;i+)couttempcodei;coutendl;int m=2*n-2;i=0;cout譯碼后為：endl;fstream outfile;outfile.open(E:textfile.txt,ios:out);/打開存放翻譯結(jié)果的文件if(!outfile) couttextfile.txt文件不能打開!endl;abort();while(inum) while(HaffNodem.lchild!=-1&HaffNodem.rchild!=-1) /判斷是不是葉子節(jié)點if(tem

18、pcodei=0) / 0為向左走m=HaffNodem.lchild;i+; else if(tempcodei=1) /1為向右走m=HaffNodem.rchild;i+;coutHaffNodem.inf;/輸出葉子節(jié)點即翻譯出的字符outfileHaffNodem.inf;/寫入文件m=2*n-2;coutendl;outfile.close();cout譯碼后的結(jié)果已經(jīng)存入textfile.txt中!endlendl;delete HaffNode;/釋放break;case 5: fstream infile2;/讀編碼infile2.open(E:code.dat,ios:in

19、|ios:binary);while(!infile2.eof() infile2.read(char*)&tempcodenum,sizeof(tempcodenum);num+;infile2.close();num-;cout從文件中讀出的編碼為endl;for(i=0; inum; i+) couttempcodei;if(i+1)%50=0) coutendl;/每輸出50個編碼換行coutendl;int m=2*n-2;i=0;coutendl;cout譯碼后為:endl;fstream outfile;outfile.open(E:textfile.txt,ios:out);i

20、f(!outfile) couttextfile.txt文件不能打開!endl;abort();while(inum)/ 從根節(jié)點0向左1向右while(HaffNodem.lchild!=-1&HaffNodem.rchild!=-1) if(tempcodei=0) m=HaffNodem.lchild;i+; else if(tempcodei=1) m=HaffNodem.rchild;i+;coutHaffNodem.inf;outfileHaffNodem.inf;m=2*n-2;coutendl;outfile.close();/關(guān)閉文件cout譯碼后的結(jié)果已經(jīng)存入textfil

21、e.txt中!endl;delete HaffNode;/釋放break;四、測試數(shù)據(jù)及程序運行情況用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。字符ABCDEFGHIJKLM頻度6413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161圖1程序運行界面：圖1：程序開始界面 圖2：程序初始化輸出Huffman樹圖2圖4圖3圖3：編碼信息輸出 圖4：對字符串編碼并輸出圖5：解碼系統(tǒng) 圖6：解碼系統(tǒng)圖5圖6對01串譯碼輸出并保存到文件讀

22、出01串（文件或鍵入）輸出字符與編碼對應(yīng)關(guān)系對已輸入的字符編碼賦初值for(i=0; i2*n-1; i+)輸入字符和權(quán)值建樹讀入一串字符（文件或鍵入）輸出Huffman樹對字符串編碼輸出并保存到文件五、實驗過程中出現(xiàn)的問題及解決方法1、用最小堆建立Huffman樹出現(xiàn)太多錯誤且過于繁瑣不易更改，故改用結(jié)構(gòu)體數(shù)組建樹。2、Huffman樹輸出時，權(quán)值大小不同導(dǎo)致顯示錯亂，故改用輸出流控制。3、編碼時出現(xiàn)非01字碼，原因是定義的存儲空間太小。后多次實驗確定合適大小。4、編碼時讀到空格會導(dǎo)致系統(tǒng)停止，后給空格定義了權(quán)值。5、文件使用txt格式存放數(shù)據(jù)讀取時出現(xiàn)亂碼，故改為dat文件。6、當(dāng)輸出非法

23、字符是會導(dǎo)致系統(tǒng)錯亂，后通過修改字符讀入方式和循環(huán)判定解決問題六、自我評析與總結(jié) 通過本次課程設(shè)計，我對哈夫曼樹及哈夫曼編碼有了更深刻的理解。同時對C+的編程以及算法的實現(xiàn)和文件的讀寫產(chǎn)生了比以往更大的興趣，還學(xué)到了許多在處理程序bug以及程序美化時的技巧和方法。如在處理數(shù)據(jù)時要分配合理的空間，也要及時釋放空間。從剛開始一點頭緒都沒有，到后來一步步編寫成功，查閱了好多資料，也詢問了好多同學(xué)。根據(jù)老師要求，在譯碼處不單實現(xiàn)了從鍵盤讀入，同時也實現(xiàn)了從文件讀入。通過這次實驗我積累了更多編程的經(jīng)驗。程序有很多不足的地方，例如程序健壯性不好，二進制讀寫容易出錯等等。從文件中修改二進制編碼功能嘗試了很久

24、還是沒能完成，沒有能實現(xiàn)哈夫曼樹的圖形化輸出，這些都是我們的遺憾。但是在程序的編寫中，我們也完善了很多問題，添加了一些功能，在一定程度上提高了程序的健壯性。每解決一個問題，我們都會發(fā)自內(nèi)心的感到高興，這大概就是寫程序的樂趣。通過這次課程設(shè)計，讓我更好的理解了本學(xué)期數(shù)據(jù)結(jié)構(gòu)的課程知識，也大大提高了我們用c+編程的能力，我們更加注重添加注釋，增強代碼的可讀性，這都是我們在本次課程設(shè)計中取得的進步。七、參考文獻 數(shù)據(jù)結(jié)構(gòu)（面向?qū)ο蠓椒ㄅcC+語言描述）殷人昆 清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu) 嚴蔚敏，吳偉民 清華大學(xué)出版社雙語版C+語言程序設(shè)計 電子工業(yè)出版社百度百科 CSDN社區(qū)/源代碼#include#in

25、clude#include#include#includeusing namespace std;#define MaxBit 50#define Maxvalue 1000#define Maxleaf 50#define Maxnode Maxleaf*2-1struct HNodeType /字符結(jié)構(gòu)體類型int weight;/權(quán)int parent;/雙親位置int lchild;/左孩子int rchild;/右孩子char inf;/字符;struct HcodeType int bitMaxBit;/存儲編碼int start;/起始位置;void Creat_Haffmant

26、ree(int &n) /建樹并輸出樹n+;HNodeType *HaffNode=new HNodeType2*n-1;int i,j;int m1,m2,x1,x2;for(i=0; i2*n-1; i+) /賦初值HaffNodei.weight=0;HaffNodei.parent=-1;HaffNodei.lchild=-1;HaffNodei.rchild=-1;HaffNodei.inf=0; for(i=0; in-1; i+) /輸入字符及權(quán)值cout請輸入字符:HaffNodei.inf;cout請輸入該字符的權(quán)值:HaffNodei.weight;HaffNoden-1.

27、inf= ;/最后一個為空格HaffNoden-1.weight=120;/空格權(quán)值for(i=0; in-1; i+) /構(gòu)造哈夫曼樹m1=m2=Maxvalue;x1=x2=0;for(j=0; jn+i; j+) /找出最小和次小if(HaffNodej.parent=-1&HaffNodej.weightm1) m2=m1;x2=x1;m1=HaffNodej.weight;x1=j; else if(HaffNodej.parent=-1&HaffNodej.weightm2) m2=HaffNodej.weight;x2=j;/合并Huffman樹HaffNodex1.parent

28、=n+i;HaffNodex2.parent=n+i;HaffNoden+i.weight=HaffNodex1.weight+HaffNodex2.weight;HaffNoden+i.lchild=x1;HaffNoden+i.rchild=x2;HaffNoden+i.inf= ;/輸出樹cout顯示存儲的哈弗曼樹信息:endl;cout 權(quán)值 左孩子 右孩子 父節(jié)點endl;for(i=0; i2*n-1; i+) coutHaffNodei.inf ;coutsetiosflags(ios:right)setw(4)HaffNodei.weight ;coutsetiosflags(

29、ios:right)setw(4)HaffNodei.lchild ;coutsetiosflags(ios:right)setw(4)HaffNodei.rchild ;coutsetiosflags(ios:right)setw(4)HaffNodei.parentendl;/寫入文件fstream outfile1;outfile1.open(E:nodedata.dat,ios:out|ios:trunc|ios:binary);/建立進行寫入的文件并清空之前數(shù)據(jù) if(!outfile1) /沒有創(chuàng)建成功則顯示相應(yīng)信息coutnodedata.dat文件不能打開endl;abort(

30、);for(i=0; i2*n-1; i+) /將內(nèi)存中從HaffNodei地址開始的sizeof(HaffNodei)的內(nèi)容寫入文件中outfile1.write(char*)&HaffNodei,sizeof(HaffNodei);outfile1.close ();/關(guān)閉文件delete HaffNode;void HaffCode(int &n) /哈夫曼編碼HNodeType *HaffNode=new HNodeTypeMaxnode;/存儲樹HcodeType *HaffCode=new HcodeTypeMaxleaf;/存儲編碼HcodeType cd;int i,j,c,p

31、;fstream in(E:nodedata.dat,ios:in|ios:binary);/打開文件in.read(char*)HaffNode,(2*n-1)*sizeof(HNodeType);/從文件中讀取樹in.close();/關(guān)閉文件fstream outfile;outfile.open(E:codedata.dat,ios:out|ios:binary);/建立進行寫入的文件for(i=0; in; i+) /進行編碼 并向數(shù)組中從右向左寫入編碼cd.start=n-1;c=i;p=HaffNodec.parent;while(p!=-1) if(HaffNodep.lchi

32、ld=c)cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=p;p=HaffNodec.parent;for(j=cd.start+1; jn; j+)/ 向結(jié)構(gòu)體數(shù)組存儲編碼HaffCodei.bitj=cd.bitj; HaffCodei.start=cd.start;for(i=0; in; i+) /向文件中存取數(shù)據(jù)outfileHaffNodei.inf;for(j=HaffCodei.start+1; jn; j+)outfileHaffCodei.bitj;cout字符信息-編碼信息endl;for(i=0; in; i+) co

33、utHaffNodei.inf-;for(j=HaffCodei.start+1; jn; j+)/輸出編碼coutHaffCodei.bitj;/編碼信息01串coutendl; outfile.close ();/關(guān)閉文件cout請輸入要編碼的字符串,基本元素為（;for(i=0; in; i+)coutHaffNodei.inf,;cout)endl;char inf100;/定義輸入字符存放數(shù)組getchar();gets(inf);/讀取屏幕字符int f=strlen(inf);fstream outfile1;outfile1.open(E:code.dat,ios:out|io

34、s:binary);/建立進行寫入的文件if(!outfile1) coutcode.dat文件不能打開!endl;abort(); else coutendl; cout字符串編碼后為:n;int num=0;for(int x=0; xf; x+) /輸出文本編碼for(i=0; in; i+) if(infx=HaffNodei.inf) for(j=HaffCodei.start+1; jn; j+) outfile1.write(char*)&HaffCodei.bitj,sizeof(HaffCodei.bitj);coutHaffCodei.bitj;num+;if(num%50

35、=0) coutendl; coutendl;coutendl;cout編譯后的代碼串已經(jīng)存入code.dat文件中!endl;coutendl;outfile1.close();delete HaffNode;delete HaffCode;/*譯碼系統(tǒng)*/void decode( int &n) int i;HNodeType *HaffNode=new HNodeType2*n-1;fstream infile1;infile1.open(E:nodedata.dat,ios:in|ios:binary);/打開文件if(!infile1) coutnodedata.dat文件不能打開e

36、ndl;abort();for(i=0; i2*n-1; i+)/從文件里讀出Huffman樹infile1.read(char*)&HaffNodei,sizeof(HNodeType);infile1.close();/關(guān)閉int tempcode100;/定義一個數(shù)組存放01串int num=0;for(i=0; i100; i+)/數(shù)組初始化tempcodei=-1;HcodeType *Code=new HcodeTypen;cout請選擇要做的操作：endl;cout4.輸入01串解碼endl;cout5.從文件中解碼q;while(q!=4&q!=5) coutq;switch(

37、q) case 4: cout請輸入要解碼的0,1串(按2結(jié)束輸入）：a;if(a!=0&a!=1&a!=2)couta;if(a!=0&a!=1&a!=2)cout輸入錯誤，請重新輸入n; else break;if(a=0) tempcodei=0;else if(a=1)tempcodei=1;else if(a=2) tempcodei=2;cout輸入的編碼為:n;for(i=0;inum;i+)couttempcodei;coutendl;int m=2*n-2;i=0;cout譯碼后為：endl;fstream outfile;outfile.open(E:textfile.txt,ios:out);/打開存放翻譯結(jié)果的文件if(!outfile) couttextfile.txt文件不能打開!endl;abort();while(inum) while(HaffNodem.lchild!=-1&HaffNodem.rchild!=-1) /判斷是不是葉子節(jié)點if(tempcodei=0) / 0為向左走m=Haff