數(shù)據(jù)結(jié)構(gòu)課程方案報(bào)告huffman編碼與資料壓縮

《數(shù)據(jù)結(jié)構(gòu)課程方案報(bào)告huffman編碼與資料壓縮》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、課程設(shè)計(jì)報(bào)告題目：題目三哈夫曼編碼與文件壓縮課程名稱：數(shù)據(jù)結(jié)構(gòu)專業(yè)班級(jí)：計(jì)算機(jī)科學(xué)與技術(shù)1003班學(xué)號(hào)：姓名：魯辰指導(dǎo)教師：報(bào)告日期：2012.09.26計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院目錄121任務(wù)書32緒言42.1課題背景42.2課題研究的目的和意義42.3國內(nèi)外概況42.4課題的主要研究工作43系統(tǒng)設(shè)計(jì)方案的研究53.1系統(tǒng)的控制特點(diǎn)與性能要求53.2系統(tǒng)實(shí)現(xiàn)的原理53.2.1Huffman算法53.2.2Huffman編碼53.2.3壓縮過程53.2.4解壓過程63.3系統(tǒng)實(shí)現(xiàn)方案分析63.3.1實(shí)現(xiàn)Huffman編碼及壓縮所需的變量63.

2、3.2文件名處理73.3.3實(shí)現(xiàn)Huffman編碼及壓縮過程所需要的函數(shù)73.3.4實(shí)現(xiàn)解壓縮過程所需要的函數(shù)83.3.5輸入輸出84基于Huffman編碼的文件壓縮程序的設(shè)計(jì)94.1主模塊功能介紹95系統(tǒng)的實(shí)現(xiàn)105.1目標(biāo)程序運(yùn)行截圖105.2測試及測試數(shù)據(jù)分析105.2.1測試數(shù)據(jù)105.2.2測試數(shù)據(jù)分析116總結(jié)與展望12參考文獻(xiàn)13附錄英文縮寫詞141任務(wù)書題目三哈夫曼編碼與文件壓縮12p設(shè)計(jì)目的：掌握二叉樹、哈夫曼樹的概念，性質(zhì)與存儲(chǔ)結(jié)構(gòu)，能夠利用哈夫曼算法實(shí)現(xiàn)哈夫曼編碼，并應(yīng)用于文件壓縮，從而提高學(xué)生綜合運(yùn)用知識(shí)的技能與

3、實(shí)踐能力。矚慫潤厲釤瘞睞櫪廡賴。p設(shè)計(jì)內(nèi)容：分析與設(shè)計(jì)哈夫曼樹的存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)哈夫曼算法以及編碼與譯碼基本功能，并對(duì)任意文本文件利用哈夫曼編碼進(jìn)行壓縮得到壓縮文件，然后進(jìn)行解壓縮得到解壓文件。有興趣的同學(xué)可以查閱資料實(shí)現(xiàn)Lempel-Zivslidingwindow壓縮方法，并與之比較。聞創(chuàng)溝燴鐺險(xiǎn)愛氌譴凈。p設(shè)計(jì)要求：（1）要求界面友好，輸入文本文件可帶路徑（如：D:docoriginal.txt），哈夫曼算法所得到的壓縮文件名為*.cod，哈夫曼樹也以文件形式保存，文件名為*.hfm。殘騖樓諍錈瀨濟(jì)溆塹籟。（2）顯示壓縮比、壓縮

4、時(shí)間、解壓時(shí)間與對(duì)應(yīng)的編碼表。p設(shè)計(jì)提示：統(tǒng)計(jì)文本文件中各字符的頻度并作為權(quán)值生成哈夫曼樹，并利用哈夫曼樹進(jìn)行二進(jìn)制編碼。p參考文獻(xiàn)：[1]嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）.北京:清華大學(xué)出版社,1997[2]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析.北京:電子工業(yè)出版社,2007[3]嚴(yán)蔚敏,吳偉民,米寧.數(shù)據(jù)結(jié)構(gòu)題集（C語言版）.北京:清華大學(xué)出版社,19992緒言2.1課題背景在計(jì)算機(jī)軟件應(yīng)用領(lǐng)域，文件壓縮是一項(xiàng)重要的技術(shù)。為了減少傳輸數(shù)據(jù)量或者減少存儲(chǔ)空間，都需要將大型文件壓縮成較小的文件。釅錒極額閉鎮(zhèn)檜豬訣錐。2.2課題研究的目的和意

5、義Huffman編碼具有速度快、簡單等優(yōu)點(diǎn)，是一種很好的壓縮方法。122.3國內(nèi)外概況1952年，DavidA.Huffman在麻省理工攻讀博士時(shí)所發(fā)明的，并發(fā)表于《一種構(gòu)建極小多余編碼的方法》（AMethodfortheConstructionofMinimum-RedundancyCodes）一文。彈貿(mào)攝爾霽斃攬磚鹵廡。2.4課題的主要研究工作（1）通過查閱書籍并在網(wǎng)上查看相關(guān)論文，對(duì)Huffman編碼算法有一個(gè)清晰的認(rèn)識(shí)。（2）使用MicrosoftVisualStudio2010實(shí)現(xiàn)基于Huffman編碼的文件壓縮程序。謀蕎摶篋

6、飆鐸懟類蔣薔。（3）通過使用各種不同的測試文件對(duì)該程序進(jìn)行測試，記錄并分析壓縮算法的壓縮比、壓縮時(shí)間等數(shù)據(jù)。（4）分析測試數(shù)據(jù)，并根據(jù)需要對(duì)代碼進(jìn)行優(yōu)化。3系統(tǒng)設(shè)計(jì)方案的研究3.1系統(tǒng)的控制特點(diǎn)與性能要求本系統(tǒng)是使用VS2010開發(fā)的MFC應(yīng)用程序，對(duì)話框是使用MFC生成的，而對(duì)文件讀寫操作以及Huffman編碼的算法部分是用C語言實(shí)現(xiàn)的。廈礴懇蹣駢時(shí)盡繼價(jià)騷。本系統(tǒng)的特點(diǎn)是圖形界面，使用簡單，便于操控。本系統(tǒng)不要求使用者安裝VisualStudio或者M(jìn)FC類庫（？）。3.2系統(tǒng)實(shí)現(xiàn)的原理3.2.1Huffman算法（1）根據(jù)給定的n

7、個(gè)權(quán)值{ω1,ω2,…,ωn}構(gòu)成n棵二叉樹的集合F={T1,T2,…,Tn}，其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為ωi的根結(jié)點(diǎn)，其左右子樹為空。煢楨廣鰳鯡選塊網(wǎng)羈淚。（2）在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹上根結(jié)點(diǎn)的權(quán)值之和。鵝婭盡損鵪慘歷蘢鴛賴。（3）在F中刪除這兩棵樹，同時(shí)將新達(dá)到的二叉樹加入F中。12（4）重復(fù)（2）和（3），直到F只含一棵樹為止。3.2.2Huffman編碼假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為ωi，其編碼長度為li，電文中只有n種字符，則電文總長為

8、i=1nωili。對(duì)應(yīng)到二叉樹上，若置ωi為葉子結(jié)點(diǎn)的權(quán)，li恰為從根到葉子結(jié)點(diǎn)的路徑長度，則i=1nωili恰為二叉樹上的帶權(quán)路徑長度。由此可見，設(shè)計(jì)電文總長最短的二進(jìn)制前綴編碼即為以n種字符出現(xiàn)的頻率做