資料結構實驗報告

實驗名稱：哈夫曼樹以及哈夫曼編碼

專業：電腦科學與技術專業

班級：計科1001

姓名：念文洪

學號： 1008030129

完成日期： 2023年11月21日

一、問題描述

通過李占利老師對《資料結構與演算法》的講解,經過自身的學習以及多次上機實驗,掌握了關與哈夫曼樹的以下知識:

(1) 哈夫曼樹的基本概念以及所用儲存結構;

(2) 哈夫曼樹的建立演算法;

(3) 哈夫曼樹的應用(哈夫曼編碼和解碼).

2、需求分析

首先，應該建立哈夫曼樹，將哈夫曼樹的結構定義為乙個結構體型別的一維陣列，每個元素含有四項：權值、雙親、左孩子、右孩子。給定的權值可以從鍵盤上輸入，要輸出所建立的哈夫曼樹，只要輸出表示出哈夫曼樹的一維陣列中的全部元素即可。

然後，要實現哈夫曼編碼，只要在所建立的哈夫曼樹上進行二進位制編碼：往左走，編碼為0，往右走，編碼為1，然後將從根結點到葉結點的所有0、1排列起來，則得到該樹葉的哈夫曼編碼。哈夫曼編碼可以用乙個結構體型別的一維陣列來儲存，每個元素包含：

編碼、編碼的開始位置、編碼所對應的字元。

最後，實現哈夫曼解碼，就是要將輸入的編碼還原成對應的字元。

3、概要設計

1、建立哈夫曼樹的結構體型別。

2、建立哈夫曼編碼的結構體型別。

3、建立哈夫曼樹

4、哈夫曼編碼。

5、哈夫曼解碼

6、編寫程式，實現哈夫曼樹的建立以及應用。

四、詳細設計

1、建立哈夫曼樹的結構體型別：

struct tree //哈夫曼樹中的乙個節點

;2、建立哈夫曼編碼的結構體型別

struct codetype//哈夫曼編碼

;3、源程式**：

/* 功能：哈夫曼樹的建立以及應用

作者；念文洪

學院：電腦科學與技術學院

班級：計科1001班

學號：1008030129

#include <>

const int n=8maxn表示葉子數目

const int m=2*n-1;//m為森林中樹的棵樹

struct tree哈夫曼樹中的乙個節點

;struct codetype哈夫曼編碼

;tree hftree[m+1];

codetype code[n+1];

/* 建立哈夫曼樹

void creathuffmantree()

cout<<"請輸入"< for (i=1;i<=n;i++)

cin>>hftree[i].weight輸入權值

for (i=n+1;i<=m;i進行次合併

以下為合併

hftree[p1].parent=i;

hftree[p2].parent=i;

hftree[i].lch=p1;

hftree[i].rch=p2;

hftree[i].weight=hftree[p1].weight+hftree[p2].weight;

}}/* 哈夫曼編碼

void huffcode()

code[i]=cd;

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

}/* 哈夫曼解碼

void trancode()

cin>>b;

}}/* 主函式實現

void main()

5、測試分析

1、給定八個權值：1，3， 5， 7， 9， 11，13，15

對應著字母是：a, b, c, d, e, f, g, h

2、對上述給定的哈夫曼樹以及得到的哈夫曼編碼，輸入一串二進位制編碼，輸出它的哈夫曼解碼。

(一)手動分析

第一步：在上述結點中尋找最小兩個：1，34

第二步：在上述結點中尋找最小兩個94

第四步：在上述結點中尋找最小兩個

1694

第五步：在上述結點中尋找最小兩個

162094

第六步：在上述結點中尋找最小兩個

28162094

第七步：在上述結點中尋找最小兩個

2836

162094

第八步：最後兩個結合：

6401

2836

0 101

1620

g h

01 01

9d e

01 f4c

0 1

a b

根據手動分析的結果如下所示

a: 11000

b: 11001

c: 1101

d: 100

e: 101

f: 111

g: 00

h: 01

(二)執行測試結果如下

6、總結

通過本次哈夫曼編碼的實驗，對哈夫曼編碼有了深刻地認識和理解、掌握，也體會到了他的優點，以及在電文加密中的使用，可以說是受益匪淺！

資料結構實驗報告

資料結構實驗報告

資料結構實驗報告

資料結構實驗報告

相關推薦