哈夫曼樹(shù)應(yīng)用課程設(shè)計(jì)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目：哈夫曼樹(shù)應(yīng)用 專 業(yè) ： 軟件工程 班 級(jí) ： 軟件 學(xué) 生 ： 學(xué) 號(hào) ： 指導(dǎo)教師 ： 羅作民 / 張翔 起止時(shí)間 ：2011-07-042011-07-08 2011 年 春季 學(xué)期目 錄一具體任務(wù).2 1功能.2 2分步實(shí)施.2. 3要求.2二哈夫曼編碼21問(wèn)題描述22.基本要求33實(shí)現(xiàn)提示3三設(shè)計(jì)流程圖4 1建立哈夫曼樹(shù).4 2編碼.5 3譯碼.6 4主程序.7四設(shè)計(jì)概要81問(wèn)題哈夫曼的定義.8.2所實(shí)現(xiàn)的功能函數(shù)如下.83功能模塊.8五源程序9六調(diào)試分析15七心得與體會(huì)18八參考文獻(xiàn)18一、任務(wù)題目：哈夫曼樹(shù)應(yīng)用1.功能： 1從終端讀入字符集大小n，以

2、及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)并將它存于文件hfmtree中.將已在內(nèi)存中的哈夫曼樹(shù)以直觀的方式（比如樹(shù)）顯示在終端上；2利用已經(jīng)建好的哈夫曼樹(shù)（如不在內(nèi)存，則從文件htmtree中讀入），對(duì)文件tobetran中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile中，并輸出結(jié)果，將文件codefile以緊湊格式先是在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件codeprint中。3利用已建好的哈夫曼樹(shù)將文件codefile中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile中，并輸出結(jié)果。2.分步實(shí)施：1） 初步完成總體設(shè)計(jì)，搭好框架，確定人機(jī)對(duì)話的界面，確定函數(shù)個(gè)數(shù)；2） 完成

3、最低要求：完成功能1；3） 進(jìn)一步要求：完成功能2和3。有興趣的同學(xué)可以自己擴(kuò)充系統(tǒng)功能。3.要求：1）界面友好，函數(shù)功能要?jiǎng)澐趾?）總體設(shè)計(jì)應(yīng)畫一流程圖3）程序要加必要的注釋4） 要提供程序測(cè)試方案5） 程序一定要經(jīng)得起測(cè)試，寧可功能少一些，也要能運(yùn)行起來(lái)，不能運(yùn)行的程序是沒(méi)有價(jià)值的。二、哈夫曼編碼1. 問(wèn)題描述利用赫夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳輸數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站編寫一個(gè)赫夫曼碼的編

4、/譯碼系統(tǒng)。2. 基本要求一個(gè)完整的系統(tǒng)應(yīng)具有以下功能：(1) i：初始化（initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立赫夫曼樹(shù)，并將它存于文件hfmtree中。(2) e：編碼（encoding）。利用已建好的赫夫曼樹(shù)（如不在內(nèi)存，則從文件hfmtree中讀入），對(duì)文件tobetran中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile中。(3) d：譯碼（decoding）。利用已建好的赫夫曼樹(shù)將文件codefile中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile中。3. 實(shí)現(xiàn)提示(1) 編碼結(jié)果以文本方式存儲(chǔ)在文件codefile中。(2) 用戶界面

5、可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號(hào)，再加上“q”，表示退出運(yùn)行quit。請(qǐng)用戶鍵入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“q”為止。(3) 在程序的一次執(zhí)行過(guò)程中，第一次執(zhí)行i， d或c命令之后，赫夫曼樹(shù)已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行i命令，因?yàn)槲募fmtree可能早已建好。三、設(shè)計(jì)流程圖建立哈夫曼樹(shù)：開(kāi)始n,=1renturn 0m=2*n-1i=1;i=n;+iwhile(getchar()=”/n”輸入字符與權(quán)值hti.ch=zhti.weight=whti.parent=0hti.lchild=0hti.rchild=0編碼：開(kāi)始cds

6、tart=”1”i=1;i=n;+istart=n-1cdstart=”0”c=i;f=hti.parent; f!=0;f=htf.parenthtf.child=l結(jié)束譯碼：開(kāi)始l=k!output_file!cout”cant open file”return 1cout”cant open file”strcmp(hi.hlchild=0結(jié)束i=1;in;i+while(hk!=”0”)j=0;jstrlen(hi);j+;l+k=0hj=”0”輸出譯碼主程序：開(kāi)始main建立哈夫曼樹(shù)choice=”i”|choice=”i”結(jié)束編碼return 0choice=”e”|choice=

7、”e”choice=”d”|choice=”d”choice=”q”|choice=”q”編碼四、概要設(shè)計(jì)1）問(wèn)題哈夫曼的定義：1.哈夫曼樹(shù)節(jié)點(diǎn)的數(shù)據(jù)類型定義為：typedef struct /赫夫曼樹(shù)的結(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)初始化哈夫曼樹(shù)，處理inputhuffman(huffman hfm)函數(shù)得到的數(shù)據(jù)，按照哈夫曼規(guī)則建立2叉樹(shù)。此函數(shù)塊調(diào)用了select（）函

8、數(shù)。2、void select(hfmtree &ht,int a,int *p1,int *p2) /select函數(shù)，選出ht樹(shù)到a為止，權(quán)值最小且parent為0的2個(gè)節(jié)點(diǎn)3、 int main()主函數(shù)： 利用已建好的哈夫曼樹(shù)（如不在內(nèi)存，則從文件hfmtree.txt中讀入）對(duì)文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile.txt中。如果正文中沒(méi)有要編碼的字符，則鍵盤讀入并存儲(chǔ)到tobetran文件中。讀入tobetran中將要編碼的內(nèi)容，將編碼好的哈夫曼編碼存儲(chǔ)到codefile中。4、encoding 編碼功能：對(duì)輸入字符進(jìn)行編碼5、decoding譯碼功能： 利用已建

9、好的哈夫曼樹(shù)將文件codefile.txt中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile.dat 中。print() 打印功能函數(shù)：輸出哈夫曼樹(shù)，字符，權(quán)值，以及它對(duì)應(yīng)的編碼。6.主函數(shù)的簡(jiǎn)要說(shuō)明，主函數(shù)主要設(shè)計(jì)的是一個(gè)分支語(yǔ)句，讓用戶挑選所實(shí)現(xiàn)的功能。使用鏈樹(shù)存儲(chǔ)，然后分別調(diào)用統(tǒng)計(jì)頻數(shù)函數(shù)，排序函數(shù)，建立哈夫曼函數(shù)，編碼函數(shù)，譯碼函數(shù)來(lái)實(shí)現(xiàn)功能。3）功能模塊：哈夫曼編碼/譯碼器初始化哈夫曼樹(shù)編碼譯碼打印哈夫曼樹(shù)打印編碼五、源程序#include#include#include#include#includetypedef struct /哈夫曼樹(shù)的結(jié)構(gòu)體char ch;int weight;

10、 /權(quán)值int parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode;void select(hfmtree &ht,int a,int *p1,int *p2) /select函數(shù)，選出ht樹(shù)到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(hti.weighthtx.weight&hti.parent=0)x=i; /選出最小的節(jié)點(diǎn)for(j=1;j=a;+j)if(htj.parent

11、=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)建哈夫曼樹(shù)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

12、);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) /建立哈夫曼樹(shù)select(ht,i-1,&p1,&p2);htp1.parent=i;htp2.parent=i;hti.lchild=p1;hti.rchild=p2;hti.

13、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個(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);

14、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 軟件092班 姓名:張耀飛 學(xué)號(hào)：3090921040n ;while(choice!=q&choice!=q) /當(dāng)choice的值不為q且不為q時(shí)循環(huán)cout *哈夫曼編碼/譯碼器*n; cout i.init e.encoding d.decoding q.exitn; coutchoice;

15、 if(choice=i|choice=i) /初始化赫夫曼樹(shù)coutn;hfmcoding(ht,hc,n);for(i=1;i=n;+i)couthti.ch:hciendl;output_file.open(hfmtree.txt);if(!output_file)coutcant open file!endl;return 1;for(i=1;i=n;i+)output_file(hti.chhci);output_file.close();cout哈夫曼樹(shù)已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入hfmtree.txt文件中!endl; else if(choice=e|choice=e) /進(jìn)行編

16、碼，并將字符放入tobetran.txt，碼值放入codefile.txt中printf(請(qǐng)輸入字符：);gets(str);output_file.open(tobetree.txt);if(!output_file)coutcant open file!endl;return 1;output_filestrendl;output_file.close();output_file.open(codefile.txt);if(!output_file)coutcant open file!endl;return 1;for(i=0;istrlen(str);i+)for(j=0;j=n;+j

17、)if(htj.ch=stri)output_filehcj;break;output_file.close();coutn;cout編碼完畢，并且已經(jīng)存入codefile.txt文件！n;input_file.open(codefile.txt); /從codefile.txt中讀入編碼，輸出在終端if(!input_file)coutcant open file!code;cout編碼碼值為：codeendl;input_file.close(); else if(choice=d|choice=d) /讀入codefile.txt中的編碼進(jìn)行譯碼，將譯出來(lái)的字符放入textfile.tx

18、t中input_file.open(codefile.txt);if(!input_file)coutcant open file!h;input_file.close();output_file.open(textfile.txt);if(!output_file)coutcant open file!endl;return 1;k=0;while(hk!=0) /先用編碼中的前幾個(gè)和字符的編碼相比較，然后往后移for(i=1;i=n;i+)l=k;for(j=0;jstrlen(hci);j+,l+)hlj=hl;hlj=0;if(strcmp(hci,hl)=0)output_fileh

19、ti.ch;k=k+strlen(hci);break;output_file.close();input_file.open(textfile.txt);if(!input_file)coutcant open file!h; couthendl;input_file.close();cout譯碼結(jié)束，字符已經(jīng)存入textfile.txt文件中！endl; else if(choice=q|choice=q) /退出程序 exit(0); else /如果選了選項(xiàng)之外的就讓用戶重新選擇cout您沒(méi)有輸入正確的步驟，請(qǐng)重新輸入！endl;coutendl;return 0;六、調(diào)試分析編碼譯碼退出七、實(shí)驗(yàn)心得與體會(huì) 在我自己課程設(shè)計(jì)中，就在編寫好源代碼后的調(diào)試中出現(xiàn)了不少的錯(cuò)誤，遇到了很多麻煩及困難，我的調(diào)試及其中的錯(cuò)誤和我最終找出錯(cuò)誤，修改為正確的能夠執(zhí)行的程序中，通過(guò)分析，我學(xué)到了：在定義頭文件時(shí)可多不可少，即我們可多寫些頭文件，肯定不會(huì)出錯(cuò)，但是若沒(méi)有定義所引用的相關(guān)頭文件，必定調(diào)試不通過(guò)；在執(zhí)行譯碼操作時(shí)，不知