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

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

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

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

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

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

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

7、刪除某條邊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 /圖中頂點表示點，存放點名稱 cha

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

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

10、(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.arcsji=

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

12、t;"需要退出請按7n" void PutOutVex(MGraph *G) /輸出每個頂點的信息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->arcs

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

15、|v1>G->vexnum) cout<<"此點編號不存在!請重新輸入頂點編號:" cin>>v1; for(v=0;v<G->vexnum;v+) / 初始化final20,p2020,finalv=1即已經(jīng)求得v0到v的最短路徑， /pvw=1則是w從v0到v當前求得最短路徑上的頂點，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; for(

16、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->vexsv0.

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

18、quot;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->arcsco

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

20、; 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) 本程序在求最短路徑的問題上采用迪杰斯特拉算法解決，雖然該算法與弗洛伊德算法相比時間復雜度低，但每求一條最短路徑都必須重新搜索一遍，在頻繁查詢