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

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

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

3、）動(dòng)手調(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è)計(jì)M. 北京：清華大學(xué)出版社，2006年.5）課程設(shè)計(jì)進(jìn)度安排內(nèi)容 天數(shù)地點(diǎn)構(gòu)思及收集資料 1圖書館程序設(shè)計(jì)與調(diào)試 3計(jì)算機(jī)房撰寫論文 1圖書館6）任務(wù)及具體要求初始化：鍵盤輸入字符集大小n、n個(gè)字符和n個(gè)權(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è)計(jì)(論文)評(píng)審意見（1）考勤和態(tài)度 ：優(yōu)（）、良（）、中（）、一般（）、差（）（2）任務(wù)難易及設(shè)計(jì)思路 ：優(yōu)（）、良（）、中（）、一般（）、差（）（3）動(dòng)手調(diào)試能力評(píng)價(jià) ：優(yōu)（）、良（）、中（）、一般（）、差（）（4）論文撰寫水平及規(guī)范性評(píng)價(jià)：優(yōu)（ ）、良（ ）、中（）、一般（）、差（） 評(píng)閱人

5、： 職稱： 講師 年 月 日目 錄1 設(shè)計(jì)任務(wù)12 需求分析13 概要設(shè)計(jì)13.1模塊設(shè)計(jì)13.2系統(tǒng)子程序即功能設(shè)計(jì)14 詳細(xì)設(shè)計(jì)25 編碼實(shí)現(xiàn)35.1數(shù)據(jù)類型定義35.2哈夫曼編碼模塊設(shè)計(jì)35.3主程序模塊66 調(diào)試分析77 課設(shè)總結(jié)9參考文獻(xiàn)9附錄9一 設(shè)計(jì)任務(wù)問題描述：設(shè)計(jì)一個(gè)利用哈夫曼算法的編碼系統(tǒng)，重復(fù)地顯示并處理以下項(xiàng)目，直到選擇退出為止?；疽螅撼跏蓟烘I盤輸入字符集大小n、n個(gè)字符和n個(gè)權(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è)計(jì)哈夫曼樹。具體構(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è)計(jì)哈哈夫曼。按照構(gòu)造出來的哈夫曼樹，規(guī)定哈夫曼樹的左分支為0，右分支為1，則從根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)所經(jīng)過的分支對(duì)應(yīng)的0和1 組成的序列便為該結(jié)點(diǎn)對(duì)應(yīng)字符的哈夫曼編碼。三 概要設(shè)計(jì)3.1模塊設(shè)計(jì)本程序包含3個(gè)模塊：主程序模塊，哈夫曼編碼模塊，和選擇模塊。其調(diào)用關(guān)系如下圖所示。選擇模塊哈夫曼編碼模塊主程序模塊3.2系統(tǒng)子程序即功能設(shè)計(jì)本程序共設(shè)置2個(gè)子程序，各子程序的函數(shù)名及各功能說明如（1）void hfmcoding(hfmtree &HT,hfmcode &HC,int n) /構(gòu)建赫夫曼樹HT，并求出n個(gè)字符的赫夫曼編碼HC（2）void Select(hfmt

8、ree &HT,int a,int *p1,int *p2) /Select函數(shù)，選出HT樹到a為止，權(quán)值最小且parent為0的2個(gè)節(jié)點(diǎn)四 詳細(xì)設(shè)計(jì) 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)

9、函數(shù)得到的數(shù)據(jù)，按照哈夫曼規(guī)則建立2叉樹。此函數(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個(gè)節(jié)點(diǎn)2、 int main() 主函數(shù)： 利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmtree.txt中讀入）對(duì)文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile.txt中。如果正文中沒有要編碼的字符，則鍵盤讀入并存儲(chǔ)到ToBeTran.中。讀入ToBeTran中將要編碼的內(nèi)容，將編碼好的哈夫曼編碼存儲(chǔ)到CodeFile中。3、En

10、coding 編碼功能：對(duì)輸入字符進(jìn)行編碼4、Decoding譯碼功能： 利用已建好的哈夫曼樹將文件codefile.txt中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile.dat 中。Print() 打印功能函數(shù)：輸出哈夫曼樹，字符，權(quán)值，以及它對(duì)應(yīng)的編碼。5.主函數(shù)的簡要說明，主函數(shù)主要設(shè)計(jì)的是一個(gè)分支語句，讓用戶挑選所實(shí)現(xiàn)的功能。使用鏈樹存儲(chǔ)，然后分別調(diào)用統(tǒng)計(jì)頻數(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)體cha

11、r ch;int weight; /權(quán)值int parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode;5.2哈夫曼編碼模塊設(shè)計(jì)哈夫曼編碼模塊設(shè)計(jì)分為兩步：首先構(gòu)造哈夫曼樹，然后完成哈夫曼編碼。void Select(hfmtree &HT,int a,int *p1,int *p2) /Select函數(shù)，選出HT樹到a為止，權(quán)值最小且parent為0的2個(gè)節(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(HT

12、i.weight<HTx.weight&&HTi.parent=0)x=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.weight<HTy.weight&&HTi.parent=0&&x!=i)y=i; /選出次小的節(jié)點(diǎn)if(x>y)*p1=y;*p2=x;else*p1=x;*p2=y;void hfmcoding(hfmtree &HT,hfmcode &HC,

13、int n) /構(gòu)建赫夫曼樹HT，并求出n個(gè)字符的赫夫曼編碼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;+i) /初始化n個(gè)葉子結(jié)點(diǎn)printf("請(qǐng)輸入第%d字符信息和權(quán)值：",i);scanf("%c%d",&z,&w);while(getchar()!='n')continue;HTi.ch=z;HTi.weight

14、=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.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.weight;HC=(hfmcode

15、)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1='0'for(i=1;i<=n;+i) /給n個(gè)字符編碼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(char);strcpy(HCi,&cdstart);free(cd);5.3主程序模

16、塊詳見源代碼 六 調(diào)試分析字符ABCDEFGHIJKLM頻度1976413223210321154757512032字符NOPQRSTUVWXYZ頻度5763115481680238181151編碼譯碼退出七 課設(shè)總結(jié) 通過本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)，我學(xué)習(xí)了很多在上課沒懂的知識(shí)，并對(duì)求哈夫曼樹及哈夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān)于哈夫曼編碼的知識(shí)，真正學(xué)會(huì)一種算法了。當(dāng)求解一個(gè)算法時(shí),不是拿到問題就不加思索地做，而是首先要先對(duì)它有個(gè)大概的了解，接著再詳細(xì)地分析每一步怎么做，無論自己以前是否有處理過相似的問題，只要按照以上的步驟，必定會(huì)順利地做出來。這次課程設(shè)計(jì)，體現(xiàn)

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

18、計(jì)過程中難免出現(xiàn)錯(cuò)誤，懇請(qǐng)老師多多指教。我在編輯中犯了不應(yīng)有的錯(cuò)誤，設(shè)計(jì)統(tǒng)計(jì)字符和合并時(shí)忘記應(yīng)該怎樣保存數(shù)據(jù)，對(duì)文件的操作也很生疏。在不斷分析后明確并改正了錯(cuò)誤和疏漏，我的程序有了更高的質(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è)計(jì)M. 浙江大學(xué)出版社. 2007.附錄#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include<str

19、ing.h>#include<fstream.h>typedef 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個(gè)節(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;

20、i<=a;+i)if(HTi.weight<HTx.weight&&HTi.parent=0)x=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.weight<HTy.weight&&HTi.parent=0&&x!=i)y=i; /選出次小的節(jié)點(diǎn)if(x>y)*p1=y;*p2=x;else*p1=x;*p2=y;void hfmcoding(hfmtree &HT,

21、hfmcode &HC,int n) /構(gòu)建赫夫曼樹HT，并求出n個(gè)字符的赫夫曼編碼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;+i) /初始化n個(gè)葉子結(jié)點(diǎn)printf("請(qǐng)輸入第%d字符信息和權(quán)值：",i);scanf("%c%d",&z,&w);while(getchar()!='n')continue;HTi

22、.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.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.we

23、ight;HC=(hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1='0'for(i=1;i<=n;+i) /給n個(gè)字符編碼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(char);strcpy(HCi,&cdstart);

24、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;cout<<"n"cout<<" "<<"軟件+電氣（1）班"<<" "<<"Q07620307"<<" "&l

25、t;<"艾寧n"while(choice!='Q'&&choice!='q') /當(dāng)choice的值不為q且不為Q時(shí)循環(huán)cout<<" "<<"*赫夫曼編碼/譯碼器*n" cout<<" "<<"I.Init"<<" "<<"E.Encoding"<<" "<<"D.Decodi

26、ng"<<" "<<"Q.Exitn" cout<<"請(qǐng)輸入您要操作的步驟："cin>>choice; if(choice='I'|choice='i') /初始化赫夫曼樹cout<<"請(qǐng)輸入字符個(gè)數(shù)："cin>>n;hfmcoding(HT,HC,n);for(i=1;i<=n;+i)cout<<HTi.ch<<":"<<HCi<&l

27、t;endl;output_file.open("hfmTree.txt");if(!output_file)cout<<"can't oen file!"<<endl;return 1;for(i=1;i<=n;i+)output_file<<"("<<HTi.ch<<HCi<<")"output_file.close();cout<<"赫夫曼樹已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入hfmTree.txt文件中!&qu

28、ot;<<endl; else if(choice='E'|choice='e') /進(jìn)行編碼，并將字符放入ToBeTran.txt，碼值放入CodeFile.txt中printf("請(qǐng)輸入字符：");gets(str);output_file.open("ToBeTran.txt");if(!output_file)cout<<"can't oen file!"<<endl;return 1;output_file<<str<<end

29、l;output_file.close();output_file.open("CodeFile.txt");if(!output_file)cout<<"can't oen file!"<<endl;return 1;for(i=0;i<strlen(str);i+)for(j=0;j<=n;+j)if(HTj.ch=stri)output_file<<HCj;break;output_file.close();cout<<"n"cout<<"編碼完畢，并且已經(jīng)存入CodeFile.txt文件！n"input_file.open("CodeFile.txt"); /從CodeFile.txt中讀入編碼，輸出在終端if(!input_file)cout<<"can't oen file!"<<endl;return 1;input_file>>code;cout<<"編碼碼值為："<<code<<endl;input_file.close(); else if(choice=