數(shù)據(jù)結(jié)構(gòu)迷宮-學(xué)校超市選址、停車場管理算法

1、精選課程設(shè)計課程：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計名稱： 1.迷宮求解路徑問題2. 停車場管理問題3. 學(xué)校超市選址問題專業(yè)班級：學(xué)生姓名：可編輯精選利用棧實(shí)現(xiàn)迷宮的求解一、 要解決的問題 ：以一個 m*n 的長方陣表示迷宮， 0 和 1 分別表示迷宮中的通路和障礙，設(shè)計一個 程序，對任意設(shè)定的迷宮， 求出一條從入口到出口的通路， 或得出沒有通路的結(jié)論。 二：算法基本思想描述 :用一個字符類型的二維數(shù)組表示迷宮，數(shù)組中每個元素取值“0 ”（表示通路）或“ 1”（表示墻壁）。二維數(shù)組的第 0 行、第 m+1 行、第 0 列、第 m+1 列元素全置成“ 1 ”， 表示迷宮 的邊界；第 1 行第 1 列元素和第 m

2、 行第 n 列元素置成“ 0 ”， 表示迷宮的入口和出口走迷宮的過程可以模擬為一個搜索的過程：每到一處，總讓它按東、南、西、北 4 個方向 順序試探下一個位置；用二維數(shù)組 move 記錄 4 個方向上行下標(biāo)增量和列下標(biāo)增量，則沿第 i 個方向前進(jìn)一步， 可能到達(dá)的新位置坐標(biāo)可利用 move 數(shù)組確定：Px=x+movei0Py=y+movei1如果某方向可以通過，并且不曾到達(dá)，則前進(jìn)一步，在新位置上繼續(xù)進(jìn)行搜索； 如果 4 個方向都走不通或曾經(jīng)到達(dá)過，則退回一步，在原來的位置上繼續(xù)試探下一位置。三：設(shè)計：1）定義三元數(shù)組元素的結(jié)構(gòu)1：數(shù)據(jù)結(jié)構(gòu)的設(shè)計：可編輯精選typedef struct Ma

3、zeDirectint Dx; / 行標(biāo)int Dy; / 列標(biāo)int direct; / 走到下一個坐標(biāo)點(diǎn)的方向 MazeDirect;（2）定義鏈表節(jié)點(diǎn)的結(jié)構(gòu)組成typedef struct LinkNodeelemtype data; / 數(shù)據(jù)域struct LinkNode *next;/ 指針域LinkNode;（3）定義鏈棧的頭指針typedef structLinkNode *top;/ 棧的頭指針LinkStack;（4）移動數(shù)組結(jié)構(gòu)的定義typedef structint x,y;/x 為行標(biāo)， y 為列標(biāo)Direction_increm;【1】迷宮圖的設(shè)計設(shè)迷宮為 m行n列

4、，利用 mazemn來表示一個迷宮，mazei j=0或1;其中：0表示通路，1表示不通，當(dāng)從某點(diǎn)向下試探時，中間點(diǎn)有4個方向可以試探，（見圖）而四個角點(diǎn)有 2個方向，其它邊緣點(diǎn)有3個方向，為使問題簡單化我們用mazem+2n+2來表示迷宮，而迷宮的四周的值全部為1。這樣做使問題簡單了，每個點(diǎn)的試探方向全部為4，不用再判斷當(dāng)前點(diǎn)的試探方向有幾個，同時與迷宮周圍是墻壁這一實(shí)際問題相一致。1111111111【2】試探方向的設(shè)計：可編輯精選在上述表示迷宮的情況下，每個點(diǎn)有4個方向去試探，如當(dāng)前點(diǎn)的坐標(biāo)(x , y),與其相鄰的4個點(diǎn)的坐標(biāo)都可根據(jù)與該點(diǎn)的相鄰方位而得到，如圖2所示。因?yàn)槌隹谠?m，

5、n)，因此試探順序規(guī)定為：從當(dāng)前位置向前試探的方向?yàn)閺恼龞|沿順時針方向進(jìn)行。為了簡化問題，方便的 求出新點(diǎn)的坐標(biāo)，將從正東開始沿順時針進(jìn)行的這4個方向(用0，1，2，3表示東、南、西、北)的坐標(biāo)增量放在一個結(jié)構(gòu)數(shù)組move 4 中，在move 數(shù)組中，每個元素有兩個域組成，x:橫坐標(biāo)增量，y：縱坐標(biāo)增量。Move數(shù)組如圖3所示。move數(shù)組定義如下：typedef struct int x ;/ 行int y ;/ 列 item ;item move4;這樣對move的設(shè)計會很方便地求出從某點(diǎn)(x, y)按某一方向v (0 v3,4,03,3,03,2,1棧中每一組數(shù)據(jù)是所到達(dá)的每走的，對于圖

6、3迷宮，走的路線為:點(diǎn)的坐標(biāo)及從該點(diǎn)沿哪個方向向下2,2,02,1,1 1,1,0(1,1,0)(2,1,1)(2,2,0)(3,2,1)(3,3,0)(3,4,0)(下腳標(biāo)表示方向)，當(dāng)無路可走，則應(yīng)回溯，對應(yīng)的操作是出棧，沿下一個方向即方向繼續(xù)試探。棧中元素是一個由行、列、方向組成的三元組，棧元素的設(shè)計如下：typedef structint x , y , d ;/*橫縱坐標(biāo)及方向*/datatype ;棧的定義為： SeqStack s ;【4.如何防止重復(fù)到達(dá)某點(diǎn)，以避免發(fā)生死循環(huán)：一種方法是另外設(shè)置一個標(biāo)志數(shù)組markmn,它的所有元素都初始化為0, 旦到達(dá)了某一點(diǎn)(i , j )

7、之后，使mark i j 置1，下次再試探這個位置時就不能再走了。另一種方法是當(dāng)?shù)竭_(dá)某點(diǎn)(i , j)后使maze i j 置-1，以便區(qū)別未到達(dá)過的點(diǎn)，同樣也能起到防止走重復(fù)點(diǎn)的目的，此處采用后一方法，算法結(jié)束前可恢復(fù)原迷宮。四：詳細(xì)設(shè)計；1. 算法的設(shè)計思想及流程圖(1) 主要函數(shù)的功能說明void ini_stack(LinkStack *)/* 初始化鏈棧 */int empty_Stack(LinkStack *)/* 判斷是否為空棧 */void push_Stack(LinkStack *,elemtype)/* 入棧 */elemtype pop_Stack(LinkStack

8、 *) /* 出棧 */int size_stack(LinkStack ) /* 棧的規(guī)模大小 */(2) 算法描述【偽代碼描述】迷宮求解算法思想如下：(1) 棧初始化 ;(2) 將入口點(diǎn)坐標(biāo)及到達(dá)該點(diǎn)的方向(設(shè)為 -1 )入棧(3) while ( 棧不空 )棧頂元素=(x , y , d )出棧 ;求出下一個要試探的方向 d+;/ 當(dāng)遇到死路的時候就出棧，尋找原來點(diǎn)的下一個方向 while (還有剩余試探方向時) if ( d 方向可走)則 (x , y , d )入棧 ;求新點(diǎn)坐標(biāo) (i, j ) ;x , y)將新點(diǎn)( i , j )切換為當(dāng)前點(diǎn)(if ( (x , y )= =(

9、m ,n)結(jié)束else 重置 d=0 ;else d+ ;五：源程序清單 ；#include #include int m,n;typedef struct MazeDirectint Dx;int Dy;int direct;MazeDirect;/* 定義三元數(shù)組元素的結(jié)構(gòu) */typedef MazeDirect elemtype;typedef struct LinkNodeelemtype data;struct LinkNode *next;/* 定義鏈表節(jié)點(diǎn)的結(jié)構(gòu)組成 */LinkNode;typedef structLinkNode *top;/* 定義鏈棧的頭指針 */Lin

10、kStack;void ini_stack(LinkStack *stack)/* 初始化鏈棧 */stack-top=NULL;int empty_Stack(LinkStack *stack)/* 判斷是否為空棧 */if (stack-top!=NULL)return 0;elsereturn 1;void push_Stack(LinkStack *stack,elemtype x)/*入棧 */LinkNode *s;s=(LinkNode *)malloc(sizeof(LinkNode);s-data=x;s-next=stack-top;stack-top=s;/* 出棧 */

11、elemtype pop_Stack(LinkStack *stack)elemtype x;LinkNode *p;elemtype tmpNull=0,0,0;if (stack-top=NULL)return tmpNull;/(NULL)elsex=stack-top-data;p=stack-top;stack-top=p-next;free(p);return (x);/* 棧的規(guī)模大小 */int size_stack(LinkStack stack)int i;LinkNode *Numb;i=0;Numb=stack.top;while(Numb!=NULL)Numb=Num

12、b-next;i+;return i;int w,t,maze100100;typedef structint x,y;/x 為行標(biāo)， y 為列標(biāo)Direction_increm;Direction_increm MazeMove4=0,1,1,0,0,-1,-1,0;typedef MazeDirect TmpType;int Maze_path()MazeDirect tmp,path;LinkStack s;int x,y,Px,Py,d,flag=0;ini_stack(&s);tmp.Dx=1;tmp.Dy=1;tmp.direct=-1;push_Stack(&s,tmp);whi

13、le (!empty_Stack(&s)tmp=pop_Stack(&s);遇到死路的時候，回溯（通過出棧完成）x=tmp.Dx;y=tmp.Dy;d=tmp.direct+1;/ while (d4)Px=x+MazeMoved.x;Py=y+MazeMoved.y;if (mazePxPy=0)tmp.Dx=x;tmp.Dy=y;tmp.direct=d;push_Stack(&s,tmp);x=Px;y=Py;mazexy=-1;/* 標(biāo)記，防止重復(fù)點(diǎn) */if(x=m&y=n)flag=1;printf(n 到達(dá)迷宮出口： %d,%d,x,y);printf(n 經(jīng)過的節(jié)點(diǎn)有： %d

14、個 ,size_stack(s);while(!empty_Stack(&s)path=pop_Stack(&s);printf(n(%d,%d,%d),path.Dx,path.Dy,path.direct);break;else d=0;/ 結(jié)束 ifelse d+;/ 結(jié)束內(nèi)部 while/ 結(jié)束外部 whilereturn flag;void main()printf( 請輸入迷宮圖的行數(shù)和列數(shù) (輸入格式為 i,j):n);scanf(%d,%d,&m,&n);printf( 創(chuàng)建迷宮圖 :n);for(w=0;wm+2;w+)for(t=0;ttoptop0) 確保棧不空，然后用個

15、 while(1) 確保輸入的車輛離 開位置的合法性。如果不和法，顯示輸入有誤，要重新輸入。通過 while(Enter-toproom)判斷離開車輛的位置，如果是中間位置，就要再用一個棧前面臨時開出來的車， 等要開出的車開出后， 再把臨時棧的車看進(jìn) 車場內(nèi)， 并要調(diào)用 PRINT(p,room); 這個函數(shù)計算顯示費(fèi)用。然后還要用 if(W-head!=W-rear)&Enter-topMAX)語句判斷便道上有沒有車，如果有車就要顯示進(jìn)車場的車的車牌號，并登記進(jìn)入時間。并要進(jìn)行相應(yīng)的出隊(duì)列和進(jìn)棧操作。五、源程序清單#include#include#include#define MAX 3/

16、停車場最大容量為 3 輛，便于觀察#define price 0.05typedef struct time/ 定義時間結(jié)構(gòu)體int hour;int min;Time;typedef struct node/ 定義車輛信息結(jié)構(gòu)體char num10;Time reach;Time leave;CarNode;typedef struct NODECarNode *stackMAX+1;int top;SeqStackCar;typedef struct carCarNode *data;struct car *next;QueueNode;typedef struct NodeQueueNo

17、de *head;QueueNode *rear;LinkQueueCar;void InitStack(SeqStackCar *);int InitQueue(LinkQueueCar *);int Arrival(SeqStackCar *,LinkQueueCar *);void Leave(SeqStackCar *,SeqStackCar *,LinkQueueCar *);void List(SeqStackCar,LinkQueueCar);void processloop();int prnmenu(void);main()processloop();void process

18、loop()可編輯精選int ichoice,ch;SeqStackCar Enter,T emp;LinkQueueCar Wait;InitStack(&Enter);InitStack(&Temp);InitQueue(&Wait);ichoice=prnmenu();while(ichoice);scanf(%d,&ichoice);while(ichoice4)printf(n 輸入錯誤，請從新輸入 =); scanf(%d,&ichoice);/ 自定義函數(shù)void InitStack(SeqStackCar *s)/ 地址棧的初始化s-top=0;s-stacks-top=NUL

19、L;int InitQueue(LinkQueueCar *Q)/ 隊(duì)列的初始化Q-head=(QueueNode *)malloc(sizeof(QueueNode);if(Q-head!=NULL)Q-head-next=NULL;Q-rear=Q-head;return(1);else return(-1);可編輯精選void PRINT(CarNode *p,int room)/ 車輛收費(fèi)int A1,A2,B1,B2;printf(n車輛離開的時間 :);scanf(%d:%d,&(p-leave.hour),&(p-leave.min);/ 此時 scanf 函數(shù)以 : 為接受數(shù)字

20、結(jié)束符printf(n離開車輛的車牌號為 :);puts(p-num);printf(n其到達(dá)時間為 : %d:%d,p-reach.hour,p-reach.min);printf(n離開時間為 : %d:%d,p-leave.hour,p-leave.min);A1=p-reach.hour;A2=p-reach.min;B1=p-leave.hour;B2=p-leave.min;printf(n應(yīng)交費(fèi)用為 : %2.1f 元 ,(B1-A1)*60+(B2-A2)*price);free(p);/ 車輛的到達(dá)登記int Arrival(SeqStackCar *Enter,LinkQu

21、eueCar *W)CarNode *p;QueueNode *t;p=(CarNode *)malloc(sizeof(CarNode);flushall();printf(n 請輸入車牌號 (例:閩 B1234):);gets(p-num);if(Enter-toptop+;printf(n 車輛在車場第 %d 位置 .,Enter-top);printf(n 車輛到達(dá)時間 :);scanf(%d:%d,&(p-reach.hour),&(p-reach.min);Enter-stackEnter-top=p;elseprintf(n 該車須在便道等待 ! 有車位時進(jìn)入車場 );getch

22、();t=(QueueNode *)malloc(sizeof(QueueNode);t-data=p;t-next=NULL;W-rear-next=t;W-rear=t;void Leave(SeqStackCar *Enter,SeqStackCar *Temp,LinkQueueCar *W) / 車輛的離開 int room;CarNode *p,*t;QueueNode *q;if(Enter-top0) / 判斷車場是否為空while(1)printf(n 請輸入車在車場的位置 /1-%d/ ： ,Enter-top);scanf(%d,&room);if(room=1&room

23、top) break;可編輯精選while(Enter-toproom) / 把要刪除的車輛的前面的車開出來，進(jìn)臨時棧。 即如果是 1， 2 號就要用到臨時棧，如果 enter-top=room ，也就是三號的話就不必用到 臨時棧Temp-top+;Temp-stackTemp-top=Enter-stackEnter-top;Enter-stackEnter-top=NULL;Enter-top-;p=Enter-stackEnter-top; / 把要刪除的車輛節(jié)點(diǎn)賦給 p 。Enter-stackEnter-top=NULL;Enter-top-;while(Temp-top=1) /

24、再把臨時棧里德車輛進(jìn)停車場Enter-top+;Enter-stackEnter-top=Temp-stackTemp-top;Temp-stackTemp-top=NULL;Temp-top-;PRINT(p,room); / 調(diào)用計費(fèi)函數(shù)計費(fèi)。 。 if(W-head!=W-rear)&Enter-tophead-next;t=q-data;Enter-top+;printf(n便道的 %s 號車進(jìn)入車場第 %d 位置 .,t-num,Enter-top);printf(n請輸入 %s 號車進(jìn)入車場的時間 :,t-num);scanf(%d:%d,&(t-reach.hour),&(t-r

25、each.min);W-head-next=q-next;if(q=W-rear) W-rear=W-head;Enter-stackEnter-top=t;free(q);else printf(n便道里沒有車 .n);else printf(n 車場里沒有車 .);void List1(SeqStackCar *S) / 顯示車場里的車輛情況int i;if(S-top0)可編輯精選printf(n 車場 :);printf(n 位置 到達(dá)時間 車牌號 n);for(i=1;itop;i+)printf( %d ,i);printf( %d:%d ,S-stacki-reach.hour,

26、S-stacki-reach.min);puts(S-stacki-num);else printf(n 車場里沒有車 );void List2(LinkQueueCar *W) / 顯示便道上的車輛情況QueueNode *p;int i;p=W-head-next;可編輯精選if(W-head!=W-rear)printf(n 等待車輛的號碼為 :);for(i=1; (p!=NULL); i+)printf(n 第 %d 車輛 .,i);puts(p-data-num);p=p-next ;else printf(n 便道里沒有車 .);printf(n);int menu()int i

27、choice;system(cls);printf( 查看車輛列表顯示 : );printf(n 1. 車場列表 n 2. 便道列表 n 3. 返回主菜單 n);printf(n 請選擇 =);scanf(%d,&ichoice);while(ichoice3)printf(n 輸入錯誤，請重新輸入 =); scanf(%d,&ichoice);return ichoice;/ 顯示 ,遍歷void List(SeqStackCar S,LinkQueueCar W)int ichoice;ichoice=menu();while(ichoice2、車輛到達(dá)登記信息，為了便于觀察，車場內(nèi)最多可

28、停3輛車，當(dāng)停車場已滿時，只登記車牌號，然后進(jìn)入便道上，即進(jìn)入隊(duì)列中?？删庉嫐g迎使用停車場系統(tǒng)1.車輛至lj達(dá)登記2,車輛離超記3,車輛列表顯不*2 B ill S7p Jli_L| L請選擇=1請輸入車牌號C例：閩旳貂Q :Eb於車須在便追等侍亍有車位旳進(jìn)入車場歡迎使用停車場系統(tǒng)1.三輛到達(dá)登記2車輛離己3三輛歹4g Uj 歹 Ox -JU lJ_i 5JU諳選擇=1請輸入車牌號t例:B1234：F6b車須在便道等待?有車位時進(jìn)入車場3 、分別顯示車場內(nèi)和便道上的車輛信息情況 示表列 M.H車閒主看場追回 12 3請選擇=2 蓋待車輛的號碼為:黒1車輛Mk 2車輛應(yīng)第3車輛用查看年郵懐顯示:

29、3堆回主彙單請選擇=1到達(dá)時間5:366：ae7:36車牌號A1B2C34、車場內(nèi)車輛離開時，輸入離開時間，然后計算、顯示費(fèi)用，如果便道上有 車，則顯示要進(jìn)入車場內(nèi)的車牌號碼，同時登記時間。歡迎使用停軍場統(tǒng)I1 車橢IJ達(dá)登記2.車輛離開登記3 * 車輛歹lj表顯喬廠4,退岀系統(tǒng) 請選擇=2諳輸入車在車場的位置2車輛離開的時間=14:30離開車輛的車牌號為汕乂M的1;!30B-3 86:;14Sa 為:間為拘號號時間黑D4D4達(dá)時蓉的人到開交這輸苴籬應(yīng)便請O35* 13 B課程設(shè)計題目：學(xué)校超市選址問題、要解決的問題及其要求:對于某一學(xué)校超市，其他各單位到其距離不同，同時各單位人員去超市的頻

30、度也不同，請為超市選址，要求實(shí)現(xiàn)總體最優(yōu)。、算法基本思想描述 創(chuàng)建圖G，利用普里姆算法得到最小生成樹的路徑和各邊權(quán)值，然后用數(shù)組名為a的數(shù)組（初始值為無窮大）存儲最小生成樹的權(quán)值。其后利用數(shù)組名為a的數(shù)組創(chuàng)建新圖R,即將數(shù)組a的元素賦給新圖的存儲邊權(quán)值的數(shù)組R-arcs.adj，在新圖的基礎(chǔ)上利用佛洛依德算法求得任意兩點(diǎn)之間的最短然后再求生成樹路徑及其相應(yīng)的路徑長度（將其存儲在數(shù)組名為 A的數(shù)組中）上各點(diǎn)到其他點(diǎn)的距離之和 果一次存到數(shù)組名為 B 的數(shù)組中，再對 B 數(shù)組元素進(jìn)行比較大小，求得最小元 素，其下標(biāo)即為最優(yōu)點(diǎn)存儲在定點(diǎn)數(shù)組 vexs 中的序號。A01+A02+A03+.AG-vex

31、 nu mG-vex num，然后將求和結(jié)三、詳細(xì)設(shè)計1. 數(shù)據(jù)結(jié)構(gòu)的設(shè)計（1）鄰接矩陣數(shù)據(jù)結(jié)構(gòu)：typedef structVRType adj; / 相通情況AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;（2）圖的數(shù)據(jù)結(jié)構(gòu)：typedef structVertexType vexsMAX_VERTEX_NUM;/ / 頂點(diǎn)向量AdjMatrix arcs; / 鄰接矩陣int fMAX_VERTEX_NUM; / 各 單 位 去超市的頻率；int vexnum,/ 圖的當(dāng)前頂點(diǎn)數(shù)arcnum;/ 圖的當(dāng)前弧數(shù) MGraph;（3 ）記錄從頂點(diǎn)集 U 到 V-U

32、 的代價最小的邊的輔助數(shù)組的數(shù)據(jù)結(jié)構(gòu)： typedef structVertexType adjvex;VRType lowcost;minsideMAX_VERTEX_NUM;2. 算法的設(shè)計思想及流程圖（1）主要函數(shù)的功能說明1. 若G中存在頂點(diǎn)u,則返回該頂點(diǎn)在圖中位置 否則返回-1。int LocateVex（MGraph ,VertexType u）52. 數(shù)組（鄰接矩陣 ）表示法,構(gòu)造無向網(wǎng) G。int Create(MGraph *) ； 由于要輸入定點(diǎn)名稱和權(quán)值來建立無向圖，所以在此處要調(diào)用 locatevex(Mgraph,VertexType u) 找到對應(yīng)該點(diǎn)名稱的存儲在

33、數(shù)組中的序 號int Create(MGraph *) ；3.or(i=0;iG.vexnum;i+)for(j=0;jarc.adj, 作 為新圖 R 各邊的權(quán)值，然后經(jīng)由佛洛依德算法得到任意兩點(diǎn)之間的最短路 徑，存到數(shù)組 A 中( 2 ) 計 算 各 點(diǎn) 分 別 到 所 有 其 他 點(diǎn) 的 路 徑 值 之 和 ， 即B0,B1,B2 .BG-vexnum(3) 再顯示佛洛依德算法的計算過程，即顯示各點(diǎn)到其他點(diǎn)的路徑(無窮大 的權(quán)值對應(yīng)的邊不顯示)(4 )根據(jù)計算出來的B數(shù)組的數(shù)組，選擇出最小值，求出其對應(yīng)下標(biāo)所對 應(yīng)的頂點(diǎn)名稱，即為超市的最佳地址(2) 模塊結(jié)構(gòu)及流程圖(3) 主要模塊算法

34、描述【1】用普里姆算法從第u個頂點(diǎn)出發(fā)構(gòu)造網(wǎng)G的最小生成樹T,輸出 T的各條邊void Min iSpa nTree_PRIM(MGraph,VertexType,i nt)構(gòu)造出最小生成樹后，利用數(shù)組 a (初始值各個元素為無窮大)存儲 最小生成樹各邊的權(quán)值?！?.用佛洛依德算法求帶權(quán)有向圖的最短路徑void Floyed(MGraph *,MGraph *)首先先將數(shù)組a的各個元素賦給新圖R,作為新圖R各邊的權(quán)值，然后經(jīng)由佛洛依德算法得到任意兩點(diǎn)之間的最短路徑，然后存到數(shù)組 A 中 將最小生成樹的各點(diǎn)到其他點(diǎn)的距離相加, 存到數(shù)組 B 中。在通過對數(shù)組 B 元素的比較大小, 是最小值的那一

35、點(diǎn)即為最優(yōu)點(diǎn), 因?yàn)樵擖c(diǎn)到其他點(diǎn)的距離 最小四、課程設(shè)計過程中的關(guān)鍵算法(1)佛洛依德算法表述：第一步,讓所有路徑加上中間頂點(diǎn) 1 ,取 Ai j 與 Ai1+A1j 中較小的 值作Aij的新值，完成后得到A(1),如此進(jìn)行下去，當(dāng)?shù)趉步完成后，A( k) ij表示從i到就且路徑上的中間頂點(diǎn)的路徑的序號小于或等于 k的最短路徑長 度。當(dāng)?shù)?n-1 步完成后，得到 A(n-1 )， A(n-1 )即所求結(jié)果。 A(n-1 ) ij 表示從 i 到 j 且路徑上的中點(diǎn)頂點(diǎn)的序號小于或等于 n-1 的最短路徑長度，即 A(n-1)ij 表示從 i 到 j 的最短路徑長度。代碼如下：void Floy

36、ed(MGraph *G,MGraph *R)/ 帶權(quán)有向圖求最短路徑 floyd 算法intAMAX_VERTEX_NUMMAX_VERTEX_NUM,BMAX_VERTEX_NUM,pathMAX_VERTEX_NUMMAX_VERTEX_NUM;int i,j,k,pre,min;int countMAX_VERTEX_NUM;for(i=0;ivexnum;i+)始化 A 和 path 數(shù)組for(j=0;jvexnum;j+)值；Aij=R-arcsij.adj; pathij=-1;counti=0; for(k=0;kvexnum;k+) 驟for(i=0;ivexnum;i+)

37、/ 初/ 置初/k 代表運(yùn)算步for(j=0;jvexnum;j+)if(Aij(Aik+Akj)/ 從 i 經(jīng) j 到 k 的一條路徑更短Aij=Aik+Akj;pathij=k;(2 )普里姆算法 :void MiniSpanTree_PRIM(MGraphG,VertexType u,intaMAX_VERTEX_NUMMAX_VERTEX_NUM)int i,j,k,m;minside closedge;k=LocateVex(G,u);for(j=0;jG.vexnum;+j) / 輔助數(shù)組初始化if(j!=k)strcpy(closedgej.adjvex,u);/ 所有邊依附的在 U 中 的頂點(diǎn)為 uclosedgej.lowcost=G.arcskj.adj;/ 所有節(jié)點(diǎn) j 到 節(jié)點(diǎn) k 的距離closedgek.lowcost=0; /初始 ,U=uprintf( 最小代價生成樹的各條邊為 :n);for(i=1;iG.vexnum;+i) / 選擇其余 G.vexnum-1 個頂點(diǎn)k=minimum(closedge,G);