哈夫曼編碼譯碼器實(shí)驗(yàn)報(bào)告(免費(fèi))-展示頁(yè)
2025-07-31 09:46本頁(yè)面
【正文】 //權(quán)重// bool b。3. void exchange(){……}用兩層for循環(huán)實(shí)現(xiàn)hufNode[i]節(jié)點(diǎn)的成員哈夫曼編碼數(shù)組code[]前后元素的對(duì)換，因?yàn)樵谥暗木幋a過(guò)程中由于是從葉節(jié)點(diǎn)追溯至根節(jié)點(diǎn)，存入code數(shù)組的哈夫曼編碼與哈夫曼編碼的概念反向，故而要調(diào)整；4. signode * getroot(){……}返回哈夫曼樹(shù)的根節(jié)點(diǎn)指針；5. signode * HFM::creat(){……}創(chuàng)建哈夫曼樹(shù)，首先用三個(gè)for循環(huán)查看forest數(shù)組，找到權(quán)值最小的兩個(gè)字符，以int型的min1,min2記錄其下標(biāo)，定義signode * 類(lèi)型指針pp指向新生成signode節(jié)點(diǎn)，用指針操作使pp指向的節(jié)點(diǎn)的權(quán)值為min1,min2權(quán)值之和，pp做孩子指向forest[min1],右孩子指向forest[min2]，min1,min2的父指針指向pp，然后將pp存入min1的位置，min2之后的每一個(gè)節(jié)點(diǎn)依次往前移一個(gè)位置，實(shí)現(xiàn)從forest數(shù)組中清除min1,min2并加入pp的操作；6. void HFM::hufcode(){……}哈夫曼編碼，用for循環(huán)控制查看hufNode 數(shù)組，其初始化已在creat（）的開(kāi)始完成，對(duì)每一個(gè)字符實(shí)現(xiàn)編碼，用while循環(huán)從葉節(jié)點(diǎn)開(kāi)始，如果該節(jié)點(diǎn)是其父節(jié)點(diǎn)的左孩子就將code[hufNode[i].size++]賦值0，否則賦為1，直至當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)為空，while循環(huán)結(jié)束；7. void HFM::savewithhufcode(FILE * inf,FILE * outf){……}將讀入的文章以哈夫曼編碼的形式存儲(chǔ)，其中inf為讀入文件的指針，outf為寫(xiě)入文件的指針,首先調(diào)用rewind(inf)函數(shù)將光標(biāo)放置在文章開(kāi)頭，防止文件未關(guān)閉導(dǎo)致的錯(cuò)誤，每讀一個(gè)字符就用for循環(huán)在hufNode 數(shù)組中查找，因?yàn)閔ufNode 數(shù)組就是保存出現(xiàn)的字符的，故一定可以找到，然后再用fputc函數(shù)將code[]數(shù)組的內(nèi)容寫(xiě)入文件，直至讀入文件結(jié)束；8. void HFM::inorder(signode * sig){……}迭代法遍歷樹(shù)，遍歷到葉節(jié)點(diǎn)時(shí)執(zhí)行hufNode[count++].sig=sig語(yǔ)句實(shí)現(xiàn)hufNode 數(shù)組指向文章中出現(xiàn)的字符；9. int HFM::maxc(){……} 計(jì)數(shù)變量，記錄哈夫曼編碼最大位數(shù)；10. void HFM::hufdecode(FILE* ipf,FILE* opf){……}解碼，從哈夫曼編碼到字符，輸出到屏幕和指定的文件中；11. void input(FILE * f){……}初始讀入文章，保存出現(xiàn)的字符記錄修改其權(quán)重；數(shù)據(jù)結(jié)構(gòu)選擇與算法設(shè)計(jì) 數(shù)據(jù)結(jié)構(gòu)選擇：signode： struct signode{ //signode節(jié)點(diǎn)，哈夫曼樹(shù)節(jié)點(diǎn)// char c。 因此，有如下分析：1. 我們需要一個(gè)功能函數(shù)對(duì)ASCII碼的初始化并需要一個(gè)數(shù)組來(lái)保存它們；2. 定義代表森林的數(shù)組，在創(chuàng)建哈夫曼樹(shù)的過(guò)程當(dāng)中保存被選中的字符，即給定報(bào)文中出現(xiàn)的字符,模擬哈夫曼樹(shù)選取和刪除左右子樹(shù)的過(guò)程；3. 自底而上地創(chuàng)建哈夫曼樹(shù)，保存根的地址和每個(gè)葉節(jié)點(diǎn)的地址，即字符的地址，然后自底而上檢索，首尾對(duì)換調(diào)整為哈夫曼樹(shù)實(shí)現(xiàn)哈弗曼編碼；4. 從哈弗曼編碼文件當(dāng)中讀入字符，根據(jù)當(dāng)前字符為0或者1的狀況訪(fǎng)問(wèn)左子樹(shù)或者右孩子，實(shí)現(xiàn)解碼；5. 使用文件讀寫(xiě)操作哈夫曼編碼和解碼結(jié)果的寫(xiě)入； 解題方法： 結(jié)構(gòu)體、數(shù)組、類(lèi)的定義：1. 定義結(jié)構(gòu)體類(lèi)型的signode 作為哈夫曼樹(shù)的節(jié)點(diǎn)，定義結(jié)構(gòu)體類(lèi)型的hufnode 作為哈夫曼編碼對(duì)照表的節(jié)點(diǎn)，定義HFM類(lèi)實(shí)現(xiàn)對(duì)哈夫曼樹(shù)的創(chuàng)建，利用其成員函數(shù)完成哈夫曼編碼譯碼的工作。 三、刪除左右子樹(shù) 從F中刪除這兩棵樹(shù)，并把這棵新的二叉樹(shù)同樣以升序排列加入到集合F中。哈夫曼樹(shù)的理論創(chuàng)建過(guò)程如下：一、構(gòu)成初始集合 對(duì)給定的n個(gè)權(quán)值{W1,W2,W3,...,Wi,...,Wn}構(gòu)成n棵二叉樹(shù)的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉樹(shù)Ti中只有一個(gè)權(quán)值為Wi的根結(jié)點(diǎn)，它的左右子樹(shù)均為空。（1） 從文件中讀入任意一篇英文短文（文件為ASCII編碼，擴(kuò)展名為txt）；（2） 統(tǒng)計(jì)并輸出不同字符在文章中出現(xiàn)的頻率（空格、換行、標(biāo)點(diǎn)等也按字符處理）；（3） 根據(jù)字符頻率構(gòu)造哈夫曼樹(shù)，并給出每個(gè)字符的哈夫曼編碼；（4） 將文本文件利用哈夫曼樹(shù)進(jìn)行編碼，存儲(chǔ)成壓縮文件（）（5） 用哈夫曼編碼來(lái)存儲(chǔ)文件，并和輸入文本文件大小進(jìn)行比較，計(jì)算文件壓縮率；（6） 進(jìn)行譯碼，將huf文件譯碼為ASCII編碼的txt文件，與原txt文件進(jìn)行比較。問(wèn)題解析與解題方法 問(wèn)題分析： 設(shè)計(jì)一個(gè)哈夫曼編碼、譯碼系統(tǒng)。對(duì)一個(gè)ASCII編碼的文本文件中的字符進(jìn)行哈夫曼編碼，生成編碼文件；反過(guò)來(lái)，可將編碼文件譯碼還原為一個(gè)文本文件。根據(jù)上述過(guò)程可以知道該編碼譯碼器的關(guān)鍵在于字符統(tǒng)計(jì)和哈夫曼樹(shù)的創(chuàng)建以及解碼。 二、選取左右子樹(shù) 在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作為新構(gòu)造的二叉樹(shù)的左右子樹(shù)，新二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左右子樹(shù)的根結(jié)點(diǎn)的權(quán)值之和。 四、重復(fù)二和三兩步， 重復(fù)二和三兩步，直到集合F中只有一棵二叉樹(shù)為止。2. 定義signode 類(lèi)型的全局?jǐn)?shù)組SN[256]（為方便調(diào)用，之后的forest[256]，hufNode[256]均為全局?jǐn)?shù)組）, 保存ASCII編碼的字符，是否在文章中出現(xiàn)（bool類(lèi)型）以及出現(xiàn)次數(shù)（int類(lèi)型，權(quán)重），左右孩子節(jié)點(diǎn)位置，父節(jié)點(diǎn)位置信息；3. 為節(jié)省存儲(chǔ)空間，定義signode * 類(lèi)型的全局?jǐn)?shù)組forest[256], 模擬森林，在創(chuàng)建哈夫曼樹(shù)的過(guò)程中保存出現(xiàn)字符的指針，模擬哈夫曼樹(shù)選取和刪除左右子樹(shù)的過(guò)程；4. 定義hufnode 類(lèi)型的全局?jǐn)?shù)組hufNode[256]，在編碼時(shí)最為哈夫曼編碼對(duì)照表的節(jié)點(diǎn)，char 型c保存字符,int code[100]保存其哈夫曼編碼；5. 定義HFM類(lèi)，主要保存哈夫曼樹(shù)的根節(jié)點(diǎn)指針，但其豐富的功能函數(shù)將實(shí)現(xiàn)哈夫曼編碼譯碼的工作及其他功能；函數(shù)介紹：1. void init(signode * sig){……} 初始化數(shù)組SN[]；2. void press(){……}輸出壓縮對(duì)比情況的信息。 //字符// int weight。 //文章中是否出現(xiàn)// signode * parent。 signode * right。 b=false。 parent=left=right=NULL。C weight b parent left rig
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1