huffman編碼與解碼實現(xiàn)文件壓縮與解壓縮(編輯修改稿)
2024-09-26 14:14 本頁面
【文章內(nèi)容簡介】 等長編 碼所對應的編碼二叉樹也可以直接看出，任何一個葉子結(jié)點都不可能是其它葉子結(jié)點的雙親，也就是說，只有當一個結(jié)點是另一個結(jié)點的雙親時，該結(jié)點的字符編碼才會是另一個結(jié)點的字符編碼的前綴。 為了使不等長編碼為前綴編碼，可用該字符集中的每個字符作為葉子結(jié)點生成一棵編碼二叉樹，為了獲得文件的最短長度，特將每個字符的出現(xiàn)頻率作為字符結(jié)點的權(quán)值賦予該結(jié)點上，求出此樹的最小帶權(quán)路徑長度就等于文件的最短長度。因此，對文件進行壓縮，就可以轉(zhuǎn)化字符集中的所有字符作為葉子結(jié)點，字符出現(xiàn)的頻率作為權(quán)值所產(chǎn)生的 huffman 樹的問題。 基 本思路大致有了后，接下來是對程序的編寫工作，程序初步形成后，對其測試，發(fā)現(xiàn)了一些變量還沒有聲明的錯誤，對遺漏的變量進行了聲明后，再次調(diào)試，發(fā)現(xiàn)一個比較大的問題，就是字符都能讀入，但是不能進行編碼，也即不能構(gòu)造 huffman 樹，最后經(jīng)過檢查發(fā)現(xiàn)原來是結(jié)點方面存在問題，最后加入sum=2*count1。語句，問題得到解決。（該語句的作用是：例如提供了 3 個權(quán)值不同的結(jié)點，現(xiàn)在要構(gòu)造 huffman 樹，那就需要 5 個結(jié)點。） 五、用戶使用說明 用戶運行本程序前，首先要在起工程文件下建立一個名字為 文本文檔，再運行本程序后，第一步，按任意鍵來讀取建立的 文本文檔 ,再據(jù)程序中提示完成第二步操作，也即是講壓縮的文件以 Huffman 編碼放入一個由用戶自己建立的文本文檔中，接著再根據(jù)提示完成第三步操作，即對要壓縮的文件解壓后放入由用戶建立的任意名的文本文檔中，由此完成操作。 六、測試結(jié)果 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計 被編碼（部分字符）： 被解碼（部分文件）： 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計 七、參考書目 [1]徐孝凱 .數(shù)據(jù)結(jié)構(gòu)實用教程 (c/c++描述 )[M].北京：清華大學出版社，2020 年 6 月 [2]鄭莉等 .c++語言程序設(shè)計 (第三版 )[M].北京：清華大學出版社， 2020 年12月 八、附錄 includeiostream includefstream includestring includeiomanip using namespace std。 string remfile[600000]。 //存放原文件字符的數(shù)組 int remcount=0。//記錄元素個數(shù) float bitecount=0。//記錄二進制碼的個數(shù) struct huffchar{ //存放讀 入字符的類 int count。//字符出現(xiàn)的個數(shù) char data。//字符 }。 int count=1。//記錄 huff 數(shù)組中字符實際出現(xiàn)的個數(shù) huffchar huff[1000]。//類的對象 //文件讀入部分和統(tǒng)計字符出現(xiàn)的頻率 bool char_judge(char c)//判斷字符出現(xiàn)的函數(shù) { 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計 for(int i=1。i=count。i++) if(huff[i].data==c){huff[i].count++。return true。}//如果出現(xiàn)過，出 現(xiàn)的頻數(shù)加1 return false。} void char_add(char c)//添加新出現(xiàn)的字符； {huff[count].data=c。 huff[count++].count++。//個數(shù)增加 } //文件的讀取 void read_file_count() {char c。 ifstream infile。 ()。//打開 文件 if(!infile)//檢查文件是否打開。 {cout不能打開 文件 。//輸出文件未打開的標志 exit(0)。 } cout讀入的文件中的內(nèi)容為： endl。 while((c=())!=EOF)//EOF 是文件結(jié)束的標志 {remfile[++remcount]=c。//recount 記錄元素個數(shù) if(!char_judge(c)) char_add(c)。} coute
公司管理相關(guān)推薦
鄂ICP備17016276號-1