哈夫曼編碼與譯碼課程設(shè)計(jì)報(bào)告

1、<p>　　課程名稱: 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) </p><p>　　學(xué) 院: 管理學(xué)院 </p><p>　　專業(yè)班級(jí): 10信息管理與信息系統(tǒng)(2)班 </p><p>　　姓 名: 王高智 </p>

2、;<p>　　學(xué) 號(hào)： 3110004891 </p><p>　　指導(dǎo)老師: 丁天翔 </p><p>　　2012年06月18日</p><p><b>　　目錄</b></p><p>　　哈夫曼編碼與譯碼

3、2</p><p>　　一、問(wèn)題及功能分析2</p><p><b>　　(一)要求：2</b></p><p><b>　　(二)分析：2</b></p><p><b>　　二、詳細(xì)設(shè)計(jì)2</b></p><p>　　(一)讀取信

4、息2</p><p>　　(二)統(tǒng)計(jì)文本信息2</p><p>　　(三)設(shè)計(jì)編碼和譯碼方案3</p><p>　　(四)計(jì)算壓縮比3</p><p>　　(五)整體流程3</p><p><b>　　三、程序?qū)崿F(xiàn)3</b></p><p><b

5、>　　(一)匯總3</b></p><p>　　(二)具體實(shí)現(xiàn)代碼3</p><p>　　1.com.gauze.Main3</p><p>　　2.com.gauze.charstatistics.CharData4</p><p>　　3.com.gauze.charstatistics.CharDat

6、aMapActor6</p><p>　　4.com.gauze.charstatistics.CharReader9</p><p>　　5.com.gauze.util.HaffmanNode10</p><p>　　6.com.gauze.util.HaffmanTree11</p><p>　　四、調(diào)試分析14<

7、;/p><p>　　(一)統(tǒng)計(jì)英文文本：14</p><p>　　(二)統(tǒng)計(jì)含有中英文文本15</p><p>　　(三)查詢只含有字符串“AAAABBBCDDBBAAA”的文本（課本示例）：16</p><p><b>　　手機(jī)信息管理17</b></p><p>　　一、問(wèn)題及功能

8、分析17</p><p>　　(一)功能要求：17</p><p>　　(二)性能要求：17</p><p>　　(三)分析：17</p><p>　　二、詳細(xì)設(shè)計(jì)20</p><p>　　(一)持久層20</p><p>　　(二)邏輯層21</p>&

9、lt;p>　　(三)展示層23</p><p>　　三、程序?qū)崿F(xiàn)27</p><p>　　四、調(diào)試分析42</p><p>　　(一)通訊錄管理42</p><p>　　(二)通話記錄47</p><p>　　(三)信箱管理53</p><p>　　五、課設(shè)總結(jié)

10、59</p><p><b>　　哈夫曼編碼與譯碼</b></p><p><b>　　問(wèn)題及功能分析</b></p><p><b>　　要求：</b></p><p>　　從某文本文件中統(tǒng)計(jì)其中字符使用頻率（由英語(yǔ)字母構(gòu)成），建立對(duì)應(yīng)的哈夫曼樹，設(shè)計(jì)哈夫曼編碼與譯碼方案，計(jì)

11、算壓縮比。</p><p><b>　　分析：</b></p><p>　　讀取并統(tǒng)計(jì)文本信息（統(tǒng)計(jì)每個(gè)字符的使用次數(shù)并計(jì)算使用頻率） 根據(jù)統(tǒng)計(jì)的信息設(shè)計(jì)編碼方案 譯碼 計(jì)算壓縮比。</p><p><b>　　詳細(xì)設(shè)計(jì)</b></p><p><b>　　讀取信息</b>

12、;</p><p>　　使用java.io.BufferedReader類讀取文本字符。</p><p><b>　　統(tǒng)計(jì)文本信息</b></p><p>　　需要統(tǒng)計(jì)的信息為字符的出現(xiàn)次數(shù)和文本的字符總數(shù)。</p><p>　　字符總數(shù)：每讀取一個(gè)字符，字符總數(shù)加1；</p><p><b

13、>　　字符出現(xiàn)次數(shù)：</b></p><p><b>　　特征：</b></p><p>　　每個(gè)字符對(duì)應(yīng)的次數(shù)隨著讀取的進(jìn)行可能會(huì)發(fā)生改變，屬于動(dòng)態(tài)變量；</p><p>　　不允許出現(xiàn)兩個(gè)存儲(chǔ)到相同的字符信息對(duì)象；</p><p>　　當(dāng)讀取到新的字符時(shí)，需要添加新的存儲(chǔ)字符信息的對(duì)象；</p

14、><p>　　每讀取到一個(gè)字符，需要對(duì)所有已經(jīng)讀取的字符進(jìn)行查找更新數(shù)據(jù)，查找頻繁。</p><p>　　分析：因?yàn)椴辉试S存儲(chǔ)重復(fù)的對(duì)象，因此應(yīng)該采用Set集合進(jìn)行存儲(chǔ)，由于查找更新數(shù)據(jù)比較頻繁，為提高效率，應(yīng)該采用Hash散列存儲(chǔ)結(jié)構(gòu)，綜上可得出結(jié)論：采用HashSet結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)效率最高。</p><p><b>　　設(shè)計(jì)編碼和譯碼方案</b>

15、</p><p>　　根據(jù)統(tǒng)計(jì)的信息：權(quán)值（頻率）進(jìn)行編碼和譯碼。</p><p><b>　　計(jì)算壓縮比</b></p><p>　　計(jì)算壓縮前和壓縮后的文件字節(jié)總數(shù)只比。</p><p><b>　　整體流程</b></p><p><b>　　程序?qū)崿F(xiàn)<

16、/b></p><p><b>　　匯總</b></p><p><b>　　具體實(shí)現(xiàn)代碼</b></p><p>　　com.gauze.Main</p><p>　　com.gauze.charstatistics.CharData</p><p>　　com.ga

17、uze.charstatistics.CharDataMapActor</p><p>　　com.gauze.charstatistics.CharReader</p><p>　　com.gauze.util.HaffmanNode</p><p>　　com.gauze.util.HaffmanTree</p><p><b>

18、;　　調(diào)試分析</b></p><p><b>　　統(tǒng)計(jì)英文文本：</b></p><p><b>　　統(tǒng)計(jì)含有中英文文本</b></p><p>　　查詢只含有字符串“AAAABBBCDDBBAAA”的文本（課本示例）：</p><p><b>　　（跟課本結(jié)論一樣）<

19、/b></p><p><b>　　手機(jī)信息管理</b></p><p><b>　　問(wèn)題及功能分析</b></p><p><b>　　功能要求：</b></p><p>　　對(duì)以下手機(jī)信息進(jìn)行有效存儲(chǔ)和管理</p><p>　　通訊錄管理，提供

20、顯示、修改、插入、刪除操作，提供查找和排序功能。</p><p>　　通話清單管理，分別給出已接、未接或打出、接入標(biāo)記，提供按姓名或時(shí)間排序等功能。</p><p>　　短信管理，將短信分別存儲(chǔ)在收件箱、發(fā)件箱、草稿箱中，提供對(duì)短信的批量刪除和按發(fā)送和接受時(shí)間的排序功能。</p><p><b>　　性能要求：</b></p>&

21、lt;p>　　通訊錄按姓名查找需要采用散列查找（可按姓名的拼音首字母散列）</p><p>　　排序要求采用快速排序或堆排序。</p><p><b>　　分析：</b></p><p>　　數(shù)據(jù)存儲(chǔ)：采用數(shù)據(jù)庫(kù)</p><p>　　使用框架：Hibernate</p><p>　　獲取名字

22、拼音首字母：使用Pinyin4J類包（內(nèi)含有可以獲取漢字拼音的方法）</p><p>　　GUI設(shè)計(jì)：使用MyEclipse、Eclipse或者Netbean進(jìn)行可視化設(shè)計(jì)</p><p>　　軟件分層：展現(xiàn)層、邏輯層、持久層</p><p><b>　　流程：</b></p><p><b>　　整體功能：&

23、lt;/b></p><p><b>　　通訊錄管理：</b></p><p><b>　　通話清單管理：</b></p><p><b>　　短信管理：</b></p><p><b>　　詳細(xì)設(shè)計(jì)</b></p><p>

24、<b>　　持久層</b></p><p>　　數(shù)據(jù)庫(kù)：采用SQL Server2005</p><p><b>　　數(shù)據(jù)庫(kù)詳細(xì)設(shè)計(jì)：</b></p><p><b>　　邏輯層</b></p><p>　　框架使用：采用Hibernate框架</p><p

25、><b>　　類包詳細(xì)設(shè)計(jì)：</b></p><p><b>　　算法設(shè)計(jì)</b></p><p><b>　　排序：</b></p><p>　　Contacts.java（通訊錄）、CallLog.java（通話記錄）、Messages.java（短信）類都繼承java.lang.Compa

26、rable接口，實(shí)現(xiàn)比較方法compareTo(Object obj)，由于CallLog.java還要實(shí)現(xiàn)多一個(gè)比較方法，所以添加一個(gè)繼承java.util.Comparator接口的內(nèi)部類。</p><p>　　Contacts：默認(rèn)按姓名進(jìn)行比較</p><p>　　CallLog：默認(rèn)按時(shí)間進(jìn)行比較，Comparator設(shè)置為按姓名進(jìn)行比較</p><p>

27、　　Messages：默認(rèn)按時(shí)間進(jìn)行比較</p><p>　　排序算法：采用堆排序算法</p><p>　　堆排序（HeapSort）是一樹形選擇排序。堆排序的特點(diǎn)是：在排序過(guò)程中，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系，在當(dāng)前無(wú)序區(qū)中選擇關(guān)鍵字最大（或最?。┑挠涗洝６雅判虻淖顗臅r(shí)間復(fù)雜度為O(nlogn)。堆序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數(shù)較多，所以堆排

28、序不適宜于記錄數(shù)較少的文件。堆排序是就地排序，輔助空間為O(1），它是不穩(wěn)定的排序方法。</p><p><b>　　查找：</b></p><p>　　查找算法：采用散列查找算法</p><p>　　散列是一種按關(guān)鍵字編址的存儲(chǔ)和檢索的高效方法。</p><p><b>　　具體設(shè)計(jì)：</b>&l

29、t;/p><p>　　散列函數(shù)：按姓名的拼音首字母編址進(jìn)行散列，如：小王 XW 、張三 ZS</p><p>　　解決沖突方法：對(duì)姓名直接進(jìn)行比較</p><p>　　查找流程：用戶輸入需要查找的姓名，比如：張三 將接收到的字符串信息進(jìn)行處理，轉(zhuǎn)換成“ZS” 調(diào)用字符串默認(rèn)的hashcode()方法獲得“ZS”的哈希碼 根據(jù)獲得的哈希碼在數(shù)據(jù)庫(kù)中進(jìn)行檢索（通訊

30、錄對(duì)象在存儲(chǔ)時(shí)，已經(jīng)將姓名的拼音首字母對(duì)應(yīng)的哈希碼值存儲(chǔ)在pinyin_tail屬性中，并在數(shù)據(jù)庫(kù)中建立了索引） 若查找到少于一個(gè)對(duì)象，直接返回查找結(jié)果；若查找到多個(gè)對(duì)象，進(jìn)一步進(jìn)行查找 調(diào)用對(duì)象的equals()方法進(jìn)行進(jìn)一步比較，按照姓名直接進(jìn)行比較 返回最終查找結(jié)果</p><p><b>　　增：</b></p><p>　　根據(jù)從Layer層接收的參數(shù)

31、新建瞬息對(duì)象調(diào)用DAO層方法進(jìn)行存儲(chǔ)</p><p><b>　　刪：</b></p><p>　　根據(jù)從Layer層接收的index參數(shù)獲取對(duì)應(yīng)托管對(duì)象調(diào)用DAO層方法進(jìn)行刪除</p><p><b>　　改：</b></p><p>　　根據(jù)從Layer層接收的index參數(shù)獲取對(duì)應(yīng)托管對(duì)象根據(jù)

32、從Layer層接收的信息對(duì)托管對(duì)象的信息進(jìn)行重新設(shè)置更改調(diào)用DAO層方法進(jìn)行存儲(chǔ)</p><p><b>　　存儲(chǔ)結(jié)構(gòu)：</b></p><p>　　對(duì)從持久層獲取的信息進(jìn)行臨時(shí)存儲(chǔ)采用java.util.ArrayList（線性表的順序?qū)崿F(xiàn)類）</p><p>　　分析：從持久層獲取的信息由于不需要進(jìn)行增刪改操作，只需要通過(guò)從layer層獲取

33、的index值進(jìn)行讀取數(shù)據(jù)，所以采用ArrayList進(jìn)行存儲(chǔ)的效率相對(duì)會(huì)比較高，可以進(jìn)行隨機(jī)讀取。</p><p><b>　　展示層</b></p><p><b>　　界面設(shè)計(jì)：</b></p><p><b>　　類包詳細(xì)設(shè)計(jì)：</b></p><p><b>

34、;　　主窗口：</b></p><p><b>　　添加通訊錄的窗口：</b></p><p><b>　　修改通訊錄的窗口：</b></p><p><b>　　查找通訊錄的窗口：</b></p><p><b>　　添加短信的窗口：</b>

35、</p><p>　　修改草稿箱信息的窗口：</p><p><b>　　關(guān)于對(duì)話框：</b></p><p><b>　　確認(rèn)刪除對(duì)話框：</b></p><p><b>　　程序?qū)崿F(xiàn)</b></p><p><b>　　排序功能：</

36、b></p><p>　　實(shí)現(xiàn)類：com.gauze.util.HeapSort</p><p><b>　　方法：</b></p><p><b>　　通訊錄管理之添加：</b></p><p><b>　　代碼：</b></p><p>　　a

37、dd(String name, String tel, String email)</p><p>　　save(Contacts transientInstance)</p><p><b>　　通訊錄管理之修改：</b></p><p><b>　　代碼：</b></p><p>　　alter

38、ContactsjButton1ActionPerformed(AlterContactsFrame fatherFrame, ActionEvent e)</p><p><b>　　通訊錄管理之排序</b></p><p><b>　　代碼：</b></p><p>　　sortByName(List list)<

39、;/p><p>　　compareTo(Object o)</p><p>　　maxheapSort(List<Comparable> table)</p><p><b>　　通訊錄管理之查找：</b></p><p><b>　　代碼：</b></p><p>

40、　　findByName(String name)</p><p>　　findByPingyingTail(Object pingyingTail)</p><p>　　getNormalFirstPingYing(String str)throws BadHanyuPinyinOutputFormatCombination</p><p>　　getHashCo

41、de(String str)</p><p>　　通話清單管理之按姓名排序：</p><p><b>　　代碼：</b></p><p>　　sortByName(List list)</p><p>　　getNameComparator()</p><p>　　compare(CallLog

42、o1, CallLog o2)</p><p>　　maxheapSort(List<Comparable> table,Comparator comparator)</p><p>　　通話清單AND短信管理之按時(shí)間排序：</p><p><b>　　代碼：</b></p><p>　　compareTo(

43、CallLog o)</p><p>　　compareTo(Object o)</p><p>　　jMenuItem14ActionPerformed(TelMainFrame fatherFrame,ActionEvent e)</p><p>　　minheapSort(List<Comparable> table,Comparator com

44、parator)</p><p><b>　　批量刪除：</b></p><p><b>　　代碼：</b></p><p>　　delete(int[] ids, int item)</p><p><b>　　調(diào)試分析</b></p><p><

45、;b>　　通訊錄管理</b></p><p><b>　　顯示界面：</b></p><p><b>　　添加通訊錄</b></p><p><b>　　刪除通訊錄</b></p><p><b>　　修改通訊錄</b></p>

46、;<p><b>　　查找通訊錄</b></p><p><b>　　按姓名排序</b></p><p><b>　　通話記錄</b></p><p><b>　　顯示</b></p><p><b>　　全部：</b>

47、</p><p><b>　　已撥：</b></p><p><b>　　已接：</b></p><p><b>　　未接：</b></p><p><b>　　刪除</b></p><p><b>　　按時(shí)間排序<

48、/b></p><p><b>　　按姓名排序</b></p><p><b>　　信箱管理</b></p><p><b>　　顯示</b></p><p><b>　　收件箱：</b></p><p><b>　

49、　發(fā)件箱：</b></p><p><b>　　草稿箱：</b></p><p><b>　　添加信箱</b></p><p>　　點(diǎn)擊發(fā)送保存在發(fā)件箱：</p><p>　　點(diǎn)擊取消保存在草稿箱：</p><p><b>　　刪除信箱</b>

50、;</p><p><b>　　修改草稿箱</b></p><p><b>　　按時(shí)間排序</b></p><p><b>　　課設(shè)總結(jié)</b></p><p>　　雖然在平常也試過(guò)去做一些小應(yīng)用，也參與做過(guò)項(xiàng)目，但真正認(rèn)真自己做課設(shè)時(shí)，卻總是遇到各種問(wèn)題。比如說(shuō)Hiberna

51、te框架session的管理，邏輯層與應(yīng)用層之間的分層感覺(jué)也不夠清晰。</p><p>　　我覺(jué)得數(shù)據(jù)結(jié)構(gòu)這門課程真的很重要，因?yàn)閷?duì)于不同的數(shù)據(jù)，采用不同的存儲(chǔ)結(jié)構(gòu)和不同的處理方法的效率也不盡相同，如何采用高效的存儲(chǔ)結(jié)構(gòu)和處理方法，是我們做程序時(shí)應(yīng)該重視的問(wèn)題。這一點(diǎn)，我曾經(jīng)切身體會(huì)過(guò)。之前做過(guò)一個(gè)項(xiàng)目，我嘗試去用List鏈表存儲(chǔ)上萬(wàn)條信息，結(jié)果在進(jìn)行查詢處理的時(shí)候，速度很慢……換了HashSet去存儲(chǔ)這些信息，