哈夫曼樹課程設計報告書

1、中南林業(yè)科技大學課程設計報告設計名稱：數(shù)據(jù)結構課程設計姓名：王昆學號：20094282專業(yè)班級：2009級軟件工程（院）：計算機與信息工程學院設計時間：20102011 學年第一學期設計地點：電子信息樓機房成績:指導教師評語:簽名：年 月 日，編寫程序求解指定問題，提高編程水平，并在此過程中培1課程設計目的1、訓練學生靈活應用所學數(shù)據(jù)結構知識，獨立完成問題分析，結合數(shù)據(jù)結構理論知識2初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技能3提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；4訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，鞏固、深化學生的理論知識養(yǎng)他們嚴

2、謹?shù)目茖W態(tài)度和良好的工作作風。2 .課程設計任務與要求任務.哈夫曼樹應用功能：(1) 從終端讀入字符集大小n,以及n個字符和n個權值，建立哈夫曼樹并將它存于文件hfmTree中.將已在內存 哈夫曼樹以直觀的方式(比如樹)顯示在終端上；(2) 利用已經建好的哈夫曼樹(如不在內存，則從文件htmTree中讀入)，對文件ToBeTran中的正文進行編碼 后將結果存入文件Cod eFile中，并輸出結果，將文件CodeFile以緊湊格式先是在終端上，每行50個代碼。同時將此 形式的編碼文件寫入文件CodePrint中。(3) 利用已建好的哈夫曼樹將文件 CodeFile中的代碼進行譯碼，結果存入文件T

3、extFile中，并輸出結果。分步實施：1) 初步完成總體設計，搭好框架，確定人機對話的界面，確定函數(shù)個數(shù)；2) 完成最低要求：完成功能1 ；3) 進一步要求：完成功能2和3。有興趣的同學可以自己擴充系統(tǒng)功能。要求：1、在處理每個題目時，要求從分析題目的需求入手，按設計抽象數(shù)據(jù)類型、構思算法、通過設計實現(xiàn)抽象數(shù)據(jù)類型、編制上機程序和上機調試等若干步驟完成題目，最終寫出完整的分析報告。前期準備工作完備與否直接影響到后序上機調試工作的效率。在程序設計階段應盡量利用已有的標準函數(shù)，加大代碼的重用率。2、 設計的題目要求達到一定工作量（300行以上代碼），并具有一定的深度和難度。3、 程序設計語言推薦

4、使用C/C+，程序書寫規(guī)范，源程序需加必要的注釋；4、 每位同學需提交可獨立運行的程序；5、 每位同學需獨立提交設計報告書（每人一份），要求編排格式統(tǒng)一、規(guī)范、內容充實，不少于10頁（代碼不算）；6、 課程設計實踐作為培養(yǎng)學生動手能力的一種手段，單獨考核3 .課程設計說明書一需求分析要求用到數(shù)據(jù)結構課上學到的線性表的知識，所以就要充分而清晰的理解關于線性表的知識。要求實現(xiàn)的基本功能很簡單，只有刪除和插入,增加功能也不過是加上修改。這些在數(shù)據(jù)結構課上已經講過，只要能夠 理解關于線性表的幾個相關的基本算法就可以了。問題是將輸入的信息保存入文件和從文件輸出。這里基本是自學的內容，而且要考慮到是否要自

5、行選擇保存的磁盤。綜上，做這個課題，要具備的知識就是線性表的基本算法，文件的保存和讀取算法，必要的C或者C+知識（本次我將使用C實現(xiàn)），以及豐富的程序調適經驗 。二概要設計程序流程圖三詳細設計1、哈夫曼樹結點結構定義struct hfmnodechar nValue;/ 節(jié)點值int weight;/ 權值int pnln dex; 父結點下標in t lchildI ndex,rchild In dex;/左右孩子的結點下標;哈夫曼樹類定義class huffma nTreepublic:void code(char nvalue,i nt w,i nt n); /對葉子結點編碼void d

6、ecode(char n value,char hfmcode,i nt n);/對葉子結點譯碼void Output(huffma nTree ht, int n);/輸出哈夫曼樹/private:hfmnode hfmNode2000;用數(shù)組存儲哈夫曼結點void creatHfmTree(char n value,i nt w,i nt n);/倉 U建哈夫曼樹void select(i nt pos,i nt &nodeOn e,i nt &n odeTwo);/查詢最小的兩個結點;2、主要函數(shù)及相關功能1 在數(shù)組hfmNode中從0開始到pos位置，查找哈夫曼樹外的權

7、值最小的兩個結點的位置void huffma nTree:select(i nt pos,i nt &nodeOn e,i nt &no deTwo)2 創(chuàng)建哈夫曼樹，nvalue是結點值，w是權值，n是葉子結點的個數(shù)void huffma nTree:creatHfmTree(char n value,i nt w,i nt n)3 求哈夫曼樹的編碼nvalue是結點值數(shù)組，w是權值數(shù)組n是葉子結點的個數(shù)void huffma nTree:code(char n value,i nt w,i nt n)4 哈夫曼譯碼 nvalue為結點值數(shù)組hfmcode為哈夫曼編碼，n個葉

8、子結點void huffma nTree:decode(char n value,char hfmcode,i nt n)5檢查輸入的字符值是否合法bool isChar(c onst stri ng& str)6 輸出哈夫曼樹，字符，權值，以及它對應的編碼void huffma nTree:Output(huffma nTree ht,i nt n)3、源程序#in clude<iostream>using n amespace std;struct hfmn ode/哈夫曼樹結點結構定義char nValue;/ 節(jié)點值int weight;/ 權值int pnln d

9、ex;/ 父結點下標int lchildI ndex,rchildl ndex;/左右孩子的結點下標;class huffma nTree/ 哈夫曼樹類定義public:void code(char nvalue,i nt w,i nt n); /對葉子結點編碼void decode(char n value,char hfmcode,i nt n);/對葉子結點譯碼void Output(huffma nTree ht, int n);/輸出哈夫曼樹/private:hfmnodehfmNode2000;用數(shù)組存儲哈夫曼結點void creatHfmTree(char n value,i n

10、t w,i nt n);倉 U建哈夫曼樹void select(i nt pos,i nt &nodeOn e,i nt &n odeTwo);/查詢最小的兩個結點；/在數(shù)組hfmNode中從O開始到pos位置，查找哈夫曼樹外的權值最小的兩個結點的位置void huffma nTree:select(i nt pos,i nt &nodeOn e,i nt &no deTwo)long w1,w2;w仁 w2=88888;for(i nt i=0;i<=pos;i+)if(hfmNodei.p nln dex=0)if(hfmNodei.weight<

11、;w1)w1=hfmNodei.weight;nodeOn e=i;for(i nt j=0;j<=pos;j+)if(hfmNodej.p nIn dex=O)if(hfmNodej.weight<w2&&no de On e!=j) w2=hfmNodej.weight;no deTwo=j;II創(chuàng)建哈夫曼樹,nvalue是結點值，w是權值，n是葉子結點的個數(shù)void huffma nTree:creatHfmTree(char n value,i nt w,i nt n)int pos;for(pos=1;pos<=n; pos+)hfmNodepos.

12、 nValue=nvaluepos-1;結點值hfmNodepos.weight=wpos-1;II 權值 hfmNodepos.p nln dex=hfmNodepos.lchildI ndex=hfmNodepos.rchildl ndex=0;II設置數(shù)組hfmNode中的其他結點for(pos=n+1;pos<=2* n_1;pos+)int nodeOne,no deTwo;select(pos-1, nodeOne,no deTwo);hfmNode nodeOn e.p nln dex=hfmNode no deTwo.p nln dex=pos;把 hfmNode n o

13、de On e和hfmNode no deTwo兩個結點加入哈夫曼樹,設置他們的父結點位置為poshfmNodepos.lchildl ndex =nodeOne;設置pos結點的左孩子為nodeOnehfmNodepos.rchildI ndex=no deTwo;/設置pos結點的右孩子為no deTwohfmNodepos.weight=hfmNode nodeOn e.weight+hfmNode no deTwo.weight;設置 pos結點的權值為左右孩子權值的和/pos父結點為0hfmNodepos.p nln dex=0;/求哈夫曼樹的編碼nvalue是結點值數(shù)組，w是權值數(shù)

14、組n是葉子結點的個數(shù)void huffma nTree:code(char n value,i nt w,i nt n)creatHfmTree( nvalue,w, n);int i,j,c,f;int start;char *cd;cd=new char n;/用于存儲哈夫曼編碼的動態(tài)空間cd n-1='0'編碼結束符cout<<"結點值編碼"<<e ndl;for(i=1;i<=n;i+)逐個字符求哈夫曼編碼start=n-1;/編碼結束符位置從葉子到根逆向求編碼for(c=i,f=hfmNodei.p nlndex; f

15、!=0;c=f,f=hfmNodef.p nln dex)/ if(hfmNodef.lchildI ndex=c)cd-start='0'elsecd-start='1'cout<<""<< nvaluei-1<<"for( j=start;j<n;j+)cout<<cdj;cout<<e ndl;delete cd;/ 釋放空間III哈夫曼譯碼nvalue為結點值數(shù)組 hfmcode為哈夫曼編碼，n個葉子結點void huffma nTree:decode(cha

16、r n value,char hfmcode,i nt n)int i,f;char c;for(i=0;i<strle n(hfmcode);)/從根節(jié)點往下走的葉子結點/左0右1for(f=2* n-1;hfmNodef.lchildl ndex!=0&&hfmNodef.rchildl ndex!=0;)c=hfmcodei;if(c='1')f=hfmNodef.rchildI ndex;i+;elsef=hfmNodef.lchildI ndex;i+;輸出找到的葉子結點cout<<hfmNodef. nValue;/cout<

17、<e ndl;換行/檢查輸入的字符值是否合法bool isChar(c onst stri ng& str)int i ;for(i = 0; i != str.length(); i+)if(!isdigit(stri)con ti nue;elsereturn false;return true;/OUTPUT*OUTPUT output*void huffma nTree:Output(huffma nTree ht,i nt n)/輸出哈夫曼樹, cout<<"哈夫曼樹儲存結構模擬："<<endl;cout<<&qu

18、ot;hfmNodeweight pnln dexIchildl ndexrchildl ndex"<<e ndl;for(i nt i=1;i<=2* n-1;i+)/ cout<<i<<" "<<hfmNodei.weight<<""<<hfmNodei.p nln dex<<""<<hfmNodeichildl ndex<<""<<hfmNodei.rchildl ndex&

19、lt;<e ndl;prin tf("%4d%12d%10d%14d%16dn",i,hfmNodei.weight,hfmNodei.p nln dex,hfmNodei.lchildl ndex,hfmNodei.rchildI ndex);* jMain */*/void mai n()/ int i=1;/ while(i=1)cout<<" "<<e ndl;cout<<"*豐構造哈夫曼刊扌*"<<cndlint n=5;/字符和權值個數(shù)cout<<"

20、;請輸入字符集大小n : "<<endl;cin»n;char str' n'/str n-1='0：char g;char str22000; 存儲哈夫曼編碼int w26;huffma nTree obj;cout<<"請輸入"<<n<<"個字符值："<<endl<<endl; cin> >str;/輸入字符不合法while(isChar(str)=O|strle n( str)!=n)cout<<e ndl;c

21、out<<"輸入錯誤，請重新輸入"<<endl; cin> >str;/ Output();/int n=strle n(str);cout<<e ndl;gocd:cout<<"輸入對應權值:"<<endl;for(i nt i=0;i< n; i+)cin> >wi;cout<<e ndl;int m;while(1)cout<<"請選擇輸入 0或1: "<<endl;cout<<"*

22、0、模擬輸出哈夫曼樹*"<<endl;cout<<"*1、進行編碼 *y<endl；cout<<"*2cin»m;switch(m)case 0:obj.creatHfmTree(str,w, n);obj.Output(obj, n); /OUTputcout<<e ndl;break;case 1:cout<<"各節(jié)點編碼如下："<<endl;obj.code(str,w ,n);cout<<e ndl;break;case 2: break

23、;default:cout<<" 很抱歉，輸入錯誤！請重新輸入:"<<endl;if(m=2)break;godc:cout<<e ndl<<"請輸入要譯碼的二進制0、1 串："<<e ndl<<e ndl;cin> >str2;cout<<e ndl;cout<<"譯碼結果如下："<<endl<<endl;obj.decode(str,str2 ,n);cout<<e ndl;cout<

24、;<e ndl;cout<<"是否繼續(xù)譯碼(Y/N)?"<<endl;getchar();g=getchar();if(g='Y')goto godc;/ 繼續(xù)譯碼cout<<"是否繼續(xù)編碼(Y/N)?"<<endl;getchar();g=getchar();if(g='Y')goto gocd;/ 繼續(xù)編碼四設計與調試分析從上面的程序可以看出 ，有些地方時沒有辦法限制的，比如說輸入整型變量的時候，沒有辦法限制其不能輸入字符型。在調試的過程中所遇到的問題很多。五用戶手冊1本程序可以在 VC+5.0和VC+6.0 的環(huán)境下運行。2在vc中創(chuàng)建一個工程，將源程序復制到.cpp中，編譯鏈接就可以3選擇編譯、運行以后會出現(xiàn)運行界面，選擇相應的選項，根據(jù)提示即可進行演示。界面如下：4、請如數(shù)字符集大小n,就是要求用戶輸入哈夫曼樹葉子結點的個數(shù)六測試成果*FzlyDocStudyc+HAFu>anDebughaLfiiBaiL-1 exe->拮輸入字符集大小n：情輸入&個字符值:abcdef g腳入錯誤，請重新輸入abcdef輸入對應權值:S7536睛選擇輸入?yún)位?;林二0、槿擬龜出哈夫曼