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

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

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

已閱讀1頁(yè)，還剩33頁(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ì)綜合成績(jī)?cè)u(píng)定　　設(shè)計(jì)題目一：二叉排序樹(shù) 　　設(shè)計(jì)題目二：最短路徑問(wèn) 題 　　設(shè)計(jì)題目三： <

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17、替代要被刪除的結(jié)點(diǎn)；　　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)：得到樹(shù)T的葉子節(jié)點(diǎn)，并得到其結(jié)點(diǎn)； 　　void outList(LinkList L)：輸出點(diǎn)鏈表； 　　BSTree copy(BSTree T)：創(chuàng)建樹(shù)R,把樹(shù)T復(fù)制給R；　　void create1(

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

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

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

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

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

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

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

26、;　　樹(shù)元素查找函數(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;　　} 　　對(duì)樹(shù)進(jìn)行插入函數(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("我要?jiǎng)h除的數(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("你要?jiǎng)h除的數(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é)點(diǎn)函數(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)建樹(shù)R函數(shù)：</b&

58、gt;　　BSTree copy(BSTree T){ //把樹(shù)T復(fù)制到樹(shù)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、　　}　　樹(shù)R左右子樹(shù)交換函數(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;　　}　　}　　計(jì)算只有一個(gè)孩子結(jié)點(diǎn)的函數(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é)點(diǎn)函數(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、該二叉排序樹(shù)的中序遍歷序列：\n");　　outTree(T);　　R=copy(T);　　create1(R);　　printf("\n2、輸入你插入的數(shù)字：&quo

71、t;);　　scanf("%d",&e);　　insert(T,e);　　outTree(T);　　printf("\n3、請(qǐng)輸入你要?jiǎng)h除的數(shù)字：");　　scanf("%

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

87、個(gè)礦生產(chǎn)的礦石都運(yùn)到頂點(diǎn)i處的運(yùn)輸量是多少，然后再來(lái)確定在哪里建選礦廠最好。一般情況下，我們以運(yùn)輸?shù)膖×km數(shù)來(lái)度量運(yùn)輸量的大小，一噸貨物運(yùn)輸一公里就叫1t×km。例如，如果選礦廠建在頂點(diǎn)0處，則總的運(yùn)輸量表示為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)　　如果選礦廠建在頂點(diǎn)1處，則總的運(yùn)輸量表示為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)　　顯然，選礦廠建在頂點(diǎn)1要比建在頂點(diǎn)0處好，因?yàn)榻ㄔ陧旤c(diǎn)1處時(shí)運(yùn)輸量較小。當(dāng)然，頂點(diǎn)1是不是最好的還不能確定，應(yīng)把g(0)，g(1)，…，g(6)都算出來(lái)再比較一下，才可以選出一個(gè)最好的建廠地點(diǎn)。　　一般情況下，給定無(wú)向網(wǎng)G=(V,E)，采用鄰接矩陣存儲(chǔ)結(jié)構(gòu)，每條邊上的權(quán)值均非負(fù)，G的每個(gè)頂點(diǎn)i還有一個(gè)“產(chǎn)量”A(i)，對(duì)于每個(gè)頂點(diǎn)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）表示頂點(diǎn)k到頂點(diǎn)i的最短路徑長(zhǎng)度。　　g(i)代表了把各個(gè)點(diǎn)的物資運(yùn)到頂點(diǎn)i處所花費(fèi)的t×km，對(duì)于具有n個(gè)頂點(diǎn)的無(wú)向網(wǎng)G來(lái)說(shuō)，使得g(i

91、)達(dá)到最小的那個(gè)頂點(diǎn)i就稱(chēng)為該網(wǎng)的中央點(diǎn)，利用dijkstra算法編程求解給定無(wú)向網(wǎng)的中央點(diǎn)。　　例如，上述圖（3）的中央點(diǎn)為頂點(diǎn)2。　　2.2 設(shè)計(jì)方案與概要設(shè)計(jì)　　最短路徑問(wèn)題應(yīng)用的存儲(chǔ)結(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]用于鄰接矩陣存儲(chǔ)，d[100]用于存儲(chǔ)路徑長(zhǎng)度,path[100]用于存儲(chǔ)上一個(gè)鄰接點(diǎn),f

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

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

97、以每個(gè)元素的運(yùn)輸量，得到總運(yùn)輸量，進(jìn)行在比較得到運(yùn)輸量最小的元素即為該網(wǎng)的中央點(diǎn)。　　設(shè)計(jì)程序的整體功能結(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)：?jiǎn)文繕?biāo)的最短路徑輸出；　　void dijkstra(int n,int s,int v)：兩定點(diǎn)間的dijkstra算法；　　void out(int n,int s,int v)：兩定點(diǎn)間的路徑輸

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

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

102、;string.h>　　#define MAX 20　　typedef char VertexType[MAX]; //頂點(diǎn)類(lèi)型　　typedef struct ArcNode{ //有向圖,省略的第二個(gè)成員　　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("請(qǐng)輸入有向圖的頂點(diǎn)數(shù)：\n");　　scanf("%d",&(G.vexnum));　　printf(&quo

109、t;請(qǐng)輸入有向圖的邊數(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個(gè)頂點(diǎn): ",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("從源點(diǎn)%d到頂點(diǎn)%d不存在路徑!\n",s,i); 　　else{　　printf("從源點(diǎn)%d到頂點(diǎn)%d的最短路徑長(zhǎng)度為%d!\n",s,i,d[i]);<p

129、>　　printf("從源點(diǎn)%d到頂點(diǎn)%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;　　}　　}　　單目標(biāo)輸出函數(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("從源點(diǎn)%d到頂點(diǎn)%d不存在路徑!\n",i,s); 　　else{　　printf("從源點(diǎn)%d到頂點(diǎn)%d的最短路徑長(zhǎng)度為%d!\n",i,s,d[i]);　　printf("從源點(diǎn)%d

135、到頂點(diǎn)%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("輸入源點(diǎn)v\n");　　sca

眾賞文庫(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ù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---關(guān)于最短路徑問(wèn)題和二叉樹(shù)排序問(wèn)題

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載

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