課程設(shè)計報告--哈夫曼編碼譯碼系統(tǒng)-文庫吧
2025-01-04 00:03 本頁面
【正文】 問題分析： 設(shè)計一個哈夫曼編碼、譯碼系統(tǒng)。對一個ASCII編碼的文本文件中的字符進行哈夫曼編碼，生成編碼文件；反過來，可將編碼文件譯碼還原為一個文本文件。（1） 從文件中讀入任意一篇英文短文（文件為ASCII編碼，擴展名為txt）；（2） 統(tǒng)計并輸出不同字符在文章中出現(xiàn)的頻率（空格、換行、標點等也按字符處理）；（3） 根據(jù)字符頻率構(gòu)造哈夫曼樹，并給出每個字符的哈夫曼編碼；（4） 將文本文件利用哈夫曼樹進行編碼，存儲成壓縮文件（）（5） 用哈夫曼編碼來存儲文件，并和輸入文本文件大小進行比較，計算文件壓縮率；（6） 進行譯碼，將huf文件譯碼為ASCII編碼的txt文件，與原txt文件進行比較。根據(jù)上述過程可以知道該編碼譯碼器的關(guān)鍵在于字符統(tǒng)計和哈夫曼樹的創(chuàng)建以及解碼。哈夫曼樹的理論創(chuàng)建過程如下：一、構(gòu)成初始集合 對給定的n個權(quán)值{W1,W2,W3,...,Wi,...,Wn}構(gòu)成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉樹Ti中只有一個權(quán)值為Wi的根結(jié)點，它的左右子樹均為空。 二、選取左右子樹 在F中選取兩棵根結(jié)點權(quán)值最小的樹作為新構(gòu)造的二叉樹的左右子樹，新二叉樹的根結(jié)點的權(quán)值為其左右子樹的根結(jié)點的權(quán)值之和。 三、刪除左右子樹 從F中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列加入到集合F中。 四、重復(fù)二和三兩步， 重復(fù)二和三兩步，直到集合F中只有一棵二叉樹為止。 因此，有如下分析：1. 我們需要一個功能函數(shù)對ASCII碼的初始化并需要一個數(shù)組來保存它們；2. 定義代表森林的數(shù)組，在創(chuàng)建哈夫曼樹的過程當(dāng)中保存被選中的字符，即給定報文中出現(xiàn)的字符,模擬哈夫曼樹選取和刪除左右子樹的過程；3. 自底而上地創(chuàng)建哈夫曼樹，保存根的地址和每個葉節(jié)點的地址，即字符的地址，然后自底而上檢索，首尾對換調(diào)整為哈夫曼樹實現(xiàn)哈弗曼編碼；4. 從哈弗曼編碼文件當(dāng)中讀入字符，根據(jù)當(dāng)前字符為0或者1的狀況訪問左子樹或者右孩子，實現(xiàn)解碼；5. 使用文件讀寫操作哈夫曼編碼和解碼結(jié)果的寫入； 解題方法： 結(jié)構(gòu)體、數(shù)組、類的定義：1. 定義結(jié)構(gòu)體類型的signode 作為哈夫曼樹的節(jié)點，定義結(jié)構(gòu)體類型的hufnode 作為哈夫曼編碼對照表的節(jié)點，定義HFM類實現(xiàn)對哈夫曼樹的創(chuàng)建，利用其成員函數(shù)完成哈夫曼編碼譯碼的工作。2. 定義signode 類型的全局數(shù)組SN[256]（為方便調(diào)用，之后的forest[256]，hufNode[256]均為全局數(shù)組）, 保存ASCII編碼的字符，是否在文章中出現(xiàn)（bool類型）以及出現(xiàn)次數(shù)（int類型，權(quán)重），左右孩子節(jié)點位置，父節(jié)點位置信息；3. 為節(jié)省存儲空間，定義signode * 類型的全局數(shù)組forest[256], 模擬森林，在創(chuàng)建哈夫曼樹的過程中保存出現(xiàn)字符的指針，模擬哈夫曼樹選取和刪除左右子樹的過程；4. 定義hufnode 類型的全局數(shù)組hufNode[256]，在編碼時最為哈夫曼編碼對照表的節(jié)點，char 型c保存字符,int code[100]保存其哈夫曼編碼；5. 定義HFM類，主要保存哈夫曼樹的根節(jié)點指針，但其豐富的功能函數(shù)將實現(xiàn)哈夫曼編碼譯碼的工作及其他功能；函數(shù)介紹：1. void init(signode * sig){……} 初始化數(shù)組SN[]；2. void press(){……}輸出壓縮對比情況的信息
高考資料相關(guān)推薦
鄂ICP備17016276號-1