數(shù)據(jù)結(jié)構(gòu)-課程設(shè)計(jì)-校園最短路徑問題(共12頁)

1、一、課程設(shè)計(jì)題目： 校園最短路徑問題二、課程設(shè)計(jì)目的：1. 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；2. 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能；3. 提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能力；4. 訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所具備的科學(xué)工作方法和作風(fēng)。三、課程設(shè)計(jì)要求：1. 設(shè)計(jì)的題目要求達(dá)到一定的工作量（300行以上代碼），并具有一定的深度和難度。2. 編寫出課程設(shè)計(jì)報告書，內(nèi)容不少于10頁（代碼不算）。四、需求分析 ：1、問題描述圖的最短路徑問題是指從指定的某一點(diǎn)v開始，求得從

2、該地點(diǎn)到圖中其它各地點(diǎn)的最短路徑，并且給出求得的最短路徑的長度及途徑的地點(diǎn)。除了完成最短路徑的求解外，還能對該圖進(jìn)行修改，如頂點(diǎn)以及邊的增刪、邊上權(quán)值的修改等。校園最短路徑問題中的數(shù)據(jù)元素有：a) 頂點(diǎn)數(shù)b) 邊數(shù)c) 邊的長度2、功能需求 要求完成以下功能：a) 輸出頂點(diǎn)信息：將校園內(nèi)各位置輸出。b) 輸出邊的信息：將校園內(nèi)每兩個位置（若兩個位置之間有直接路徑）的距離輸出。c) 修改：修改兩個位置（若兩個位置之間有直接路徑）的距離，并重新輸出每兩個位置（若兩個位置之間有直接路徑）的距離。d) 求最短路徑：輸出給定兩點(diǎn)之間的最短路徑的長度及途徑的地點(diǎn)或輸出任意一點(diǎn)與其它各點(diǎn)的最短路徑。e) 刪

3、除：刪除任意一條邊。f) 插入：插入任意一條邊。3、實(shí)現(xiàn)要點(diǎn) a) 對圖的創(chuàng)建采用鄰接矩陣的存儲結(jié)構(gòu)，而且對圖的操作設(shè)計(jì)成了模板類。為了便于處理，對于圖中的每一個頂點(diǎn)和每一條邊都設(shè)置了初值。 b) 為了便于訪問，用戶可以先輸出所有的地點(diǎn)和距離。 c) 用戶可以隨意修改兩點(diǎn)之間好的距離。 d) 用戶可以增加及刪除邊。 e) 當(dāng)用戶操作錯誤時，系統(tǒng)會出現(xiàn)出錯提示。五、概要設(shè)計(jì):1. 抽象數(shù)據(jù)類型圖的定義如下：ADT Graph數(shù)據(jù)對象V：V是具有相同特性數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R：R=VRVR=（v，w）| v , wV, (v , w)表示v和w之間存在路徑基本操作P：CreatGr

4、aph(&G, V, VR)初始條件： V是圖的頂點(diǎn)集，VR是圖中邊的集合。操作結(jié)果： 按定義(V, VR) 構(gòu)造圖G。DestroyGraph(&G)初始條件： 圖G已存在。操作結(jié)果： 銷毀圖。LocateVex(G, u) 初始條件： 圖G存在，u和G中頂點(diǎn)具有相同特征。操作結(jié)果： 若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中“位置” ；否則返回其它信息。GetVex(G, v) 初始條件： 圖G存在，v是G中某個頂點(diǎn)。操作結(jié)果： 返回v的信息。InsertVex(&G, v) 初始條件： 圖G存在，v和G中頂點(diǎn)具有相同特征。操作結(jié)果： 在圖G中增添新頂點(diǎn)v。DeleteV

5、ex(&G, v)初始條件： 圖G存在，v和G中頂點(diǎn)具有相同特征。操作結(jié)果： 刪除G中頂點(diǎn)v及其相關(guān)的邊。InsertArc(&G, v, w) 初始條件： 圖G存在，v和w是G中兩個頂點(diǎn)。操作結(jié)果： 在G中增添弧<v,w>，若G是無向的，則還增添對稱弧<w,v>。DeleteArc(&G, v, w)初始條件： 圖G存在，v和w是G中兩個頂點(diǎn)。操作結(jié)果： 在G中刪除弧<v,w>，若G是無向的，則還刪除對稱弧<w,v>。 ADT Graph2. 主程序void main() 初始化； while(“命令”!=“退出”) S

6、witch語句 接受命令（輸入選擇項(xiàng)序號）； 處理命令； 3. 本程序運(yùn)用函數(shù)的調(diào)用，只有兩個模塊，它們的調(diào)用關(guān)系為：主程序模塊帶權(quán)無向圖模塊六、詳細(xì)設(shè)計(jì)（詳細(xì)見下面的源代碼）typedef struct /圖中頂點(diǎn)表示點(diǎn)，存放點(diǎn)名稱void Menu() /輸出菜單void PutOutVex(MGraph *G) /輸出每個頂點(diǎn)的信息void PutOutArc(MGraph *G) /輸出每條邊的信息void Dijkstra(MGraph * G) /迪杰斯特拉算法求最短路徑void DeleteVex(MGraph *G) /刪除某個頂點(diǎn)void DeleteArc(MGraph *

7、G) /刪除某條邊void InsertArc(MGraph *G) /插入某條邊void main() /主函數(shù)七、源程序代碼#include <stdio.h> #include <iostream.h>#include<stdlib.h> #include<conio.h> #include <malloc.h> #include<string.h> #define MAX 10000 #define MAXLEN 8 #define ADJTYPE int typedef struct /圖中頂點(diǎn)表示點(diǎn)，存放點(diǎn)名稱

8、 char name30; int num; VEXTYPE; typedef struct VEXTYPE vexsMAXLEN; /頂點(diǎn)的信息 ADJTYPE arcsMAXLENMAXLEN; /鄰接矩陣 int vexnum,arcnum ; /頂點(diǎn)數(shù)和邊數(shù) MGraph;MGraph b; MGraph InitGraph() /*建立無向網(wǎng)的鄰接矩陣結(jié)構(gòu)*/ int i, j; MGraph G; G.vexnum =8; /存放頂點(diǎn)數(shù)G.arcnum =13; /存放邊點(diǎn)數(shù) for(i=0;i<G.vexnum;i+) G.vexsi.num=i; strcpy(G.vex

9、,"第四教學(xué)樓"); strcpy(G.,"第三教學(xué)樓"); strcpy(G.,"圖書館"); strcpy(G.,"食堂"); strcpy(G.,"第一教學(xué)樓"); strcpy(G.,"第二教學(xué)樓"); strcpy(G.,"綜合實(shí)驗(yàn)樓"); strcpy(G.,"校醫(yī)院");

10、 for(i=0;i<G.vexnum;i+) for(j=0;j<G.vexnum;j+) G.arcsij=MAX;G.arcs01=130;G.arcs02=80; G.arcs03=260; G.arcs13=75; G.arcs24=50; G.arcs34=120; G.arcs15=265; G.arcs35=85; G.arcs36=400; G.arcs46=350; G.arcs56=120; G.arcs47=200; G.arcs67=150; for(i=0;i<G.vexnum;i+) for(j=0;j<G.vexnum;j+) G.arc

11、sji=G.arcsij;return G;void Menu() /輸出菜單 cout<<"需要輸出頂點(diǎn)的信息請按0n" cout<<"需要邊的信息輸出請按1n" cout<<"需要修改請按2n" cout<<"需要求出最短路徑請按3n" cout<<"需要刪除某個頂點(diǎn)請按4n" cout<<"需要刪除某條邊請按5n" cout<<"需要插入某條邊請按6n" cout&l

12、t;<"需要退出請按7n" void PutOutVex(MGraph *G) /輸出每個頂點(diǎn)的信息int v; for(v=0;v<G->vexnum;v+) cout<<G->vexsv.num<<G-><<endl; void PutOutArc(MGraph *G) /輸出每條邊的信息for(int i=0;i<G->vexnum;i+) for(int j=0;j<G->vexnum;j+) if(G->arcsij<MAX) cout<

13、<"從" <<G-><<"到"<<G-><<G->arcsij<<endl; void Change(MGraph *G) /修改 int v0,v1,length; cout<<"changen" cin>>v0; cin>>v1; cout<<"length:" cin>>length; G->arcsv0v1=G->

14、arcsv1v0=length;void Dijkstra(MGraph * G) /迪杰斯特拉算法求最短路徑 int v,w,i,min,t=0,x,v0,v1; int final20, D20, p2020; cout<<"請輸入源頂點(diǎn):n" cin>>v0; if(v0<0|v0>G->vexnum) cout<<"此點(diǎn)編號不存在!請重新輸入頂點(diǎn)編號:" cin>>v0; cout<<"請輸入結(jié)束頂點(diǎn):n" cin>>v1; if(v1&

15、lt;0|v1>G->vexnum) cout<<"此點(diǎn)編號不存在!請重新輸入頂點(diǎn)編號:" cin>>v1; for(v=0;v<G->vexnum;v+) / 初始化final20,p2020,finalv=1即已經(jīng)求得v0到v的最短路徑， /pvw=1則是w從v0到v當(dāng)前求得最短路徑上的頂點(diǎn)，Dv帶權(quán)長度 finalv=0; Dv=G->arcsv0v; for(w=0;w<G->vexnum;w+) pvw=0; if(Dv<MAX) pvv0=1;pvv=1; Dv0=0;finalv0=1;

16、for(i=1;i<G->vexnum;i+) min=MAX; for(w=0;w<G->vexnum;w+) if(!finalw) if(Dw<min)v=w;min=Dw; finalv=1; for(w=0;w<G->vexnum;w+) if(!finalw&&(min+G->arcsvw<Dw) Dw=min+G->arcsvw; for(x=0;x<G->vexnum;x+) pwx=pvx; pww=1; cout<<"從"<<G->vex

17、<<"到"<<G-><<"的最短路徑長度為："<<Dv1<<endl; cout<<"路徑為：" for(int j=0;j<G->vexnum;j+) if(pv1j=1) cout<<G-><<endl; void DeleteVex(MGraph *G) /刪除某個頂點(diǎn)int row,col;int v0;cout<<"請輸入要刪除

18、的頂點(diǎn)"cin>>v0;for(int i=v0;i<G->vexnum;i+)G->vexsi=G->vexsi+1;G->vexnum-;for(row=0;row<G->vexnum;row+)for(col=v0;col<G->vexnum;col+)G->arcsrowcol=G->arcsrowcol+1;for(col=0;col<G->vexnum;col+)for(row=v0;row<G->vexnum;row+)G->arcscolrow=G->ar

19、cscolrow+1;void DeleteArc(MGraph *G) /刪除某條邊 int v0,v1; cout<<"請輸入兩頂點(diǎn):n" cin>>v0>>v1; G->arcsv0v1=MAX; G->arcsv1v0=MAX;void InsertArc(MGraph *G) /插入某條邊 int v0,v1,l=0; cout<<"請輸入兩頂點(diǎn):n" cin>>v0>>v1; cout<<"請輸入路徑長度:n" cin>&

20、gt;l; G->arcsv0v1=l; G->arcsv1v0=l;void main() /主函數(shù) int a; b=InitGraph(); Menu(); cin>>a; while(a!=7) switch(a) case 0:PutOutVex(&b);Menu();break; case 1:PutOutArc(&b);Menu();break; case 2:Change(&b);Menu();break; case 3:Dijkstra(&b);Menu();break; case 4:DeleteVex(&b);Menu();break; case 5:DeleteArc(&b);Menu();break; case 6:InsertArc(&b);Menu();break; case 7:exit(1);break; default:break; cin>>a; 八、調(diào)試分析 1) 本程序在求最短路徑的問題上采用迪杰斯特拉算法解決，雖然該算法與弗洛伊德算法相比時間復(fù)雜度低，但每求一條最短路徑都必須重新搜索一遍，在頻繁查詢時會導(dǎo)致