數(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 問(wèn)題描述3 問(wèn)題解決方法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)輸出代碼文件，以緊湊格式顯示。二問(wèn)題描述利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。這要求在發(fā)送端通過(guò)一

2、個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(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)。三問(wè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é)點(diǎn)，將每種

3、字符的出現(xiàn)次數(shù)作為對(duì)應(yīng)節(jié)點(diǎn)權(quán)值。在編碼過(guò)程中，較科學(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)的左孩子，則編碼為0，若為右孩子，則編碼為1。然后將父節(jié)點(diǎn)作為下一輪循環(huán)的子節(jié)點(diǎn)，繼續(xù)重復(fù)上述步驟，直至到達(dá)根節(jié)點(diǎn)為止，即得到初始葉節(jié)點(diǎn)對(duì)應(yīng)的編碼。譯碼是編碼的逆過(guò)程，所以譯碼只需讀入編碼位串，從根結(jié)點(diǎn)開始，若讀到0，則走向左孩子，讀到1，則走向右孩子。并將對(duì)應(yīng)的子節(jié)點(diǎn)作為下一輪循環(huán)的葉節(jié)點(diǎn)，重復(fù)上述步驟，直至到達(dá)

4、最終葉節(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;im;i+) treei=new Huffmantree(); float small1,small2; /建立哈夫曼樹 for(i=0;in;i+) /初始化葉節(jié)點(diǎn)，

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

6、) small2=small1; small1= treej.weight; p2=p1; p1=j; else if(treej.weightsmall2) small2=treej.weight; p2=j; treep1.parent=i; /建立子節(jié)點(diǎn)與父節(jié)點(diǎn)間的對(duì)應(yīng)關(guān)系，并將父節(jié)點(diǎn)權(quán)值賦為兩子節(jié)點(diǎn)權(quán)值之和 treep2.parent=i; treei.lchild=p1; treei.rchild=p2; treei.weight=treep1.weight+treep2.weight; (2) 編碼模塊 數(shù)據(jù)結(jié)構(gòu)： Code為定義在codetype類上的數(shù)組對(duì)象。 c為緩沖變量，其

7、值為當(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 Codetypen; for(i=0;in;i+) Codei=new Codetype(); Codei.bits=new Charactern; for(i=0;in;i+) Codei.start=n; /start為編碼位串的起始位置 Codei.ch=treei.ch; c=i; p=treei.parent; while(p!=0) Codei.start-; if(treep.lchil

8、d=c) /向上回溯編碼 Codei.bitsCodei.start=0; else Codei.bitsCodei.start=1; c=p; p=treep.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為存放待譯碼文件內(nèi)容的數(shù)組。 ym存放譯碼結(jié)果。 對(duì)應(yīng)代碼段： for(int q=0;qt;q+) if(bq=0) p=treep.lchild; else p=treep.rchild; if(treep.lchild=-1) String ym=treep.ch.toStrin

9、g(); fw1.write(ym); p=m-1;（4） 字符統(tǒng)計(jì)模塊 數(shù)據(jù)結(jié)構(gòu)：len為文章中的字符數(shù)。ai為存放文章內(nèi)容的數(shù)組。Chj存放不同種類的字符,開始里面所有字符都為0值。arr存放每種字符在文章中出現(xiàn)的次數(shù)。對(duì)應(yīng)代碼段： for(int i=0;ilen;i+) /選出文章中每一種字符串 for(int j=0;jn;j+) if(ai=chj)break; else if(j=n-1)chn-1=ai; /若ch中找不到ai中存放的字符，則將該種字符放到ch中。 若找到，則說(shuō)明該種字符已被存入ch. n+; break; /初始化ch,存放字符種類 for(int i=0;i

10、len;i+) for(int j=0;jn;j+) if(ai=chj) arrj+; /統(tǒng)計(jì)文章中每種字符的出現(xiàn)次數(shù)。 （5） Huffman類 public class Huffmantree public int weight; /weight為節(jié)點(diǎn)的權(quán)值public int parent,lchild,rchild; /分別為當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)，左、右子節(jié)點(diǎn)編號(hào)public Character ch; /ch為節(jié)點(diǎn)名，即對(duì)應(yīng)的字符。public Huffmantree() /初始化，每個(gè)節(jié)點(diǎn)構(gòu)成一個(gè)單節(jié)點(diǎn)樹，權(quán)值為0。weight=0;parent=0;lchild=-1;rchild

11、=-1;ch=0;(5)codetype類public class Codetype public Character bits; /一維數(shù)組，存放每個(gè)字符對(duì)應(yīng)的編碼位串 public int start; /start為每個(gè)字符位串的起始位置 public char ch; public Codetype() start=0; ch=0; 2.流程圖 將文件內(nèi)容讀入數(shù)組 統(tǒng)計(jì)文件中字符的種類和出現(xiàn)次數(shù) 建立哈夫曼樹 哈夫曼樹編碼 將編碼內(nèi)容寫入數(shù)組和文件 對(duì)編碼文件進(jìn)行譯碼五調(diào)試與測(cè)試 分別輸入多篇文章進(jìn)行測(cè)試，文章字符數(shù)由少到多。在程序編寫過(guò)程中，要應(yīng)用的數(shù)組較多，數(shù)組的使用使原本難于實(shí)現(xiàn)

12、的算法變得簡(jiǎn)單易行。但因數(shù)組產(chǎn)生的問(wèn)題也較多。編碼時(shí)因存放文章及其頻率的數(shù)組定義長(zhǎng)度較短，不能給較長(zhǎng)的文章編碼。故要把相應(yīng)數(shù)組長(zhǎng)度改大一些。輸出時(shí)會(huì)因?yàn)閿?shù)組長(zhǎng)度不匹配的問(wèn)題出現(xiàn)空字符，也要做相應(yīng)的調(diào)整。測(cè)試文章：1. su.fv,y,u ew gbu;i;fewiu!2. When I was a little girl ,I dreamed to grow up. Because I think a child doesnt has freedom,and cant do anything by myself. But now I have grow up,to my surprise,I

13、feel more tired and have more responsibility.Though I can do something myself, I dont feel happy at all. I believe you also have the same thoughs with me. when every us was a child , we wanted to grow up, but when we became a older man,we dont have such nice life as wish. So whatever we are children

14、 or adults, we should try to make our life better, and make ourselves more happy. we should try our best to study hard, then we can let parents have good life, too! do our best to do ourself ! Believe yourself ! You are the best!六測(cè)試結(jié)果1. 2.七心得體會(huì) 通過(guò)本次實(shí)驗(yàn)，我復(fù)習(xí)了數(shù)據(jù)結(jié)構(gòu)中常見的一種結(jié)構(gòu)樹形結(jié)構(gòu)，本次實(shí)驗(yàn)對(duì)象是一種特殊的樹結(jié)構(gòu)，即哈夫曼樹。通過(guò)構(gòu)造哈

15、夫曼樹，我熟練掌握了樹的構(gòu)建及其要素。而編碼和譯碼是在以了解樹形結(jié)構(gòu)的基礎(chǔ)上，考驗(yàn)我的算法分析與設(shè)計(jì)能力。而字符統(tǒng)計(jì)及文件連接又涉及到許多文件操作，這使我深入了解了java關(guān)于文件的庫(kù)函數(shù)及操作語(yǔ)句。這些提高了我在程序設(shè)計(jì)上的綜合能力。 同時(shí)，本次實(shí)驗(yàn)也出現(xiàn)了一些問(wèn)題如在數(shù)組、文件等操作上考慮不周，使程序運(yùn)行結(jié)果不盡如人意。但通過(guò)多次的調(diào)試及測(cè)試，我逐步改正了這些問(wèn)題。這使我認(rèn)識(shí)到調(diào)試的重要性，即編寫程序不僅要知道怎么實(shí)現(xiàn)，更要知道怎么找出錯(cuò)誤并改正錯(cuò)誤，這是很重要的一項(xiàng)技能。 8 源代碼 主類package Huffman;import java.io.File;import java.io

16、.FileReader;import java.io.FileWriter;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;File file=new File(d:原文件.txt); FileReader fr=new FileReader(file); c

17、har a=new char(int)file.length(); fr.read(a); fr.close(); len=a.length; /len為文件長(zhǎng)度，n為字符種類數(shù) for(int i=0;ilen;i+) for(int j=0;jn;j+) if(ai=chj)break; else if(j=n-1)chn-1=ai; n+; break; /初始化ch,存放字符種類 System.out.println(文件中內(nèi)容如下:); for(int u=0;ulen;u+) System.out.print(au); System.out.println(n); for(int

18、i=0;ilen;i+) for(int j=0;jn;j+) if(ai=chj) sumj+; System.out.println(文件中各字符及其出現(xiàn)次數(shù)如下:); for(int i=0;in-1;i+) System.out.println(chi+:+sumi); int i,j,p1,p2,x; n-; int m=n*2-1; tree=new Huffmantreem; for(i=0;im;i+) treei=new Huffmantree(); float small1,small2; /建立哈夫曼樹 for(i=0;in;i+) treei.parent=0; tre

19、ei.lchild=-1; treei.rchild=-1; treei.weight=0; for(i=0;in;i+) treei.ch=chi; treei.weight=sumi; for(i=n;im;i+) p1=0;p2=0; small1=10000;small2=100; for(j=0;ji;j+) if(treej.parent=0) if(treej.weightsmall1) small2=small1; small1= treej.weight; p2=p1; p1=j; else if(treej.weightsmall2) small2=treej.weight

20、; p2=j; treep1.parent=i; treep2.parent=i; treei.lchild=p1; treei.rchild=p2; treei.weight=treep1.weight+treep2.weight; int c,p; /編碼部分 Code=new Codetypen; for(i=0;in;i+) Codei=new Codetype(); Codei.bits=new Charactern; for(i=0;in;i+) Codei.start=n; Codei.ch=treei.ch; c=i; p=treei.parent; while(p!=0) C

21、odei.start-; if(treep.lchild=c) Codei.bitsCodei.start=0; else Codei.bitsCodei.start=1; c=p; p=treep.parent; Codei=Codei; System.out.println(每種字符的編碼結(jié)果如下：); for(i=0;in;i+) System.out.print(Codei.ch+:); for(int r=Codei.start;rn;r+) System.out.print(Codei.bitsr); System.out.println( ); FileWriter fw=new FileWriter(d:編碼文件.txt); for(int k=0;klen;k+) for(int l=0;ln;l+) if(ak=Codel.ch) for(int h=Codel.start;hn;h+) String bm=Codel.bitsh.toS