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

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

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

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

4、最終葉節(jié)點，該葉節(jié)點即為編碼對應的節(jié)點。四程序模塊功能及流程圖1. 主要程序模塊及功能 （1） 建立哈夫曼樹 數(shù)據(jù)結(jié)構(gòu)： tree為定義在Huffmantree類上的數(shù)組對象。 n為節(jié)點個數(shù)，即字符種類數(shù)。 m為建好的哈夫曼樹的總節(jié)點數(shù)，在哈夫曼樹中，m=2*n-1。 Smal、small2分別存放每輪循環(huán)中權(quán)值最小和次小的節(jié)點的權(quán)值。 p1,p2分別記住每次合并時權(quán)值最小和次小的兩個根結(jié)點的下標。對應代碼段： for(i=0;im;i+) treei=new Huffmantree(); float small1,small2; /建立哈夫曼樹 for(i=0;in;i+) /初始化葉節(jié)點，

5、使每個葉結(jié)點都為獨立的根節(jié)點 treei.parent=0; treei.lchild=-1; treei.rchild=-1; treei.weight=0; for(i=0;in;i+) /將每種字符及其出現(xiàn)次數(shù)賦給葉節(jié)點，使每個 葉節(jié)點對應一種字符 treei.ch=chi; treei.weight=arri; for(i=n;im;i+) /由n個葉節(jié)點生成n-1個父節(jié)點 p1=0;p2=0; small1=10000;small2=100; for(j=0;ji;j+) /選出權(quán)值最小與次小的兩個節(jié)點 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é)點與父節(jié)點間的對應關(guān)系，并將父節(jié)點權(quán)值賦為兩子節(jié)點權(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ù)組對象。 c為緩沖變量，其

7、值為當前節(jié)點的下標值。 p為父節(jié)點的下標值。 Start為每個字符編碼位串中第一個字符的起始位置。對應代碼段： int c,p; /編碼部分，c為當前節(jié)點編號，p為其父節(jié)點編號 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é)點作為下一輪循環(huán)的子節(jié)點 Codei=Codei; （3） 譯碼模塊 數(shù)據(jù)結(jié)構(gòu)： p為父節(jié)點編號。 t為待譯碼文件的字符數(shù)。 b為存放待譯碼文件內(nèi)容的數(shù)組。 ym存放譯碼結(jié)果。 對應代碼段： 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)計模塊 數(shù)據(jù)結(jié)構(gòu)：len為文章中的字符數(shù)。ai為存放文章內(nèi)容的數(shù)組。Chj存放不同種類的字符,開始里面所有字符都為0值。arr存放每種字符在文章中出現(xià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; /若ch中找不到ai中存放的字符，則將該種字符放到ch中。 若找到，則說明該種字符已被存入ch. n+; break; /初始化ch,存放字符種類 for(int i=0;i

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

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

12、的算法變得簡單易行。但因數(shù)組產(chǎn)生的問題也較多。編碼時因存放文章及其頻率的數(shù)組定義長度較短，不能給較長的文章編碼。故要把相應數(shù)組長度改大一些。輸出時會因為數(shù)組長度不匹配的問題出現(xiàn)空字符，也要做相應的調(diào)整。測試文章：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!六測試結(jié)果1. 2.七心得體會 通過本次實驗，我復習了數(shù)據(jù)結(jié)構(gòu)中常見的一種結(jié)構(gòu)樹形結(jié)構(gòu)，本次實驗對象是一種特殊的樹結(jié)構(gòu)，即哈夫曼樹。通過構(gòu)造哈

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