第一篇：數(shù)據(jù)結(jié)構(gòu)實驗六報告

實驗六報告

課程名稱： 數(shù)據(jù)結(jié)構(gòu) 實驗名稱：二叉樹的應(yīng)用

實驗日期

2011/11/23

一、實驗?zāi)康模?/p>

掌握赫夫曼二叉樹的建立及赫夫曼編碼的生成。

二、實驗內(nèi)容與要求：

根據(jù)給定的n個權(quán)值生成赫夫曼二叉樹，輸出赫夫曼編碼。

三、數(shù)據(jù)結(jié)構(gòu)設(shè)計

順序表的存儲結(jié)構(gòu)，建立了二叉樹的關(guān)系

Struct HTNode{

int weight;

unsigned int parent,lchild,rchild;};

四、算法設(shè)計

1、從數(shù)據(jù)中選擇較小的兩個數(shù)據(jù)元素

void Select(HTNode *HT, const int n, int &a, int &b){ //選擇較小的兩個元素

} int x,y;

x=y=0x7fff;for(int j=0;j

if(HT[j].parent==0)

if(HT[j].weight

2、建立赫夫曼樹

void CreatHuff(HTNode *HT,int *p,const int n){

} int m=2*n-1;int i,a,b;for(i=0;i

Select(HT ,i,a,b);HT[a].parent=HT[b].parent=i;HT[i].weight=HT[a].weight+HT[b].weight;HT[i].lchild=a;HT[i].rchild=b;}

3、生成赫夫曼編碼

void HuffCoding(HTNode *HT, Huffcode &HC, const int n){

//

}HC=new

char*[n+1];

char *code=new char[n];code[n-1]='