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

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁(yè)數(shù)：18 大小：194.50KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

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

版權(quán)說(shuō)明：本文檔由用戶(hù)提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　數(shù)據(jù)結(jié)構(gòu)　　課程設(shè)計(jì)報(bào)告　　設(shè)計(jì)題目：哈夫曼樹(shù)應(yīng)用　　專(zhuān) 業(yè) ：軟件工程 　　班級(jí) ：軟件

2、 　　學(xué) 生： 　　學(xué) 號(hào) ： 　　指導(dǎo)教師： 　　起止時(shí)間：2011-07-04—2011-07-08 <

3、/p>　　2011 年春季學(xué)期　　目錄　　一．具體任務(wù)…..2　　1功能……………………………………………………………………………...2　　2分步實(shí)施……………………………………………………

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

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

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

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

8、t;　　五．源程序9　　六．調(diào)試分析15　　七．心得與體會(huì)18　　八．參考文獻(xiàn)18　　一、任務(wù)<p&

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

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

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

12、t;b>　　3.要求：　　1）界面友好，函數(shù)功能要?jiǎng)澐趾?lt;/p>　　2）總體設(shè)計(jì)應(yīng)畫(huà)一流程圖　　3）程序要加必要的注釋　　要提供程序測(cè)試方案　　程序一定要經(jīng)得起測(cè)試，寧可功能

13、少一些，也要能運(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)的

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

15、以及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)行譯碼

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

17、了“Q”為止。　　(3) 在程序的一次執(zhí)行過(guò)程中，第一次執(zhí)行I， D或C命令之后，赫夫曼樹(shù)已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因?yàn)槲募fmTree可能早已建好。　　三、設(shè)計(jì)流程圖　　建立哈夫曼樹(shù)：

18、　　編碼：　　譯碼：　　主程序：　　四、概要設(shè)計(jì)　　1）問(wèn)題哈夫曼的定義：&

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

20、t,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ī)則建

21、立2叉樹(shù)。此函數(shù)塊調(diào)用了Select（）函數(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ù)：利用已建好的哈夫曼

22、樹(shù)（如不在內(nèi)存，則從文件hfmtree.txt中讀入）　　對(duì)文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile.txt中。如果正文中沒(méi)有要編碼的字符，則鍵盤(pán)讀入并存儲(chǔ)到ToBeTran文件中。讀入ToBeTran中將要編碼的內(nèi)容，將編碼好的哈夫曼編碼存儲(chǔ)到CodeFile中。　　4、Encoding 　　編

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

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

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

26、/p>　　typedef struct{ //哈夫曼樹(shù)的結(jié)構(gòu)體　　char ch;　　int weight; //權(quán)值　　int parent,lchild,rchild;<p

27、>　　}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)　　{</

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é)點(diǎn)　　}　　}　　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é)點(diǎn)　　}　　}　　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) //構(gòu)建哈夫曼樹(shù)HT，并求出n個(gè)字符的哈夫曼編碼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個(gè)葉子結(jié)點(diǎn)　　{　　printf("請(qǐng)輸入第%d字符信息和權(quán)值：",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) //初始化其余的結(jié)點(diǎn)　　{　　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) //建立哈夫曼樹(shù)</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個(gè)字符編碼　　{　　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班"<<" "<<"姓名:張耀飛"<<" "<<"學(xué)號(hào)：3090921040\n" ;<p&g

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

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

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

55、hoice=='I'||choice=='i') //初始化赫夫曼樹(shù)　　{　　cout<<"請(qǐng)輸入字符個(gè)數(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<<"哈夫曼樹(shù)已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入hfmTree

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

61、;b>　　{　　printf("請(qǐng)輸入字符：");　　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中的編碼進(jìn)行譯碼，將譯出來(lái)的字符放入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') //先用編碼中的前幾個(gè)和字符的編碼相比較，然后往后移　　{　　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<<"譯碼結(jié)束，字符已經(jīng)存入Textfile.txt文件中！"<<en

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

81、　　}　　else //如果選了選項(xiàng)之外的就讓用戶(hù)重新選擇　　{　　cout<<"您沒(méi)有輸入正確的步驟，請(qǐng)重新輸入！"

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

83、;　　}　　六、調(diào)試分析　　編碼　　譯碼　　退出<b

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

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

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

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

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

眾賞文庫(kù)> 全部分類(lèi)> 畢業(yè)設(shè)計(jì)

溫馨提示

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

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載