數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)三題目二：哈夫曼樹(shù)(已修改)
2025-04-06 03:01 本頁(yè)面
【正文】 北京郵電大學(xué)電信工程學(xué)院2008級(jí)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱： 實(shí)驗(yàn)三 樹(shù)學(xué)生姓名： 班 級(jí)： 班內(nèi)序號(hào)： 學(xué) 號(hào)： 日 期： 20013年11月26日1．實(shí)驗(yàn)要求實(shí)驗(yàn)?zāi)康耐ㄟ^(guò)選擇下面兩個(gè)題目之一進(jìn)行實(shí)現(xiàn)，掌握如下內(nèi)容：掌握二叉樹(shù)基本操作的實(shí)現(xiàn)方法了解赫夫曼樹(shù)的思想和相關(guān)概念學(xué)習(xí)使用二叉樹(shù)解決實(shí)際問(wèn)題的能力實(shí)驗(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)行分析，討論赫夫曼編碼的壓縮效果。2. 程序分析哈夫曼樹(shù)結(jié)點(diǎn)的儲(chǔ)存結(jié)構(gòu)除了二叉樹(shù)所有的雙親域parents，左子樹(shù)域lchild，右子樹(shù)域rchild。還需要有字符域word，權(quán)重域weight，編碼域code。其中由于編碼是一串由0和1組成的字符串，所以code是一個(gè)字符數(shù)組。進(jìn)行哈夫曼編碼首先要對(duì)用戶輸入的信息進(jìn)行統(tǒng)計(jì)，將每個(gè)字符作為哈夫曼樹(shù)的葉子結(jié)點(diǎn)。統(tǒng)計(jì)每個(gè)字符出現(xiàn)的次數(shù)（頻度）作為葉子的權(quán)重，統(tǒng)計(jì)次數(shù)可以根據(jù)每個(gè)字符不同的ASCII碼。并根據(jù)葉子結(jié)點(diǎn)的權(quán)重建立一個(gè)哈夫曼樹(shù)。建立每個(gè)葉子的編碼從根結(jié)點(diǎn)開(kāi)始，規(guī)定通往左子樹(shù)路徑記為0，所以需要前序遍歷哈夫曼樹(shù)，故編碼過(guò)程是以前序遍歷二叉樹(shù)為基礎(chǔ)的。同時(shí)注意遞歸函數(shù)中能否直接對(duì)結(jié)點(diǎn)的編碼域進(jìn)行操作。編碼信息只要遍歷字符串中每個(gè)字符，從哈夫曼樹(shù)中找到相應(yīng)的葉子結(jié)點(diǎn)，取得相應(yīng)的編碼。最后再將所有找到的編碼連接起來(lái)即可。譯碼則是將編碼串從左到右諸位
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1