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

..中南大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告題目哈夫曼編譯器學(xué)生姓名指導(dǎo)教師學(xué)院信息科學(xué)與工程學(xué)院專業(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ā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼,在接收端將傳來的數(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)成一顆哈夫曼樹。每種字符對應(yīng)一個節(jié)點,將每種字符的出現(xiàn)次數(shù)作為對應(yīng)節(jié)點權(quán)值。在編碼過程中,較科學(xué)的方法是統(tǒng)計文章中每種字符出現(xiàn)的頻率,并以其作為對應(yīng)節(jié)點的權(quán)值,使出現(xiàn)頻率較高的節(jié)點離根結(jié)點較近,從而使出現(xiàn)頻率越高的字符所得的編碼位數(shù)越少,這樣做得到的編碼結(jié)果是最簡練的,也更有利于譯碼。編碼需從葉節(jié)點向上回溯,若葉節(jié)點為其父結(jié)點的左孩子,則編碼為0,若為右孩子,則編碼為1。然后將父節(jié)點作為下一輪循環(huán)的子節(jié)點,繼續(xù)重復(fù)上述步驟,直至到達根節(jié)點為止,即得到初始葉節(jié)點對應(yīng)的編碼。譯碼是編碼的逆過程,所以譯碼只需讀入編碼位串,從根結(jié)點開始,若讀到0,則走向左孩子,讀到1,則走向右孩子。并將對應(yīng)的子節(jié)點作為下一輪循環(huán)的葉節(jié)點,重復(fù)上述步驟,直至到達最終葉節(jié)點,該葉節(jié)點即為編碼對應(yīng)的節(jié)點。四．程序模塊功能及流程圖主要程序模塊及功能建立哈夫曼樹數(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é)點的下標。對應(yīng)代碼段：for<i=0;i<m;i++>{tree[i]=newHuffmantree<>; }floatsmall1,small2;//建立哈夫曼樹for<i=0;i<n;i++>//初始化葉節(jié)點,使每個葉結(jié)點都為獨立的根節(jié)點 {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é)點,使每個葉節(jié)點對應(yīng)一種字符 {tree[i].ch=ch[i];tree[i].weight=arr[i]; }for<i=n;i<m;i++>//由n個葉節(jié)點生成n-1個父節(jié)點 { p1=0;p2=0; small1=10000;small2=100;for<j=0;j<i;j++>//選出權(quán)值最小與次小的兩個節(jié)點if<tree[j].parent==0>if<tree[j].weight<small1> { small2=small1; small1=tree[j].weight; p2=p1; p1=j; }elseif<tree[j].weight<small2> { small2=tree[j].weight; p2=j; }tree[p1].parent=i;//建立子節(jié)點與父節(jié)點間的對應(yīng)關(guān)系,并將父節(jié)點權(quán)值賦為兩子節(jié)點權(quán)值之和tree[p2].parent=i;tree[i].lchild=p1;tree[i].rchild=p2;tree[i].weight=tree[p1].weight+tree[p2].weight; }編碼模塊數(shù)據(jù)結(jié)構(gòu)：Code[]為定義在codetype類上的數(shù)組對象。c為緩沖變量,其值為當(dāng)前節(jié)點的下標值。p為父節(jié)點的下標值。Start為每個字符編碼位串中第一個字符的起始位置。對應(yīng)代碼段：intc,p;//編碼部分,c為當(dāng)前節(jié)點編號,p為其父節(jié)點編號Code=newCodetype[n];for<i=0;i<n;i++>{Code[i]=newCodetype<>;Code[i].bits=newCharacter[n]; }for<i=0;i<n;i++> {Code[i].start=n;//start為編碼位串的起始位置Code[i].ch=tree[i].ch; c=i; p=tree[i].parent;while<p!=0> {Code[i].start--;if<tree[p].lchild==c>//向上回溯編碼Code[i].bits[Code[i].start]='0';elseCode[i].bits[Code[i].start]='1'; c=p; p=tree[p].parent;//將父節(jié)點作為下一輪循環(huán)的子節(jié)點 }Code[i]=Code[i]; }譯碼模塊數(shù)據(jù)結(jié)構(gòu)：p為父節(jié)點編號。t為待譯碼文件的字符數(shù)。b[]為存放待譯碼文件內(nèi)容的數(shù)組。ym存放譯碼結(jié)果。對應(yīng)代碼段：for<intq=0;q<t;q++>{if<b[q]=='0'> p=tree[p].lchild;else p=tree[p].rchild;if<tree[p].lchild==-1> { Stringym=tree[p].ch.toString<>; fw1.write<ym>; p=m-1;}} 字符統(tǒng)計模塊數(shù)據(jù)結(jié)構(gòu)：len為文章中的字符數(shù)。a[i]為存放文章內(nèi)容的數(shù)組。Ch[j]存放不同種類的字符,開始里面所有字符都為0值。arr[]存放每種字符在文章中出現(xiàn)的次數(shù)。對應(yīng)代碼段：for<inti=0;i<len;i++>{//選出文章中每一種字符串for<intj=0;j<n;j++>{if<a[i]==ch[j]>break; elseif<j==n-1>{ch[n-1]=a[i];//若ch[]中找不到a[i]中存放的字符,則將該種字符放到ch[]中。若找到,則說明該種字符已被存入ch[].n++;break; } }}//初始化ch[],存放字符種類for<inti=0;i<len;i++>for<intj=0;j<n;j++> {if<a[i]==ch[j]> arr[j]++;//統(tǒng)計文章中每種字符的出現(xiàn)次數(shù)。 }Huffman類publicclassHuffmantree{ publicintweight;//weight為節(jié)點的權(quán)值 publicintparent,lchild,rchild;//分別為當(dāng)前節(jié)點的父節(jié)點,左、右子節(jié)點編號 publicCharacterch;//ch為節(jié)點名,即對應(yīng)的字符。 publicHuffmantree<>{//初始化,每個節(jié)點構(gòu)成一個單節(jié)點樹,權(quán)值為0。 weight=0; parent=0; lchild=-1; rchild=-1; ch='0'; }<5>codetype類publicclassCodetype{ publicCharacterbits[];//一維數(shù)組,存放每個字符對應(yīng)的編碼位串 publicintstart;//start為每個字符位串的起始位置 publiccharch; publicCodetype<>{ start=0; ch=0;}}}2.流程圖將文件內(nèi)容讀入數(shù)組統(tǒng)計文件中字符的種類和出現(xiàn)次數(shù)建立哈夫曼樹哈夫曼樹編碼將編碼內(nèi)容寫入數(shù)組和文件對編碼文件進行譯碼五．調(diào)試與測試分別輸入多篇文章進行測試,文章字符數(shù)由少到多。在程序編寫過程中,要應(yīng)用的數(shù)組較多,數(shù)組的使用使原本難于實現(xiàn)的算法變得簡單易行。但因數(shù)組產(chǎn)生的問題也較多。編碼時因存放文章及其頻率的數(shù)組定義長度較短,不能給較長的文章編碼。故要把相應(yīng)數(shù)組長度改大一些。輸出時會因為數(shù)組長度不匹配的問題出現(xiàn)空字符,也要做相應(yīng)的調(diào)整。測試文章：su.fv,y,uewgbu;i;fewiu!WhenIwasalittlegirl,Idreamedtogrowup.BecauseIthinkachilddoesn'thasfreedom,andcan'tdoanythingbymyself.ButnowIhavegrowup,tomysurprise,Ifeelmoretiredandhavemoreresponsibility.ThoughIcandosomethingmyself,Idon'tfeelhappyatall.Ibelieveyoualsohavethesamethoughswithme.wheneveryuswasachild,wewantedtogrowup,butwhenwebecameaolderman,wedon'thavesuchnicelifeaswish.Sowhateverwearechildrenoradults,weshouldtrytomakeourlifebetter,andmakeourselvesmorehappy.weshouldtryourbesttostudyhard,thenwecanletparentshavegoodlife,too!doourbesttodoourself!Believeyourself!Youarethebest!六．測試結(jié)果1.2.七．心得體會通過本次實驗,我復(fù)習(xí)了數(shù)據(jù)結(jié)構(gòu)中常見的一種結(jié)構(gòu)——樹形結(jié)構(gòu),本次實驗對象是一種特殊的樹結(jié)構(gòu),即哈夫曼樹。通過構(gòu)造哈夫曼樹,我熟練掌握了樹的構(gòu)建及其要素。而編碼和譯碼是在以了解樹形結(jié)構(gòu)的基礎(chǔ)上,考驗我的算法分析與設(shè)計能力。而字符統(tǒng)計及文件連接又涉及到許多文件操作,這使我深入了解了java關(guān)于文件的庫函數(shù)及操作語句。這些提高了我在程序設(shè)計上的綜合能力。同時,本次實驗也出現(xiàn)了一些問題如在數(shù)組、文件等操作上考慮不周,使程序運行結(jié)果不盡如人意。但通過多次的調(diào)試及測試,我逐步改正了這些問題。這使我認識到調(diào)試的重要性,即編寫程序不僅要知道怎么實現(xiàn),更要知道怎么找出錯誤并改正錯誤,這是很重要的一項技能。源代碼主類packageHuffman;importjava.io.File;importjava.io.FileReader;importjava.io.FileWriter;publicclassMain{ publicstaticHuffmantree[]tree; publicstaticCodetype[]Code;publicstaticvoidmain<String[]args>throwsException{ floatlen; intn=1;int[]sum=newint[50000]; char[]ch=newchar[50000]; Filefile=newFile<"d:\\原文件.txt">; FileReaderfr=newFileReader<file>; char[]a=newchar[<int>file.length<>]; fr.read<a>; fr.close<>; len=a.length;//len為文件長度,n為字符種類數(shù) for<inti=0;i<len;i++>{ for<intj=0;j<n;j++>{ if<a[i]==ch[j]>break; else if<j==n-1>{ch[n-1]=a[i]; n++; break; } }}//初始化ch[],存放字符種類 System.out.println<"文件中內(nèi)容如下:">; for<intu=0;u<len;u++> {System.out.print<a[u]>; } System.out.println<"\n">; for<inti=0;i<len;i++> for<intj=0;j<n;j++> {if<a[i]==ch[j]> sum[j]++; }System.out.println<"文件中各字符及其出現(xiàn)次數(shù)如下:">; for<inti=0;i<n-1;i++>{ System.out.println<ch[i]+":"+sum[i]>; } inti,j,p1,p2,x; n--; intm=n*2-1; tree=newHuffmantree[m]; for<i=0;i<m;i++>{ tree[i]=newHuffmantree<>; } floatsmall1,small2;//建立哈夫曼樹 for<i=0;i<n;i++> { tree[i].parent=0; tree[i].lchild=-1; tree[i].rchild=-1; tree[i].weight=0; } for<i=0;i<n;i++> { tree[i].ch=ch[i]; tree[i].weight=sum[i]; } for<i=n;i<m;i++> { p1=0;p2=0; small1=10000;small2=100; for<j=0;j<i;j++> if<tree[j].parent==0> if<tree[j].weight<small1> { small2=small1; small1=tree[j].weight; p2=p1; p1=j; } else if<tree[j].weight<small2> { small2=tree[j].weight; p2=j; } tree[p1].parent=i; tree[p2].parent=i; tree[i].lchild=p1; tree[i].rchild=p2; tree[i].weight=tree[p1].weight+tree[p2].weight; } intc,p;//編碼部分 Code=newCodetype[n]; for<i=0;i<n;i++>{ Code[i]=newCodetype<>; Code[i].bits=newCharacter[n]; } for<i=0;i<n;i++> { Code[i].start=n; Code[i].ch=tree[i].ch; c=i; p=tree[i].parent; while<p!=0> { Code[i].start--; if<tree[p].lchild==c> Code[i].bits[Code[i].start]='0'; else Code[i].bits[Code[i].start]='1'; c=p; p=tree[p].parent; } Code[i]=Code[i]; } System.out.println<"每種字符的編碼結(jié)果如下：">; for<i=0;i<n;i++>{ System.out.print<Code[i].ch+":">; for<intr=Code[i].start;r<n;r++> System.out.print<Code[i].bits[r]>; System.out.println<"">; } FileWriterfw=newFileWriter<"d:\\編碼文件.txt">; for<intk=0;k<len;k++>{ for<intl=0;l<n;l++> if<a[k]==Code[l].ch>{ for<inth=Code[l].start;h