數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(赫夫曼樹的建立)

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

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

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

文檔簡介

1、　　哈夫曼樹的建立　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)文檔　　班級(jí)： 　　小組組長: 　　成員： &

2、lt;/p>　　指導(dǎo)老師： 　　第一章前言　　數(shù)據(jù)結(jié)構(gòu)作為一門學(xué)科主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及對(duì)數(shù)據(jù)的各種操作。因此，主要有三個(gè)方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)；對(duì)數(shù)據(jù)的操作（或算法）。通常，算法的設(shè)計(jì)取決于數(shù)據(jù)的邏輯

3、結(jié)構(gòu)，算法的實(shí)現(xiàn)取決于數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是信息的一種組織方式，其目的是為了提高算法的效率，它通常與一組算法的集合相對(duì)應(yīng)，通過這組算法集合可以對(duì)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行某種操作。在當(dāng)今信息時(shí)代，信息技術(shù)己成為當(dāng)代知識(shí)經(jīng)濟(jì)的核心技術(shù)。我們時(shí)刻都在和數(shù)據(jù)打交道。比如人們在外出工作時(shí)找最短路徑，在銀行查詢存款、通過互聯(lián)網(wǎng)查新聞、以及遠(yuǎn)程教育報(bào)名等，所有這些都在與數(shù)據(jù)發(fā)生關(guān)系。實(shí)際上，現(xiàn)實(shí)世界中的實(shí)體經(jīng)過抽象以后，就可以成為計(jì)算機(jī)上所處理的

4、數(shù)據(jù)。數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中所出現(xiàn)的計(jì)算機(jī)操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)軟件和計(jì)算機(jī)硬件之間的一門計(jì)算機(jī)專業(yè)的核心課程，它是計(jì)算機(jī)程序設(shè)計(jì)、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了將實(shí)際問題中所涉及的對(duì)象在計(jì)算機(jī)中表示出來并對(duì)它們　　通過此次課程設(shè)計(jì)主要達(dá)到以下目的：

5、　　了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；　　初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能；　　提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力；　　四、訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟

6、件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。　　概要設(shè)計(jì)　　數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)　　使用樹TREE的結(jié)構(gòu)，編造最優(yōu)二叉樹（即哈夫曼樹），涉及到主要函數(shù)有Inithuffmantree,Destoryhuffmantree,huffmancodeing

7、,Visithuffmantree等，用于在一定時(shí)間復(fù)雜度內(nèi)尋找到最佳（最短）路徑，節(jié)約比較次數(shù)。　　層次調(diào)用關(guān)系　　在main（）函數(shù)中調(diào)用哈夫曼樹的各種操作函數(shù)　　ADT描述 　　H

8、uffman tree 　　{　　? 數(shù)據(jù)對(duì)象D: D為帶有各自實(shí)數(shù)W(D)的數(shù)據(jù)元素的集合　　數(shù)據(jù)關(guān)系：D=NULL 則huffmantree不存在D≠NULL R={H}.H為如下二元關(guān)系： </p&g

9、t;　　? ①D中存在唯一根數(shù)據(jù)元素root,這個(gè)元素?zé)o前驅(qū)。 　　? ②D-{root} ≠NULL.則存在D-{root} ={D1，Dr}.且D1∧Dr=NULL 　　? ③若D1 ≠NULL ，則D1

10、中存在唯一元素xr,<root, xr>∈H ? 　　且存在Dr上關(guān)系Hr∈H,H= {<root,x1>,<root,xr>,H1,Hr}; 　　? ④符合① ② ③的R的組合中，存在一個(gè)組合R’使D中所有結(jié)點(diǎn)到roo

11、t的長度與其權(quán)值W(Di)相乘的和最小，此時(shí)的<D/R>集合稱為huffmantree.　　}　　詳細(xì)設(shè)計(jì)　　編譯環(huán)境：VC6.0　　實(shí)現(xiàn)該該程序的主要算法是：

12、;　　基本操作　　Init huffmantree(&T) 　　操作結(jié)果：構(gòu)造一個(gè)已知節(jié)點(diǎn)和權(quán)值的哈夫曼樹　　Destory huffmantree(&T) 　　條件：huffman

13、tree 已存在　　結(jié)果：銷毀huffmantree　　huffman coding（&T）　　條件：huffmantree 已經(jīng)存在　　結(jié)果：輸出huffman code　　Visit huffmantree（&

14、T)　　條件：huffmantree 已經(jīng)存在　　結(jié)果：顯示huffman tree　　一、二叉樹的設(shè)計(jì)　　typedef struct　　{</p

15、>　　unsigned int weight;　　unsigned int parent,lchild,rchild;　　} HTNode,*HuffmanTree;　　typedef char **HuffmanCode;　　typedef

16、struct　　{　　unsigned int s1;　　unsigned int s2;　　}MinCode;　　二、主要過程<

17、/b>　　int main()　　{　　int code=0;　　HuffmanTree HT=NULL;　　HuffmanCode HC=NULL;<p&

18、gt;　　unsigned int *w=NULL;　　unsigned int i,n;　　printf("Input n:\n"); 　　scanf("%d",&n);　　w=

19、(unsigned int*)malloc((n+1)*sizeof(unsigned int*)); w[0]=0; 　　printf("Enter weight:\n"); &#

20、160; 　　for(i=1;i<=n;i++)　　{ 　　printf("w[%d]=",i);　　scanf("%

21、d",&w[i]); 　　} 　　HT=inithuffmantree(w,n); 　　huff

22、mantreecoding (HT,HC,n) 　　outputhuffmantree (HT,n); 　　destroyhuffmantree (HT);　　}&l

23、t;/p>　　三、結(jié)構(gòu)流程圖　　程序代碼　　#include<stdio.h>　　#include<stdlib.h>　　#include<

24、;cstring>　　#include<conio.h>　　#include<iostream>　　#include<algorithm>　　using namespace std;　　t

25、ypedef struct　　{　　unsigned int weight;　　unsigned int parent,lchild,rchild;　　} HTNode,*HuffmanTree;<p&g

26、t;　　typedef char **HuffmanCode;　　typedef struct　　{　　unsigned int s1;　　unsigned int s2;

27、　}MinCode;　　void outputhuffmantree(HuffmanTree HT,unsigned int n);　　HuffmanTree inithuffmantree(unsigned int *w,unsigned int n);　　HuffmanCode huffm

28、antreecoding(HuffmanTree HT,HuffmanCode HC,unsigned int n);　　void Error(char *message);　　MinCode Select(HuffmanTree HT,unsigned int n);　　void destroyhuffmant

29、ree(HuffmanTree *ht);　　void Error(char *message)　　{　　fprintf(stderr,"Error:%s\n",message);　　exit(1

30、);　　}　　void destroyhuffmantree(HuffmanTree ht)　　{　　cout<<"-------------------

31、------------------------------------------------------------"<<endl;　　free(ht);　　printf("huffmantree destroied\n");&l

32、t;b>　　exit(1);　　}　　HuffmanCode huffmantreecoding(HuffmanTree HT,HuffmanCode HC,unsigned int n)　　{

33、;　　char *cd;　　unsigned int i,start,c,f;　　HC=(HuffmanCode)malloc((n+1)*sizeof(char *));　　cd=(char *)malloc(n*sizeof(char *));<

34、;/p>　　cd[n-1]='\0';　　for(i=1;i<=n;i++)　　{　　start=n-1;　　for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[

35、f].parent)　　if(HT[f].lchild==c) cd[--start]='0';　　else　　cd[--start]='1';　　HC[i]=(char *)malloc((n-sta

36、rt)*sizeof(char *));　　strcpy(HC[i],&cd[start]);　　}　　free(cd);　　cout<<"-------------

37、------------------------------------------------------------------"<<endl;　　printf("Number\t\tWeight\t\tCode\n");　　for(i=1;i<=n;i++)

38、　printf("%d\t\t%d\t\t%s\n",i,HT[i].weight,HC[i]);　　return HC;　　}　　HuffmanTree inithuffmantree(unsigned int *w,unsigned int n)<

39、;/p>　　{　　unsigned int i,s1=0,s2=0;　　HuffmanTree p,HT;　　unsigned int m;　　MinCode min;<p&g

40、t;　　if(n<=1) Error("節(jié)點(diǎn)數(shù)量太少，創(chuàng)建失??！\n");　　m=2*n-1;　　HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));　　if(!HT)<

41、;/p>　　Error("無法創(chuàng)建哈夫曼樹，請查看磁盤空間是否足夠！");　　for(p=HT,i=0;i<=n;i++,p++,w++)　　{　　p->weight=*w;

42、　　p->parent=0;　　p->lchild=0;　　p->rchild=0;　　}　　for(;i<=m;i++,p++)　　{</b&

43、gt;　　p->weight=0;　　p->parent=0;　　p->lchild=0;　　p->rchild=0;　　}

44、　for(i=n+1;i<=m;i++)　　{　　min=Select(HT,i-1);　　s1=min.s1;　　s2=min.s2;　　HT[s1].parent=i;</p&

45、gt;　　HT[s2].parent=i;　　HT[i].lchild=s1;　　HT[i].rchild=s2;　　HT[i].weight=HT[s1].weight+HT[s2].weight;　　}<

46、;/p>　　return HT;　　}　　MinCode Select(HuffmanTree HT,unsigned int n)　　{　　unsigned int

47、min,secmin;　　unsigned int temp;　　unsigned int i,s1,s2,tempi;　　MinCode code;　　s1=1;　　s2=

48、1;　　for(i=1;i<=n;i++)　　if(HT[i].parent==0)　　{　　min=HT[i].weight;　　s1=i;<

49、;/b>　　break;　　}　　tempi=i++;　　for(;i<=n;i++)　　{</p

50、>　　if(HT[i].weight<min&&HT[i].parent==0)　　{　　min=HT[i].weight;　　s1=i;<

51、b>　　}　　}　　for(i=tempi;i<=n;i++)　　{　　if(HT[i].parent==0&&i!=s1)

52、　　{　　secmin=HT[i].weight;　　s2=i;　　break;　　}</p&g

53、t;　　}　　for(i=1;i<=n;i++)　　{　　if(HT[i].weight<secmin&&i!=s1&&HT[i].parent==0)

54、　　{　　secmin=HT[i].weight;　　s2=i;　　}　　}

55、　　if(s1>s2)　　{　　temp=s1;　　s1=s2;　　s2=t

56、emp;　　}　　code.s1=s1;　　code.s2=s2;　　return code;　　}<p

57、>　　void outputhuffmantree(HuffmanTree HT,unsigned int n)　　{　　unsigned int i;　　printf("HT List:\n");　　p

58、rintf("Number\t\tweight\t\tparent\t\tlchild\t\trchild\n");　　cout<<"********************************************************************************"<<endl;

59、　　for(i=n+1;i<=2*n-1;i++)　　printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);　　}&l

60、t;p>　　int main()　　{　　int code=0;　　HuffmanTree HT=NULL;　　HuffmanCode HC=NULL;　　unsigned int *w

61、=NULL;　　unsigned int i,n;　　P:　　system("color A");　　cout<<"※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※

62、※"<<endl;　　cout<<"※ ※"<<endl;　　cout<<"※

63、哈夫曼樹計(jì)算與編碼程序 ※"<<endl;　　cout<<"※ ※"<<endl;

64、cout<<"※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※"<<endl<<endl;　　printf("請輸入節(jié)點(diǎn)的數(shù)量(大于1個(gè)):\n");　　scanf("%d",&n);<p&g

65、t;　　if(n==1)　　{　　system("CLS");　　printf("節(jié)點(diǎn)數(shù)太少,請重新輸入.....\n");　　for(int j=1;j&

66、lt;600000000;j++){;}　　system("CLS");　　goto P;　　}　　w=(unsigned int *)malloc((n+1)*sizeof(

67、unsigned int *));　　w[0]=0;　　printf("請輸入它們對(duì)應(yīng)的權(quán)值:\n");　　for(i=1;i<=n;i++)　　{

68、　　printf("w[%d]=",i);　　scanf("%d",&w[i]);　　}　　sort(w+1,w+n+1);　　HT=inithuffmantree(

69、w,n);　　GP:　　system("CLS");　　cout<<"*******************************************************************************&qu

70、ot;<<endl;　　cout<<" 1.哈夫曼樹編碼 "<<endl;　　cout<<" 2.哈弗曼樹顯示

71、 "<<endl;　　cout<<" 3.摧毀哈夫曼樹并退出程序 "<<endl;　　cout<

72、;<" "<<endl;　　cout<<"**********************************************************************

73、*********"<<endl;　　cout<<"請輸入操作編碼："<<endl;　　cin>>code;　　system("CLS");　　switch(code)<

74、;/p>　　{　　case 1:　　{　　huffmantreecoding(HT,HC,n);　　system("PA

75、USE");　　cout<<endl<<endl;　　goto GP;　　break;　　}<

76、;p>　　case 2:　　{　　outputhuffmantree(HT,n);　　system("PAUSE");　　cout<<endl<<

77、endl;　　goto GP;　　break;　　}　　case 3:<

78、;b>　　{　　destroyhuffmantree(HT);　　system("PAUSE");　　break;　　}<

79、;p>　　default:　　{　　system("color A");　　cout<<"非法字符，請重新輸入"<<endl<<endl;

80、;　　for(int j=0;j<700000000;j++){}　　system("CLS");　　goto GP;　　break;<b&g

81、t;　　}　　}　　return 0;　　}　　測試顯示結(jié)果

82、;　　初始界面：　　輸入節(jié)點(diǎn)及權(quán)值：　　選擇界面：　　哈夫曼樹編碼界面：　　哈夫曼樹顯示：</b

83、>　　退出界面：　　總結(jié)　　A：主要負(fù)責(zé)程序的設(shè)計(jì)和代碼的編輯。根據(jù)《數(shù)據(jù)結(jié)構(gòu)-C語言版》作者嚴(yán)蔚敏、吳偉民著一書的理論知識(shí)，以及章節(jié)后的偽代碼，我適合的更改，做出了課程設(shè)計(jì)中的作品。在打代碼的過程中，出現(xiàn)好多次錯(cuò)誤，在網(wǎng)上查找，

84、得到解決。這次課程設(shè)計(jì)對(duì)數(shù)據(jù)結(jié)構(gòu)有了更深的認(rèn)識(shí)。　　B：主要負(fù)責(zé)文檔的編寫。這次的課程設(shè)計(jì)中，與王文忠配合，把課程設(shè)計(jì)的文檔寫出來。為了更好地展現(xiàn)我們的成果以及代碼，對(duì)于調(diào)試代碼的界面，我們以截圖的方式展現(xiàn)在文檔中，讓讀者更好地查看。　　C：主要負(fù)責(zé)文檔的編寫。在這次課程設(shè)計(jì)及中，學(xué)到了很多知識(shí)，還有很多知識(shí)還要現(xiàn)學(xué)。只要用心，就能學(xué)到自己想學(xué)的東西。&

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

溫馨提示

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(赫夫曼樹的建立)

文檔簡介

溫馨提示

最新文檔

評(píng)論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(赫夫曼樹的建立)

文檔簡介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載