數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---關(guān)于最短路徑問題和二叉樹排序問題

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---關(guān)于最短路徑問題和二叉樹排序問題_第1頁

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

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

文檔簡介

1、　　課程設(shè)計綜合成績評定　　設(shè)計題目一：二叉排序樹 　　設(shè)計題目二：最短路徑問題 　　設(shè)計題目三： <

2、/p>　　目錄　　1.二叉排序樹1　　1.1 問題描述1　　1.2 設(shè)計方案與概要設(shè)計2　　1.3 詳細設(shè)計4

3、;　　1.4 程序運行說明與結(jié)果11　　2.最短路徑問題13　　2.1 問題描述13　　2.2 設(shè)計方案與概要設(shè)計16　　2.3 詳細設(shè)計17　　2.4 程序運行說明與結(jié)果27<

4、p>　　3.總結(jié)與分析32　　1. 二叉排序樹　　1.1 問題描述　　知二叉排序樹的二叉鏈表存儲結(jié)構(gòu)的類型定義如下：　　typedef struct node{ &l

5、t;/p>　　int data; //用整數(shù)表示一個結(jié)點的名　　struct node *LChild,*RChild; //左右指針域　　}BSTNode,*BSTree; 　?。?）鍵盤輸入一個元素序列創(chuàng)建一棵如圖（1）的二叉排序樹，并輸出該二叉排序樹的中序遍

6、歷序列；　　圖（1）　?。?）在圖（1）中所得的二叉排序樹中插入一個值為58的結(jié)點，輸　　出它的中序遍歷序列； 　　（3）在題（2）中所得的二叉排序樹中刪除值為45的結(jié)點，輸出它的中序遍歷序列；<p&

7、gt;　?。?）我們知道教材中P220給出的二叉排序樹的刪除操作算法中，是用左子樹中最右下結(jié)點來替代要被刪除的結(jié)點（即為要被刪除結(jié)點的中序前驅(qū)），也可以用右子樹中最左下結(jié)點來替代要被刪除的結(jié)點（即為要被刪除結(jié)點的中序后繼），根據(jù)此思路修改P220算法在寫一個刪除操作，并利用修改后的刪除算法刪除圖（1）中二叉排序樹的值為45的結(jié)點，輸出它的中序遍歷序列；　?。?）利用題（2）中所得的二叉排序樹的所

8、有葉子結(jié)點構(gòu)造一個帶頭結(jié)點的單鏈表L。要求不能破壞這棵二叉排序樹。所得的單鏈表L元素遞增，并輸出單鏈表L。　?。?）設(shè)計算法將圖（1）的二叉排序樹的左右子樹進行交換。最后輸出所得到的二叉樹的中序遍歷序列。　　所得二叉排序樹如圖所示：　　圖（2）<

9、p>　?。?）用計算法統(tǒng)計并輸出圖（1）中所得的二叉排序樹中只有一個孩子結(jié)點的結(jié)點個數(shù)。　?。?）由圖（1）的二叉排序樹，用計算法并編寫程序輸出結(jié)點40的所有祖先結(jié)點。　　1.2 設(shè)計方案與概要設(shè)計　　二叉排序樹應(yīng)用的存儲結(jié)構(gòu)　　typedef struct no

10、de{ // 二叉排序樹的存儲結(jié)構(gòu)　　int data; 　　struct node *LChild,*RChild; 　　}BSTNode,*BSTree; 　　typedef struct LNode{ //單鏈表的存儲結(jié)構(gòu)

11、　　int data;　　struct LNode *next;　　}LNode,*LinkList;　　二叉排序樹的設(shè)計用到了單鏈表L。　　單鏈表L主要用于題（5）的設(shè)計，用來存儲圖（1）的

12、二叉排序樹中所有葉子結(jié)點，并將其輸出。　　2.方案設(shè)計　　本方案設(shè)計主要應(yīng)用二叉樹的性質(zhì)。創(chuàng)建空二叉排序樹T，再輸入圖（1）中的元素后向T插入所有元素，在插入時比根結(jié)點小的放在樹的左子樹，比根結(jié)點大則放在樹的右子樹，同時樹的左右子樹也要遵循這個規(guī)律。　　在刪除操作中當只有一個

13、結(jié)點時可直接刪除，否則用左子樹中最右下結(jié)點來替代要被刪除的結(jié)點進行刪除操作，亦可用右子樹中最左下結(jié)點來替代要被刪除的結(jié)點進行刪除操作，可視為同種刪除方法。　　尋找葉子節(jié)點時主要采用遞歸方法，從根結(jié)點開始遍歷當發(fā)現(xiàn)結(jié)點無左右孩子時則得到當前的結(jié)點元素并用尾插法將其放入單鏈表中直至遍歷完畢，最后輸出單鏈表L。　　在二叉排序樹進行左右子樹交換時新創(chuàng)建樹R避免對

14、樹T的干擾，把樹T復(fù)制給樹R,調(diào)用樹R采用遞歸法和交換法進行左右子樹的交換。　　尋找只有一個孩子結(jié)點的結(jié)點個數(shù)時也是采用遞歸法，從根結(jié)點開始遍歷當發(fā)現(xiàn)結(jié)點只有左孩子或右孩子是則計數(shù)加1直至遍歷完畢，輸出最后的計數(shù)。　　在取某元素的祖先結(jié)點時，從根結(jié)點與該元素對比并尋找該元素，其所走路徑即為該元素的祖先結(jié)點路徑，因此用數(shù)組將該路徑存儲起來，并將其輸出。&l

15、t;/p>　　設(shè)計程序的整體功能結(jié)構(gòu)（整體算法的描述）　　void create(BSTree &T):用來創(chuàng)建樹，輸入樹的所有元素；　　int search(BSTree T,int K,BSTree &q)：對樹進行查找，判斷元素是否存在樹中；　　void inse

16、rt(BSTree &T,int e)：對樹進行元素插入；　　void deleteBST(BSTree &T,int k,int &e)：刪除中序前驅(qū)，用左子樹中最右下結(jié)點來替代要被刪除的結(jié)點；　　void deleteBST1(BSTree &T,int k,int &e)：刪除中序后驅(qū)，用右子樹中最左下結(jié)點來

17、替代要被刪除的結(jié)點；　　void outTree(BSTree &T)：中序遍歷函數(shù)，并輸出T;　　int createList(LinkList &L): 創(chuàng)建單鏈表L并為空;　　int insertList(LinkList &L,int e)：用尾插法向單鏈表插入元素；</p&

18、gt;　　void leaf(BSTree T,LinkList &L)：得到樹T的葉子節(jié)點，并得到其結(jié)點； 　　void outList(LinkList L)：輸出點鏈表； 　　BSTree copy(BSTree T)：創(chuàng)建樹R,把樹T復(fù)制給R；　　void create1(

19、BSTree &R)：把樹R的左右子樹進行交換； 　　int jie(BSTree R)：計算只有一個孩子結(jié)點元素的個數(shù); 　　void bstree(BSTree R,int e)：得到某元素的祖先結(jié)點并將其輸出； 　　int main()：主函數(shù); <p

20、>　　1.3 詳細設(shè)計　　#include <stdio.h>　　#include <stdlib.h>　　#define TRUE 1　　#define FALSE 0<

21、p>　　#define MAX 20　　typedef struct node{ // 二叉排序樹的存儲結(jié)構(gòu) 　　int data; //用整數(shù)表示一個結(jié)點的名　　struct node *LChild,*RChild; //左右指針域<

22、p>　　}BSTNode,*BSTree; 　　typedef struct LNode{ //單鏈表的存儲結(jié)構(gòu)　　int data;　　struct LNode *next;　　}LNode,*LinkList;</

23、p>　　創(chuàng)建樹函數(shù)：　　void create(BSTree &T){　　int e;　　BSTree q;<b&g

24、t;　　T=NULL;　　printf("請輸入二叉樹的根：");　　scanf("%d",&e);　　printf("依次輸入個結(jié)點以-1結(jié)束：\n");　　while(e!=-1)

25、　　{ if(!search(T,e,q)) 　　insert(T,e);　　scanf("%d",&e);　　}　　}

26、;　　樹元素查找函數(shù)：　　int search(BSTree T,int K,BSTree &q){　　BSTree p,f;　　p=T;<

27、b>　　f=NULL;　　if(p==NULL)　　return FALSE;　　while(p){　　if(K==p->data)　　{

28、 q=p;　　return TRUE;}　　else if(K<p->data)　　{ f=p;　　p=p->LChild;}

29、　else　　{ f=p; 　　p=p->RChild;}　　} 　　q=f;　　return FALSE;<p&

30、gt;　　} 　　對樹進行插入函數(shù)：　　void insert(BSTree &T,int e){　　BSTree p,q;　　if(T==NULL)<

31、p>　　{ p=(BSTree)malloc(sizeof(BSTNode));　　p->data=e;　　p->LChild=p->RChild=NULL;　　T=p;}　　else&

32、lt;/b>　　{ if(!search(T,e,q))　　{ p=(BSTree)malloc(sizeof(BSTNode));　　p->data=e;　　p->LChild=p->RChild=NULL;&

33、lt;p>　　if(e<q->data)　　q->LChild=p;　　else　　q->RChild=p;}　　}<

34、b>　　}　　刪除函數(shù)（刪除中序前驅(qū)）：　　void deleteBST(BSTree &T,int k,int &e){　　BSTree q,s,v,t;　　q=T;

35、　　v=NULL;　　while(q)　　{ if(k==q->data) break; 　　else if(k<q->data)<b&g

36、t;　　{ v=q;　　q=q->LChild;}　　else　　{ v=q;　　q=q->RChild;}&

37、lt;b>　　}　　if(!q) 　　{ printf("我要刪除的數(shù)字不存在。\n");　　return;}　　e=q->data;<p

38、>　　if(q->LChild&&q->RChild)　　{ s=q->LChild;　　v=q;　　while(s->RChild)　　{ v=s;<

39、/b>　　s=s->RChild;}　　q->data=s->data;　　q=s;　　}　　if(q->LChild)

40、 t=q->LChild;　　else t=q->RChild;　　if(q==T) T=t;　　else if(q==v->LChild) v->LChild=t;　　else v->RChild=t;<

41、/p>　　free(q);　　} 　　刪除函數(shù)（刪除中序后繼）：　　void deleteBST1(BSTree &T,int k,int &e){　　BSTree q,s

42、,v,t;　　q=T;　　v=NULL;　　while(q)　　{ if(k==q->data) break;

43、　　else if(k<q->data)　　{ v=q;　　q=q->LChild;}　　else　　{ v=q;</b&g

44、t;　　q=q->RChild;}　　}　　if(!q) 　　{ printf("你要刪除的數(shù)字不存在。\n");　　return;}

45、　　e=q->data;　　if(q->LChild&&q->RChild)　　{ s=q->RChild;　　v=q;　　w

46、hile(s->LChild)　　{ v=s;　　s=s->LChild;}　　q->data=s->data;　　q=s;

47、　　}　　if(q->RChild) t=q->RChild;　　else t=q->LChild;　　if(q==T) T=t;　　else if(q==v->RChild) v-

48、>RChild=t;　　else v->LChild=t;　　free(q);　　} 　　中序遍歷函數(shù)： 　　void outTre

49、e(BSTree &T){　　if(T)　　{ outTree(T->LChild);　　printf("%4d",T->data);　　outTree(T->RChild);<

50、;/p>　　}　　}　　創(chuàng)建單鏈表： 　　int createList(LinkList &L){ //單鏈表初始化 <

51、p>　　L=(LinkList)malloc(sizeof(LNode));　　if(!L) return FALSE;　　L->next=NULL;　　return TRUE; 　　} </p&

52、gt;　　單鏈表插入函數(shù)：　　int insertList(LinkList &L,int e){ //向單鏈表插入元素 　　LNode *p=L,*q;　　q=(LNode *)malloc(sizeof(LNode));

53、;　　if(!q) return FALSE;　　while(p->next!=NULL)　　p=p->next;　　q->data=e;　　q->next=p->next;<p

54、>　　p->next=q;　　} 　　葉子結(jié)點函數(shù): 　　void leaf(BSTree T,LinkList &L){　　if(T){ <

55、;p>　　if(T->LChild==NULL&&T->RChild==NULL)　　insertList(L,T->data);　　leaf(T->LChild,L);　　leaf(T->RChild,L);} <

56、;b>　　}　　單鏈表輸出函數(shù)： 　　void outList(LinkList L){ //輸出單鏈表　　LNode *p;　　p=L->next;

57、;　　while(p)　　{ printf("%4d",p->data); 　　p=p->next;}　　}　　創(chuàng)建樹R函數(shù)：</b&

58、gt;　　BSTree copy(BSTree T){ //把樹T復(fù)制到樹R　　BSTree R;　　if(T==NULL) return NULL; 　　R=(BSTree)malloc(sizeof(BSTNode)

59、);　　R->data=T->data;　　R->LChild=copy(T->LChild);　　R->RChild=copy(T->RChild);　　return R;

60、　　}　　樹R左右子樹交換函數(shù)： 　　void create1(BSTree &R){ 　　BSTree q; 　　if(R)<p&g

61、t;　　{ create1(R->LChild); 　　create1(R->RChild);　　q=R->RChild;　　R->RChild=R->LChild;　　R->LChild=q;<p&

62、gt;　　}　　}　　計算只有一個孩子結(jié)點的函數(shù)： 　　int jie(BSTree R){ 　　int left,right,a;　　if(!

63、R) return 0;　　if(R->LChild==NULL&&R->RChild!=NULL)　　return 1;　　if(R->LChild!=NULL&&R->RChild==NULL)

64、;　　return 1;　　left=jie(R->LChild);　　right=jie(R->RChild); 　　a=left+right;　　return a;

65、;　　}　　祖先結(jié)點函數(shù)： 　　void bstree(BSTree R,int e){ 　　int v[MAX],i=0,j;　　BSTree q=R;<

66、b>　　while(q)　　{ if(e==q->data) break; 　　else if(e<q->data)　　{ v[i]=q->data;　　q=q->RChild;}</p&

67、gt;　　else　　{ v[i]=q->data;　　q=q->LChild;}　　++i;　　}

68、;　　if(!q) return;　　for(j=0;j<i;j++)　　printf("%4d",v[j]);　　} 　　主函數(shù)： </b&

69、gt;　　int main(){ 　　int e,k,a=0;　　char c;　　BSTree T,R;　　LinkList L;　　create

70、(T);　　printf("1、該二叉排序樹的中序遍歷序列：\n");　　outTree(T);　　R=copy(T);　　create1(R);　　printf("\n2、輸入你插入的數(shù)字：&quo

71、t;);　　scanf("%d",&e);　　insert(T,e);　　outTree(T);　　printf("\n3、請輸入你要刪除的數(shù)字：");　　scanf("%

72、d",&k);　　deleteBST(T,k,e);　　outTree(T);　　printf("\n4、請輸入你要刪除的數(shù)字：");　　scanf("%d",&k);<p&g

73、t;　　deleteBST1(T,k,e);　　outTree(T); 　　createList(L);　　printf("\n5、是否輸出葉子結(jié)點構(gòu)成的單鏈表 Y or N: ");　　scanf("%s",&c);&

74、lt;/p>　　if(c=='Y')　　{ leaf(T,L);　　outList(L);}　　printf("\n6、是否輸出二叉排序樹的左右子樹進行交換后的二叉樹 Y or N: ");　　sc

75、anf("%s",&c);　　if(c=='Y')　　outTree(R); 　　printf("\n7、是否輸出二叉排序樹中只有一個孩子結(jié)點的結(jié)點個數(shù) Y or N: ");　　scanf("

76、;%s",&c);　　if(c=='Y')　　printf("%4d",jie(R));　　printf("\n8、請輸入要求祖先結(jié)點的元素: ");　　scanf("%d",

77、&e);　　bstree(R,e); 　　system("pause");　　return 0;　　} 　　1

78、.4 程序運行說明與結(jié)果　　1、創(chuàng)建二叉排序樹，并以中序遍歷輸出圖（1）：　　向二叉排序樹插入元素58：　　3、刪除二叉排序樹元素45（刪除中序前驅(qū)）：　　4、刪除二叉排序樹元素45（刪除中序后繼）：　　由于在3中已刪除45，故

79、給出提示，輸出原樹。　　5、輸出葉子結(jié)點：　　由于樹T在2中輸入58，故多了元素58。　　6、交換樹T的左右子樹，輸出圖（2）：　　中序遍歷輸出的圖（2）是圖（1）的倒序。　　輸出只有一個子樹

80、的結(jié)點個數(shù)：　　8、查找元素40的祖先結(jié)點，并輸出：　　9、所有的運行結(jié)果視圖：　　2. 最短路徑問題　　2.1 問題描述　　假設(shè)網(wǎng)中的頂點用一個整數(shù)來

81、表示，并從0開始編號，若網(wǎng)中有n個頂點，則這n個頂點為0，1，……，n-1。并假設(shè)網(wǎng)中不存在頂點到自身的弧。若網(wǎng)采用鄰接矩陣存儲結(jié)構(gòu)，則直接用一個二維數(shù)組來表示。如下圖所示的一個有向網(wǎng)：　　圖（1）　?。?）基于圖的鄰接表存儲結(jié)構(gòu)重新設(shè)計dijkstra算法及其輸出算法，并以圖（1）的有向網(wǎng)為測試實例編程實現(xiàn)。<

82、;/p>　?。?）dijkstra算法適合求解權(quán)值非負的單源最短路徑問題，即求一個頂點到其余各個頂點的最短路徑?，F(xiàn)給定一個有向網(wǎng)G=(V,E)，各條邊上的權(quán)值均非負，給定G中一個頂點t，要求求出其余各個頂點到頂點t的最短路徑長度并構(gòu)造最短路徑，這個問題稱為單目標最短路徑問題。基于鄰接矩陣存儲結(jié)構(gòu)設(shè)計算法并以圖（1）的有向網(wǎng)為測試實例編程實現(xiàn)。　　（3）假設(shè)dijkst

83、ra算法采用鄰接矩陣存儲結(jié)構(gòu)，利用dijkstra算法求有向網(wǎng)中任意兩個頂點間的最短路徑長度并構(gòu)造最短路徑。以圖（1）的有向網(wǎng)為測試實例編程實現(xiàn)。　?。?）假設(shè)dijkstra算法采用鄰接矩陣存儲結(jié)構(gòu)，求有向網(wǎng)中頂點i到頂點j的最短路徑長度并輸出最短路徑，只求頂點i到頂點j的最短路徑，不能有冗余的循環(huán)，i和j從鍵盤輸入，并作為函數(shù)參數(shù)。　?。?）dijk

84、stra算法不僅可以求解有向網(wǎng)中權(quán)值非負的單源最短路徑問題，對于無向網(wǎng)中權(quán)值非負的單源最短路徑問題，同樣適用。　　設(shè)G=(V,E)是一個連通無向網(wǎng)，采用鄰接矩陣存儲結(jié)構(gòu)，每條邊上的權(quán)值均非負，從G中任取一個頂點i，考慮頂點i到各個頂點的最短路徑長度：d(i,0)，d(i,1)，……，d(i,n-1)　　其中d(i,k)（0≤k≤n-1）表示頂點i到頂點k

85、的最短路徑長度，規(guī)定d(i,i)=0。這n個值中最大的那個稱為頂點i的最大距離，記為L(i)，在所有頂點中，使L(i)達到最小的頂點稱為網(wǎng)G的中心。利用dijkstra算法編程求解給定無向網(wǎng)的中心。　　例如，下面這個無向網(wǎng)的中心為頂點5　　圖（2）　?。?）假設(shè)將5題中的網(wǎng)看

86、成是一個礦區(qū)，它有7個礦，分別在頂點0,1，…..,6處，這7個礦每天的礦產(chǎn)量分別是0：3000t，1：2000t，2：7000t，3：1000t，4：5000t，5：1000t，6：4000t，如下圖所示。　　圖（3）　　現(xiàn)在要在頂點0,1，…..,6中選一個來建選礦廠，如果選礦廠建在了頂點i，那么我們關(guān)心的是將各

87、個礦生產(chǎn)的礦石都運到頂點i處的運輸量是多少，然后再來確定在哪里建選礦廠最好。一般情況下，我們以運輸?shù)膖×km數(shù)來度量運輸量的大小，一噸貨物運輸一公里就叫1t×km。例如，如果選礦廠建在頂點0處，則總的運輸量表示為g(0)，它等于　　g(0)=3000×0+2000×3+7000×5+1000×6.3+5000×9.3+1000

88、×4.5+4000×6=122300(t×km)　　如果選礦廠建在頂點1處，則總的運輸量表示為g(1)，它等于　　g(1)=3000×3+2000×0+7000×2+1000×3.3+5000×6.3+1000×1.5+4000×3=68300(t

89、5;km)　　顯然，選礦廠建在頂點1要比建在頂點0處好，因為建在頂點1處時運輸量較小。當然，頂點1是不是最好的還不能確定，應(yīng)把g(0)，g(1)，…，g(6)都算出來再比較一下，才可以選出一個最好的建廠地點。　　一般情況下，給定無向網(wǎng)G=(V,E)，采用鄰接矩陣存儲結(jié)構(gòu)，每條邊上的權(quán)值均非負，G的每個頂點i還有一個“產(chǎn)量”A(i)，對于每個頂點i，令：&

90、lt;/p>　　g(i)=A(0)×d(0,i)+ A(1)×d(1,i)+……+A(n-1)×d(n-1,i)　　其中d(k,i)（0≤k≤n-1）表示頂點k到頂點i的最短路徑長度。　　g(i)代表了把各個點的物資運到頂點i處所花費的t×km，對于具有n個頂點的無向網(wǎng)G來說，使得g(i

91、)達到最小的那個頂點i就稱為該網(wǎng)的中央點，利用dijkstra算法編程求解給定無向網(wǎng)的中央點。　　例如，上述圖（3）的中央點為頂點2。　　2.2 設(shè)計方案與概要設(shè)計　　最短路徑問題應(yīng)用的存儲結(jié)構(gòu)　　typedef struct ArcNode{ </p&g

92、t;　　int weight;　　int adjvex; 　　struct ArcNode *nextarc; 　　}ArcNode; 　　typedef struct VNode{

93、　　VertexType data; 　　ArcNode *firstarc; 　　}VNode; 　　typedef struct {　　VNode vertices[MAX];<

94、;p>　　int vexnum,arcnum; 　　int kind;　　}ALGraph;　　應(yīng)用到很多的數(shù)組，其g[100][100]用于鄰接矩陣存儲，d[100]用于存儲路徑長度,path[100]用于存儲上一個鄰接點,f

95、inal[100]用于區(qū)分集合S和V，final[]=1時在集合S,final[]=0時在集合V。　　2.方案設(shè)計　　通過鄰接表尋找有向圖中源點到各點的最短路徑，要先創(chuàng)建鄰接表。把dijkstra算法設(shè)計為利用鄰接表查找最短路徑的算法，在輸入源點后調(diào)用方法并進行輸出操作。至于單目標問題創(chuàng)建一個與原鄰接表相反的逆鄰接表

96、，如果創(chuàng)建成功則與源點問題相同。任意兩點間的最短路徑是把個元素分別作為源點，依次調(diào)用方法并進行輸出，得到任意兩點間的最短路徑。固定兩點的最短路徑是通過鄰接矩陣實現(xiàn)，利用dijkstra算法得到所有的最短路徑，在輸出時只輸出固定兩點的最短路徑。無向網(wǎng)的最短路徑方法亦可用dijkstra算法實現(xiàn)，得到以所有元素為源點的最短路徑，并獲得每個元素的最大距離，然后比較每個元素的最大距離得到最小距離即為網(wǎng)G的中心。在獲得每個元素到個頂點距離時同時乘

97、以每個元素的運輸量，得到總運輸量，進行在比較得到運輸量最小的元素即為該網(wǎng)的中央點。　　設(shè)計程序的整體功能結(jié)構(gòu)（整體算法的描述）　　int LocateVex(ALGraph &G, VertexType v)：查找元素是否存在有向圖中；　　void CreateDG(ALGraph &G,ALGr

98、aph &L)：創(chuàng)建鄰接表有向圖G和其逆鄰接表；　　void GraphOutput(ALGraph &G)：用鄰接表輸出有向圖G;　　void dijkstra(int s,ALGraph &G) ：鄰接表型的dijkstra算法；　　void out(int s,ALGraph &a

99、mp;G)：鄰接表dijkstra算法的輸出；　　void out1(int s,ALGraph &L)：單目標的最短路徑輸出；　　void dijkstra(int n,int s,int v)：兩定點間的dijkstra算法；　　void out(int n,int s,int v)：兩定點間的路徑輸

100、出；　　void dijkstra(int n, int s)：dijkstra算法；　　void out(int n, int s)：最短路徑輸出和獲得最大距離；　　void out1(int n, int s)：輸出總運輸量；　　int main():主函數(shù)； &

101、lt;/p>　　2.3 詳細設(shè)計　　題（1）、（2）和（3）代碼如下：　　#include <stdio.h>　　#include <stdlib.h>　　#include <

102、;string.h>　　#define MAX 20　　typedef char VertexType[MAX]; //頂點類型　　typedef struct ArcNode{ //有向圖,省略的第二個成員　　int weight;

103、;　　int adjvex; 　　struct ArcNode *nextarc; 　　}ArcNode; 　　typedef struct VNode{　　VertexType data; </p&

104、gt;　　ArcNode *firstarc; 　　}VNode; 　　typedef struct {　　VNode vertices[MAX];　　int vexnum,arcnum; </p&

105、gt;　　int kind;　　}ALGraph;　　查找函數(shù)： 　　int LocateVex(ALGraph &G, VertexType v)

106、;　　{ int i;　　for (i=0;i<G.vexnum;i++)　　if(strcmp(G.vertices[i].data,v)==0) 　　return i;<p

107、>　　return -1;}　　創(chuàng)建有向圖： 　　void CreateDG(ALGraph &G,ALGraph &L){ 　　int i,k,j,a,x,y;　　VertexType v1,v2;

108、;　　ArcNode *p,*s;　　G.kind=3;　　printf("請輸入有向圖的頂點數(shù)：\n");　　scanf("%d",&(G.vexnum));　　printf(&quo

109、t;請輸入有向圖的邊數(shù):\n");　　scanf("%d",&(G.arcnum));　　L.vexnum=G.vexnum;　　L.arcnum=G.arcnum;　　for(k=0;k<G.vexnum;k++)</p

110、>　　{ getchar();　　printf("輸入第%d個頂點: ",k+1);　　scanf("%s",G.vertices[k].data);　　strcpy(L.vertices[k].data,G.vertices[k].dat

111、a);　　G.vertices[k].firstarc=NULL; 　　L.vertices[k].firstarc=NULL;}　　for(k=0;k<G.arcnum;k++)　　{ getchar();　　print

112、f("輸入第%d邊和權(quán)值\n",k+1);　　scanf("%s%s%d",v1,v2,&a);　　i= LocateVex (G,v1);　　j= LocateVex (G,v2);　　x= LocateVex (

113、L,v1);　　y= LocateVex (L,v2);　　if(i<0 ||j<0||x<0||y<0) {printf("error!!!!!"); return ;}　　p=(ArcNode *) malloc(sizeof(ArcNode));

114、;　　s=(ArcNode *) malloc(sizeof(ArcNode));　　p->adjvex=j;　　s->adjvex=x;　　p->weight=a;　　s->weight=a;<

115、p>　　p->nextarc=G.vertices[i].firstarc;　　s->nextarc=L.vertices[y].firstarc;　　G.vertices[i].firstarc =p; 　　L.vertices[y].firstarc =s; <

116、p>　　}　　}　　輸出鄰接表函數(shù)：　　void GraphOutput(ALGraph &G) //鄰接表的輸出

117、　　{ int i;　　ArcNode *s;　　for(i=0;i<G.vexnum;i++)　　{ printf("(%d)%s: ",i,G.vertices[i].data);　　s=G.vertices[i].firstarc;

118、　　while(s)　　{ printf("--->%4d 權(quán)值%d",s->adjvex,s->weight); s=s->nextarc; }　　printf("\n"); } }

119、　　鄰接表dijkstra算法函數(shù)：　　int final[100],d[100],path[100];　　void dijkstra(int s,ALGraph &G) 　　{ int i,j,k,min,b;

120、ArcNode *p;　　p=G.vertices[s].firstarc;　　final[s]=1;　　for(i=0;i<G.vexnum;i++)　　if(i!=s){<b&

121、gt;　　d[i]=999;　　path[i]=-1;　　final[i]=0;}　　while(p){ 　　d[p->adjvex]=p->weight;　　path[p->adjve

122、x]=s; 　　p=p->nextarc;　　}　　for(j=1;j<G.vexnum;j++)　　{ min=999;　　for(i=0;i<G.vexnum;

123、i++)　　if(!final[i]&&d[i]<=min)　　{ min=d[i];　　k=i; }　　if(d[k]==999)　　break;</b&

124、gt;　　final[k]=1;　　p=G.vertices[k].firstarc;　　while(p){ 　　b=p->adjvex;　　if(!final[b]&&p->weight+d[k]&l

125、t;d[b])　　{ d[b]=p->weight+d[k];　　path[p->adjvex]=k; 　　}　　p=p->nextarc;　　}&l

126、t;/b>　　}　　}　　鄰接表dijkstra算法輸出函數(shù)：　　void out(int s,ALGraph &G){ 　　i

127、nt b[100];　　int i,j,p,m;　　dijkstra(s, G);　　for(i=0;i<G.vexnum;i++)　　if(i!=s){ 　　p=path[i];

128、　if(p==-1) 　　printf("從源點%d到頂點%d不存在路徑!\n",s,i); 　　else{　　printf("從源點%d到頂點%d的最短路徑長度為%d!\n",s,i,d[i]);<p

129、>　　printf("從源點%d到頂點%d的最短路徑為:",s, i);　　m=0;　　b[m]=i;　　m++;　　while(p

130、!=s){ 　　b[m]=p;　　p=path[p];　　m++;　　}　　b[m]=s;&l

131、t;/b>　　for(j=m;j>=0;j--)　　printf("%4d",b[j]);　　printf("\n");　　}<b&g

132、t;　　}　　}　　單目標輸出函數(shù)：　　void out1(int s,ALGraph &L){ 　　int b[100];&l

133、t;p>　　int i,j,p,m;　　dijkstra(s, L);　　for(i=0;i<L.vexnum;i++)　　if(i!=s){ 　　p=path[i];　　if(p==-1)

134、　　printf("從源點%d到頂點%d不存在路徑!\n",i,s); 　　else{　　printf("從源點%d到頂點%d的最短路徑長度為%d!\n",i,s,d[i]);　　printf("從源點%d

135、到頂點%d的最短路徑為:",i,s);　　m=0;　　b[m]=i;　　m++;　　while(p!=s){ <p

136、>　　b[m]=p;　　p=path[p];　　m++;　　}　　b[m]=s;<p

137、>　　for(j=0;j<=m;j++)　　printf("%4d",b[j]);　　printf("\n");　　}　　}

138、　　}　　主函數(shù)：　　int main()　　{ int v,i;　　char a;<p&g

139、t;　　ALGraph G,L;　　CreateDG(G,L);　　printf("有向圖鄰接表\n");　　GraphOutput(G);　　printf("輸入源點v\n");　　sca

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

溫馨提示

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---關(guān)于最短路徑問題和二叉樹排序問題

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---關(guān)于最短路徑問題 和 二叉樹排序問題

文檔簡介

溫馨提示

最新文檔

評論

免費下載

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---關(guān)于最短路徑問題和二叉樹排序問題