數(shù)據(jù)結構課程設計(赫夫曼樹的建立)

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

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

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

文檔簡介

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

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

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

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

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

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

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

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

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

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

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

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

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

14、T)　　條件：huffmantree 已經(jīng)存在　　結果：顯示huffman tree　　一、二叉樹的設計　　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>　　三、結構流程圖　　程序代碼　　#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é)點數(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、哈夫曼樹計算與編碼程序 ※"<<endl;　　cout<<"※ ※"<<endl;

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

65、t;　　if(n==1)　　{　　system("CLS");　　printf("節(jié)點數(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("請輸入它們對應的權值:\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;　　}　　測試顯示結果

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

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

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

眾賞文庫> 全部分類> 畢業(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. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結構課程設計(赫夫曼樹的建立)

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結構課程設計(赫夫曼樹的建立)

文檔簡介

溫馨提示

最新文檔

評論

免費下載