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

1、一、課程設(shè)計(jì)題目： 校園最短路徑問題二、課程設(shè)計(jì)目的：1. 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；2. 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能；3. 提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(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ì)報(bào)告書，內(nèi)容不少于10頁（代碼不算）。四、需求分析 ：1、問題描述圖的最短路徑問題是指從指定的某一點(diǎn)v開始，求得從

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

3、除：刪除任意一條邊。f) 插入：插入任意一條邊。3、實(shí)現(xiàn)要點(diǎn) a) 對(duì)圖的創(chuàng)建采用鄰接矩陣的存儲(chǔ)結(jié)構(gòu)，而且對(duì)圖的操作設(shè)計(jì)成了模板類。為了便于處理，對(duì)于圖中的每一個(gè)頂點(diǎn)和每一條邊都設(shè)置了初值。 b) 為了便于訪問，用戶可以先輸出所有的地點(diǎn)和距離。 c) 用戶可以隨意修改兩點(diǎn)之間好的距離。 d) 用戶可以增加及刪除邊。 e) 當(dāng)用戶操作錯(cuò)誤時(shí)，系統(tǒng)會(huì)出現(xiàn)出錯(cuò)提示。五、概要設(shè)計(jì):1. 抽象數(shù)據(jù)類型圖的定義如下：ADT Graph數(shù)據(jù)對(duì)象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中某個(gè)頂點(diǎn)。操作結(jié)果： 返回v的信息。InsertVex(&G, v) 初始條件： 圖G存在，v和G中頂點(diǎn)具有相同特征。操作結(jié)果： 在圖G中增添新頂點(diǎn)v。DeleteVex(&G, v)初始條

5、件： 圖G存在，v和G中頂點(diǎn)具有相同特征。操作結(jié)果： 刪除G中頂點(diǎn)v及其相關(guān)的邊。InsertArc(&G, v, w) 初始條件： 圖G存在，v和w是G中兩個(gè)頂點(diǎn)。操作結(jié)果： 在G中增添弧，若G是無向的，則還增添對(duì)稱弧。DeleteArc(&G, v, w)初始條件： 圖G存在，v和w是G中兩個(gè)頂點(diǎn)。操作結(jié)果： 在G中刪除弧，若G是無向的，則還刪除對(duì)稱弧。 ADT Graph2. 主程序void main() 初始化； while(“命令”!=“退出”) Switch語句 接受命令（輸入選擇項(xiàng)序號(hào)）； 處理命令； 3. 本程序運(yùn)用函數(shù)的調(diào)用，只有兩個(gè)模塊，它們的調(diào)用關(guān)系為：主程序模塊帶權(quán)無向

6、圖模塊六、詳細(xì)設(shè)計(jì)（詳細(xì)見下面的源代碼）typedef struct /圖中頂點(diǎn)表示點(diǎn)，存放點(diǎn)名稱void Menu() /輸出菜單void PutOutVex(MGraph *G) /輸出每個(gè)頂點(diǎn)的信息void PutOutArc(MGraph *G) /輸出每條邊的信息void Dijkstra(MGraph * G) /迪杰斯特拉算法求最短路徑void DeleteVex(MGraph *G) /刪除某個(gè)頂點(diǎn)void DeleteArc(MGraph *G) /刪除某條邊void InsertArc(MGraph *G) /插入某條邊void main() /主函數(shù)七、源程序代碼#inc

7、lude #include #include #include #include #include #define MAX 10000 #define MAXLEN 8 #define ADJTYPE int typedef struct /圖中頂點(diǎn)表示點(diǎn)，存放點(diǎn)名稱 char name30; int num; VEXTYPE; typedef struct VEXTYPE vexsMAXLEN; /頂點(diǎn)的信息 ADJTYPE arcsMAXLENMAXLEN; /鄰接矩陣 int vexnum,arcnum ; /頂點(diǎn)數(shù)和邊數(shù) MGraph;MGraph b; MGraph InitGrap

8、h() /*建立無向網(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;iG.vexnum;i+) G.vexsi.num=i; strcpy(G.,第四教學(xué)樓); strcpy(G.,第三教學(xué)樓); strcpy(G.,圖書館); strcpy(G.,食堂); strcpy(G.,第一教學(xué)樓); strcpy(G.,第二教學(xué)樓); strcpy(G.

9、,綜合實(shí)驗(yàn)樓); strcpy(G.,校醫(yī)院); for(i=0;iG.vexnum;i+) for(j=0;jG.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;iG.vexnum;i+) for(j=0;j

10、G.vexnum;j+) G.arcsji=G.arcsij;return G;void Menu() /輸出菜單 cout需要輸出頂點(diǎn)的信息請(qǐng)按0n; cout需要邊的信息輸出請(qǐng)按1n; cout需要修改請(qǐng)按2n; cout需要求出最短路徑請(qǐng)按3n; cout需要?jiǎng)h除某個(gè)頂點(diǎn)請(qǐng)按4n; cout需要?jiǎng)h除某條邊請(qǐng)按5n; cout需要插入某條邊請(qǐng)按6n; cout需要退出請(qǐng)按7n; void PutOutVex(MGraph *G) /輸出每個(gè)頂點(diǎn)的信息int v; for(v=0;vvexnum;v+) endl; void PutOutArc(

11、MGraph *G) /輸出每條邊的信息for(int i=0;ivexnum;i+) for(int j=0;jvexnum;j+) if(G-arcsijMAX) cout從 到arcsijendl; void Change(MGraph *G) /修改 int v0,v1,length; coutv0; cinv1; coutlength; G-arcsv0v1=G-arcsv1v0=length;void Dijkstra(MGraph * G) /迪杰斯特拉算法求最短路徑 int v,w,i,min,t=0,x,v0,v1; int final

12、20, D20, p2020; coutv0; if(v0G-vexnum) coutv0; coutv1; if(v1G-vexnum) coutv1; for(v=0;vvexnum;v+) / 初始化final20,p2020,finalv=1即已經(jīng)求得v0到v的最短路徑， /pvw=1則是w從v0到v當(dāng)前求得最短路徑上的頂點(diǎn)，Dv帶權(quán)長(zhǎng)度 finalv=0; Dv=G-arcsv0v; for(w=0;wvexnum;w+) pvw=0; if(DvMAX) pvv0=1;pvv=1; Dv0=0;finalv0=1; for(i=1;ivexnum;i+) min=MAX; for(

13、w=0;wvexnum;w+) if(!finalw) if(Dwmin)v=w;min=Dw; finalv=1; for(w=0;wvexnum;w+) if(!finalw&(min+G-arcsvwarcsvw; for(x=0;xvexnum;x+) pwx=pvx; pww=1; cout從到的最短路徑長(zhǎng)度為：Dv1endl; cout路徑為：; for(int j=0;jvexnum;j+) if(pv1j=1) endl; void DeleteVex(MGraph *G) /刪除某個(gè)頂點(diǎn)int row,c

14、ol;int v0;coutv0;for(int i=v0;ivexnum;i+)G-vexsi=G-vexsi+1;G-vexnum-;for(row=0;rowvexnum;row+)for(col=v0;colvexnum;col+)G-arcsrowcol=G-arcsrowcol+1;for(col=0;colvexnum;col+)for(row=v0;rowvexnum;row+)G-arcscolrow=G-arcscolrow+1;void DeleteArc(MGraph *G) /刪除某條邊 int v0,v1; coutv0v1; G-arcsv0v1=MAX; G-a

15、rcsv1v0=MAX;void InsertArc(MGraph *G) /插入某條邊 int v0,v1,l=0; coutv0v1; coutl; G-arcsv0v1=l; G-arcsv1v0=l;void main() /主函數(shù) int a; b=InitGraph(); Menu(); cina; 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)

16、;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; cina; 八、調(diào)試分析 1) 本程序在求最短路徑的問題上采用迪杰斯特拉算法解決，雖然該算法與弗洛伊德算法相比時(shí)間復(fù)雜度低，但每求一條最短路徑都必須重新搜索一遍，在頻繁查詢時(shí)會(huì)導(dǎo)致查詢效率低，而弗洛伊德算法只要計(jì)算一次，即可求得每一對(duì)頂點(diǎn)之間的最短路徑，雖然時(shí)間復(fù)雜度為高，但以后每次查

17、詢只要查表即可，會(huì)極大地提高查詢的效率，而且，弗洛伊德算法還支持帶負(fù)權(quán)的圖的最短路徑的計(jì)算。由此可見，選用算法時(shí)必須綜合各方面因素考慮。2) 由于功能函數(shù)較多，在編寫程序時(shí)將函數(shù)逐個(gè)添加完成的，就是說，每增加一個(gè)函數(shù)，進(jìn)行一次編譯運(yùn)行，此函數(shù)通過了再寫下一個(gè)函數(shù)?；蛟S這種方法比較麻煩，但當(dāng)有錯(cuò)誤時(shí)只要針對(duì)新加函數(shù)進(jìn)行修改即可。同時(shí)，要充分利用軟件所提供的調(diào)試功能，這也會(huì)大大減少編程人員的負(fù)擔(dān)。九、調(diào)試結(jié)果a) 開始界面b) 輸出頂點(diǎn)信息c) 輸出邊的信息d) 修改e) 求最短路徑f) 刪除某一頂點(diǎn)g) 刪除某條邊 h) 插入某條邊i) 退出十、總結(jié)及體會(huì) 課程設(shè)計(jì)是培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識(shí),發(fā)現(xiàn),提出,分析和解決實(shí)際問題,鍛煉實(shí)踐能力的重要環(huán)節(jié),是對(duì)學(xué)生實(shí)際工作能力的具體訓(xùn)練和考察過程。通過這次課程設(shè)計(jì)使我懂得了理論與實(shí)際相