數(shù)據(jù)結(jié)構(gòu)試驗三 哈夫曼編解碼器

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)試驗三哈夫曼編解碼器北京郵電大學(xué)信息與通信工程學(xué)院

數(shù)據(jù)結(jié)構(gòu)試驗報告

試驗名稱：試驗三——樹學(xué)生姓名：大學(xué)霸班級：xxxxxxxxxx班內(nèi)序號：xx學(xué)號：xxxxxxxxxx日期：2023年12月1日

1．試驗要求

a.試驗?zāi)康?/p>

通過選擇兩個題目之一進(jìn)行實現(xiàn)，把握如下內(nèi)容：?把握二叉樹基本操作的實現(xiàn)方法?了解赫夫曼樹的思想和相關(guān)概念?學(xué)習(xí)使用二叉樹解決實際問題的能力b.試驗內(nèi)容

利用二叉樹結(jié)構(gòu)實現(xiàn)赫夫曼編/解碼器。基本要求：

1、初始化(Init)：能夠?qū)斎氲娜我忾L度的字符串s進(jìn)行統(tǒng)計，統(tǒng)計每個字符的頻度，并建立赫夫曼樹

2、建立編碼表(CreateTable)：利用已經(jīng)建好的赫夫曼樹進(jìn)行編碼，并將每個字符的編碼輸出。

3、編碼(Encoding)：根據(jù)編碼表對輸入的字符串進(jìn)行編碼，并將編碼后的字符串輸出。

4、譯碼(Decoding)：利用已經(jīng)建好的赫夫曼樹對編碼后的字符串進(jìn)行譯碼，并輸出譯碼結(jié)果。

5、打印(Print)：以直觀的方式打印赫夫曼樹（選作）

6、計算輸入的字符串編碼前和編碼后的長度，并進(jìn)行分析，探討赫夫曼編碼的壓縮效果。

測試數(shù)據(jù)：

IlovedataStructure,IloveComputer。Iwilltrymybesttostudydata

第1頁

北京郵電大學(xué)信息與通信工程學(xué)院

Structure.

提醒：

1、用戶界面可以設(shè)計為“菜單〞方式：能夠進(jìn)行交互。

2、根據(jù)輸入的字符串中每個字符出現(xiàn)的次數(shù)統(tǒng)計頻度，對沒有出現(xiàn)的

字符一律不用編碼。

2.程序分析

2.1存儲結(jié)構(gòu)

哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長度最短的二叉樹。只有度為0和2的結(jié)點的二叉樹成為正則二叉樹。哈夫曼樹就是這樣。根據(jù)二叉樹的性質(zhì)，一顆有n個葉子的哈夫曼樹共有2n-1個葉子結(jié)點，可以用一個大小為2n-1的一維數(shù)組存放哈夫曼樹的各個節(jié)點。由于每個結(jié)點同時還包括其雙親信息和孩子信息，所以用一個靜態(tài)三叉鏈表來存儲哈夫曼樹。

weightlchildrchildparent

2-1-140

3-1-1416-1-152

9-1-163

5015451142662035-1

C++描述如下20structHNode//靜態(tài)三叉鏈表元素01{

11Aintweight;//結(jié)點權(quán)值

intparent;//雙親指針0intlchild;//左孩子指針

5intrchild;//右孩子指針

01intmark;//標(biāo)記是否已經(jīng)訪問過

};

ZC

如下圖的哈夫曼樹，其對應(yīng)的編碼表可以是如下圖的結(jié)構(gòu)，實際上字符的編碼應(yīng)當(dāng)用bit表示，即對于1個字符‘Z’使用三個比特001表示

哈夫曼編碼表的C++描述：structHCode//哈夫曼編碼表{charch[2];//字符intfreq;//頻度charcode[100];//字符編碼};

第2頁

1B北京郵電大學(xué)信息與通信工程學(xué)院

2.2關(guān)鍵算法分析核心算法思想：

1.哈夫曼編碼(HuffmanCoding)是不等長編碼。編碼時借助哈夫曼樹，也即帶權(quán)路徑長度

最小的二叉樹，來建立編碼。

2.哈夫曼編碼可以實現(xiàn)無損數(shù)據(jù)壓縮。單個字符用一個特定長度的位序列替代：在字符串

中出現(xiàn)頻率高的符號，使用短的位序列，而那些很少出現(xiàn)的符號，則用較長的位序列。

關(guān)鍵算法思想描述和實現(xiàn)：關(guān)鍵算法1：初始化函數(shù)

用字符串記錄用戶輸入的原始數(shù)據(jù)，統(tǒng)計一共出現(xiàn)了多少種字符，各出現(xiàn)了多少次即為字符的權(quán)值。對未出現(xiàn)的字符不予統(tǒng)計編碼。將統(tǒng)計的葉子節(jié)點編制成數(shù)組。為創(chuàng)立哈夫曼樹作準(zhǔn)備。

[1]用字符串str接收用戶輸入的數(shù)據(jù)[2]用數(shù)組frequency存儲字符出現(xiàn)的個數(shù)[3]假使字符出現(xiàn)過，葉子節(jié)點數(shù)加1

[4]創(chuàng)立哈夫曼樹Htree，哈夫曼編碼表HcodeTable[5]初始化哈夫曼編碼表

[5.1]判斷字符是否出現(xiàn)過[5.1.1]記錄權(quán)值和字符[5.1.2]編碼形式置空[6]初始化哈夫曼樹

[6.1]標(biāo)記葉子節(jié)點，無左子樹右子樹及父節(jié)點

C++實現(xiàn)如下

voidHuffman::Initial(){

[1]cin.getline(str,MAXSIZE);//從鍵盤接收字符串shortfrequency[128]={0};leaf=0;