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

1、一、課程設(shè)計題目：一、課程設(shè)計題目：校園最短路徑問題二、課程設(shè)計目的：二、課程設(shè)計目的：1.了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨(dú)立分析和設(shè)計能力；2.初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；3.提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能力；4.訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所具備的科學(xué)工作方法和作風(fēng)。三、課程設(shè)計要求：三、課程設(shè)計要求：1.設(shè)計的題

2、目要求達(dá)到一定的工作量（300行以上代碼），并具有一定的深度和難度。2.編寫出課程設(shè)計報告書，內(nèi)容不少于10頁（代碼不算）。四、需求分析四、需求分析：1、問題描述、問題描述圖的最短路徑問題是指從指定的某一點v開始，求得從該地點到圖中其它各地點的最短路徑，并且給出求得的最短路徑的長度及途徑的地點。除了完成最短路徑的求解外，還能對該圖進(jìn)行修改，如頂點以及邊的增刪、邊上權(quán)值的修改等。校園最短路徑問題中的數(shù)據(jù)元素有：a)頂點數(shù)b)邊數(shù)c)邊的長

3、度2、功能需求、功能需求要求完成以下功能：a)輸出頂點信息：將校園內(nèi)各位置輸出。b)輸出邊的信息：將校園內(nèi)每兩個位置（若兩個位置之間有直接路徑）的距離輸出。c)修改：修改兩個位置（若兩個位置之間有直接路徑）的距離，并重新輸出每兩個位置（若兩個位置之間有直接路徑）的距離。d)求最短路徑：輸出給定兩點之間的最短路徑的長度及途徑的地點或輸出任意一點與其它各點的最短路徑。e)刪除：刪除任意一條邊。f)插入：插入任意一條邊。3、實現(xiàn)要點、實現(xiàn)要點

4、a)對圖的創(chuàng)建采用鄰接矩陣的存儲結(jié)構(gòu)，而且對圖的操作設(shè)計成了模板類。為了便于處理，對于圖中的每一個頂點和每一條邊都設(shè)置了初值。b)為了便于訪問，用戶可以先輸出所有的地點和距離。c)用戶可以隨意修改兩點之間好的距離。d)用戶可以增加及刪除邊。Switch語句接受命令（輸入選擇項序號）；處理命令；3.本程序運(yùn)用函數(shù)的調(diào)用，只有兩個模塊，它們的調(diào)用關(guān)系為：主程序模塊帶權(quán)無向圖模塊六、詳細(xì)設(shè)計六、詳細(xì)設(shè)計（詳細(xì)見下面的源代碼）typedefst

5、ruct圖中頂點表示點，存放點名稱voidMenu()輸出菜單voidPutOutVex(MGraphG)輸出每個頂點的信息voidPutOutArc(MGraphG)輸出每條邊的信息voidDijkstra(MGraphG)迪杰斯特拉算法求最短路徑voidVex(MGraphG)刪除某個頂點voidArc(MGraphG)刪除某條邊voidArc(MGraphG)插入某條邊voidmain()主函數(shù)七、源程序代碼七、源程序代碼#inc

6、lude#include#include#include#include#include#defineMAX10000#defineMAXLEN8#defineADJTYPEinttypedefstruct圖中頂點表示點，存放點名稱name[30]intnumVEXTYPEtypedefstructVEXTYPEvexs[MAXLEN]頂點的信息ADJTYPEarcs[MAXLEN][MAXLEN]鄰接矩陣intvexnumarcnum