哈夫曼樹課程設計報告

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：18 大?。?94.50KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩17頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　數(shù)據(jù)結構　　課程設計報告　　設計題目：哈夫曼樹應用　　專業(yè) ：軟件工程 　　班級：軟件

2、 　　學生： 　　學號： 　　指導教師： 　　起止時間：2011-07-04—2011-07-08 <

3、/p>　　2011 年春季學期　　目錄　　一．具體任務…..2　　1功能……………………………………………………………………………...2　　2分步實施……………………………………………………

4、…………………...2.　　3要求……………………………………………………………………………...2　　二．哈夫曼編碼2　　1問題描述2　　2.基本要求3

5、;　　3實現(xiàn)提示3　　三．設計流程圖4　　1建立哈夫曼樹…………………………………………………………………...4　　2編碼……………………………………………………………………………...5&

6、lt;/p>　　3譯碼……………………………………………………………………………...6　　4主程序…………………………………………………………………………...7　　四．設計概要8　　1問題哈夫曼的定義.....................

7、.........................................................................8..　　2所實現(xiàn)的功能函數(shù)如下………………………………………………………..8　　3功能模塊………………………………………………………………………..8<b&g

8、t;　　五．源程序9　　六．調試分析15　　七．心得與體會18　　八．參考文獻18　　一、任務<p&

9、gt;　　題目：哈夫曼樹應用　　1.功能： 　　1．從終端讀入字符集大小n，以及n個字符和n個權值，建立哈夫曼樹并將它存于文件hfmTree中.將已在內存中的哈夫曼樹以直觀的方式（比如樹）顯示在終端上；　　2．利用已經(jīng)建好的哈夫曼樹（如不

10、在內存，則從文件htmTree中讀入），對文件ToBeTran中的正文進行　　編碼，然后將結果存入文件CodeFile中，并輸出結果，將文件CodeFile以緊湊格式先是在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrint中。　　3．利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結果存入文件TextFile中，并輸

11、出結果。　　2.分步實施：　　初步完成總體設計，搭好框架，確定人機對話的界面，確定函數(shù)個數(shù)；　　完成最低要求：完成功能1；　　進一步要求：完成功能2和3。有興趣的同學可以自己擴充系統(tǒng)功能。&l

12、t;b>　　3.要求：　　1）界面友好，函數(shù)功能要劃分好　　2）總體設計應畫一流程圖　　3）程序要加必要的注釋　　要提供程序測試方案　　程序一定要經(jīng)得起測試，寧可功能

13、少一些，也要能運行起來，不能運行的程序是沒有價值的。　　二、哈夫曼編碼　　1. 問題描述　　利用赫夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳輸數(shù)據(jù)預先編碼，在接收端將傳來的

14、數(shù)據(jù)進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站編寫一個赫夫曼碼的編/譯碼系統(tǒng)。　　基本要求　　一個完整的系統(tǒng)應具有以下功能：　　(1) I：初始化（Initialization）。從終端讀入字符集大小n，

15、以及n個字符和n個權值，建立赫夫曼樹，并將它存于文件hfmTree中。　　(2) E：編碼（Encoding）。利用已建好的赫夫曼樹（如不在內存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結果存入文件CodeFile中。　　(3) D：譯碼（Decoding）。利用已建好的赫夫曼樹將文件CodeFile中的代碼進行譯碼

16、，結果存入文件Textfile中。　　實現(xiàn)提示　　(1) 編碼結果以文本方式存儲在文件Codefile中。　　(2) 用戶界面可以設計為“菜單”方式：顯示上述功能符號，再加上“Q”，表示退出運行Quit。請用戶鍵入一個選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇

17、了“Q”為止。　　(3) 在程序的一次執(zhí)行過程中，第一次執(zhí)行I， D或C命令之后，赫夫曼樹已經(jīng)在內存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因為文件hfmTree可能早已建好。　　三、設計流程圖　　建立哈夫曼樹：

18、　　編碼：　　譯碼：　　主程序：　　四、概要設計　　1）問題哈夫曼的定義：&

19、lt;p>　　1.哈夫曼樹節(jié)點的數(shù)據(jù)類型定義為：　　typedef struct{ //赫夫曼樹的結構體　　char ch;　　int weight; //權值　　int paren

20、t,lchild,rchild;　　}htnode,*hfmtree;　　2）所實現(xiàn)的功能函數(shù)如下　　1、void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈夫曼樹，處理InputHuffman(Huffman Hfm)函數(shù)得到的數(shù)據(jù)，按照哈夫曼規(guī)則建

21、立2叉樹。此函數(shù)塊調用了Select（）函數(shù)。　　2、void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函數(shù)，選出HT樹到a為止，權值最小且parent為0的2個節(jié)點　　3、 int main()　　主函數(shù)：利用已建好的哈夫曼

22、樹（如不在內存，則從文件hfmtree.txt中讀入）　　對文件中的正文進行編碼，然后將結果存入文件codefile.txt中。如果正文中沒有要編碼的字符，則鍵盤讀入并存儲到ToBeTran文件中。讀入ToBeTran中將要編碼的內容，將編碼好的哈夫曼編碼存儲到CodeFile中。　　4、Encoding 　　編

23、碼功能：對輸入字符進行編碼　　5、Decoding　　譯碼功能：利用已建好的哈夫曼樹將文件codefile.txt中的代碼進行譯碼，結果存入文件textfile.dat 中。　　Print() 打印功能函數(shù)：輸出哈夫曼樹，字符，權值，以及它對應的編碼。　　6.主函數(shù)的簡

24、要說明，主函數(shù)主要設計的是一個分支語句，讓用戶挑選所實現(xiàn)的功能。　　使用鏈樹存儲，然后分別調用統(tǒng)計頻數(shù)函數(shù)，排序函數(shù)，建立哈夫曼函數(shù)，編碼函數(shù)，譯碼函數(shù)來實現(xiàn)功能。　　3）功能模塊：　　五、源程序

25、　　#include<iostream.h>　　#include<stdio.h>　　#include<stdlib.h>　　#include<string.h>　　#include<fstream.h><

26、/p>　　typedef struct{ //哈夫曼樹的結構體　　char ch;　　int weight; //權值　　int parent,lchild,rchild;<p

27、>　　}htnode,*hfmtree;　　typedef char **hfmcode;　　void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函數(shù)，選出HT樹到a為止，權值最小且parent為0的2個節(jié)點　　{</

28、b>　　int i,j,x,y;　　for(j=1;j<=a;++j){　　if(HT[j].parent==0){　　x=j;　　break;

29、;　　}　　}　　for(i=j+1;i<=a;++i){　　if(HT[i].weight<HT[x].weight&&HT[i].parent==0){</p

30、>　　x=i; //選出最小的節(jié)點　　}　　}　　for(j=1;j<=a;++j){　　if(HT[j].parent==0

31、&&x!=j)　　{　　y=j;　　break;　　}<

32、b>　　}　　for(i=j+1;i<=a;++i)　　{　　if(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i)

33、;　　{　　y=i; //選出次小的節(jié)點　　}　　}　　if(x>y){<

34、/p>　　*p1=y;　　*p2=x;　　}　　else　　{</b

35、>　　*p1=x;　　*p2=y;　　}　　}　　void hfmcod

36、ing(hfmtree &HT,hfmcode &HC,int n) //構建哈夫曼樹HT，并求出n個字符的哈夫曼編碼HC　　{　　int i,start,c,f,m,w;　　int p1,p2;　　char *cd,

37、z;　　if(n<=1){　　return;　　}　　m=2*n-1;

38、　HT=(hfmtree)malloc((m+1)*sizeof(htnode));　　for(i=1;i<=n;++i) //初始化n個葉子結點　　{　　printf("請輸入第%d字符信息和權值：",i);

39、;　　scanf("%c%d",&z,&w);　　while(getchar()!='\n')　　{　　continue;

40、　　}　　HT[i].ch=z;　　HT[i].weight=w;　　HT[i].parent=0;　　HT[i].lchild=0;　　HT[i].rchild=0;

41、　　}　　for(;i<=m;++i) //初始化其余的結點　　{　　HT[i].ch='0';　　HT[i].weight=0;</p

42、>　　HT[i].parent=0;　　HT[i].lchild=0;　　HT[i].rchild=0;　　}　　for(i=n+1;i<=m;++i) //建立哈夫曼樹</p&g

43、t;　　{　　Select(HT,i-1,&p1,&p2);　　HT[p1].parent=i;HT[p2].parent=i;　　HT[i].lchild=p1;HT[i].rchild=p2;

44、　　HT[i].weight=HT[p1].weight+HT[p2].weight;　　}　　HC=(hfmcode)malloc((n+1)*sizeof(char *));　　cd=(char *)malloc(n*sizeof(char));&

45、lt;p>　　cd[n-1]='\0';　　for(i=1;i<=n;++i) //給n個字符編碼　　{　　start=n-1;　　for(c=i,f=HT[i].parent;f

46、!=0;c=f,f=HT[f].parent)　　{　　if(HT[f].lchild==c)　　{　　cd[--start]='0';&

47、lt;b>　　}　　else　　{　　cd[--start]='1';　　}

48、;　　}　　HC[i]=(char*)malloc((n-start)*sizeof(char));　　strcpy(HC[i],&cd[start]);　　}　　fre

49、e(cd);　　}　　int main(){　　char code[100],h[100],hl[100];　　int n,i,j,k,l;　　ifstream input

50、_file; //文件輸入輸出流　　ofstream output_file;　　char choice,str[100];　　hfmtree HT;　　hfmcode HC;　　cout<<"\n&q

51、uot;;　　cout<<" "<<"軟件092班"<<" "<<"姓名:張耀飛"<<" "<<"學號：3090921040\n" ;<p&g

52、t;　　while(choice!='Q'&&choice!='q') //當choice的值不為q且不為Q時循環(huán)　　{　　cout<<" "<<"*************

53、************哈夫曼編碼/譯碼器*************************\n";　　cout<<" "<<"I.Init"<<" "<<"E.Encoding"<<"

54、"<<"D.Decoding"<<" "<<"Q.Exit\n";　　cout<<"請輸入您要操作的步驟：";　　cin>>choice;　　if(c

55、hoice=='I'||choice=='i') //初始化赫夫曼樹　　{　　cout<<"請輸入字符個數(shù)：";　　cin>>n;<

56、;/p>　　hfmcoding(HT,HC,n);　　for(i=1;i<=n;++i)　　{　　cout<<HT[i].ch<<":"<<HC[i]<<endl;</

57、p>　　}　　output_file.open("hfmTree.txt");　　if(!output_file){　　cout<<"can't open file!"<<en

58、dl;　　return 1;　　}　　for(i=1;i<=n;i++)　　{　　output_file<

59、;<"("<<HT[i].ch<<HC[i]<<")";　　}　　output_file.close();　　cout<<"哈夫曼樹已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入hfmTree

60、.txt文件中!"<<endl;　　}　　else if(choice=='E'||choice=='e') //進行編碼，并將字符放入ToBeTran.txt，碼值放入CodeFile.txt中<

61、;b>　　{　　printf("請輸入字符：");　　gets(str);　　output_file.open("ToBeTree.txt");　　if(!output_file)&

62、lt;p>　　{　　cout<<"can't open file!"<<endl;　　return 1;　　}<

63、p>　　output_file<<str<<endl;　　output_file.close();　　output_file.open("CodeFile.txt");　　if(!output_file){　　cout&l

64、t;<"can't open file!"<<endl;　　return 1;　　}　　for(i=0;i<strlen(str);i++){

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

66、lt;b>　　break;　　}　　}　　}　　output_file.close();

67、　cout<<"\n";　　cout<<"編碼完畢，并且已經(jīng)存入CodeFile.txt文件！\n";　　input_file.open("CodeFile.txt"); //從CodeFile.txt中讀入編碼，輸出在終端<

68、p>　　if(!input_file)　　{　　cout<<"can't open file!"<<endl;　　return 1;<

69、;b>　　}　　input_file>>code;　　cout<<"編碼碼值為："<<code<<endl;　　input_file.close();　　}&l

70、t;/b>　　else if(choice=='D'||choice=='d') //讀入CodeFile.txt中的編碼進行譯碼，將譯出來的字符放入Textfile.txt中　　{　　input_file.open("

71、CodeFile.txt");　　if(!input_file){　　cout<<"can't open file!"<<endl;　　return 1;

72、　　}　　input_file>>h;　　input_file.close();　　output_file.open("Textfile.txt");　　if(!output_file)<p

73、>　　{　　cout<<"can't open file!"<<endl;　　return 1;　　}

74、;　　k=0;　　while(h[k]!='\0') //先用編碼中的前幾個和字符的編碼相比較，然后往后移　　{　　for(i=1;i<=n;i++){&

75、lt;b>　　l=k;　　for(j=0;j<strlen(HC[i]);j++,l++){　　hl[j]=h[l];　　}　　hl[j]='\0';<p&

76、gt;　　if(strcmp(HC[i],hl)==0)　　{　　output_file<<HT[i].ch;　　k=k+strlen(HC[i]);　　break;

77、;　　}　　}　　}　　output_file.close();　　input_file.open("Textfile.txt

78、");　　if(!input_file){　　cout<<"can't open file!"<<endl;　　return 1;　　}

79、;　　input_file>>h; 　　cout<<h<<endl;　　input_file.close();　　cout<<"譯碼結束，字符已經(jīng)存入Textfile.txt文件中！"<<en

80、dl;　　}　　else if(choice=='Q'||choice=='q') //退出程序　　{ 　　exit(0);

81、　　}　　else //如果選了選項之外的就讓用戶重新選擇　　{　　cout<<"您沒有輸入正確的步驟，請重新輸入！"

82、;<<endl;　　}　　cout<<endl;　　}　　return 0;

83、;　　}　　六、調試分析　　編碼　　譯碼　　退出<b

84、>　　七、實驗心得與體會　　在我自己課程設計中，就在編寫好源代碼后的調試中出現(xiàn)了不少的錯誤，遇到了很多麻煩及困難，我的調試及其中的錯誤和我最終找出錯誤，修改為正確的能夠執(zhí)行的程序中，通過分析，我學到了：　　在定義頭文件時可多不可少，即我們可多寫些頭文件，肯定不會出錯，但是若沒有定義所引用的相關頭文件，必定調試不通過；</p

85、>　　在執(zhí)行譯碼操作時，不知什么原因，總是不能把要編譯的二進制數(shù)與編譯成的字符用連接號連接起來，而是按順序直接放在一起，視覺效果不是很好。還有就是，很遺憾的是，我們的哈夫曼編碼/譯碼器沒有像老師要求的那樣完成編一個文件的功能，這是我們設計的失敗之處。　　通過本次數(shù)據(jù)結構的課程設計，我學習了很多在上課沒懂的知識，并對求哈夫曼樹及哈夫曼編碼/譯碼的算法有了更加深刻的了解，

86、更鞏固了課堂中學習有關于哈夫曼編碼的知識，真正學會一種算法了。當求解一個算法時,不是拿到問題就不加思索地做，而是首先要先對它有個大概的了解，接著再詳細地分析每一步怎么做，無論自己以前是否有處理過相似的問題，只要按照以上的步驟，必定會順利地做出來。　　這次課程設計，我在編輯中犯了不應有的錯誤，設計統(tǒng)計字符和合并時忘記應該怎樣保存數(shù)據(jù)，對文件的操作也很生疏。在不斷分析后明確并改正了錯誤和疏漏，我的程

87、序有了更高的質量。　　八．參考文獻：　　[1 ] 　譚浩強. C 程序設計(第二版) [M] . 北京:清華大學出版社,1999. 161 - 163.　　[2 ] 　譚浩強,張基溫,唐永炎. C 語言程序設計教程(第二版) [M] . 北京:高等教育出版社,1998. 11

88、3 - 115.　　[3 ] 　嚴蔚敏,吳偉民. 數(shù)據(jù)結構(C 語言版) [M] . 北京:清華大學出版社,2002. 55 - 58.　　[4] 　李士峰,張謝華,孫清滇. ActiveX文檔技術在《VB 程序設計》網(wǎng)絡課件制作中的應用 [5 ] 　王　穎,王正洲. 漢諾塔問題迭代算法實現(xiàn)和分析[J ] . 合肥聯(lián)合大學學報,1999 , </p

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

哈夫曼樹課程設計報告

文檔簡介

溫馨提示

最新文檔

評論

哈夫曼樹課程設計報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載