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

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

數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告

試驗(yàn)名稱(chēng)：試驗(yàn)三——樹(shù)學(xué)生姓名：大學(xué)霸班級(jí)：xxxxxxxxxx班內(nèi)序號(hào)：xx學(xué)號(hào)：xxxxxxxxxx日期：2023年12月1日

1．試驗(yàn)要求

a.試驗(yàn)?zāi)康?/p>

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

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

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

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

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

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

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

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

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

IlovedataStructure,IloveComputer。Iwilltrymybesttostudydata

第1頁(yè)

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

Structure.

提醒：

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

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

字符一律不用編碼。

2.程序分析

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

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

weightlchildrchildparent

2-1-140

3-1-1416-1-152

9-1-163

5015451142662035-1

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

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

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

5intrchild;//右孩子指針

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

};

ZC

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

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

第2頁(yè)

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

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

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

最小的二叉樹(shù)，來(lái)建立編碼。

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

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

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

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

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

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

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

[6.1]標(biāo)記葉子節(jié)點(diǎn)，無(wú)左子樹(shù)右子樹(shù)及父節(jié)點(diǎn)

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

voidHuffman::Initial(){

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