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