1、成績(jī)?cè)u(píng)定教師簽名嘉應(yīng)學(xué)院 計(jì)算機(jī)學(xué)院實(shí)驗(yàn)報(bào)告課程名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)開(kāi)課學(xué)期：2017-2018學(xué)年第2學(xué)期班 級(jí)：指導(dǎo)老師：實(shí)驗(yàn)題目：哈夫曼樹(shù)學(xué) 號(hào)：姓 名：上機(jī)時(shí)間：一、實(shí)驗(yàn)?zāi)康谋緦?shí)驗(yàn)的目的是通過(guò)對(duì)簡(jiǎn)單的哈夫曼編/譯碼系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)來(lái)熟練掌握樹(shù)形結(jié)構(gòu)在實(shí)際問(wèn)題中的應(yīng)用。二、實(shí)驗(yàn)問(wèn)題描述利用哈夫曼編碼進(jìn)行通信可以大大提高通信利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼，此試驗(yàn)即設(shè)計(jì)這樣的一個(gè)簡(jiǎn)單的編/譯碼系統(tǒng)。系統(tǒng)應(yīng)該具備如下的幾個(gè)功能。1、求出各個(gè)葉子節(jié)點(diǎn)的權(quán)重值輸入一個(gè)字符串，統(tǒng)計(jì)其中各個(gè)字母的個(gè)數(shù)和總的

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

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

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

5、類和個(gè)數(shù)保存到infomaxleaf中。函數(shù)原型：void fundchar（）如輸入的字符串是“sddfffgggg”則顯示如下。（2） 哈夫曼樹(shù)的建立模塊此模塊的功能為從（1）中計(jì)算出的結(jié)點(diǎn)個(gè)數(shù)和各個(gè)葉子結(jié)點(diǎn)的權(quán)值構(gòu)造一棵哈弗曼樹(shù)。函數(shù)原型：Hnodetype* huffmantree()/函數(shù)返回結(jié)點(diǎn)類型的數(shù)組（3） 打印哈弗曼樹(shù)的功能模塊此模塊的功能是將由(2)建立的哈弗曼樹(shù)按照一定規(guī)則打印在屏幕上。函數(shù)原型：void print(Hnodetype *hufftree) 如輸入的字符串是”sddfffgggg”，則構(gòu)造的哈夫曼樹(shù)為（4） 建立哈夫曼編碼的功能模塊此模塊功能為將（2）中

6、建立的哈夫曼樹(shù)進(jìn)行哈弗曼編碼，然后將字符與對(duì)應(yīng)的0、1代碼串打印到屏幕上。函數(shù)原型：void huffmancode(Hnodetype *hufftree)如輸入的字符串是“sddfffgggg”，則每個(gè)字母的代碼和輸入的字符串的哈夫曼編碼是（5） 譯碼的功能模塊此模塊的功能為接收需要譯碼的0和1代碼串，按照（4）中建立的編碼規(guī)則將其翻譯成字符集中字符所組成的字符串形式，并將翻譯的結(jié)果在屏幕上打印出來(lái)。函數(shù)原型：void translation(Hnodetype *hufftree)如輸入的代碼串是“”，則對(duì)應(yīng)的字符串是“sdfg”四、實(shí)驗(yàn)結(jié)果（程序）及分析1、實(shí)驗(yàn)主要模塊代碼(一) 函數(shù)

7、功能：統(tǒng)計(jì)字母種類和個(gè)數(shù)模塊void fundchar()int k,m; cout請(qǐng)輸入字符串s; /s為輸入的字符串while(sv)v+;cout共有字符v個(gè)endl; / v是全局變量 info0.ch=s0;info0.num=1; for(k=1;k=v;k+) /統(tǒng)計(jì)s中字母種類和個(gè)數(shù)for(m=0;mn)info+n.ch=sk;infon.num=1; for(m=0;mn;m+) /輸出種類和個(gè)數(shù)cout字符infom.ch有infom.num個(gè)endl;(二) 函數(shù)功能:哈弗曼樹(shù)的建立模塊Hnodetype* huffmantree() Hnodetype *hufftr

8、ee=new Hufftree; int i,j,m1,m2,x1,x2;/m1記錄最小的重權(quán)值，m2為次小 for(i=0;i2*n-1;i+) /結(jié)點(diǎn)初始化 hufftreei.parent=-1; hufftreei.weight=0; hufftreei.lchild=-1; hufftreei.rchild=-1; for(i=0;in;i+) /將每個(gè)字母的個(gè)數(shù)當(dāng)做葉子結(jié)點(diǎn)的權(quán)值 hufftreei.weight=infoi.num; for(i=0;in-1;i+) m1=m2=maxvalue; x1=x2=0; for(j=0;jn+i;j+) if(hufftreej.pa

9、rent=-1 & hufftreej.weightm1) m2=m1; x2=x1; m1=hufftreej.weight; x1=j;/x1記錄最小重權(quán)值在數(shù)組中的下標(biāo) else if(hufftreej.parent=-1 & hufftreej.weightm2) m2=hufftreej.weight; x2=j;/x2記錄次小重權(quán)值在數(shù)組中的下標(biāo) hufftreex1.parent=n+i; hufftreex2.parent=n+i; hufftreen+i.weight=m1+m2; hufftreen+i.lchild=x1; hufftreen+i.rchild=x2;

10、return hufftree;/返回?cái)?shù)組首地址(三) 函數(shù)功能：打印哈弗曼樹(shù)的功能模塊void print(Hnodetype *hufftree) coutendlendlendl; /界面優(yōu)化 cout哈弗曼樹(shù)-endl; cout weight lchild rchild parentendl;/界面優(yōu)化 for(int i=0;i2*n-1;i+)cout hufftreei.weight hufftreei.lchild hufftreei.rchild hufftreei.parentendl;(四) 函數(shù)功能：建立哈弗曼編碼的功能模塊void huffmancode(Hnode

11、type *hufftree) Hcodetype huffcodemaxleaf,cd; int i,j,c,p; for(i=0;in;i+)/求每個(gè)結(jié)點(diǎn)的哈弗曼編碼 cd.start=n-1; c=i; p=hufftreec.parent; while(p!=-1)/由葉子結(jié)點(diǎn)向上直到樹(shù)根 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;jn;j+) /將結(jié)果保存 huffcodei.bitj=cd.b

12、itj;/保存每位號(hào)碼 huffcodei.start=cd.start; /保存開(kāi)始位置 coutendlendlendl; cout哈弗曼編碼endl; for(i=0;in;i+) /打印各個(gè)字母對(duì)應(yīng)的編碼 cout-endl; coutinfoi.ch的代碼是; for(j=huffcodei.start+1;jn;j+) couthuffcodei.bitj; coutendl; cout-endl; coutendl輸入的字符串的哈夫曼編碼為：endl; for(i=0;iv;i+)/打印輸入的字符串的編碼結(jié)果 for(int y=0;y=n;y+) if(si=infoy.ch)

13、 for(j= huffcodey.start+1;jn;j+) couthuffcodey.bitj; coutendl;(五) 函數(shù)功能：譯碼的功能模塊void translation(Hnodetype *hufftree) string code; /code記錄輸入的0，1代碼 int t; coutendlendlendl; coutcode; int num=0; while(codenum) num+; /確定0，1代碼長(zhǎng)度 Hnodetype *p=&hufftree2*n-2; coutendlendlendl; cout譯碼結(jié)果-endl; for(int i=0;ilc

14、hild; else p=&hufftreep-rchild; if(p-lchild=-1 & p-rchild=-1) /如果到達(dá)葉子結(jié)點(diǎn) t=p-weight; /保存葉子結(jié)點(diǎn)的權(quán)值 for(int j=0;jn;j+)if(hufftreej.weight=t) coutinfoj.ch; /輸出權(quán)值的對(duì)應(yīng)的字母 break; p=&hufftree2*n-2; /重新從根節(jié)點(diǎn)開(kāi)始 coutendl;2、測(cè)試數(shù)據(jù) sfddaaassss實(shí)驗(yàn)結(jié)果截圖3、 調(diào)試過(guò)程中出現(xiàn)的問(wèn)題以及解決策略譯碼模塊中，如果輸入的代碼串無(wú)對(duì)應(yīng)的字母，則會(huì)出錯(cuò)。解決辦法：提示用戶輸入時(shí)注意附最終代碼：#incl

15、ude#include#define maxvalue 12#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;/權(quán)值 int parent; int lchild; int rchild;Hnodetype;typedef Hnodetype Hufftreemaxnode;/-const int maxbit=10;typedef struc

16、t int bitmaxbit; int start;Hcodetype;void fundchar()int k,m; cout請(qǐng)輸入字符串s;while(sv)v+;cout共有字符v個(gè)endl; info0.ch=s0;info0.num=1; for(k=1;k=v;k+)for(m=0;mn)info+n.ch=sk;infon.num=1; for(m=0;mn;m+)cout字符infom.ch有infom.num個(gè)endl;Hnodetype* huffmantree() Hnodetype *hufftree=new Hufftree; int i,j,m1,m2,x1,x2

17、;/m1記錄最小的重權(quán)值，m2為次小 for(i=0;i2*n-1;i+) /結(jié)點(diǎn)初始化 hufftreei.parent=-1; hufftreei.weight=0; hufftreei.lchild=-1; hufftreei.rchild=-1; for(i=0;in;i+) /將每個(gè)字母的個(gè)數(shù)當(dāng)做葉子結(jié)點(diǎn)的權(quán)值 hufftreei.weight=infoi.num; for(i=0;in-1;i+) m1=m2=maxvalue; x1=x2=0; for(j=0;jn+i;j+) if(hufftreej.parent=-1 & hufftreej.weightm1) m2=m1;

18、 x2=x1; m1=hufftreej.weight; x1=j;/x1記錄最小重權(quán)值在數(shù)組中的下標(biāo) else if(hufftreej.parent=-1 & hufftreej.weightm2) m2=hufftreej.weight; x2=j;/x2記錄次小重權(quán)值在數(shù)組中的下標(biāo) hufftreex1.parent=n+i; hufftreex2.parent=n+i; hufftreen+i.weight=m1+m2; hufftreen+i.lchild=x1; hufftreen+i.rchild=x2; return hufftree;/返回?cái)?shù)組首地址void huffman

19、code(Hnodetype *hufftree) Hcodetype huffcodemaxleaf,cd; int i,j,c,p; for(i=0;in;i+)/求每個(gè)結(jié)點(diǎn)的哈弗曼編碼 cd.start=n-1; c=i; p=hufftreec.parent; while(p!=-1)/由葉子結(jié)點(diǎn)向上直到樹(shù)根 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;jn;j+) /將結(jié)果保存 huffcodei

20、.bitj=cd.bitj;/保存每位號(hào)碼 huffcodei.start=cd.start; /保存開(kāi)始位置 coutendlendlendl; cout哈弗曼編碼endl; for(i=0;in;i+) /打印各個(gè)字母對(duì)應(yīng)的編碼 cout-endl; coutinfoi.ch的代碼是; for(j=huffcodei.start+1;jn;j+) couthuffcodei.bitj; coutendl; cout-endl; coutendl輸入的字符串的哈夫曼編碼為：endl; for(i=0;iv;i+)/打印輸入的字符串的編碼結(jié)果 for(int y=0;y=n;y+) if(si=infoy.ch) for(j= huffcodey.start+1;jn;j+) couthuffcodey.bitj; coutendl;void print(Hnodetype *hufftree) coutendlendlendl; cout哈弗曼樹(shù)-endl; cout weig