實驗報告

一、實驗目的

掌握哈夫曼樹及其應用。

二、實驗內容

利用哈夫曼算法，構造最優二叉樹，然后對構造好的二叉樹的葉子結點進行前綴編碼。

三、實驗步驟

（1）審清題意，分析并理出解決問題的基本思路。（2）根據基本思路，設計好程序的算法。（3）根據算法編寫源程序。（4）在計算機上編譯程序，檢驗程序的可運行性

數據結構設計：

// 赫夫曼樹和赫夫曼編碼的存儲結構

typedef struct // 結點的結構，在教科書第147頁

{ unsigned int weight; // 結點的權值

unsigned int parent,lchild,rchild;

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

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

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int* w,int n) // 算法6.12

{ // w存放n個字符的權值(均>0)，構造赫夫曼樹HT，并求出n個字符的赫夫曼編碼HC int start;

unsigned f;

// 以下是從葉子到根逆向求每個字符的赫夫曼編碼

int m,i,s1,s2;

unsigned c;

HuffmanTree p;

char *cd;

if(n<=1) // 葉子結點數不大于n

return;

m=2*n-1; // n個葉子結點的赫夫曼樹共有m個結點

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0號單元未用

for(p=HT+1,i=1;i<=n;++i,++p,++w) // 從1號單元開始到n號單元，給葉子結點賦值{ // p的初值指向1號單元

(*p).weight=*w; // 賦權值

(*p).parent=0; // 雙親域為空(是根結點)

(*p).lchild=0; // 左右孩子為空(是葉子結點，即單結點樹)

(*p).rchild=0;