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

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

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

3、度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)刪除：刪除任意一條邊。f)插入：插入任意一條邊。3、實(shí)現(xiàn)要點(diǎn)、實(shí)現(xiàn)要點(diǎn)

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

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

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