哈夫曼編碼課程設(shè)計報告

1、課程設(shè)計(論文)任務(wù)書 軟件 學(xué)院 軟件+電氣 專業(yè) 1 班 一、課程設(shè)計(論文)題目 哈夫曼樹及其編碼 二、課程設(shè)計(論文)工作自 2015年 1 月 5 日起至 2015年 1 月 9日止。三、課程設(shè)計(論文) 地點(diǎn): 創(chuàng)新大樓303,305 四、課程設(shè)計(論文)內(nèi)容要求：1課程設(shè)計的目的為了配合數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)，使學(xué)生能更深刻的領(lǐng)會數(shù)據(jù)結(jié)構(gòu)課程的重要性，特開設(shè)此課程設(shè)計；編寫一些在特定數(shù)據(jù)結(jié)構(gòu)上的算法，通過上機(jī)調(diào)試，更好的掌握各種數(shù)據(jù)結(jié)構(gòu)及其特點(diǎn)，培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)理論知識解決復(fù)雜實(shí)際問題的實(shí)踐能力、研究性學(xué)習(xí)能力和團(tuán)隊(duì)合作能力。2課程設(shè)計的任務(wù)及要求1）基本要求（1）課程設(shè)計前必須

2、選定課程設(shè)計題目，并認(rèn)真進(jìn)行需求分析與系統(tǒng)設(shè)計； （2）上機(jī)調(diào)試之前要認(rèn)真準(zhǔn)備實(shí)驗(yàn)程序及調(diào)試時所需的測試數(shù)據(jù)；（3）獨(dú)立思考，獨(dú)立完成，嚴(yán)禁抄襲，調(diào)試過程要規(guī)范，認(rèn)真記錄調(diào)試結(jié)果； （4）上機(jī)結(jié)束后認(rèn)真規(guī)范撰寫課設(shè)報告，對設(shè)計進(jìn)行總結(jié)和討論。2）課程設(shè)計論文編寫要求（1）要按照書稿的規(guī)格撰寫打印課設(shè)論文（2）論文包括任務(wù)書、目錄、緒論、正文、總結(jié)、參考文獻(xiàn)、附錄等（3）正文中要有問題描述、抽象數(shù)據(jù)類型的定義、數(shù)據(jù)的存儲結(jié)構(gòu)、設(shè)計的求解算法、算法的實(shí)現(xiàn)、調(diào)試分析與測試結(jié)果（4）課設(shè)論文裝訂按學(xué)校的統(tǒng)一要求完成3）課設(shè)考核從以下幾方面來考查：（1）考勤和態(tài)度； （2）任務(wù)的難易程度及設(shè)計思路；（3

3、）動手調(diào)試能力；（4）論文撰寫的水平、格式的規(guī)范性。4）參考文獻(xiàn)1 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版）M. 北京：清華大學(xué)出版社, 2007年.2 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu)題集（C語言版）M. 北京：清華大學(xué)出版社, 2007年.3 譚浩強(qiáng). C語言程序設(shè)計M. 北京：清華大學(xué)出版社，2006年.5）課程設(shè)計進(jìn)度安排內(nèi)容 天數(shù)地點(diǎn)構(gòu)思及收集資料 1圖書館程序設(shè)計與調(diào)試 3計算機(jī)房撰寫論文 1圖書館6）任務(wù)及具體要求初始化：鍵盤輸入字符集大小n、n個字符和n個權(quán)值，建立哈夫曼樹；編碼：利用建好的哈夫曼樹生成哈夫曼編碼； 輸出其哈夫曼樹及哈夫曼編碼； 設(shè)字符集及頻度如下表： 字符 空格

4、A B C D E F G H I J K L M 頻度 197 64 13 22 32 103 21 15 47 57 5 1 20 32 字符 N O P Q R S T U V W X Y Z 頻度 57 63 1 15 48 16 80 23 8 18 1 51 1 學(xué)生簽名： 年 月 日課程設(shè)計(論文)評審意見（1）考勤和態(tài)度 ：優(yōu)（）、良（）、中（）、一般（）、差（）（2）任務(wù)難易及設(shè)計思路 ：優(yōu)（）、良（）、中（）、一般（）、差（）（3）動手調(diào)試能力評價 ：優(yōu)（）、良（）、中（）、一般（）、差（）（4）論文撰寫水平及規(guī)范性評價：優(yōu)（ ）、良（ ）、中（）、一般（）、差（） 評閱人

5、： 職稱： 講師 年 月 日目 錄1 設(shè)計任務(wù)12 需求分析13 概要設(shè)計13.1模塊設(shè)計13.2系統(tǒng)子程序即功能設(shè)計14 詳細(xì)設(shè)計25 編碼實(shí)現(xiàn)35.1數(shù)據(jù)類型定義35.2哈夫曼編碼模塊設(shè)計35.3主程序模塊66 調(diào)試分析77 課設(shè)總結(jié)9參考文獻(xiàn)9附錄9一 設(shè)計任務(wù)問題描述：設(shè)計一個利用哈夫曼算法的編碼系統(tǒng)，重復(fù)地顯示并處理以下項(xiàng)目，直到選擇退出為止?；疽螅撼跏蓟烘I盤輸入字符集大小n、n個字符和n個權(quán)值，建立哈夫曼樹；編碼：利用建好的哈夫曼樹生成哈夫曼編碼；輸出其哈夫曼樹及哈夫曼編碼；設(shè)字符集及頻度如下表：字符 空格 A B C D E F G H I J K L M頻度 197 64

6、 13 22 32 103 21 15 47 57 5 1 20 32字符 N O P Q R S T U V W X Y Z 頻度 57 63 1 15 48 16 80 23 8 18 1 51 1 二 需求分析（1）設(shè)計哈夫曼樹。具體構(gòu)造方法如下：以字符集（空格 A B C D E F G H I J K N O P Q R S T U V W X Y Z L M）作為葉子結(jié)點(diǎn)。以各字母出現(xiàn)的次數(shù)即頻度（197 64 13 22 32 103 21 15 47 57 5 1 20 32 57 63 1 15 48 16 80 23 8 18 1 51 1）作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造一棵哈夫曼

7、樹。（2）設(shè)計哈哈夫曼。按照構(gòu)造出來的哈夫曼樹，規(guī)定哈夫曼樹的左分支為0，右分支為1，則從根結(jié)點(diǎn)到每個葉子結(jié)點(diǎn)所經(jīng)過的分支對應(yīng)的0和1 組成的序列便為該結(jié)點(diǎn)對應(yīng)字符的哈夫曼編碼。三 概要設(shè)計3.1模塊設(shè)計本程序包含3個模塊：主程序模塊，哈夫曼編碼模塊，和選擇模塊。其調(diào)用關(guān)系如下圖所示。選擇模塊哈夫曼編碼模塊主程序模塊3.2系統(tǒng)子程序即功能設(shè)計本程序共設(shè)置2個子程序，各子程序的函數(shù)名及各功能說明如（1）void hfmcoding(hfmtree &HT,hfmcode &HC,int n) /構(gòu)建赫夫曼樹HT，并求出n個字符的赫夫曼編碼HC（2）void Select(hfmtree &HT,

8、int a,int *p1,int *p2) /Select函數(shù)，選出HT樹到a為止，權(quán)值最小且parent為0的2個節(jié)點(diǎn)四 詳細(xì)設(shè)計 1問題分析哈夫曼樹的定義1）哈夫曼樹節(jié)點(diǎn)的數(shù)據(jù)類型定義為：typedef struc t/赫夫曼樹的結(jié)構(gòu)體 char ch;int weight; /權(quán)值int parent,lchild,rchild;htnode,*hfmtree;2）所實(shí)現(xiàn)的功能函數(shù)如下1、void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈夫曼樹，處理InputHuffman(Huffman Hfm)函數(shù)得到的數(shù)據(jù)，按照哈夫曼規(guī)則建立2叉樹

9、。此函數(shù)塊調(diào)用了Select（）函數(shù)。2、void Select(hfmtree &HT,int a,int *p1,int *p2) /Select函數(shù)，選出HT樹到a為止，權(quán)值最小且parent為0的2個節(jié)點(diǎn)2、 int main() 主函數(shù)： 利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmtree.txt中讀入）對文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile.txt中。如果正文中沒有要編碼的字符，則鍵盤讀入并存儲到ToBeTran.中。讀入ToBeTran中將要編碼的內(nèi)容，將編碼好的哈夫曼編碼存儲到CodeFile中。3、Encoding 編碼功能：對輸入字符進(jìn)行編碼4、D

10、ecoding譯碼功能： 利用已建好的哈夫曼樹將文件codefile.txt中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile.dat 中。Print() 打印功能函數(shù)：輸出哈夫曼樹，字符，權(quán)值，以及它對應(yīng)的編碼。5.主函數(shù)的簡要說明，主函數(shù)主要設(shè)計的是一個分支語句，讓用戶挑選所實(shí)現(xiàn)的功能。使用鏈樹存儲，然后分別調(diào)用統(tǒng)計頻數(shù)函數(shù)，排序函數(shù)，建立哈夫曼函數(shù)，編碼函數(shù)，譯碼函數(shù)來實(shí)現(xiàn)功能。系統(tǒng)結(jié)構(gòu)圖（功能模塊圖）哈夫曼編碼/譯碼器打印哈夫曼樹打印編碼譯碼編碼初始化哈夫曼樹五 編碼實(shí)現(xiàn)5.1數(shù)據(jù)類型定義typedef struct /赫夫曼樹的結(jié)構(gòu)體char ch;int weight; /權(quán)值int

11、parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode;5.2哈夫曼編碼模塊設(shè)計哈夫曼編碼模塊設(shè)計分為兩步：首先構(gòu)造哈夫曼樹，然后完成哈夫曼編碼。void Select(hfmtree &HT,int a,int *p1,int *p2) /Select函數(shù)，選出HT樹到a為止，權(quán)值最小且parent為0的2個節(jié)點(diǎn)int i,j,x,y;for(j=1;j=a;+j)if(HTj.parent=0)x=j;break;for(i=j+1;i=a;+i)if(HTi.weightHTx.weight&HTi.parent=0)x=i;

12、 /選出最小的節(jié)點(diǎn)for(j=1;j=a;+j)if(HTj.parent=0&x!=j)y=j;break;for(i=j+1;i=a;+i)if(HTi.weighty)*p1=y;*p2=x;else*p1=x;*p2=y;void hfmcoding(hfmtree &HT,hfmcode &HC,int n) /構(gòu)建赫夫曼樹HT，并求出n個字符的赫夫曼編碼HCint i,start,c,f,m,w;int p1,p2;char *cd,z;if(n=1)return;m=2*n-1;HT=(hfmtree)malloc(m+1)*sizeof(htnode);for(i=1;i=n;

13、+i) /初始化n個葉子結(jié)點(diǎn)printf(請輸入第%d字符信息和權(quán)值：,i);scanf(%c%d,&z,&w);while(getchar()!=n)continue;HTi.ch=z;HTi.weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i=m;+i) /初始化其余的結(jié)點(diǎn)HTi.ch=0;HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i=m;+i) /建立赫夫曼樹Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.pare

14、nt=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.weight;HC=(hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;+i) /給n個字符編碼start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*sizeof

15、(char);strcpy(HCi,&cdstart);free(cd);5.3主程序模塊詳見源代碼 六 調(diào)試分析字符ABCDEFGHIJKLM頻度1976413223210321154757512032字符NOPQRSTUVWXYZ頻度5763115481680238181151編碼譯碼退出七 課設(shè)總結(jié) 通過本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計，我學(xué)習(xí)了很多在上課沒懂的知識，并對求哈夫曼樹及哈夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān)于哈夫曼編碼的知識，真正學(xué)會一種算法了。當(dāng)求解一個算法時,不是拿到問題就不加思索地做，而是首先要先對它有個大概的了解，接著再詳細(xì)地分析每一步怎么做，無論自

16、己以前是否有處理過相似的問題，只要按照以上的步驟，必定會順利地做出來。這次課程設(shè)計，體現(xiàn)出自己單獨(dú)設(shè)計程序的能力以及綜合運(yùn)用知識的能力，體會了學(xué)以致用、突出自己勞動成果的喜悅心情。從中發(fā)現(xiàn)自己平時學(xué)習(xí)的不足和薄弱環(huán)節(jié)，從而加以彌補(bǔ)。通過這次課程設(shè)計，我對這種寫程序的方法有了一定的了解，自己有一個很明確的思路去寫程序，提高了效率。這種框架的程序?qū)懛?，對我以后學(xué)習(xí)編程有進(jìn)一步的提高。在此感謝我們的王玨老師.，老師嚴(yán)謹(jǐn)細(xì)致、一絲不茍的作風(fēng)一直是我工作、學(xué)習(xí)中的榜樣；老師循循善誘的教導(dǎo)和不拘一格的思路給予我無盡的啟迪；而您開朗的個性和寬容的態(tài)度，幫助我能夠很順利的完成了這次課程設(shè)計。 同時感謝對我?guī)椭?/p>

17、過的同學(xué)們，謝謝你們對我的幫助和支持，讓我感受到同學(xué)的友誼。由于自己的設(shè)計能力有限，在設(shè)計過程中難免出現(xiàn)錯誤，懇請老師多多指教。我在編輯中犯了不應(yīng)有的錯誤，設(shè)計統(tǒng)計字符和合并時忘記應(yīng)該怎樣保存數(shù)據(jù)，對文件的操作也很生疏。在不斷分析后明確并改正了錯誤和疏漏，我的程序有了更高的質(zhì)量。參考文獻(xiàn)嚴(yán)蔚敏,吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C語言版)M. 清華大學(xué)出版社. 2010.3 嚴(yán)蔚敏,吳偉民. 數(shù)據(jù)結(jié)構(gòu)題集(C語言版)M.清華大學(xué)出版社. 1999.2何欽銘,馮燕等. 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計M. 浙江大學(xué)出版社. 2007.附錄#include#include#include#include#includetype

18、def struct /赫夫曼樹的結(jié)構(gòu)體char ch;int weight; /權(quán)值int parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode;void Select(hfmtree &HT,int a,int *p1,int *p2) /Select函數(shù)，選出HT樹到a為止，權(quán)值最小且parent為0的2個節(jié)點(diǎn)int i,j,x,y;for(j=1;j=a;+j)if(HTj.parent=0)x=j;break;for(i=j+1;i=a;+i)if(HTi.weightHTx.weight&HTi.parent=0)x=

19、i; /選出最小的節(jié)點(diǎn)for(j=1;j=a;+j)if(HTj.parent=0&x!=j)y=j;break;for(i=j+1;i=a;+i)if(HTi.weighty)*p1=y;*p2=x;else*p1=x;*p2=y;void hfmcoding(hfmtree &HT,hfmcode &HC,int n) /構(gòu)建赫夫曼樹HT，并求出n個字符的赫夫曼編碼HCint i,start,c,f,m,w;int p1,p2;char *cd,z;if(n=1)return;m=2*n-1;HT=(hfmtree)malloc(m+1)*sizeof(htnode);for(i=1;i=

20、n;+i) /初始化n個葉子結(jié)點(diǎn)printf(請輸入第%d字符信息和權(quán)值：,i);scanf(%c%d,&z,&w);while(getchar()!=n)continue;HTi.ch=z;HTi.weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i=m;+i) /初始化其余的結(jié)點(diǎn)HTi.ch=0;HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i=m;+i) /建立赫夫曼樹Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.pa

21、rent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.weight;HC=(hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;+i) /給n個字符編碼start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*size

22、of(char);strcpy(HCi,&cdstart);free(cd);int main()char code100,h100,hl100;int n,i,j,k,l;ifstream input_file; /文件輸入輸出流ofstream output_file;char choice,str100;hfmtree HT;hfmcode HC;coutn;cout 軟件+電氣（1）班 Q07620307 艾寧n;while(choice!=Q&choice!=q) /當(dāng)choice的值不為q且不為Q時循環(huán)cout *赫夫曼編碼/譯碼器*n; cout I.Init E.Encodin

23、g D.Decoding Q.Exitn; coutchoice; if(choice=I|choice=i) /初始化赫夫曼樹coutn;hfmcoding(HT,HC,n);for(i=1;i=n;+i)coutHTi.ch:HCiendl;output_file.open(hfmTree.txt);if(!output_file)coutcant oen file!endl;return 1;for(i=1;i=n;i+)output_file(HTi.chHCi);output_file.close();cout赫夫曼樹已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入hfmTree.txt文件中!endl;

24、 else if(choice=E|choice=e) /進(jìn)行編碼，并將字符放入ToBeTran.txt，碼值放入CodeFile.txt中printf(請輸入字符：);gets(str);output_file.open(ToBeTran.txt);if(!output_file)coutcant oen file!endl;return 1;output_filestrendl;output_file.close();output_file.open(CodeFile.txt);if(!output_file)coutcant oen file!endl;return 1;for(i=0;istrlen(str);i+)for(j=0;j=n;+j)if(HTj.ch=stri)output_fileHCj;break;output_file.close();coutn;cout編碼完畢，并且已經(jīng)存