數據結構實驗報告 實驗五

一.實驗內容：

實現哈夫曼編碼的生成算法。

二.實驗目的：

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

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

三.問題描述：

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

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

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

四.問題的實現

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

typedef struct{

unsigned int weight;

unsigned int parent,lchild,rchild;

}HTNode,*HuffmanTree; //動態分配數組存儲郝夫曼樹

郝夫曼編碼的存儲表示

typedef char* *HuffmanCode;//動態分配數組存儲郝夫曼編碼

(2)主要的實現思路：

a.首先定義郝夫曼樹的存儲形式，這裏使用了數組

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

c.構造郝夫曼樹HT，並求出n個字符的郝夫曼編碼HC

總結

1.基本上沒有什麼太大的問題，在調用select()這個函數時，想把權值最小的'兩個結點的序號帶回HuffmanCoding()，所以把那2個序號設置成了引用。

2.在編程過程中，在什麼時候分配內存，什麼時候初始化花的時間比較長

3.最後基本上實現後，發現結果仍然存在問題，經過分步調試，發現了特別低級的輸入錯誤。把HT[i]ht=HT[s1]ht+HT[s2]ht;中的s2寫成了i

附：

//動態分配數組存儲郝夫曼樹

typedef struct{

int weight; //字符的權值

int parent,lchild,rchild;

}HTNode,*HuffmanTree;

//動態分配數組存儲郝夫曼編碼

typedef char* *HuffmanCode;

//選擇n個(這裏是k=n)節點中權值最小的兩個結點

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

{ int i;

i=1;

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

//下面選出權值最小的結點，用s1指向其序號

s1=i;

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

{

if(HT[i]nt==0&&HT[i]ht

}

//下面選出權值次小的結點，用s2指向其序號

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

{

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

}

s2=i;

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

{

if(HT[i]nt==0&&i!=s1&&HT[i]ht

}

}

//構造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個結點

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0號單元未用，預分配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); //選出當前權值最小的

HT[s1]nt=i;

HT[s2]nt=i;

HT[i]ld=s1;

HT[i]ld=s2;

HT[i]ht=HT[s1]ht+HT[s2]ht;

}

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

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

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

cd[n-1]='';//編碼結束符

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

{

start=n-1; //編碼結束符位置

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

{

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

else

cd[--start]='1';

}

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

strcpy(HC[i],&cd[start]);//從cd複製編碼到HC

}

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

}

void main()

{ int n,i;

int* w; //記錄權值

char* ch; //記錄字符

HuffmanTree HT;

HuffmanCode HC;

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

cin>>n;

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

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

cout<<"依次輸入待編碼的字符data及其權值weight"<

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

{

cout<<"data["<

}