哈夫曼樹課程設(shè)計

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

2、化學(xué)生的理論知識，提高編程水平，并在此過程中培養(yǎng)他們嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度和良好的工作作風(fēng)。2課程設(shè)計任務(wù)與要求：任務(wù). 哈夫曼樹應(yīng)用功能： (1) 從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹并將它存于文件hfmTree中.將已在內(nèi)存中的哈夫曼樹以直觀的方式（比如樹）顯示在終端上；(2) 利用已經(jīng)建好的哈夫曼樹（如不在內(nèi)存，則從文件htmTree中讀入），對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件Cod eFile中，并輸出結(jié)果，將文件CodeFile以緊湊格式先是在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrint中。(3) 利用已建好的哈

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

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

5、輸出。這里基本是自學(xué)的內(nèi)容，而且要考慮到是否要自行選擇保存的磁盤。綜上，做這個課題，要具備的知識就是線性表的基本算法，文件的保存和讀取算法，必要的C或者C+知識（本次我將使用C實現(xiàn)），以及豐富的程序調(diào)適經(jīng)驗。二 概要設(shè)計程序流程圖 圖 1三 詳細(xì)設(shè)計1、哈夫曼樹結(jié)點結(jié)構(gòu)定義struct hfmnode char nValue;/節(jié)點值 int weight;/權(quán)值 int pnIndex;/父結(jié)點下標(biāo) int lchildIndex,rchildIndex;/左右孩子的結(jié)點下標(biāo);哈夫曼樹類定義class huffmanTreepublic:void code(char nvalue,int w

6、,int n); /對葉子結(jié)點編碼void decode(char nvalue,char hfmcode,int n);/對葉子結(jié)點譯碼void Output(huffmanTree ht,int n);/輸出哈夫曼樹/private:hfmnode hfmNode2000;/用數(shù)組存儲哈夫曼結(jié)點void creatHfmTree(char nvalue,int w,int n);/創(chuàng)建哈夫曼樹void select(int pos,int &nodeOne,int &nodeTwo);/查詢最小的兩個結(jié)點;2、主要函數(shù)及相關(guān)功能 1 在數(shù)組hfmNode中從O開始到pos位

7、置，查找哈夫曼樹外的權(quán)值最小的兩個結(jié)點的位置void huffmanTree:select(int pos,int &nodeOne,int &nodeTwo)2 創(chuàng)建哈夫曼樹，nvalue是結(jié)點值，w是權(quán)值，n是葉子結(jié)點的個數(shù)void huffmanTree:creatHfmTree(char nvalue,int w,int n)3 求哈夫曼樹的編碼 nvalue是結(jié)點值數(shù)組，w是權(quán)值數(shù)組 n是葉子結(jié)點的個數(shù)void huffmanTree:code(char nvalue,int w,int n)4 哈夫曼譯碼 nvalue為結(jié)點值數(shù)組 hfmcode為哈夫曼編碼，n個葉

8、子結(jié)點void huffmanTree:decode(char nvalue,char hfmcode,int n)5 檢查輸入的字符值是否合法bool isChar(const string& str)6 輸出哈夫曼樹，字符，權(quán)值，以及它對應(yīng)的編碼void huffmanTree:Output(huffmanTree ht,int n)3、源程序#include<iostream>using namespace std;struct hfmnode/哈夫曼樹結(jié)點結(jié)構(gòu)定義char nValue;/節(jié)點值int weight;/權(quán)值int pnIndex;/父結(jié)點下標(biāo)int

9、lchildIndex,rchildIndex;/左右孩子的結(jié)點下標(biāo);class huffmanTree/哈夫曼樹類定義public:void code(char nvalue,int w,int n); /對葉子結(jié)點編碼void decode(char nvalue,char hfmcode,int n);/對葉子結(jié)點譯碼void Output(huffmanTree ht,int n);/輸出哈夫曼樹/private:hfmnode hfmNode2000;/用數(shù)組存儲哈夫曼結(jié)點void creatHfmTree(char nvalue,int w,int n);/創(chuàng)建哈夫曼樹void s

10、elect(int pos,int &nodeOne,int &nodeTwo);/查詢最小的兩個結(jié)點;/在數(shù)組hfmNode中從O開始到pos位置，查找哈夫曼樹外的權(quán)值最小的兩個結(jié)點的位置void huffmanTree:select(int pos,int &nodeOne,int &nodeTwo)long w1,w2;w1=w2=88888;for(int i=0;i<=pos;i+)if(hfmNodei.pnIndex=0)if(hfmNodei.weight<w1)w1=hfmNodei.weight;nodeOne=i;for(int

11、 j=0;j<=pos;j+)if(hfmNodej.pnIndex=0)if(hfmNodej.weight<w2&&nodeOne!=j)w2=hfmNodej.weight;nodeTwo=j;/創(chuàng)建哈夫曼樹，nvalue是結(jié)點值，w是權(quán)值，n是葉子結(jié)點的個數(shù)void huffmanTree:creatHfmTree(char nvalue,int w,int n)int pos;for(pos=1;pos<=n;pos+)hfmNodepos.nValue=nvaluepos-1;/結(jié)點值hfmNodepos.weight=wpos-1;/權(quán)值hfmN

12、odepos.pnIndex=hfmNodepos.lchildIndex=hfmNodepos.rchildIndex=0;/設(shè)置數(shù)組hfmNode中的其他結(jié)點for(pos=n+1;pos<=2*n-1;pos+)int nodeOne,nodeTwo;select(pos-1,nodeOne,nodeTwo);hfmNodenodeOne.pnIndex=hfmNodenodeTwo.pnIndex=pos;/把hfmNodenodeOne和hfmNodenodeTwo兩個結(jié)點加入哈夫曼樹，設(shè)置他們的父結(jié)點位置為poshfmNodepos.lchildIndex=nodeOne;/

13、設(shè)置pos結(jié)點的左孩子為nodeOnehfmNodepos.rchildIndex=nodeTwo;/設(shè)置pos結(jié)點的右孩子為nodeTwohfmNodepos.weight=hfmNodenodeOne.weight+hfmNodenodeTwo.weight;/設(shè)置pos結(jié)點的權(quán)值為左右孩子權(quán)值的和hfmNodepos.pnIndex=0; /pos父結(jié)點為0/求哈夫曼樹的編碼 nvalue是結(jié)點值數(shù)組，w是權(quán)值數(shù)組 n是葉子結(jié)點的個數(shù)void huffmanTree:code(char nvalue,int w,int n)creatHfmTree(nvalue,w,n);int i,j

14、,c,f;int start;char *cd;cd=new charn;/用于存儲哈夫曼編碼的動態(tài)空間cdn-1='0'/編碼結(jié)束符cout<<" 結(jié)點值 編碼"<<endl;for(i=1;i<=n;i+)/逐個字符求哈夫曼編碼start=n-1; /編碼結(jié)束符位置for(c=i,f=hfmNodei.pnIndex;f!=0;c=f,f=hfmNodef.pnIndex)/從葉子到根逆向求編碼if(hfmNodef.lchildIndex=c)cd-start='0'elsecd-start='1&

15、#39;cout<<" "<<nvaluei-1<<" "for(j=start;j<n;j+)cout<<cdj;cout<<endl;delete cd;/釋放空間/哈夫曼譯碼 nvalue為結(jié)點值數(shù)組 hfmcode為哈夫曼編碼，n個葉子結(jié)點void huffmanTree:decode(char nvalue,char hfmcode,int n)int i,f;char c;for(i=0;i<strlen(hfmcode);)/從根節(jié)點往下走的葉子結(jié)點/左0右1for(f

16、=2*n-1;hfmNodef.lchildIndex!=0&&hfmNodef.rchildIndex!=0;)c=hfmcodei;if(c='1')f=hfmNodef.rchildIndex;i+;elsef=hfmNodef.lchildIndex;i+;cout<<hfmNodef.nValue;/輸出找到的葉子結(jié)點cout<<endl;/換行/檢查輸入的字符值是否合法bool isChar(const string& str) int i ; for(i = 0; i != str.length(); i+) if(

17、!isdigit(stri) continue; elsereturn false; return true;/OUTPUT *OUTPUT output*void huffmanTree:Output(huffmanTree ht,int n)/輸出哈夫曼樹，cout<<"哈夫曼樹儲存結(jié)構(gòu)模擬："<<endl;cout<<"hfmNode weight pnIndex lchildIndex rchildIndex"<<endl; for(int i=1;i<=2*n-1;i+)/cout<&

18、lt;i<<" "<<hfmNodei.weight<<" "<<hfmNodei.pnIndex<<" "<<hfmNodei.lchildIndex<<" "<<hfmNodei.rchildIndex<<endl;printf("%4d%12d%10d%14d%16dn",i,hfmNodei.weight,hfmNodei.pnIndex,hfmNodei.lchildIndex,

19、hfmNodei.rchildIndex);/*-Main-*/*-=*/void main() /int i=1;/while(i=1)cout<<" "<<endl;cout<<" *-構(gòu)造哈夫曼樹-*"<<endl;int n=5;/字符和權(quán)值個數(shù)cout<<"請輸入字符集大小n："<<endl;cin>>n;char str'n' /strn-1='0'char g;char str22000;/存儲哈夫曼編碼i

20、nt w26;huffmanTree obj; cout<<"請輸入"<<n<<"個字符值："<<endl<<endl;cin>>str;/輸入字符不合法while(isChar(str)=0|strlen(str)!=n)cout<<endl;cout<<"輸入錯誤，請重新輸入"<<endl;cin>>str;/Output();/int n=strlen(str);cout<<endl;gocd:co

21、ut<<"輸入對應(yīng)權(quán)值："<<endl;for(int i=0;i<n;i+)cin>>wi;cout<<endl;int m;while(1)cout<<"請選擇輸入0或1："<<endl;cout<<"*0、模擬輸出哈夫曼樹*"<<endl;cout<<"*1、進(jìn)行編碼*"<<endl;cout<<"*2、進(jìn)行譯碼*"<<endl;cin>

22、;>m;switch(m)case 0:obj.creatHfmTree(str,w,n);obj.Output(obj,n);/OUTputcout<<endl;break;case 1:cout<<"各節(jié)點編碼如下："<<endl;obj.code(str,w,n);cout<<endl;break;case 2: break;default:cout<<"很抱歉，輸入錯誤！請重新輸入："<<endl;if(m=2)break; godc:cout<<endl<<"請輸入要譯碼的二進(jìn)制0、1串："<<endl<<endl;cin>>st