數(shù)據結構課程設計——基于哈夫曼的文件壓縮解壓程序

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

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

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

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

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

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

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

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

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

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

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

12、00111100011011011123 指的是，任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴。三、前綴編碼 利用赫夫曼樹可以構造一種不等長的二進制編碼，并且構造所得的赫夫曼編碼是一種最優(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)， 請構造相應的哈夫曼樹（要求樹中所有結點的左右孩子權值必須左大右?。?，求出每個字符的哈夫曼編碼。 25解： 設左子樹編碼為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)，假設電文中共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)頻率則該電文的碼長（即帶權路徑長度