內(nèi)蒙古科技大學(xué)課程設(shè)計說明書 數(shù) 據(jù) 結(jié) 構(gòu)課程設(shè)計說明書題 目Huffman編碼和譯碼學(xué) 號1367111126姓 名楊科指導(dǎo)教師孫濤日 期2015.1.6內(nèi)蒙古科技大學(xué)課程設(shè)計任務(wù)書課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計題目Huffman編碼和譯碼指導(dǎo)教師孫濤時間2014年秋學(xué)期第15周至第19周一、教學(xué)要求1. 掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨(dú)立分析和設(shè)計能力2. 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能3. 提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能力4. 訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)二、設(shè)計資料及參數(shù)每個學(xué)生在教師提供的課程設(shè)計題目中任意選擇一題，獨(dú)立完成，題目選定后不可更換。Huffman編碼和譯碼根據(jù)給定的字符集和各字符的頻率值，求出其中給定字符Huffman編碼，并針對一段文本（定義在該字符集上）進(jìn)行編碼和譯碼，實現(xiàn)一個Huffman編碼/譯碼系統(tǒng)。要求設(shè)計類（或類模板）來描述Huffman樹及其操作，包含必要的構(gòu)造函數(shù)和析構(gòu)函數(shù)，以及其他能夠完成如下功能的成員函數(shù)：v 求Huffman編碼v 輸入字符串，求出編碼v 輸入一段編碼，實現(xiàn)譯碼 并設(shè)計主函數(shù)測試該類。三、設(shè)計要求及成果1. 分析課程設(shè)計題目的要求2. 寫出詳細(xì)設(shè)計說明3. 編寫程序代碼，調(diào)試程序使其能正確運(yùn)行4. 設(shè)計完成的軟件要便于操作和使用5. 設(shè)計完成后提交課程設(shè)計報告四、進(jìn)度安排資料查閱與討論（1天）系統(tǒng)分析（2天）系統(tǒng)的開發(fā)與測試（5天）編寫課程設(shè)計說明書和驗收（2天）五、評分標(biāo)準(zhǔn)1. 根據(jù)平時上機(jī)考勤、表現(xiàn)和進(jìn)度，教師將每天點名和檢查2. 根據(jù)課程設(shè)計完成情況，必須有可運(yùn)行的軟件。3. 根據(jù)課程設(shè)計報告的質(zhì)量，如有雷同，則所有雷同的所有人均判為不及格。4. 根據(jù)答辯的情況，應(yīng)能夠以清晰的思路和準(zhǔn)確、簡練的語言敘述自己的設(shè)計和回答教師的提問六、參考資料1數(shù)據(jù)結(jié)構(gòu) （C語言版）嚴(yán)蔚敏、吳偉民 主編 清華大學(xué)出版社 2004.112數(shù)據(jù)結(jié)構(gòu)課程設(shè)計案例精編（用C/C+描述），李建學(xué) 等 編著，清華大學(xué)出版社 2007.23.數(shù)據(jù)結(jié)構(gòu):用面向?qū)ο蠓椒ㄅcC+語言描述，殷人昆 主編，清華大學(xué)出版社 2007目 錄目 錄III第一章 需求分析41.1引言41.2任務(wù)概述41.3數(shù)據(jù)描述41.4功能需求51.5性能需求51.6運(yùn)行需求5第二章概要設(shè)計62.1總體設(shè)計6（一） 設(shè)計目的：6（二） 函數(shù)劃分72.2數(shù)據(jù)類型設(shè)計（或數(shù)據(jù)結(jié)構(gòu)設(shè)計）72.3接口設(shè)計72.4運(yùn)行界面設(shè)計8第三章詳細(xì)設(shè)計93.1輸入、創(chuàng)建模塊設(shè)計93.2編碼模塊設(shè)計103.3譯碼模塊設(shè)計113.4主函數(shù)模塊設(shè)計13第四章測試分析154.1測試程序執(zhí)行情況154.2出現(xiàn)的問題和解決的方法17第五章課程設(shè)計總結(jié)18附錄：程序代碼19參考文獻(xiàn)2626第一章 需求分析1.1 引言目前，進(jìn)行快速遠(yuǎn)距離通信的主要手段是電報，即將需傳送的文字轉(zhuǎn)化成由二級制的字符組成的字符串。利用哈夫曼樹求得的用于通信的二進(jìn)制編碼稱為哈夫曼編碼。樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個對應(yīng)的字符的編碼，這就是哈夫曼編碼。通常我們把數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報通信是傳遞文字的二進(jìn)制碼形式的字符串。但在信息傳遞時，總希望總長度盡可能最短，即采用最短碼。因此，哈夫曼樹在通信、編碼和數(shù)據(jù)壓縮等技術(shù)領(lǐng)域有著廣泛的應(yīng)用。此設(shè)計說明書是對編碼/譯碼系統(tǒng)開發(fā)的一個初步的分析說明性文檔，旨在通過該文檔清晰的闡述系統(tǒng)的實際功能，方便系統(tǒng)開發(fā)人員對系統(tǒng)的理解以及與用戶的溝通。文檔相關(guān)說明部分在目錄部分已全部涵蓋，閱讀此文檔的相關(guān)人員可以通過目錄索引找到相應(yīng)部分予以閱讀。1.2 任務(wù)概述Huffman編碼和譯碼根據(jù)給定的字符集和各字符的頻率值，求出其中給定字符Huffman編碼，并針對一段文本（定義在該字符集上）進(jìn)行編碼和譯碼，實現(xiàn)一個Huffman編碼/譯碼系統(tǒng)。1.3 數(shù)據(jù)描述該哈夫曼編碼/譯碼系統(tǒng)程序中的數(shù)據(jù)主要有：哈夫曼樹、哈夫曼編碼，哈夫曼譯碼等。1.4 功能需求（1）. 輸入模塊：輸入各個元素，建立哈夫曼樹；（2）. 編碼模塊：將輸入的各個元素建立哈夫曼樹，進(jìn)行編碼；（3）. 譯碼模塊：將電文以0或1輸入后，根據(jù)之前的哈夫曼樹進(jìn)行譯碼；（4）. 輸出模塊：建立好的哈夫曼樹、編碼、譯碼進(jìn)行輸出。1.5 性能需求（1）. 要求該編碼/譯碼系統(tǒng)具有一定的可擴(kuò)展性以便適應(yīng)發(fā)展，且便于維護(hù)；（2）. 要求該編碼/譯碼系統(tǒng)便于使用，使用步驟簡易明了。1.6 運(yùn)行需求基于windows平臺下的窗口圖形界面軟件，運(yùn)行主界面為windows的經(jīng)典運(yùn)行界面，采用多文檔界面，從而使程序更加美觀，整齊有序，簡易操作。軟件運(yùn)行基于windows平臺上的xp,Vista,win7等第二章 概要設(shè)計2.1 總體設(shè)計（一） 設(shè)計目的：（1） 掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨(dú)立分析和設(shè)計能力；（2） 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；（3） 提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能力；（4） 訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。主菜單根據(jù)輸入電文進(jìn)行譯碼根據(jù)哈夫曼樹進(jìn)行編碼輸入元素建立哈夫曼樹圖2.1：程序主體設(shè)計圖（二） 函數(shù)劃分該程序有一個主函數(shù)和多個子函數(shù)，主函數(shù)完成對子函數(shù)的調(diào)用，各子函數(shù)實現(xiàn)相應(yīng)的功能。（1） 結(jié)點的開辟。（2） 實現(xiàn)對輸入字符串中出現(xiàn)的不同字符及其出現(xiàn)字?jǐn)?shù)的信息記錄。（3） 用葉子結(jié)點構(gòu)造赫夫曼樹。（4） 獲得構(gòu)造的赫夫曼樹中所有葉子結(jié)點的元素及其赫夫曼編碼。（5） 輸出各葉子結(jié)點元素及其對應(yīng)的赫夫曼編碼。（6） 輸出輸入的字符串的赫夫曼編碼。（7） 調(diào)用各子函數(shù)2.2 數(shù)據(jù)類型設(shè)計（或數(shù)據(jù)結(jié)構(gòu)設(shè)計）表2.1：數(shù)據(jù)類型設(shè)計數(shù)據(jù)數(shù)據(jù)類型權(quán)值整數(shù)數(shù)據(jù)雙親整數(shù)數(shù)據(jù)左孩子整數(shù)數(shù)據(jù)右孩子整數(shù)數(shù)據(jù)struct結(jié)構(gòu)體類型2.3 接口設(shè)計表2.1：函數(shù)列表函數(shù)名函數(shù)格式 /即函數(shù)首部函數(shù)功能structtypedef樹結(jié)點的結(jié)構(gòu)定義樹結(jié)點的存儲定義HuffmanCreateint創(chuàng)建哈夫曼樹Encodingvoid對創(chuàng)建好的哈夫曼樹進(jìn)行編碼Decodingvoid根據(jù)創(chuàng)建好的哈夫曼樹進(jìn)行譯碼2.4 運(yùn)行界面設(shè)計圖2.1：運(yùn)行界面設(shè)計第三章 詳細(xì)設(shè)計3.1 輸入、創(chuàng)建模塊設(shè)計輸入、創(chuàng)建哈夫曼樹：int HuffmanCreate(HuffNode*ht)int i,k,n,m1,m2,p1,p2;printf(請輸入元素個數(shù)n);scanf(%d,&n);for(i=1;i=n;i+) /輸入結(jié)點值和信息getchar();/接收回車printf(第%d個元素的:n結(jié)點值:,i);scanf(%c,&hti.data);printf(權(quán)值:);scanf(%d,&hti.weight);for(i=1;i=2*n-1;i+) /對數(shù)組初始化hti.parent=hti.left=hti.right=0;for(i=n+1;i=2*n-1;i+)m1=m2=32767; /初始化，令m1,m2為整數(shù)最大值p1=p2=1;for(k=1;k=i-1;k+) /從數(shù)組中找if(htk.parent=0) /parent為零切權(quán)值最小的兩個結(jié)點if(htk.weightm1)m2=m1; /令m1為最小權(quán)值p2=p1; /p1 為最小權(quán)值的位置m1=htk.weight; /m1存放最小權(quán)值p1=k;else if(htk.weightm2)m2=htk.weight; /m2 為次小權(quán)值p2=k; /p2為次小權(quán)值所在位置htp1.parent=i; /i分別付給下標(biāo)為p1，p2的數(shù)組中htp2.parent=i;hti.weight=m1+m2; /新節(jié)點權(quán)值為最小權(quán)值和次小權(quán)值之和hti.left=p1; /p1為新節(jié)點的左孩子hti.right=p2; /p2為新節(jié)點的右孩子printf(哈夫曼樹已成功建立!n);return n; /返回結(jié)點數(shù)3.2 編碼模塊設(shè)計根據(jù)創(chuàng)建好的哈夫曼樹，進(jì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; /從葉結(jié)點開始向上f=hti.parent;while(f!=0) /到樹根結(jié)束if(htf.left=c)d.cd-d.start=0; /規(guī)定左數(shù)代碼為零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); /先輸出結(jié)點for(k=hcdi.start;k=n;k+) /在輸出對應(yīng)編碼printf(%c,hcdi.cdk);printf(n);3.3 譯碼模塊設(shè)計根據(jù)已有的哈夫曼樹和提供的電文，進(jìn)行譯碼：void Decoding(HuffNode ht,HuffCode hcd,int n)int f,m,k;DataType c,ch200; /c接收文件,ch存儲printf(請輸入電文(0 or 1),以#結(jié)束n);c=getchar();k=1;while(c!=#) /單字符循環(huán)輸入，以#結(jié)束chk=c; /單字符一次存入ch字串中c=getchar();k=k+1; /ch 下地址后移m=k; /標(biāo)記數(shù)組存儲末位位置f=2*n-1;k=1;/k 記錄電文字符個數(shù)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;第四章 測試分析4.1 測試程序執(zhí)行情況圖4.1：選擇建立哈夫曼樹圖4.2：輸入需建立哈夫曼樹的元素個數(shù)圖4.3：成功建立哈夫曼樹圖4.4：根據(jù)建立好的哈夫曼樹，進(jìn)行編碼圖4.5：根據(jù)建立好的哈夫曼樹以及輸入的電文，進(jìn)行譯碼4.2 出現(xiàn)的問題和解決的方法1. 程序的語句結(jié)束后，忘記打分號：程序運(yùn)行出現(xiàn)錯誤后，加上分號；2. 輸入電文時，誤將0和1輸成其他數(shù)據(jù)，結(jié)果程序出現(xiàn)將其他數(shù)據(jù)隨機(jī)當(dāng)做0或1。第五章 課程設(shè)計總結(jié)在課程設(shè)計過程中，我們每個人選擇一個課題，認(rèn)真研究，根據(jù)課堂教授內(nèi)容，借助書本，自己動手實踐。這樣不但有助于我們消化課堂所講解的內(nèi)容，還可以增強(qiáng)我們的獨(dú)立思考能力和動手能力；通過編寫實驗代碼和調(diào)試運(yùn)行，我們可以逐步積累調(diào)試C程序的經(jīng)驗并逐漸培養(yǎng)我們的編程能力、用計算機(jī)解決實際問題的能力。在課程設(shè)計過程中，我們不但有自己的獨(dú)立思考，還借助各種參考文獻(xiàn)來幫助我們完成系統(tǒng)。更為重要的是，我們同學(xué)之間加強(qiáng)了交流，在對問題的認(rèn)識方面可以交換不同的意見。在寫代碼前，首先，對問題進(jìn)行了分析，明確了目標(biāo)，列出了大的框架，然后逐漸細(xì)化，劃分出不同的功能模塊，由具體的子函數(shù)去實現(xiàn)，先在紙上編寫代碼，寫好后進(jìn)行了反復(fù)的邏輯推理，發(fā)現(xiàn)并解決邏輯問題，然后，上機(jī)調(diào)試，方法是：一個一個功能模塊分開進(jìn)行調(diào)試，主要看調(diào)試的模塊能否達(dá)到預(yù)期的結(jié)果，這樣可以縮小排錯的范圍，便以糾錯和提高編程的效率，當(dāng)每個功能模塊都調(diào)試好后，就把各個部分組合起來，再進(jìn)行調(diào)試，主要檢查各函數(shù)接口是否正確，當(dāng)達(dá)到預(yù)期的結(jié)果，調(diào)試結(jié)束，編程部分完成，然后按實驗要求完成實驗報告。數(shù)據(jù)結(jié)構(gòu)課程具有比較強(qiáng)的理論性，同時也具有較強(qiáng)的可應(yīng)用性和實踐性。課程設(shè)計是一個重要的教學(xué)環(huán)節(jié)。我們在一般情況下都能夠重視實驗環(huán)節(jié)，但是容易忽略實驗的總結(jié)，忽略實驗報告的撰寫。通過這次實驗讓我們明白：作為一名大學(xué)生必須嚴(yán)格訓(xùn)練分析總結(jié)能力、書面表達(dá)能力。需要逐步培養(yǎng)書寫科學(xué)實驗報告以及科技論文的能力。只有這樣，我們的綜合素質(zhì)才會有好的提高。附錄：程序代碼#include#include#include#include#include#include#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR -1#define INFEASIBLE -1typedef char DataType;#define MAXNUM 50typedef struct /huffman 樹結(jié)點的結(jié)構(gòu)定義DataType data; /數(shù)據(jù)用字符表示int weight; /權(quán)值int parent; /雙親int left; /左孩子int right; /右孩子HuffNode;typedef struct/huffman 樹結(jié)點的存儲定義DataType cdMAXNUM; /存放編碼位串int start; /編碼起始位置HuffCode;int HuffmanCreate(HuffNode*ht)int i,k,n,m1,m2,p1,p2;printf(請輸入元素個數(shù)n);scanf(%d,&n);for(i=1;i=n;i+) /輸入結(jié)點值和信息getchar(); /接收回車printf(第%d個元素的:n結(jié)點值:,i);scanf(%c,&hti.data);printf(權(quán)值:);scanf(%d,&hti.weight);for(i=1;i=2*n-1;i+) /對數(shù)組初始化hti.parent=hti.left=hti.right=0;for(i=n+1;i=2*n-1;i+)m1=m2=32767; /初始化，令m1,m2為整數(shù)最大值p1=p2=1;for(k=1;k=i-1;k+) /從數(shù)組中找if(htk.parent=0) /parent為零切權(quán)值最小的兩個結(jié)點if(htk.weightm1)m2=m1; /令m1為最小權(quán)值p2=p1; /p1 為最小權(quán)值的位置m1=htk.weight; /m1存放最小權(quán)值p1=k;else if(htk.weightm2)m2=htk.weight; /m2 為次小權(quán)值p2=k; /p2為次小權(quán)值所在位置htp1.parent=i; /i分別付給下標(biāo)為p1，p2的數(shù)組中htp2.parent=i;hti.weight=m1+m2; /新節(jié)點權(quán)值為最小權(quán)值和次小權(quán)值之和hti.left=p1;/p1為新節(jié)點的左孩子hti.right=p2;/p2為新節(jié)點的右孩子printf(哈夫曼樹已成功建立!n);return n; /返回結(jié)點數(shù)/編碼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; /從葉結(jié)點開始向上f=hti.parent;while(f!=0) /到樹根結(jié)束if(htf.left=c)d.cd-d.start=0; /規(guī)定左數(shù)代碼為零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); /先輸出結(jié)點for(k=hcdi.start;k=n;k+) /在輸出對應(yīng)編碼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),以#結(jié)束n);c=getchar();k=1;while(c!=#) /單字符循環(huán)輸入，以#結(jié)束chk=c; /單字符一次存入ch字串中c=getchar();k=k+1; /ch下地址后移m=k; /標(biāo)記數(shù)組存儲末位位置f=2*n-1;k=1; /k記錄電文字符個數(shù)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;參考文獻(xiàn)1. 數(shù)據(jù)結(jié)構(gòu) （C語言版）嚴(yán)蔚敏、吳偉民 主編 清華大學(xué)出版社 2. 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計案例精編（用C/C+描述），李建學(xué) 等 編著，清華大學(xué)出版社3. 數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程（修訂版）嚴(yán)蔚敏、陳文博 編著 清華大學(xué)出版社