《數據結構哈夫曼報告.doc》由會員分享，可在線閱讀，更多相關《數據結構哈夫曼報告.doc（26頁珍藏版）》請在裝配圖網上搜索。

1、內蒙古科技大學課程設計說明書 數 據 結 構課程設計說明書題 目Huffman編碼和譯碼學 號1367111126姓 名楊科指導教師孫濤日 期2015.1.6內蒙古科技大學課程設計任務書課程名稱數據結構課程設計設計題目Huffman編碼和譯碼指導教師孫濤時間2014年秋學期第15周至第19周一、教學要求1. 掌握數據結構與算法的設計方法，具備初步的獨立分析和設計能力2. 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技能3. 提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力4. 訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應具備的科學的工作方法

2、和作風二、設計資料及參數每個學生在教師提供的課程設計題目中任意選擇一題，獨立完成，題目選定后不可更換。Huffman編碼和譯碼根據給定的字符集和各字符的頻率值，求出其中給定字符Huffman編碼，并針對一段文本（定義在該字符集上）進行編碼和譯碼，實現(xiàn)一個Huffman編碼/譯碼系統(tǒng)。要求設計類（或類模板）來描述Huffman樹及其操作，包含必要的構造函數和析構函數，以及其他能夠完成如下功能的成員函數：v 求Huffman編碼v 輸入字符串，求出編碼v 輸入一段編碼，實現(xiàn)譯碼 并設計主函數測試該類。三、設計要求及成果1. 分析課程設計題目的要求2. 寫出詳細設計說明3. 編寫程序代碼，調試程序使

3、其能正確運行4. 設計完成的軟件要便于操作和使用5. 設計完成后提交課程設計報告四、進度安排資料查閱與討論（1天）系統(tǒng)分析（2天）系統(tǒng)的開發(fā)與測試（5天）編寫課程設計說明書和驗收（2天）五、評分標準1. 根據平時上機考勤、表現(xiàn)和進度，教師將每天點名和檢查2. 根據課程設計完成情況，必須有可運行的軟件。3. 根據課程設計報告的質量，如有雷同，則所有雷同的所有人均判為不及格。4. 根據答辯的情況，應能夠以清晰的思路和準確、簡練的語言敘述自己的設計和回答教師的提問六、參考資料1數據結構 （C語言版）嚴蔚敏、吳偉民 主編 清華大學出版社 2004.112數據結構課程設計案例精編（用C/C+描述），李建

4、學 等 編著，清華大學出版社 2007.23.數據結構:用面向對象方法與C+語言描述，殷人昆 主編，清華大學出版社 2007目 錄目 錄III第一章 需求分析41.1引言41.2任務概述41.3數據描述41.4功能需求51.5性能需求51.6運行需求5第二章概要設計62.1總體設計6（一） 設計目的：6（二） 函數劃分72.2數據類型設計（或數據結構設計）72.3接口設計72.4運行界面設計8第三章詳細設計93.1輸入、創(chuàng)建模塊設計93.2編碼模塊設計103.3譯碼模塊設計113.4主函數模塊設計13第四章測試分析154.1測試程序執(zhí)行情況154.2出現(xiàn)的問題和解決的方法17第五章課程設計總結

5、18附錄：程序代碼19參考文獻2626第一章 需求分析1.1 引言目前，進行快速遠距離通信的主要手段是電報，即將需傳送的文字轉化成由二級制的字符組成的字符串。利用哈夫曼樹求得的用于通信的二進制編碼稱為哈夫曼編碼。樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個對應的字符的編碼，這就是哈夫曼編碼。通常我們把數據壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報通信是傳遞文字的二進制碼形式的字符串。但在信息傳遞時，總希望總長度盡可能最短，即采用最短碼。因此，哈夫曼樹在通信、編碼和數據壓縮等技術

6、領域有著廣泛的應用。此設計說明書是對編碼/譯碼系統(tǒng)開發(fā)的一個初步的分析說明性文檔，旨在通過該文檔清晰的闡述系統(tǒng)的實際功能，方便系統(tǒng)開發(fā)人員對系統(tǒng)的理解以及與用戶的溝通。文檔相關說明部分在目錄部分已全部涵蓋，閱讀此文檔的相關人員可以通過目錄索引找到相應部分予以閱讀。1.2 任務概述Huffman編碼和譯碼根據給定的字符集和各字符的頻率值，求出其中給定字符Huffman編碼，并針對一段文本（定義在該字符集上）進行編碼和譯碼，實現(xiàn)一個Huffman編碼/譯碼系統(tǒng)。1.3 數據描述該哈夫曼編碼/譯碼系統(tǒng)程序中的數據主要有：哈夫曼樹、哈夫曼編碼，哈夫曼譯碼等。1.4 功能需求（1）. 輸入模塊：輸入各個

7、元素，建立哈夫曼樹；（2）. 編碼模塊：將輸入的各個元素建立哈夫曼樹，進行編碼；（3）. 譯碼模塊：將電文以0或1輸入后，根據之前的哈夫曼樹進行譯碼；（4）. 輸出模塊：建立好的哈夫曼樹、編碼、譯碼進行輸出。1.5 性能需求（1）. 要求該編碼/譯碼系統(tǒng)具有一定的可擴展性以便適應發(fā)展，且便于維護；（2）. 要求該編碼/譯碼系統(tǒng)便于使用，使用步驟簡易明了。1.6 運行需求基于windows平臺下的窗口圖形界面軟件，運行主界面為windows的經典運行界面，采用多文檔界面，從而使程序更加美觀，整齊有序，簡易操作。軟件運行基于windows平臺上的xp,Vista,win7等第二章 概要設計2.1

8、總體設計（一） 設計目的：（1） 掌握數據結構與算法的設計方法，具備初步的獨立分析和設計能力；（2） 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技能；（3） 提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；（4） 訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應具備的科學的工作方法和作風。主菜單根據輸入電文進行譯碼根據哈夫曼樹進行編碼輸入元素建立哈夫曼樹圖2.1：程序主體設計圖（二） 函數劃分該程序有一個主函數和多個子函數，主函數完成對子函數的調用，各子函數實現(xiàn)相應的功能。（1） 結點的開辟。（2） 實現(xiàn)對輸入字符串中出現(xiàn)的不同字符及其出現(xiàn)

9、字數的信息記錄。（3） 用葉子結點構造赫夫曼樹。（4） 獲得構造的赫夫曼樹中所有葉子結點的元素及其赫夫曼編碼。（5） 輸出各葉子結點元素及其對應的赫夫曼編碼。（6） 輸出輸入的字符串的赫夫曼編碼。（7） 調用各子函數2.2 數據類型設計（或數據結構設計）表2.1：數據類型設計數據數據類型權值整數數據雙親整數數據左孩子整數數據右孩子整數數據struct結構體類型2.3 接口設計表2.1：函數列表函數名函數格式 /即函數首部函數功能structtypedef樹結點的結構定義樹結點的存儲定義HuffmanCreateint創(chuàng)建哈夫曼樹Encodingvoid對創(chuàng)建好的哈夫曼樹進行編碼Decoding

10、void根據創(chuàng)建好的哈夫曼樹進行譯碼2.4 運行界面設計圖2.1：運行界面設計第三章 詳細設計3.1 輸入、創(chuàng)建模塊設計輸入、創(chuàng)建哈夫曼樹：int HuffmanCreate(HuffNode*ht)int i,k,n,m1,m2,p1,p2;printf(請輸入元素個數n);scanf(%d,&n);for(i=1;i=n;i+) /輸入結點值和信息getchar();/接收回車printf(第%d個元素的:n結點值:,i);scanf(%c,&hti.data);printf(權值:);scanf(%d,&hti.weight);for(i=1;i=2*n-1;i+) /對數組初始化hti

11、.parent=hti.left=hti.right=0;for(i=n+1;i=2*n-1;i+)m1=m2=32767; /初始化，令m1,m2為整數最大值p1=p2=1;for(k=1;k=i-1;k+) /從數組中找if(htk.parent=0) /parent為零切權值最小的兩個結點if(htk.weightm1)m2=m1; /令m1為最小權值p2=p1; /p1 為最小權值的位置m1=htk.weight; /m1存放最小權值p1=k;else if(htk.weightm2)m2=htk.weight; /m2 為次小權值p2=k; /p2為次小權值所在位置htp1.pare

12、nt=i; /i分別付給下標為p1，p2的數組中htp2.parent=i;hti.weight=m1+m2; /新節(jié)點權值為最小權值和次小權值之和hti.left=p1; /p1為新節(jié)點的左孩子hti.right=p2; /p2為新節(jié)點的右孩子printf(哈夫曼樹已成功建立!n);return n; /返回結點數3.2 編碼模塊設計根據創(chuàng)建好的哈夫曼樹，進行編碼：void Encoding(HuffNode ht,HuffCode hcd,int n)HuffCode d;int i,k,f,c;for(i=1;i=n;i+)/對所有節(jié)點循環(huán)d.start=n+1; /起始地點c=i; /

13、從葉結點開始向上f=hti.parent;while(f!=0) /到樹根結束if(htf.left=c)d.cd-d.start=0; /規(guī)定左數代碼為零elsed.cd-d.start=1; /規(guī)定右樹代碼為一c=f;/c為孩子位置f=htf.parent; /f指雙親位置hcdi=d;printf(輸出哈夫曼編碼:n);for(i=1;i=n;i+)printf(%c:,hti.data); /先輸出結點for(k=hcdi.start;k=n;k+) /在輸出對應編碼printf(%c,hcdi.cdk);printf(n);3.3 譯碼模塊設計根據已有的哈夫曼樹和提供的電文，進行譯碼

14、：void Decoding(HuffNode ht,HuffCode hcd,int n)int f,m,k;DataType c,ch200; /c接收文件,ch存儲printf(請輸入電文(0 or 1),以#結束n);c=getchar();k=1;while(c!=#) /單字符循環(huán)輸入，以#結束chk=c; /單字符一次存入ch字串中c=getchar();k=k+1; /ch 下地址后移m=k; /標記數組存儲末位位置f=2*n-1;k=1;/k 記錄電文字符個數printf(輸出哈夫曼譯碼:n);while(k=1&select=4)if(select!=1&select!=4

15、&flag=0)printf(請先建立哈夫曼樹在選擇其他功能!n);continue;flag=TRUE;switch(select) case 1:n=HuffmanCreate(ht);break;case 2:Encoding(ht,hcd,n);break;case 3:Decoding(ht,hcd,n);break;case 4:exit(0);elseprintf(請重新輸入!n);return 0;第四章 測試分析4.1 測試程序執(zhí)行情況圖4.1：選擇建立哈夫曼樹圖4.2：輸入需建立哈夫曼樹的元素個數圖4.3：成功建立哈夫曼樹圖4.4：根據建立好的哈夫曼樹，進行編碼圖4.5：根

16、據建立好的哈夫曼樹以及輸入的電文，進行譯碼4.2 出現(xiàn)的問題和解決的方法1. 程序的語句結束后，忘記打分號：程序運行出現(xiàn)錯誤后，加上分號；2. 輸入電文時，誤將0和1輸成其他數據，結果程序出現(xiàn)將其他數據隨機當做0或1。第五章 課程設計總結在課程設計過程中，我們每個人選擇一個課題，認真研究，根據課堂教授內容，借助書本，自己動手實踐。這樣不但有助于我們消化課堂所講解的內容，還可以增強我們的獨立思考能力和動手能力；通過編寫實驗代碼和調試運行，我們可以逐步積累調試C程序的經驗并逐漸培養(yǎng)我們的編程能力、用計算機解決實際問題的能力。在課程設計過程中，我們不但有自己的獨立思考，還借助各種參考文獻來幫助我們完

17、成系統(tǒng)。更為重要的是，我們同學之間加強了交流，在對問題的認識方面可以交換不同的意見。在寫代碼前，首先，對問題進行了分析，明確了目標，列出了大的框架，然后逐漸細化，劃分出不同的功能模塊，由具體的子函數去實現(xiàn)，先在紙上編寫代碼，寫好后進行了反復的邏輯推理，發(fā)現(xiàn)并解決邏輯問題，然后，上機調試，方法是：一個一個功能模塊分開進行調試，主要看調試的模塊能否達到預期的結果，這樣可以縮小排錯的范圍，便以糾錯和提高編程的效率，當每個功能模塊都調試好后，就把各個部分組合起來，再進行調試，主要檢查各函數接口是否正確，當達到預期的結果，調試結束，編程部分完成，然后按實驗要求完成實驗報告。數據結構課程具有比較強的理論性

18、，同時也具有較強的可應用性和實踐性。課程設計是一個重要的教學環(huán)節(jié)。我們在一般情況下都能夠重視實驗環(huán)節(jié)，但是容易忽略實驗的總結，忽略實驗報告的撰寫。通過這次實驗讓我們明白：作為一名大學生必須嚴格訓練分析總結能力、書面表達能力。需要逐步培養(yǎng)書寫科學實驗報告以及科技論文的能力。只有這樣，我們的綜合素質才會有好的提高。附錄：程序代碼#include#include#include#include#include#include#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR -1#define INFEASIB

19、LE -1typedef char DataType;#define MAXNUM 50typedef struct /huffman 樹結點的結構定義DataType data; /數據用字符表示int weight; /權值int parent; /雙親int left; /左孩子int right; /右孩子HuffNode;typedef struct/huffman 樹結點的存儲定義DataType cdMAXNUM; /存放編碼位串int start; /編碼起始位置HuffCode;int HuffmanCreate(HuffNode*ht)int i,k,n,m1,m2,p1,

20、p2;printf(請輸入元素個數n);scanf(%d,&n);for(i=1;i=n;i+) /輸入結點值和信息getchar(); /接收回車printf(第%d個元素的:n結點值:,i);scanf(%c,&hti.data);printf(權值:);scanf(%d,&hti.weight);for(i=1;i=2*n-1;i+) /對數組初始化hti.parent=hti.left=hti.right=0;for(i=n+1;i=2*n-1;i+)m1=m2=32767; /初始化，令m1,m2為整數最大值p1=p2=1;for(k=1;k=i-1;k+) /從數組中找if(htk

21、.parent=0) /parent為零切權值最小的兩個結點if(htk.weightm1)m2=m1; /令m1為最小權值p2=p1; /p1 為最小權值的位置m1=htk.weight; /m1存放最小權值p1=k;else if(htk.weightm2)m2=htk.weight; /m2 為次小權值p2=k; /p2為次小權值所在位置htp1.parent=i; /i分別付給下標為p1，p2的數組中htp2.parent=i;hti.weight=m1+m2; /新節(jié)點權值為最小權值和次小權值之和hti.left=p1;/p1為新節(jié)點的左孩子hti.right=p2;/p2為新節(jié)點的

22、右孩子printf(哈夫曼樹已成功建立!n);return n; /返回結點數/編碼void Encoding(HuffNode ht,HuffCode hcd,int n)HuffCode d;int i,k,f,c;for(i=1;i=n;i+) /對所有節(jié)點循環(huán)d.start=n+1; /起始地點c=i; /從葉結點開始向上f=hti.parent;while(f!=0) /到樹根結束if(htf.left=c)d.cd-d.start=0; /規(guī)定左數代碼為零elsed.cd-d.start=1; /規(guī)定右樹代碼為一c=f; /c為孩子位置f=htf.parent; /f指雙親位置hc

23、di=d;printf(輸出哈夫曼編碼:n);for(i=1;i=n;i+)printf(%c:,hti.data); /先輸出結點for(k=hcdi.start;k=n;k+) /在輸出對應編碼printf(%c,hcdi.cdk);printf(n);/譯碼void Decoding(HuffNode ht,HuffCode hcd,int n)int f,m,k;DataType c,ch200; /c接收文件,ch存儲printf(請輸入電文(0 or 1),以#結束n);c=getchar();k=1;while(c!=#) /單字符循環(huán)輸入，以#結束chk=c; /單字符一次存入

24、ch字串中c=getchar();k=k+1; /ch下地址后移m=k; /標記數組存儲末位位置f=2*n-1;k=1; /k記錄電文字符個數printf(輸出哈夫曼譯碼:n);while(k=1&select=4)if(select!=1&select!=4&flag=0)printf(請先建立哈夫曼樹在選擇其他功能!n);continue;flag=TRUE;switch(select)case 1:n=HuffmanCreate(ht);break;case 2:Encoding(ht,hcd,n);break;case 3:Decoding(ht,hcd,n);break;case 4:exit(0);elseprintf(請重新輸入!n);return 0;參考文獻1. 數據結構 （C語言版）嚴蔚敏、吳偉民 主編 清華大學出版社 2. 數據結構課程設計案例精編（用C/C+描述），李建學 等 編著，清華大學出版社3. 數據結構及應用算法教程（修訂版）嚴蔚敏、陳文博 編著 清華大學出版社