數(shù)據(jù)結(jié)構(gòu)課程設(shè)計——基于哈夫曼的文件壓縮解壓程序

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計陳正銘1教學目的與要求 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計的目的就是要達到理論與實際應用相結(jié)合，使同學們能夠根據(jù)數(shù)據(jù)對象的特性，學會數(shù)據(jù)組織的方法，能把現(xiàn)實世界中的實際問題在計算機內(nèi)部表示出來，并培養(yǎng)基本的、良好的程序設(shè)計技能。 通過這次課程設(shè)計，要求掌握數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示，數(shù)據(jù)結(jié)構(gòu)的選擇應用、算法的設(shè)計及其實現(xiàn)和性能分析等方面中加深對課程基本內(nèi)容的理解。同時，在程序設(shè)計方法以及上機操作等基本技能和科學作風方面受到比較系統(tǒng)和嚴格的訓練。2數(shù)據(jù)結(jié)構(gòu)基本原理簡要復習 1數(shù)據(jù)元素之間的四種基本邏輯結(jié)構(gòu)： 非線性，線性，樹，圖2數(shù)據(jù)物理表示（存儲方法）： 順序存儲，鏈式存儲，索引存儲，散列存儲

2、3算法的特征： 有窮性，可行性，確定性，正確性 算法設(shè)計的要求： 可讀性，健壯性，高效性34算法的時間復雜度、空間復雜度及分析： O（1），O（n），O（logn），O（n2）5典型的幾種數(shù)據(jù)結(jié)構(gòu)：順序表，鏈表，順序棧，鏈棧，循環(huán)隊列，鏈隊列，字符串，多維數(shù)組，二叉鏈表樹，二叉順序樹，鄰接矩陣圖，鄰接表圖，散列表 4設(shè)計題目 基于哈夫曼樹的文件壓縮/解壓程序 （數(shù)據(jù)結(jié)構(gòu)課程設(shè)計案例精編P329） 該參考教材同學們可自行借閱或在網(wǎng)上購買（一般8折），也可聯(lián)系出版社市場部集體定購（清華大學出版社市場部電話：（轉(zhuǎn)分機號220），可能有更大折扣。該參考教材內(nèi)容豐富，尤其是C+語言 STL方面的內(nèi)容，對

3、日后從事開發(fā)設(shè)計工作的同學有較大參考作用。但教材價格較貴，零售價45元，因此本學期沒為大家指定定購，大家可按需購買，但建議購買。 5STL（Standard Template Library，標準模板庫）概述STL的一個重要特點是數(shù)據(jù)結(jié)構(gòu)和算法的分離。盡管這是個簡單的概念，但這種分離確實使得STL變得非常通用。例如，由于STL的sort()函數(shù)是完全通用的，你可以用它來操作幾乎任何數(shù)據(jù)集合，包括鏈表，容器和數(shù)組。 STL另一個重要特性是它不是面向?qū)ο蟮?。為了具有足夠通用性，STL主要依賴于模板而不是封裝，繼承和虛函數(shù)（多態(tài)性）OOP的三個要素。 STL提供了大量的模板類和函數(shù)，可以在OOP和常

4、規(guī)編程中使用。所有的STL的大約50個算法都是完全通用的，而且不依賴于任何特定的數(shù)據(jù)類型。6STL組成三個基本的STL組件：1）迭代器，提供了訪問容器中對象的方法。例如，可以使用一對迭代器指定list或vector中的一定范圍的對象。迭代器就如同一個指針。事實上，C+的指針也是一種迭代器。但是，迭代器也可以是那些定義了operator*()以及其他類似于指針的操作符地方法的類對象。2）容器，是一種數(shù)據(jù)結(jié)構(gòu)，如list，vector，和deques ，以模板類的方法提供。為了訪問容器中的數(shù)據(jù)，可以使用由容器類輸出的迭代器。3）算法，是用來操作容器中的數(shù)據(jù)的模板函數(shù)。例如，STL用sort()來對

5、一個vector中的數(shù)據(jù)進行排序，用find()來搜索一個list中的對象。函數(shù)本身與他們操作的數(shù)據(jù)的結(jié)構(gòu)和類型無關(guān)，因此他們可以在從簡單數(shù)組到高度復雜容器的任何數(shù)據(jù)結(jié)構(gòu)上使用。7STL總結(jié)盡管很多程序員仍然在使用標準C與C+函數(shù)，使用標準C函數(shù)確實方便(如使用sprintf()進行格式化輸出)。但是C與C+函數(shù)不使用異常機制來報告錯誤，也不適合處理新的數(shù)據(jù)類型。而且標準C與C+函數(shù)經(jīng)常使用內(nèi)存分配技術(shù)，沒有經(jīng)驗的程序員很容易寫出bug來。.STL的最主要的兩個特點：數(shù)據(jù)結(jié)構(gòu)和算法的分離，非面向?qū)ο蟊举|(zhì)。訪問對象是通過象指針一樣的迭代器實現(xiàn)的；容器是象鏈表，矢量之類的數(shù)據(jù)結(jié)構(gòu)，并按模板方式提供

6、；算法是函數(shù)模板，用于操作容器中的數(shù)據(jù)。由于STL以模板為基礎(chǔ)，所以能用于任何數(shù)據(jù)類型和結(jié)構(gòu)。8STL示例排序算法（1）自行寫排序算法與調(diào)用；（2）調(diào)用標準C+函數(shù)qsort()完成排序；（3）部分使用STL特性；（4）完全使用STL特性。9設(shè)計要求 基于哈夫曼樹的文件壓縮/解壓程序 基本要求：實現(xiàn)一個基于哈夫曼樹的文件壓縮程序和文件解壓程序。要求壓縮程序讀入源文件，分析每種字符的頻度，然后建立相應的哈夫曼樹，再求出相應哈夫曼編碼，根據(jù)編碼對源文件進行壓縮，得到源文件對應的壓縮文件。解壓程序讀入壓縮文件，根據(jù)相應的哈夫曼編碼解壓還原 ，得到對應的源文件。選做內(nèi)容：求出壓縮率；打印哈夫曼樹；對文

7、件夾壓縮；圖形圖形化窗口操作界面。 （參考教材的本題目設(shè)計指導部分的掃描頁）程序建議使用c語言完成，建議開發(fā)工具為Microsoft Visusl C+ 2005 Express（可在微軟網(wǎng)站免費下載）。10設(shè)計報告撰寫指導 1、 需求分析 以無歧義的陳述說明所選設(shè)計題目的任務，強調(diào)的是程序要做什么？明確規(guī)定：輸入的形式和輸出、值的范圍；輸出的形式；程序所能達到的功能；測試的數(shù)據(jù)：包括正確的輸入和錯誤的輸入及其相應的輸出結(jié)果；2、 概要設(shè)計 問題解決的思路概述；說明程序中用到的所有抽象數(shù)據(jù)類型的定義，主程序的流程以及各程序模塊之間的層次（調(diào)用）關(guān)系。113、 詳細設(shè)計 實現(xiàn)概要設(shè)計中定義所有數(shù)

8、據(jù)類型，對每個操作只需要寫出偽代碼算法，畫出函數(shù)的調(diào)用關(guān)系圖。4、 調(diào)試分析報告 調(diào)試過程中遇到的問題并且是如何解決的以及對設(shè)計實現(xiàn)的回顧討論和分析算法的時空分析（包括基本操作和主要算法的時空復雜度的分析）和改進設(shè)想經(jīng)驗和體會等125、 用戶使用說明 向用戶說明如何使用你編寫的程序，詳細列出每一步的操作步驟。6、 測試結(jié)果 列出測試結(jié)果，包括輸入的數(shù)據(jù)和相應的輸出數(shù)據(jù)。這里的測試數(shù)據(jù)應該完整和嚴格，最好多于需求分析中所列的測試項。7、 附錄（電子版文檔必須要，打印版該部分可不打?。?應附上帶詳細注釋的可讀性好的源程序。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告示例文檔13時間安排 時間內(nèi)容地點備注第1周復習數(shù)據(jù)結(jié)構(gòu)

9、相關(guān)原理，明確題目要求、確定數(shù)據(jù)結(jié)構(gòu)與設(shè)計方案課室第28周編寫程序，準備測試數(shù)據(jù)實驗室或宿舍在實驗室或宿舍完成編寫程序任務第9周上機演示，回答教師提問，按格式撰寫課程設(shè)計報告實驗室課程設(shè)計報告應嚴格按照上述設(shè)計報告撰寫要求撰寫；最后將報告用A4紙打印裝訂；第10周以班為單位上交課程設(shè)計的資料光盤（內(nèi)含每個同學的課程設(shè)計的源程序、編譯后可直接運行的目標程序與課程設(shè)計報告的電子文檔），課程設(shè)計報告打印稿2009年11月16日前交齊全部課程資料，逾期者以缺考處理，課程成績0分。14考核方式與成績 程序：30課程設(shè)計報告：70 2009年11月16日前以班為單位交齊全部課程考核資料（光盤和課程設(shè)計打印

10、稿），逾期者以缺考處理，課程成績0分。 156.8 哈 夫 曼 樹 與 哈 夫 曼 編 碼 最優(yōu)樹的定義 如何構(gòu)造最優(yōu)樹 前綴編碼 16 樹的帶權(quán)路徑長度定義為： 樹中所有葉子結(jié)點的帶權(quán)路徑長度之和 WPL(T) = wklk (對所有葉子結(jié)點) 在所有含 n 個葉子結(jié)點、并帶相同權(quán)值的 m 叉樹中，必存在一棵其帶權(quán)路徑長度取最小值的樹，稱為“最優(yōu)樹”。例如： 一、最優(yōu)樹的定義1727 9 75492WPL(T)= 72+52+23+43+92 =60WPL(T)= 74+94+53+42+21 =89 5418 根據(jù)給定的 n 個權(quán)值 w1, w2, , wn， 構(gòu)造 n 棵二叉樹的集合 F

11、 = T1, T2, , Tn， 其中每棵二叉樹中均只含一個帶權(quán)值 為 wi 的根結(jié)點,其左、右子樹為空樹;二、如何構(gòu)造最優(yōu)樹(1)(赫夫曼算法) 以二叉樹為例:19 在 F 中選取其根結(jié)點的權(quán)值為最 小的兩棵二叉樹，分別作為左、 右子樹構(gòu)造一棵新的二叉樹，并 置這棵新的二叉樹根結(jié)點的權(quán)值 為其左、右子樹根結(jié)點的權(quán)值之 和;(2)20 從F中刪去這兩棵樹，同時加入 剛生成的新樹; 重復 (2) 和 (3) 兩步，直至 F 中只 含一棵樹為止。(3)(4)219例如: 已知權(quán)值 W= 5, 6, 2, 9, 7 562752769767139527226713952795271667132900

12、00111100011011011123 指的是，任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴。三、前綴編碼 利用赫夫曼樹可以構(gòu)造一種不等長的二進制編碼，并且構(gòu)造所得的赫夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長度最短。24練習題 有一份電文中共使用八種字符，頻率依次為： A(0.04)，B(0.3)，C(0.08)，D(0.09)，E(0.13)，F(xiàn)(0.22)，G(0.03)，H(0.11)， 請構(gòu)造相應的哈夫曼樹（要求樹中所有結(jié)點的左右孩子權(quán)值必須左大右?。?，求出每個字符的哈夫曼編碼。 25解： 設(shè)左子樹編碼為0，右子樹編碼為1，則A,B,C,D,E,F,G,H字符的哈夫曼編碼為：A：01010 B：00 C：0100 D：111 E：011 F：10 G：01011 H：11026 電文中共使用八種字符，如果按一般方法對其進行編碼，則最少需要3位碼長，如：A(000)，B(001)，C(010)，D(011)，E(100)，F(xiàn)(101)，G(110)，H(111)，假設(shè)電文中共100個字符，按其出現(xiàn)頻率則該電文的碼長為：3*100300。 若按哈夫曼編碼A：01010（5位）B：00（2位）C：0100（4位）D：111（3位）E：011（3位）F：10（2位）G：01011（5位）H：110（3位），按其出現(xiàn)頻率則該電文的碼長（即帶權(quán)路徑長度