1、使學(xué)生熟練掌握哈夫曼樹的生成算法。

2、熟練掌握哈夫曼編碼的方法。

三.問題描述：

已知n個字符在原文中出現(xiàn)的頻率，求它們的哈夫曼編碼。

1、讀入n個字符，以及字符的權(quán)值，試建立一棵Huffman樹。

2、根據(jù)生成的Huffman樹，求每個字符的Huffman編碼。并對給定的待編碼字符序列進行編碼，并輸出。

四.問題的實現(xiàn)

(1)郝夫曼樹的存儲表示

typedef struct{

unsigned int weight;

unsigned int parent,lchild,rchild;

}HTNode,*HuffmanTree; //動態(tài)分配數(shù)組存儲郝夫曼樹

郝夫曼編碼的存儲表示

typedef char* *HuffmanCode;//動態(tài)分配數(shù)組存儲郝夫曼編碼

(2)主要的實現(xiàn)思路：

a.首先定義郝夫曼樹的存儲形式，這里使用了數(shù)組

b.用select()遍歷n個字符，找出權(quán)值最小的兩個

c.構(gòu)造郝夫曼樹HT，并求出n個字符的郝夫曼編碼HC

總結(jié)

1.基本上沒有什么太大的問題，在調(diào)用select()這個函數(shù)時，想把權(quán)值最小的兩個結(jié)點的序號帶回HuffmanCoding()，所以把那2個序號設(shè)置成了引用。

2.在編程過程中，在什么時候分配內(nèi)存，什么時候初始化花的時間比較長

3.最后基本上實現(xiàn)后，發(fā)現(xiàn)結(jié)果仍然存在問題，經(jīng)過分步調(diào)試，發(fā)現(xiàn)了特別低級的輸入錯誤。把HT[i].weight=HT[s1].weight+HT[s2].weight;中的s2寫成了i

附：

//動態(tài)分配數(shù)組存儲郝夫曼樹

typedef struct{

int weight; //字符的權(quán)值

int parent,lchild,rchild;

}HTNode,*HuffmanTree;

//動態(tài)分配數(shù)組存儲郝夫曼編碼

typedef char* *HuffmanCode;

//選擇n個(這里是k=n)節(jié)點中權(quán)值最小的兩個結(jié)點

void Select(HuffmanTree &HT,int k,int &s1,int &s2)

{ int i;

i=1;

while(i<=k && HT[i].parent!=0)i++;

//下面選出權(quán)值最小的結(jié)點，用s1指向其序號

s1=i;

for(i=1;i<=k;i++)

{

if(HT[i].parent==0&&HT[i].weight

}

//下面選出權(quán)值次小的結(jié)點，用s2指向其序號

for(i=1;i<=k;i++)

{

if(HT[i].parent==0&&i!=s1)break;

}

s2=i;

for(i=1;i<=k;i++)

{

if(HT[i].parent==0&&i!=s1&&HT[i].weight

}

}

//構(gòu)造Huffman樹，求出n個字符的編碼

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)

{

int m,c,f,s1,s2,i,start;

char *cd;

if(n<=1)return;

m=2*n-1; //n個葉子n-1個結(jié)點

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0號單元未用，預(yù)分配m+1個單元

HuffmanTree p=HT+1;

w++; //w的號單元也沒有值，所以從號單元開始

for(i=1;i<=n;i++,p++,w++)

{

p->weight=*w;

p->parent=p->rchild=p->lchild=0;

}

for(;i<=m;++i,++p)

{

p->weight=p->parent=p->rchild=p->lchild=0;

}

for(i=n+1;i<=m;i++)

{

Select(HT,i-1,s1,s2); //選出當前權(quán)值最小的

HT[s1].parent=i;

HT[s2].parent=i;

HT[i].lchild=s1;

HT[i].rchild=s2;

HT[i].weight=HT[s1].weight+HT[s2].weight;

}

//從葉子到根逆向求每個字符的郝夫曼編碼

HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); //分配n個字符編碼的頭指針變量

cd=(char*)malloc(n*sizeof(char)); //分配求編碼的工作空間

cd[n-1]='';//編碼結(jié)束符

for(i=1;i<=n;i++) //逐個字符求郝夫曼編碼

{

start=n-1; //編碼結(jié)束符位置

for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) //從葉子到根逆向求編碼

{

if(HT[f].lchild==c)cd[--start]='0';

else

cd[--start]='1';

}

HC[i]=(char*)malloc((n-start)*sizeof(char)); //為第i個字符編碼分配空間

strcpy(HC[i],&cd[start]);//從cd復(fù)制編碼到HC

}

free(cd); //釋放工作空間

}

void main()

{ int n,i;

int* w; //記錄權(quán)值

char* ch; //記錄字符

HuffmanTree HT;

HuffmanCode HC;

cout<<"請輸入待編碼的字符個數(shù)n=";

cin>>n;

w=(int*)malloc((n+1)*sizeof(int)); //記錄權(quán)值，號單元未用

ch=(char*)malloc((n+1)*sizeof(char));//記錄字符，號單元未用

cout<<"依次輸入待編碼的字符data及其權(quán)值weight"<

for(i=1;i<=n;i++)

{

cout<<"data["<

}

【數(shù)據(jù)結(jié)構(gòu)實驗報告 實驗五】相關(guān)文章：

實驗報告實驗心得05-21

科技實驗報告05-26

化學(xué)實驗報告07-03

實驗報告總結(jié)02-14

生物實驗報告08-13

關(guān)于實驗報告01-27

化學(xué)實驗報告01-28

電路實驗報告11-09

實驗報告范文09-05

實驗室安全實驗報告04-26