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

《哈夫曼樹應(yīng)用課程設(shè)計(jì)報(bào)告》由會(huì)員分享，可在線閱讀，更多相關(guān)《哈夫曼樹應(yīng)用課程設(shè)計(jì)報(bào)告（19頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、 數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)報(bào)告 設(shè)計(jì)題目：哈夫曼樹應(yīng)用 專 業(yè) ： 軟件工程 班 級(jí) ： 軟件 學(xué) 生 ： 學(xué) 號(hào) ： 指導(dǎo)教師 ： 羅作民 / 張翔 起止時(shí)間 ：2011-07-04—2011-07-08 2011 年 春季 學(xué)期 目 錄 一．具體任務(wù) …..2

2、 1功能……………………………………………………………………………...2 2分步實(shí)施………………………………………………………………………...2. 3要求……………………………………………………………………………...2 二．哈夫曼編碼 2 1問題描述 2 2.基本要求 3 3實(shí)現(xiàn)提示 3 三．設(shè)計(jì)流程圖 4 1建立哈夫曼樹…………………………………………………………………...4 2編碼……………………………………………………………………………...5 3譯碼……………………………………

3、………………………………………...6 4主程序…………………………………………………………………………...7 四．設(shè)計(jì)概要 8 1問題哈夫曼的定義..............................................................................................8.. 2所實(shí)現(xiàn)的功能函數(shù)如下………………………………………………………..8 3功能模塊………………………………………………………………………..8 五．源程序 9 六．調(diào)試分析 15 七．心得與體會(huì) 18 八．參考文獻(xiàn) 1

4、8 一、任務(wù) 題目：哈夫曼樹應(yīng)用 1.功能： 1．從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹并將它存于文件hfmTree中.將已在內(nèi)存中的哈夫曼樹以直觀的方式（比如樹）顯示在終端上； 2．利用已經(jīng)建好的哈夫曼樹（如不在內(nèi)存，則從文件htmTree中讀入），對文件ToBeTran中的正文進(jìn)行 編碼，然后將結(jié)果存入文件CodeFile中，并輸出結(jié)果，將文件CodeFile以緊湊格式先是在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件CodePrint中。 3．利用已建好的哈夫曼樹將

5、文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中，并輸出結(jié)果。 2.分步實(shí)施： 1） 初步完成總體設(shè)計(jì)，搭好框架，確定人機(jī)對話的界面，確定函數(shù)個(gè)數(shù)； 2） 完成最低要求：完成功能1； 3） 進(jìn)一步要求：完成功能2和3。有興趣的同學(xué)可以自己擴(kuò)充系統(tǒng)功能。 3.要求： 1）界面友好，函數(shù)功能要?jiǎng)澐趾? 2）總體設(shè)計(jì)應(yīng)畫一流程圖 3）程序要加必要的注釋 4） 要提供程序測試方案 5） 程序一定要經(jīng)得起測試，寧可功能少一些，也要能運(yùn)行起來，不能運(yùn)行的程序是沒有價(jià)值的。 二、哈夫曼編碼 1. 問題描述 利用赫夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短

6、信息傳輸時(shí)間，降低傳輸成本。這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對待傳輸數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站編寫一個(gè)赫夫曼碼的編/譯碼系統(tǒng)。 2. 基本要求 一個(gè)完整的系統(tǒng)應(yīng)具有以下功能： (1) I：初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立赫夫曼樹，并將它存于文件hfmTree中。 (2) E：編碼（Encoding）。利用已建好的赫夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進(jìn)行編碼，然后

7、將結(jié)果存入文件CodeFile中。 (3) D：譯碼（Decoding）。利用已建好的赫夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件Textfile中。 3. 實(shí)現(xiàn)提示 (1) 編碼結(jié)果以文本方式存儲(chǔ)在文件Codefile中。 (2) 用戶界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號(hào)，再加上“Q”，表示退出運(yùn)行Quit。請用戶鍵入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。 (3) 在程序的一次執(zhí)行過程中，第一次執(zhí)行I， D或C命令之后，赫夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因?yàn)槲募fmTree可能早已建好。

8、三、設(shè)計(jì)流程圖 建立哈夫曼樹： 開始 n,<=1 Renturn 0 m=2*n-1 i=1;i<=n;++i While(getchar()=”/n” 輸入字符與權(quán)值 HT[i].ch=z HT[i].weight=w HT[i].parent=0 HT[i].lchild=0 HT[i].rchild=0 編碼： 開始 cd[start]=”1” i=1;i<=n;++i start=n-1 cd[start]=”0” c=I;f=HT[i].parent; f!=0;f=HT[f].parent HT[f].child=

9、=l 結(jié)束 譯碼： 開始 L=k !output_file !cout”cant open file” Return 1 Cout”can’t open file” Strcmp(H[i].hlchild==0 結(jié)束 i=1;i

10、choice==”e” choice==”D”||choice==”d” choice==”Q”||choice==”q” 編碼 四、概要設(shè)計(jì) 1）問題哈夫曼的定義： 1.哈夫曼樹節(jié)點(diǎn)的數(shù)據(jù)類型定義為： typedef struct{ //赫夫曼樹的結(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,

11、int n)初始化哈夫曼樹，處理InputHuffman(Huffman Hfm)函數(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) 3、 int main() 主函數(shù)： 利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmtree.txt中讀入） 對文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile.txt中。如果正文中沒有要編碼的字符，則鍵盤讀入并存儲(chǔ)到ToB

12、eTran文件中。讀入ToBeTran中將要編碼的內(nèi)容，將編碼好的哈夫曼編碼存儲(chǔ)到CodeFile中。 4、Encoding 編碼功能：對輸入字符進(jìn)行編碼 5、Decoding 譯碼功能： 利用已建好的哈夫曼樹將文件codefile.txt中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile.dat 中。 Print() 打印功能函數(shù)：輸出哈夫曼樹，字符，權(quán)值，以及它對應(yīng)的編碼。 6.主函數(shù)的簡要說明，主函數(shù)主要設(shè)計(jì)的是一個(gè)分支語句，讓用戶挑選所實(shí)現(xiàn)的功能。 使用鏈樹存儲(chǔ)，然后分別調(diào)用統(tǒng)計(jì)頻數(shù)函數(shù)，排序函數(shù)，建立哈夫曼函數(shù)，編碼函數(shù)，譯碼函數(shù)來實(shí)現(xiàn)功能。 3）功能模塊： 哈夫曼編

13、碼/譯碼器 初始化哈夫曼樹 編碼 譯碼 打印哈夫曼樹 打印編碼 五、源程序 #include #include #include #include #include typedef struct{ //哈夫曼樹的結(jié)構(gòu)體 char ch; int weight; //權(quán)值 int parent,lchild,rchild; }htnode,*hfmtree; typedef char **

14、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(HT[j].parent==0){ x=j; break; } } for(i=j+1;i<=a;++i){ if(HT[i].weight

15、 } } for(j=1;j<=a;++j) { if(HT[j].parent==0&&x!=j) { y=j; break; } } for(i=j+1;i<=a;++i) { if(HT[i].weighty){ *p1=y; *p2=x; } else { *p1=x; *p2=y; } }

16、 void hfmcoding(hfmtree &HT,hfmcode &HC,int n) //構(gòu)建哈夫曼樹HT，并求出n個(gè)字符的哈夫曼編碼HC { int 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("請輸入第%d字符信息和權(quán)值：",i); scanf("%c%

17、d",&z,&w); while(getchar()!=\n) { continue; } HT[i].ch=z; HT[i].weight=w; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for(;i<=m;++i) //初始化其余的結(jié)點(diǎn) { HT[i].ch=0; HT[i].weight=0; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for(i=n+

18、1;i<=m;++i) //建立哈夫曼樹 { Select(HT,i-1,&p1,&p2); HT[p1].parent=i;HT[p2].parent=i; HT[i].lchild=p1;HT[i].rchild=p2; HT[i].weight=HT[p1].weight+HT[p2].weight; } HC=(hfmcode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char)); cd[n-1]=\0; for(i=1;i<=n;++i)

19、 //給n個(gè)字符編碼 { start=n-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) { if(HT[f].lchild==c) { cd[--start]=0; } else { cd[--start]=1; } } HC[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); } free(cd); }

20、 int main(){ char code[100],h[100],hl[100]; int n,i,j,k,l; ifstream input_file; //文件輸入輸出流 ofstream output_file; char choice,str[100]; hfmtree HT; hfmcode HC; cout<<"\n"; cout<<" "<<"軟件092班"<<" "<<"姓名:張耀飛"<<" "<<"學(xué)號(hào)：3090921040\n" ; while(choice!=Q&&choice!=q)

21、 //當(dāng)choice的值不為q且不為Q時(shí)循環(huán) { cout<<" "<<"*************************哈夫曼編碼/譯碼器*************************\n"; cout<<" "<<"I.Init"<<" "<<"E.Encoding"<<" "<<"D.Decoding"<<" "<<"Q.Exit\n"; cout<<"請輸入您要操作的步驟："; cin>>choice; if(choice=

22、=I||choice==i) //初始化赫夫曼樹 { cout<<"請輸入字符個(gè)數(shù)："; cin>>n; hfmcoding(HT,HC,n); for(i=1;i<=n;++i) { cout<

23、1;i<=n;i++) { output_file<<"("<

24、pen("ToBeTree.txt"); if(!output_file) { cout<<"cant open file!"<

25、;i++){ for(j=0;j<=n;++j) { if(HT[j].ch==str[i]) { output_file<

26、ut_file) { cout<<"cant open file!"<>code; cout<<"編碼碼值為："<

27、ile){ cout<<"cant open file!"<>h; input_file.close(); output_file.open("Textfile.txt"); if(!output_file) { cout<<"cant open file!"<

28、 for(i=1;i<=n;i++){ l=k; for(j=0;j

29、e.txt"); if(!input_file){ cout<<"cant open file!"<>h; cout<

30、 //如果選了選項(xiàng)之外的就讓用戶重新選擇 { cout<<"您沒有輸入正確的步驟，請重新輸入！"<

31、關(guān)頭文件，必定調(diào)試不通過； 在執(zhí)行譯碼操作時(shí)，不知什么原因，總是不能把要編譯的二進(jìn)制數(shù)與編譯成的字符用連接號(hào)連接起來，而是按順序直接放在一起，視覺效果不是很好。還有就是，很遺憾的是，我們的哈夫曼編碼/譯碼器沒有像老師要求的那樣完成編一個(gè)文件的功能，這是我們設(shè)計(jì)的失敗之處。 通過本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)，我學(xué)習(xí)了很多在上課沒懂的知識(shí)，并對求哈夫曼樹及哈夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān)于哈夫曼編碼的知識(shí)，真正學(xué)會(huì)一種算法了。當(dāng)求解一個(gè)算法時(shí),不是拿到問題就不加思索地做，而是首先要先對它有個(gè)大概的了解，接著再詳細(xì)地分析每一步怎么做，無論自己以前是否有處理過

32、相似的問題，只要按照以上的步驟，必定會(huì)順利地做出來。 這次課程設(shè)計(jì)，我在編輯中犯了不應(yīng)有的錯(cuò)誤，設(shè)計(jì)統(tǒng)計(jì)字符和合并時(shí)忘記應(yīng)該怎樣保存數(shù)據(jù)，對文件的操作也很生疏。在不斷分析后明確并改正了錯(cuò)誤和疏漏，我的程序有了更高的質(zhì)量。 八．參考文獻(xiàn)： [1 ] 　譚浩強(qiáng). C 程序設(shè)計(jì)(第二版) [M] . 北京:清華大學(xué)出版社,1999. 161 - 163. [2 ] 　譚浩強(qiáng),張基溫,唐永炎. C 語言程序設(shè)計(jì)教程(第二版) [M] . 北京:高等教育出版社,1998. 113 - 115. [3 ] 　嚴(yán)蔚敏,吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C 語言版) [M] . 北京:清華大學(xué)出版社,2002. 55 - 58. [4] 　李士峰,張謝華,孫清滇. ActiveX文檔技術(shù)在《VB 程序設(shè)計(jì)》網(wǎng)絡(luò)課件制作中的應(yīng)用 [5 ] 　王　穎,王正洲. 漢諾塔問題迭代算法實(shí)現(xiàn)和分析[J ] . 合肥聯(lián)合大學(xué)學(xué)報(bào),1999 , 考核成績評(píng)定： 簽字： 年 月 日 19