數(shù)據(jù)結構課程設計-哈夫曼樹(共14頁)

1、精選優(yōu)質文檔-傾情為你奉上成績評定教師簽名嘉應學院 計算機學院實驗報告課程名稱：數(shù)據(jù)結構課程設計開課學期：2017-2018學年第2學期班 級：指導老師：實驗題目：哈夫曼樹學 號：姓 名：上機時間：一、實驗目的本實驗的目的是通過對簡單的哈夫曼編/譯碼系統(tǒng)的設計與實現(xiàn)來熟練掌握樹形結構在實際問題中的應用。二、實驗問題描述利用哈夫曼編碼進行通信可以大大提高通信利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼，此試驗即設計這樣的一個簡單的編/譯碼系統(tǒng)。系統(tǒng)應該具備如下的幾個功能。1、求出各個葉子節(jié)點的權重值輸入一個字符串，統(tǒng)

2、計其中各個字母的個數(shù)和總的字母個數(shù)。2、構造哈夫曼樹統(tǒng)計出的字母種類為葉子結點個數(shù)，每個字母個數(shù)為相應的權值，建立哈夫曼樹。3、打印哈弗曼樹的功能模塊 按照一定形式打印出哈夫曼樹。4、編碼利用已經建立好的哈夫曼樹進行編碼。5、譯碼根據(jù)編碼規(guī)則對輸入的代碼進行翻譯并將譯碼。三、實驗步驟1、實驗問題分析（1） 設計一個結構體數(shù)組保存字母的類型和個數(shù)。typedef structchar ch; /字母的種類int num; /字母的個數(shù)inf;（2） 在構造哈夫曼樹時，設計一個結構體數(shù)組Hufftree保存哈夫曼樹中各結 點的信息，根據(jù)二叉樹的性質可知，具有n個結點的哈夫曼樹共有2n-1個結 點，

3、所以數(shù)組大小設置為2n-1,描述結點的數(shù)據(jù)類型為：typedef structint weight;/權值int parent; /雙親int lchild; /左孩子int rchild; /右孩子Hnodetype;typedef Hnodetype Hufftreemaxnode;/定義此類型的數(shù)組（3） 求哈夫曼編碼，實質上是在已經建立的哈夫曼樹中，從葉子結點開始， 沿著結點的雙親鏈表域退回到根節(jié)點，每退回一步，就走過了哈夫曼樹的一個分支，從而得到一位哈夫曼值，由于一個字符的哈夫曼編碼是從根結點所經過的路徑上各分支所組成的0、1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支

4、代碼為所求編碼的高位碼，所以設計如下的數(shù)據(jù)類型：const int maxbit=10;typedef struct int bitmaxbit; /每個結點的哈夫曼編碼 int start; /開始位置Hcodetype;（4） 設置全局變量。string s; /s為輸入的字符串int n=0; /記錄輸入的字符串中字母的種類，即葉子結點個數(shù)int v=0; /記錄字符串中字母的總個數(shù)inf infomaxleaf;/葉子結點類型2、 功能（函數(shù)）設計（1） 統(tǒng)計字母種類和個數(shù)模塊此模塊的功能為從鍵盤接受一個字符串，統(tǒng)計字符串中字母種類即結點個數(shù)，每種字母出現(xiàn)次數(shù)即各葉子結點的權值。全局變

5、量s保存輸入的字符串，將種類和個數(shù)保存到infomaxleaf中。函數(shù)原型：void fundchar（）如輸入的字符串是“sddfffgggg”則顯示如下。（2） 哈夫曼樹的建立模塊此模塊的功能為從（1）中計算出的結點個數(shù)和各個葉子結點的權值構造一棵哈弗曼樹。函數(shù)原型：Hnodetype* huffmantree()/函數(shù)返回結點類型的數(shù)組（3） 打印哈弗曼樹的功能模塊此模塊的功能是將由(2)建立的哈弗曼樹按照一定規(guī)則<weight,lchild,rchild,parent>打印在屏幕上。函數(shù)原型：void print(Hnodetype *hufftree) 如輸入的字符串是”

6、sddfffgggg”，則構造的哈夫曼樹為（4） 建立哈夫曼編碼的功能模塊此模塊功能為將（2）中建立的哈夫曼樹進行哈弗曼編碼，然后將字符與對應的0、1代碼串打印到屏幕上。函數(shù)原型：void huffmancode(Hnodetype *hufftree)如輸入的字符串是“sddfffgggg”，則每個字母的代碼和輸入的字符串的哈夫曼編碼是（5） 譯碼的功能模塊此模塊的功能為接收需要譯碼的0和1代碼串，按照（4）中建立的編碼規(guī)則將其翻譯成字符集中字符所組成的字符串形式，并將翻譯的結果在屏幕上打印出來。函數(shù)原型：void translation(Hnodetype *hufftree)如輸入的代碼

7、串是“”，則對應的字符串是“sdfg”四、實驗結果（程序）及分析1、實驗主要模塊代碼(一) 函數(shù)功能：統(tǒng)計字母種類和個數(shù)模塊void fundchar()int k,m; cout<<"請輸入字符串"<<endl;cin>>s; /s為輸入的字符串while(sv)v+;cout<<"共有字符"<<v<<"個"<<endl; / v是全局變量 info0.ch=s0;info0.num=1; for(k=1;k<=v;k+) /統(tǒng)計s中字母種類和

8、個數(shù)for(m=0;m<=n;m+)if(infom.ch=sk)+infom.num;break;if(m>n)info+n.ch=sk;infon.num=1; for(m=0;m<n;m+) /輸出種類和個數(shù)cout<<"字符"<<infom.ch<<"有"<<infom.num<<"個"<<endl;(二) 函數(shù)功能:哈弗曼樹的建立模塊Hnodetype* huffmantree() Hnodetype *hufftree=new Huf

9、ftree; int i,j,m1,m2,x1,x2;/m1記錄最小的重權值，m2為次小 for(i=0;i<2*n-1;i+) /結點初始化 hufftreei.parent=-1; hufftreei.weight=0; hufftreei.lchild=-1; hufftreei.rchild=-1; for(i=0;i<n;i+) /將每個字母的個數(shù)當做葉子結點的權值 hufftreei.weight=infoi.num; for(i=0;i<n-1;i+) m1=m2=maxvalue; x1=x2=0; for(j=0;j<n+i;j+) if(hufftr

10、eej.parent=-1 && hufftreej.weight<m1) m2=m1; x2=x1; m1=hufftreej.weight; x1=j;/x1記錄最小重權值在數(shù)組中的下標 else if(hufftreej.parent=-1 && hufftreej.weight<m2) m2=hufftreej.weight; x2=j;/x2記錄次小重權值在數(shù)組中的下標 hufftreex1.parent=n+i; hufftreex2.parent=n+i; hufftreen+i.weight=m1+m2; hufftreen+i.lc

11、hild=x1; hufftreen+i.rchild=x2; return hufftree;/返回數(shù)組首地址(三) 函數(shù)功能：打印哈弗曼樹的功能模塊void print(Hnodetype *hufftree) cout<<endl<<endl<<endl; /界面優(yōu)化 cout<<"哈弗曼樹-"<<endl; cout<<" "<<"weight"<<" "<<"lchild"<

12、;<" "<<"rchild"<<" "<<"parent"<<endl;/界面優(yōu)化 for(int i=0;i<2*n-1;i+)cout<<" "<<hufftreei.weight<<" "<<hufftreei.lchild<<" "<<hufftreei.rchild<<" "<

13、<hufftreei.parent<<endl;(四) 函數(shù)功能：建立哈弗曼編碼的功能模塊void huffmancode(Hnodetype *hufftree) Hcodetype huffcodemaxleaf,cd; int i,j,c,p; for(i=0;i<n;i+)/求每個結點的哈弗曼編碼 cd.start=n-1; c=i; p=hufftreec.parent; while(p!=-1)/由葉子結點向上直到樹根 if(hufftreep.lchild=c) cd.bitcd.start=0; else cd.bitcd.start=1; cd.sta

14、rt-; c=p; p=hufftreec.parent; for(j=cd.start+1;j<n;j+) /將結果保存 huffcodei.bitj=cd.bitj;/保存每位號碼 huffcodei.start=cd.start; /保存開始位置 cout<<endl<<endl<<endl; cout<<"哈弗曼編碼"<<endl; for(i=0;i<n;i+) /打印各個字母對應的編碼 cout<<"-"<<endl; cout<<in

15、foi.ch<<"的代碼是" for(j=huffcodei.start+1;j<n;j+) cout<<huffcodei.bitj; cout<<endl; cout<<"-"<<endl; cout<<endl<<"輸入的字符串的哈夫曼編碼為："<<endl; for(i=0;i<v;i+)/打印輸入的字符串的編碼結果 for(int y=0;y<=n;y+) if(si=infoy.ch) for(j= huffc

16、odey.start+1;j<n;j+) cout<<huffcodey.bitj; cout<<endl;(五) 函數(shù)功能：譯碼的功能模塊void translation(Hnodetype *hufftree) string code; /code記錄輸入的0，1代碼 int t; cout<<endl<<endl<<endl; cout<<"請輸入代碼串:" cin>>code; int num=0; while(codenum) num+; /確定0，1代碼長度 Hnodety

17、pe *p=&hufftree2*n-2; cout<<endl<<endl<<endl; cout<<"譯碼結果-"<<endl; for(int i=0;i<num;i+)if(codei='0') /從根向下 p=&hufftreep->lchild; else p=&hufftreep->rchild; if(p->lchild=-1 && p->rchild=-1) /如果到達葉子結點 t=p->weight; /

18、保存葉子結點的權值 for(int j=0;j<n;j+)if(hufftreej.weight=t) cout<<infoj.ch; /輸出權值的對應的字母 break; p=&hufftree2*n-2; /重新從根節(jié)點開始 cout<<endl;2、測試數(shù)據(jù) sfddaaassss實驗結果截圖3、 調試過程中出現(xiàn)的問題以及解決策略譯碼模塊中，如果輸入的代碼串無對應的字母，則會出錯。解決辦法：提示用戶輸入時注意附最終代碼：#include<iostream>#include<string>#define maxvalue 12#

19、define maxleaf 12#define maxnode 23using namespace std;int n=0;int v=0;string s;typedef structchar ch;int num;inf;inf info12;typedef struct int weight;/權值 int parent; int lchild; int rchild;Hnodetype;typedef Hnodetype Hufftreemaxnode;/-const int maxbit=10;typedef struct int bitmaxbit; int start;Hcod

20、etype;void fundchar()int k,m; cout<<"請輸入字符串"<<endl;cin>>s;while(sv)v+;cout<<"共有字符"<<v<<"個"<<endl; info0.ch=s0;info0.num=1; for(k=1;k<=v;k+)for(m=0;m<=n;m+)if(infom.ch=sk)+infom.num;break;if(m>n)info+n.ch=sk;infon.num=1;

21、 for(m=0;m<n;m+)cout<<"字符"<<infom.ch<<"有"<<infom.num<<"個"<<endl;Hnodetype* huffmantree() Hnodetype *hufftree=new Hufftree; int i,j,m1,m2,x1,x2;/m1記錄最小的重權值，m2為次小 for(i=0;i<2*n-1;i+) /結點初始化 hufftreei.parent=-1; hufftreei.weight=0;

22、 hufftreei.lchild=-1; hufftreei.rchild=-1; for(i=0;i<n;i+) /將每個字母的個數(shù)當做葉子結點的權值 hufftreei.weight=infoi.num; for(i=0;i<n-1;i+) m1=m2=maxvalue; x1=x2=0; for(j=0;j<n+i;j+) if(hufftreej.parent=-1 && hufftreej.weight<m1) m2=m1; x2=x1; m1=hufftreej.weight; x1=j;/x1記錄最小重權值在數(shù)組中的下標 else if(

23、hufftreej.parent=-1 && hufftreej.weight<m2) m2=hufftreej.weight; x2=j;/x2記錄次小重權值在數(shù)組中的下標 hufftreex1.parent=n+i; hufftreex2.parent=n+i; hufftreen+i.weight=m1+m2; hufftreen+i.lchild=x1; hufftreen+i.rchild=x2; return hufftree;/返回數(shù)組首地址void huffmancode(Hnodetype *hufftree) Hcodetype huffcodemax

24、leaf,cd; int i,j,c,p; for(i=0;i<n;i+)/求每個結點的哈弗曼編碼 cd.start=n-1; c=i; p=hufftreec.parent; while(p!=-1)/由葉子結點向上直到樹根 if(hufftreep.lchild=c) cd.bitcd.start=0; else cd.bitcd.start=1; cd.start-; c=p; p=hufftreec.parent; for(j=cd.start+1;j<n;j+) /將結果保存 huffcodei.bitj=cd.bitj;/保存每位號碼 huffcodei.start=c

25、d.start; /保存開始位置 cout<<endl<<endl<<endl; cout<<"哈弗曼編碼"<<endl; for(i=0;i<n;i+) /打印各個字母對應的編碼 cout<<"-"<<endl; cout<<infoi.ch<<"的代碼是" for(j=huffcodei.start+1;j<n;j+) cout<<huffcodei.bitj; cout<<endl; c

26、out<<"-"<<endl; cout<<endl<<"輸入的字符串的哈夫曼編碼為："<<endl; for(i=0;i<v;i+)/打印輸入的字符串的編碼結果 for(int y=0;y<=n;y+) if(si=infoy.ch) for(j= huffcodey.start+1;j<n;j+) cout<<huffcodey.bitj; cout<<endl;void print(Hnodetype *hufftree) cout<<

27、endl<<endl<<endl; cout<<"哈弗曼樹-"<<endl; cout<<" "<<"weight"<<" "<<"lchild"<<" "<<"rchild"<<" "<<"parent"<<endl;/界面優(yōu)化 for(int i=0;i<2*n-1;i+)cout<<" "<<hufftreei.weight<<" "<<huff