數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)哈夫曼編譯器

1、中南大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題 目哈夫曼編譯器 學(xué)生 指導(dǎo)教師 學(xué) 院信息科學(xué)與工程學(xué)院專業(yè)班級(jí)計(jì)科1302目錄實(shí)驗(yàn)要求 3問題描述 3問題解決方法 3程序模塊功能及流程圖 4調(diào)試與測(cè)試 8測(cè)試結(jié)果 9心得體會(huì) 11源代碼 12 一實(shí)驗(yàn)要求(1) 從鍵盤讀入字符集大小n ,以及n個(gè)字符和權(quán)值，建立哈夫曼樹。(2) 利用已建好的哈夫曼樹對(duì)文件正文進(jìn)行編碼，將結(jié)果存入相關(guān)文件中。(3) 利用已建好的哈夫曼樹將編碼文件中的代碼進(jìn)行譯碼，結(jié)果存入文件中。(4) 輸出代碼文件，以緊湊格式顯示。二問題描述利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。這要求在發(fā)送端通過一個(gè)編

2、碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端 將傳來的數(shù)據(jù)進(jìn)行譯碼。對(duì)于雙向傳輸信息的信道，每端都需要一個(gè)完整的編譯 碼系統(tǒng)。為這樣的信息收發(fā)站編寫哈夫曼編譯系統(tǒng)。哈夫曼樹又稱最優(yōu)二叉樹，構(gòu)造的規(guī)則即給定n個(gè)權(quán)值不同的葉子節(jié)點(diǎn)，構(gòu) 造一棵二叉樹，使二叉樹的帶權(quán)路徑長(zhǎng)度達(dá)到最小。具體做法即要使權(quán)值較大的 結(jié)點(diǎn)離根節(jié)點(diǎn)較近，權(quán)值較小的結(jié)點(diǎn)離根節(jié)點(diǎn)較遠(yuǎn)。三問題解決方法建立哈夫曼樹時(shí)要進(jìn)行多次選擇，每次選擇出權(quán)值最小和次小的兩個(gè)節(jié)點(diǎn)，將兩結(jié)點(diǎn)權(quán)值相加，作為新生成父節(jié)點(diǎn)的權(quán)值。并分別將其作為左、右孩子。再 將父節(jié)點(diǎn)加入需選擇的結(jié)點(diǎn)序列中， 繼續(xù)選擇，直到將所有節(jié)點(diǎn)都選完為止，構(gòu) 成一顆哈夫曼樹。每種字符對(duì)應(yīng)一個(gè)節(jié)

3、點(diǎn)，將每種字符的出現(xiàn)次數(shù)作為對(duì)應(yīng)節(jié)點(diǎn) 權(quán)值。在編碼過程中，較科學(xué)的方法是統(tǒng)計(jì)文章中每種字符出現(xiàn)的頻率， 并以其作 為對(duì)應(yīng)節(jié)點(diǎn)的權(quán)值，使出現(xiàn)頻率較高的節(jié)點(diǎn)離根結(jié)點(diǎn)較近， 從而使出現(xiàn)頻率越高 的字符所得的編碼位數(shù)越少，這樣做得到的編碼結(jié)果是最簡(jiǎn)練的， 也更有利于譯 碼。編碼需從葉節(jié)點(diǎn)向上回溯，若葉節(jié)點(diǎn)為其父結(jié)點(diǎn)的左孩子，貝U編碼為0,若為右孩子，則編碼為1。然后將父節(jié)點(diǎn)作為下一輪循環(huán)的子節(jié)點(diǎn)，繼續(xù)重復(fù)上述 步驟，直至到達(dá)根節(jié)點(diǎn)為止，即得到初始葉節(jié)點(diǎn)對(duì)應(yīng)的編碼。譯碼是編碼的逆過程，所以譯碼只需讀入編碼位串，從根結(jié)點(diǎn)開始，若讀到 0，則走向左孩子，讀到1，則走向右孩子。并將對(duì)應(yīng)的子節(jié)點(diǎn)作為下一輪循環(huán)的

4、葉節(jié)點(diǎn)，重復(fù)上述步驟，直至到達(dá)最終葉節(jié)點(diǎn)，該葉節(jié)點(diǎn)即為編碼對(duì)應(yīng)的節(jié)點(diǎn) 四程序模塊功能及流程圖1.主要程序模塊及功能(1)建立哈夫曼樹數(shù)據(jù)結(jié)構(gòu)：tree 為定義在Huffmantree類上的數(shù)組對(duì)象。n為節(jié)點(diǎn)個(gè)數(shù)，即字符種類數(shù)。m為建好的哈夫曼樹的總節(jié)點(diǎn)數(shù)，在哈夫曼樹中，m=2*n-1。Smal、small2分別存放每輪循環(huán)中權(quán)值最小和次小的節(jié)點(diǎn)的權(quán)值。p1,p2分別記住每次合并時(shí)權(quán)值最小和次小的兩個(gè)根結(jié)點(diǎn)的下標(biāo)。 對(duì)應(yīng)代碼段：for (i=0;i<m;i+)t reei= new Huffmantree();float small1,small2; /建立哈夫曼樹for (i=0;i&l

5、t;n;i+)/初始化葉節(jié)點(diǎn)，使每個(gè)葉結(jié)點(diǎn)都為獨(dú)立的根節(jié)點(diǎn)tree i.parent=0;tree i.lchild=-1;tree i.rchild=-1;tree i.weight=0;for (i=0;i<n;i+)/將每種字符及其岀現(xiàn)次數(shù)賦給葉節(jié)點(diǎn)，使每個(gè)葉節(jié)點(diǎn)對(duì)應(yīng)一種字符tree i.ch=chi;tree i.weight=arri;for (i=n;i<m;i+) /由n個(gè)葉節(jié)點(diǎn)生成 n-1個(gè)父節(jié)點(diǎn)p1=0;p2=0;small1=10000;small2=100;for (j=0;j<i;j+)/選岀權(quán)值最小與次小的兩個(gè)節(jié)點(diǎn)if (tree j.parent=

6、0)if (tree j.weight<small1)small2=small1;small1=tree j.weight;p2=p1;Pl=j；elseif (tree j.weight<small2)small2= tree j.weight;p2=j； treep1.pare nt=i; /建立子節(jié)點(diǎn)與父節(jié)點(diǎn)間的對(duì)應(yīng)關(guān)系，并將父節(jié)點(diǎn)權(quán)值賦為兩子節(jié)點(diǎn)權(quán)值之和tree p2.parent=i;tree i.lchild=p1;tree i.rchild=p2;tree i.weight= tree p1.weight+ tree p2.weight;(2)編碼模塊數(shù)據(jù)結(jié)構(gòu)：Cod

7、e為定義在codetype類上的數(shù)組對(duì)象。c為緩沖變量，其值為當(dāng)前節(jié)點(diǎn)的下標(biāo)值。p為父節(jié)點(diǎn)的下標(biāo)值。Start為每個(gè)字符編碼位串中第一個(gè)字符的起始位置。對(duì)應(yīng)代碼段：int c,p;/編碼部分，c為當(dāng)前節(jié)點(diǎn)編號(hào)，p為其父節(jié)點(diǎn)編號(hào)Code= new Codetype n;for (i=0;i<n;i+)COdei= new Codetype(); Cbdei.bits=new Character n;for (i=0;i<n;i+) Cod&i.start=n;/start為編碼位串的起始位置Codei.ch= tree i.ch;c=i;p= tree i.parent;wh

8、ile (p!=0)Codgi.start-;if (tree p.lchild=c) / 向上回溯編碼 Codei.bitsCodei.start='0'elseCodei.bitsCodei.start='1'c=p;p= tree p.parent; / 將父節(jié)點(diǎn)作為下一輪循環(huán)的子節(jié)點(diǎn) Codei= Codei;3)譯碼模塊數(shù)據(jù)結(jié)構(gòu)： p 為父節(jié)點(diǎn)編號(hào)。 t 為待譯碼文件的字符數(shù)。 b 為存放待譯碼文件容的數(shù)組。 ym 存放譯碼結(jié)果。對(duì)應(yīng)代碼段：for (int q=0;q<t;q+)if (bq='0')p= tree p.lchi

9、ld;elsep= tree p.rchild;if (tree p.lchild=-1) String ym= tree p.ch.toString(); fw1.write(ym);p=m-1;4)字符統(tǒng)計(jì)模塊 數(shù)據(jù)結(jié)構(gòu)：len 為文章中的字符數(shù)。ai 為存放文章容的數(shù)組。Chj 存放不同種類的字符 , 開始里面所有字符都為 0 值。arr 存放每種字符在文章中出現(xiàn)的次數(shù)。 對(duì)應(yīng)代碼段：for ( int i=0;i<len;i+) / 選出文章中每一種字符串f or ( int j=0;j<n;j+)if (ai=chj) break ;elseif (j=n-1)chn-1

10、=ai; / 若 ch 中找不到 ai 中存放的字符，則 將該種字符放到 ch 中 若找到，則說明該種字符已被存入 ch.n+;break ;/初始化ch,存放字符種類for (int i=0;i<len;i+)for (int j=O;j<n;j+) if (ai=chj)arrj+;/統(tǒng)計(jì)文章中每種字符的岀現(xiàn)次數(shù)。(5) Huffman 類public class Huffma ntree /weight為節(jié)點(diǎn)的權(quán)值public int weight;public int pare nt,lchild,rchild; /分別為當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)，左、右子節(jié)點(diǎn)編號(hào)為節(jié)點(diǎn)名，即對(duì)應(yīng)的

11、字符。初始化，每個(gè)節(jié)點(diǎn)構(gòu)成一個(gè)單節(jié)點(diǎn)樹，權(quán)值為0一維數(shù)組，存放每個(gè)字符對(duì)應(yīng)的編碼位串為每個(gè)字符位串的起始位置public Character ch; /ch public Huffma ntree() / weight=0; pare nt=0; lchild=-1; rchild=-1;ch='0'(5)codetype 類public class Codetype public Character bits; /public int start; /startpublic char ch;public Codetype()start=0;ch=0;2.流程圖將文件容讀入數(shù)組

12、 統(tǒng)計(jì)文件中字符的種類和出現(xiàn)次數(shù)建立哈夫曼樹哈夫曼樹編碼將編碼容寫入數(shù)組和文件對(duì)編碼文件進(jìn)行譯碼五調(diào)試與測(cè)試分別輸入多篇文章進(jìn)行測(cè)試，文章字符數(shù)由少到多。在程序編寫過程中，要應(yīng)用的數(shù)組較多，數(shù)組的使用使原本難于實(shí)現(xiàn)的算法 變得簡(jiǎn)單易行。但因數(shù)組產(chǎn)生的問題也較多。編碼時(shí)因存放文章及其頻率的數(shù)組 定義長(zhǎng)度較短，不能給較長(zhǎng)的文章編碼。故要把相應(yīng)數(shù)組長(zhǎng)度改大一些。輸出時(shí)會(huì)因?yàn)閿?shù)組長(zhǎng)度不匹配的問題出現(xiàn)空字符，也要做相應(yīng)的調(diào)整。測(cè)試文章：1. su.fv,y,u ew gbu;i;fewiu!2. When I was a little girl ,I dreamedto grow up. Because

13、 I thi nk a childdoes n't hasfreedom,a nd can't do anything by myself.But now I have grow up,to my surprise feel more tired and have more resp on sibility.Though I can do someth ing myself, I don't feel happy at all.I believe you also have the same thoughs with me. whe n every us was a c

14、hild , we wan ted to grow up, but whe n we became a older man,we don't have such nice life as wish.So whatever we are children or adults, we should try to make our life better, and make ourselves more happy. we should try our best to study hard, the n we can let pare nts have good life, too!do o

15、ur best to do ourself ! Believe yourself ! You are the best!六測(cè)試結(jié)果1.wtEnnintd ix/l迫in |Java A! ： i首種字符的編碼結(jié)果如下:3!u:10D；aQoiX；0111v：noio<:ioioy:0011J1011e： 1100W；11Q1g：niODb：moi；：1110iillll! :0110文件中內(nèi)容如下：Sil,±v u ew gtou; i;±ewiu !文件中各字符及其出現(xiàn)友數(shù)如下:s : 1u；: 4:1X ；3v:l：2:2e:22toil；：2i:2! !13譯碼

16、文件bl -記事本丈禪犧(E)播式(0)章看岡 su. fVj y? u ew gbu; 1; f ewiu !2.文件中內(nèi)容如下：IflieE I wcu 0 1 itt le girl f I direeatied to g'r ow up . Sccemse I think cl child do ear But now I have groisr up,to my surprise, I feel more tired and have more respors I believe you also have the same thoughs ulxh me. ¥he

17、n every ws was q child * 呂口 whsteveE" Tje 牙苦。oh i I dlrsTl 口附 曰日口丄七 且* mb n卉口 14I日 tpy 匸口 wisfclrp- quf I if e b'Ftt er, 肓 Let1 s do our best to do ouraell ! Believe yourself ! You are the bsst!文件中各字符反苴出現(xiàn)次數(shù)如下:142W: 1h：31en:24I:Sm 19&:39s:1:27評(píng) bEjr匚h 左 konsoie .'=：tet*miriaterl IVla

18、in (1) J2721犯931122515餐£：10731051014:sV" 1 I IT i L3 : 1.! : 4L : 1豊希竽育的編礙箱果加下:口6W : iCiLiOOl 1 1Oii s xioxiQ s DIO血：1O111X e llXlOClw : J_XX±1.O£L ： 口丄 L 口9 ! TX 3_D3_1 8 L1OOL1 i xmigot ： m liCff :xxxxoxoe : Xd±00* s XOLXO±wL： XLCIUOms九盅口1O1n ? icvaiUL： 1OL 口 Lp 5 XI

19、LIL JL1 3 LI11OCOB i 丄>IXOCOlC： £ XCVQOQQ>Ci 101100X0ltl : iam1 = 1 meal1111 3口m 瓷 OzL J.O s = moi 1 z 3L 1DD11 5 10 I OC匚=口 Hla sliiicicu I 5L11OO .± 3l口厘 1C3L els 1 1DOC TOi 1 1O1C1 Q S 1OO1 us dLOipi p = a li id.11 » * 3l 11 ICDClEl ； ICllOOC 1 Q £ 1OOOOO K；XO11CO1C1 : &

20、#177;:l±l i± O 1 ± = HCl 口 DCI3l311O1COID » 3. 111O1 121OOO1IO=loooi j.aV31OOO1OTf 1OZ1CO1 111S110X100000! « XUllXQCL 二 Ji QI ZLClCl口1V : 3L口 H 丄口口3_ 九口3ft文件 Jxt -記黑t X文彳機(jī)D囁憎式(0)蠻看陰禍助When I was 以 little girl ,1 ctreaired to grrw up” Because I think a child doesn't But no

21、常 I liave row up, tu my suipiise, I fttil ncipb! tirad aud have mare TespmiBAbL I believe you also havo tho sarrc thoughs th me. hen every uu was a child , we So whatever w ar? children or adults, iv= shculd try toour Life better, andLetJ s do our best to da ourself ! Believe vrurself ! You are the

22、best!七心得體會(huì)通過本次實(shí)驗(yàn)，我復(fù)習(xí)了數(shù)據(jù)結(jié)構(gòu)中常見的一種結(jié)構(gòu)樹形結(jié)構(gòu)，本次實(shí)我熟練掌握了樹考驗(yàn)我的算法分驗(yàn)對(duì)象是一種特殊的樹結(jié)構(gòu)，即哈夫曼樹。通過構(gòu)造哈夫曼樹, 的構(gòu)建及其要素。而編碼和譯碼是在以了解樹形結(jié)構(gòu)的基礎(chǔ)上，這使我深入了解析與設(shè)計(jì)能力。而字符統(tǒng)計(jì)及文件連接又涉及到許多文件操作，了 java關(guān)于文件的庫(kù)函數(shù)及操作語(yǔ)句。這些提高了我在程序設(shè)計(jì)上的綜合能力。同時(shí)，本次實(shí)驗(yàn)也出現(xiàn)了一些問題如在數(shù)組、文件等操作上考慮不周，使程序運(yùn)行結(jié)果不盡如人意。但通過多次的調(diào)試及測(cè)試，我逐步改正了這些問題。這 使我認(rèn)識(shí)到調(diào)試的重要性，即編寫程序不僅要知道怎么實(shí)現(xiàn)，更要知道怎么找出 錯(cuò)誤并改正錯(cuò)誤，這是

23、很重要的一項(xiàng)技能。八源代碼主類package Huffman;public class Main public static Huffmantree tree;public static Codetype Code;public static void main(String args) throws Exception float len;int n=1;int sum=new int50000;char ch=new char50000;原文件 .txt");FileReader fr=new FileReader(file);char a=new char(int)file.l

24、ength();fr.read(a);fr.close();len=a.length; /len為文件長(zhǎng)度， n 為字符種類數(shù)for(int i=0;i<len;i+)for(int j=0;j<n;j+)if(ai=chj)break;elseif(j=n-1)chn-1=ai;n+;break;/ 初始化 ch, 存放字符種類文件中容如下 :");for(int u=0;u<len;u+)for(int i=0;i<len;i+)for(int j=0;j<n;j+)if(ai=chj)sumj+;文件中各字符及其出現(xiàn)次數(shù)如下 :"); f

25、or(int i=0;i<n-1;i+)int i,j,p1,p2,x;n-;int m=n*2-1;tree=new Huffmantreem;for(i=0;i<m;i+)treei=new Huffmantree();float small1,small2; / 建立哈夫曼樹for(i=0;i<n;i+)treei.parent=0;treei.lchild=-1;treei.rchild=-1;treei.weight=0;for(i=0;i<n;i+)treei.ch=chi;treei.weight=sumi;for(i=n;i<m;i+)p1=0;p

26、2=0;small1=10000;small2=100; for(j=0;j<i;j+) if(treej.parent=0) if(treej.weight<small1)small2=small1;small1= treej.weight;p2=p1;p1=j;elseif(treej.weight<small2)small2=treej.weight;p2=j;treep1.parent=i;treep2.parent=i;treei.lchild=p1;treei.rchild=p2;treei.weight=treep1.weight+treep2.weight;編

27、碼部分int c,p; /Code=new Codetypen;for(i=0;i<n;i+)Codei=new Codetype();Codei.bits=new Charactern;for(i=0;i<n;i+)Codei.start=n;Codei.ch=treei.ch;c=i;p=treei.parent;while(p!=0)Codei.start-;if(treep.lchild=c)Codei.bitsCodei.start='0'elseCodei.bitsCodei.start='1'c=p;p=treep.parent;Codei=Codei;每種字符的編碼結(jié)果