數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告-校園導(dǎo)游圖

1、淮 海 工 學(xué) 院 計(jì)算機(jī)工程學(xué)院課程設(shè)計(jì)報(bào)告設(shè)計(jì)名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 選題名稱： 校園導(dǎo)游圖 姓 名： 聶睿 學(xué)號： 2012122631 專業(yè)班級： 系 （院）： 計(jì)算機(jī)工程學(xué)院 設(shè)計(jì)時(shí)間： 2011.12.192011.12.30 設(shè)計(jì)地點(diǎn)： 軟件工程實(shí)驗(yàn)室、教室 成績：指導(dǎo)教師評語： 簽名： 年 月 日數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 第 40 頁，共 頁1課程設(shè)計(jì)目的1、訓(xùn)練學(xué)生靈活應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識，獨(dú)立完成問題分析，結(jié)合數(shù)據(jù)結(jié)構(gòu)理論知識，編寫程序求解指定問題。 2.初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能；3.提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解

2、決問題的能力；4.訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，鞏固、深化學(xué)生的理論知識，提高編程水平，并在此過程中培養(yǎng)他們嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度和良好的工作作風(fēng)。2課程設(shè)計(jì)任務(wù)與要求：任務(wù)根據(jù)教材數(shù)據(jù)結(jié)構(gòu)-C語言描述（耿國華主編）和參考書數(shù)據(jù)結(jié)構(gòu)題集（C語言版）（嚴(yán)蔚敏、吳偉民主編）選擇課程設(shè)計(jì)題目，要求通過設(shè)計(jì)，在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面加深對課程基本內(nèi)容的理解和綜合運(yùn)用。設(shè)計(jì)題目從任務(wù)書所列選題表中選取，每班每題不得超過2人。學(xué)生自選課題學(xué)生原則上可以結(jié)合個(gè)人愛好自選課題，要求課題有一定的深度與難度，有一定的算法復(fù)雜性，能夠鞏固數(shù)據(jù)結(jié)構(gòu)課程所學(xué)

3、的知識。學(xué)生自選課題需在18周前報(bào)課程設(shè)計(jì)指導(dǎo)教師批準(zhǔn)方可生效。要求：1、在處理每個(gè)題目時(shí)，要求從分析題目的需求入手，按設(shè)計(jì)抽象數(shù)據(jù)類型、構(gòu)思算法、通過設(shè)計(jì)實(shí)現(xiàn)抽象數(shù)據(jù)類型、編制上機(jī)程序和上機(jī)調(diào)試等若干步驟完成題目，最終寫出完整的分析報(bào)告。前期準(zhǔn)備工作完備與否直接影響到后序上機(jī)調(diào)試工作的效率。在程序設(shè)計(jì)階段應(yīng)盡量利用已有的標(biāo)準(zhǔn)函數(shù)，加大代碼的重用率。 2、.設(shè)計(jì)的題目要求達(dá)到一定工作量（300行以上代碼），并具有一定的深度和難度。3、程序設(shè)計(jì)語言推薦使用C/C+，程序書寫規(guī)范，源程序需加必要的注釋;4、每位同學(xué)需提交可獨(dú)立運(yùn)行的程序；5 、每位同學(xué)需獨(dú)立提交設(shè)計(jì)報(bào)告書（每人一份），要求編排格式

4、統(tǒng)一、規(guī)范、內(nèi)容充實(shí)，不少于10頁（代碼不算）；6、課程設(shè)計(jì)實(shí)踐作為培養(yǎng)學(xué)生動手能力的一種手段，單獨(dú)考核。 3課程設(shè)計(jì)說明書一 需求分析1功能需求：用無向網(wǎng)表示淮海工學(xué)院的校園景點(diǎn)平面圖，選取若干個(gè)淮海工學(xué)院有代表性的景點(diǎn)抽象成無向帶權(quán)圖，圖中頂點(diǎn)表示校內(nèi)各頂點(diǎn)，邊上權(quán)值表示路徑長度。2性能需求：（1）為來訪客人查詢各景點(diǎn)的相關(guān)信息；（2）為來訪客人查詢圖中任意兩個(gè)景點(diǎn)間的最短路徑（3）為來訪客人查詢圖中任意兩個(gè)景點(diǎn)間的所有路徑（7）為來訪客人輸出對應(yīng)編號景點(diǎn)的信息 3數(shù)據(jù)需求：建立無向圖G，圖中頂點(diǎn)ver表示主要景點(diǎn)，存放景點(diǎn)編號position、名稱name、簡介introduction等

5、信息，圖中邊arc表示景點(diǎn)間的道路，存放路徑長度信息distance。 二 概要設(shè)計(jì)1ADT Graph數(shù)據(jù)對象V：V具有相同特性的數(shù)組元素的集合，稱為頂點(diǎn)集數(shù)據(jù)關(guān)系R：R=VR VR=<x,y>|P(x,y)(x,y屬于V)ADT Graph 數(shù)據(jù)對象V：一個(gè)集合，該集合中的所有元素具有相同的特性 數(shù)據(jù)關(guān)系R：R=VR VR=<x,y>|P(x,y)(x,y屬于V) 基本操作：（1）    initgraph(&G)；（2）   creatgraph(mgraph &G)  

6、;；（3）   DeleteplanArc(mgraph &G) ；  （4）   DeleteVertex(mgraph &G)；（5）  enarc(mgraph &G)；  （6）  enverx(mgraph &G) ；ADT Graph基本操作：1、void displaycampus(mgraph g)輸出所有頂點(diǎn)信息（即將展示校園全景圖）2、void seaabout(mgraph G)根據(jù)輸入編號用來查詢各個(gè)景點(diǎn)信息3、void

7、 shortestpath_Floyd(mgragh *g)用弗洛伊德阿算法求兩個(gè)景點(diǎn)間最短路徑4、void Allpaths(mgragh *g)顯示輸入兩個(gè)頂點(diǎn)間的所有路徑14、int initgraph(mgraph& G) 校園導(dǎo)游圖的初始化15、void main( )主函數(shù)，可以調(diào)用子函數(shù)16、exit(0) 退出程序三 詳細(xì)設(shè)計(jì)總體流程圖：1、創(chuàng)建無向網(wǎng)圖算法的偽代碼描述如下：int creatgraph(mgraph &G)/構(gòu)造圖的鄰接矩陣輸入矩陣對應(yīng)的頂點(diǎn)數(shù)G.vernum和邊數(shù)G.arcnum;for(i=0;i<G.vernum;i+)輸入對應(yīng)的景

8、點(diǎn)編號、景點(diǎn)名稱、景點(diǎn)簡介：初始化任意景點(diǎn)的路徑修改兩頂點(diǎn)間的路徑2、輸出學(xué)校平面圖的算法的偽代碼描述如下:void displaycampus(mgraph G)/顯示景點(diǎn)信息；對應(yīng)輸出景點(diǎn)編號，景點(diǎn)名稱，景點(diǎn)簡介3、按編號查詢景點(diǎn)的相關(guān)信息的算法的偽代碼描述如下:void seaabout(mgraph G)/景點(diǎn)信息查詢；請輸入要查詢的景點(diǎn)編號n;if(n<0|n>11)該景點(diǎn)不存在，請重新輸入：else 根據(jù)編號輸出對應(yīng)的景點(diǎn)信息；4、更改圖的信息的算法的偽代碼描述如下 ：int changegraph(mgraph G)重新建圖輸入1 刪除結(jié)點(diǎn)輸入2 刪除邊輸入3 增加結(jié)

9、點(diǎn)輸入4 增加邊輸入5 更新圖信息輸入6 打印鄰接矩陣輸入7 返回程序 輸入8 5、求無向圖的最短路徑的算法的偽代碼描述如下:void shortestpath_Floyd(mgraph *G) 定義數(shù)組三維p101010,用于尋找任意兩景點(diǎn)間最短路徑中的景點(diǎn)，定義二維數(shù)組D1010 用于存放兩頂點(diǎn)間的最短路徑; 初始化任意兩景點(diǎn)間的最短路徑和最短路徑上的景點(diǎn) Dvw=G->arcsvw.adj;/把v,w路徑的值放到Dvw中 v,w是，v,w路徑上的景點(diǎn)，所以pvwv=1;pvww=1; 如果u到v,w之間的兩條路徑之和小于v,w之間的路徑，則使Dvw=Dvu+Duw 若i是v,u上的

10、最短路徑的景點(diǎn)，或是u，w之間最短路徑的景點(diǎn)，則i是v,w之間最短路徑上的景點(diǎn)int flag=1；while(flag) 輸入出發(fā)點(diǎn)和目的地的編號:k, jif(k<0|k>G->vernum|j<0|j>G->vernum)景點(diǎn)編號不存在!請重新輸入出發(fā)點(diǎn)和目的地的編號:k, j if(k>=0&&k<頂點(diǎn)數(shù)目 &&j>=0&&j<頂點(diǎn)數(shù)目) flag=0; 逐個(gè)輸出最短路徑上的景點(diǎn)名字以及總路線長6、求無向圖的所有路徑的算法的偽代碼描述如下:void Allpath(mgraph

11、*G)int v,w,k,j,flag=1,定義數(shù)組三維p101010,用于尋找任意兩景點(diǎn)間路徑中的景點(diǎn)，定義二維數(shù)組D1010 用于存放兩頂點(diǎn)間的路徑長度; while(flag) 輸入出發(fā)點(diǎn)和目的地的編號k,j; if(k<0|k>頂點(diǎn)數(shù)目|j<0|j頂點(diǎn)數(shù)目) 重新輸入出發(fā)點(diǎn)和目的地的編號: k,j; Dvw=G->arcsvw.adj;/初始化數(shù)組Dvwif(Dvw!=A)如果這兩個(gè)頂點(diǎn)間存在路徑，則使pvw為1，否則為0； pvw=1;pwv=1; if(pkj=1)如果這兩個(gè)景點(diǎn)間有路徑，則輸出路徑中的所有景點(diǎn)和長度 7、增添路徑的信息的算法的偽代碼描述如下

12、：int enarc(mgraph &G)/增加路徑輸入增加邊的起始點(diǎn)v0，終點(diǎn)v1，及邊的長度distance G.arcsv0v1.adj=G.arcsv0v1.adj=distance;設(shè)置增加的路徑長度；8、增添景點(diǎn)的信息的算法的偽代碼描述如下：int enverx(mgraph &G)/增加結(jié)點(diǎn)輸入要添加的景點(diǎn)的信息：包括編號，名稱，簡介G.vernum+;增加一條邊G.arcsiG.vernum-1.adj=G.arcsiG.vernum-1.adj=A;/修改矩陣信息return 1;9、刪除路徑的信息的算法的偽代碼描述如下：int DeleteplanArc(m

13、graph &G)/刪除圖一條邊；輸入要刪除的一條邊對應(yīng)的兩個(gè)頂點(diǎn)v0,v1 調(diào)用locatevex函數(shù)找到這兩個(gè)點(diǎn)的位置 更改邊的信息邊數(shù)減少1；10、刪除景點(diǎn)的信息的算法的偽代碼描述如下：int DeleteVertex(mgraph &G)/刪除景點(diǎn)輸入要刪除的景點(diǎn)編號v調(diào)用locatevex函數(shù)找到這個(gè)點(diǎn)的位置if(m<0)重新輸入if(m>0)for(i=m;i<景點(diǎn)數(shù)G.vernum ;i+)更改景點(diǎn)的名稱strcpy(G.,G.vexs i+1.name);更改頂點(diǎn)的簡介strcpy(G.roduction,

14、G.vexsi+1.introduction);刪除該景點(diǎn)所在矩陣的行 刪除該景點(diǎn)所在矩陣的 G.vernum-;邊數(shù)減少111、初始化導(dǎo)游圖算法偽代碼描述如下：int initgraph(mgraph& G)/校園導(dǎo)游圖的初始化設(shè)置景點(diǎn)數(shù)G.vernum=10;設(shè)置路徑數(shù)G.arcnum=15;/初始化景點(diǎn)平面圖設(shè)置景點(diǎn)編號值，名稱，簡介初始化邊矩陣12、打印無向圖鄰接矩陣算法的偽代碼描述如下：void printmatrix(mgraph G)/打印圖的鄰接矩陣；根據(jù)路徑的初始化信息輸出一個(gè)n行n列的矩陣（n是景點(diǎn)的個(gè)數(shù)），矩陣中的元素是路徑的長度，如果兩景點(diǎn)間無長度，則輸出0；1

15、3、景點(diǎn)定位的算法的偽代碼描述如下：int locatevex(mgraph c,int v)/景點(diǎn)的定位傳入要查找的頂點(diǎn)位置v如果找到改點(diǎn)，返回改點(diǎn)14、更新校園導(dǎo)游圖景點(diǎn)信息算法的偽代碼描述如下：int newgraph(mgraph &G)/更新景點(diǎn)的信息輸入更改的景點(diǎn)數(shù)n;for(int i=0;i<n;i+)/修改景點(diǎn)信息逐個(gè)輸入景點(diǎn)的編號、景點(diǎn)的名稱：、景點(diǎn)的簡介輸入更改的路徑數(shù)n;int distance,v0,v1;輸入更新的路徑的信息for(i=0;i<n;i+)/修改路徑信息逐條輸入起始景點(diǎn)編號v0、終點(diǎn)景點(diǎn)編號v1、路勁長度distance 四 設(shè)計(jì)與

16、調(diào)試分析1.校園導(dǎo)游圖景點(diǎn)介紹（輸出各景點(diǎn)信息）：應(yīng)輸出所有景點(diǎn)的信息，如下：景點(diǎn)編號（position）景點(diǎn)名稱(name)景點(diǎn)介紹(intoduction)0淮工主樓淮海工學(xué)院標(biāo)志建筑，樓高10層1計(jì)算機(jī)樓計(jì)算機(jī)學(xué)院學(xué)生學(xué)習(xí)基地,樓高6層2行政樓校領(lǐng)導(dǎo)日常工作之處，樓高5層"3圖書館樓高5層，藏書逾十萬4文通樓文通樓，樓高6層，學(xué)生學(xué)習(xí)自習(xí)地點(diǎn)5文淵樓文淵樓，樓高5層，教師辦公室6大活中心內(nèi)設(shè)大量娛樂設(shè)施，學(xué)生周末娛樂場所7淮工西門淮工西門是車站，學(xué)生在這里坐公交到達(dá)火車的站8實(shí)驗(yàn)樓做實(shí)驗(yàn)的地點(diǎn)，樓高6層，內(nèi)有大量先進(jìn)實(shí)驗(yàn)儀器9體育館學(xué)生體育鍛煉地點(diǎn)實(shí)際輸出的信息為：操作成功，與

17、預(yù)期結(jié)果一致。2.打印校園導(dǎo)游圖的鄰接矩陣：操作成功，與預(yù)期結(jié)果一致。3、查詢景點(diǎn)間最短路徑：比如：2015查詢景點(diǎn)1（計(jì)算機(jī)樓）和3（圖書館）之間的最短路徑，預(yù)期結(jié)果應(yīng)為：計(jì)算機(jī)樓 > 文通樓 > 圖書館，路徑總長度為35操作成功，與預(yù)期結(jié)果一致。4、景點(diǎn)信息查詢：比如：查詢景點(diǎn)為1的景點(diǎn)信息，預(yù)期結(jié)果應(yīng)為：景點(diǎn)序號（position）景點(diǎn)名稱(name)景點(diǎn)介紹(intoduction)1計(jì)算機(jī)樓計(jì)算機(jī)學(xué)院學(xué)生學(xué)習(xí)基地,樓高6層與預(yù)期結(jié)果一致。查詢成功。5、更改圖的信息：更改圖信息主頁面：5.1重新建圖 比如重新建一個(gè)有3個(gè)景點(diǎn)和3條路徑的無向圖：景點(diǎn)信息分別為：景點(diǎn)序號（po

18、sition）景點(diǎn)名稱(name)景點(diǎn)介紹(intoduction)0計(jì)算機(jī)樓信息中心1第一食堂飲食中心2B#宿舍男生宿舍矩陣關(guān)系為：015251505025500 與預(yù)期結(jié)果一致，重新建圖成功。5.2刪除景點(diǎn)：比如刪除景點(diǎn)編號為1的景點(diǎn)：則輸出的矩陣中應(yīng)失去原第一行第一列，并且其信息不再出現(xiàn)在校園導(dǎo)游中：刪除景點(diǎn)前的圖信息：刪除景點(diǎn)前的矩陣：刪除景點(diǎn)后的圖的信息和矩陣：與預(yù)期結(jié)果一致，刪除景點(diǎn)成功。5.3刪除兩景點(diǎn)間的路徑：比如刪除編號為0和2的兩景點(diǎn)間的路徑，則打印出來的矩陣在第0行第2列和第2行第0列的值應(yīng)為0。刪除路徑前的矩陣： 刪除路徑后的矩陣： 與預(yù)期結(jié)果一致，刪除路徑成功。54增

19、加景點(diǎn)信息比如增加一個(gè)景點(diǎn)，其信息為：景點(diǎn)序號（position）景點(diǎn)名稱(name)景點(diǎn)介紹(intoduction)10A#7宿舍樓計(jì)算機(jī)學(xué)院女生宿舍對應(yīng)的矩陣中應(yīng)增加一行一列，第10行和第10列上所有元素都應(yīng)為0，輸出的圖信息中最后應(yīng)增加上述的信息。增加景點(diǎn)前的圖信息：增加景點(diǎn)前的矩陣：增加景點(diǎn)后的圖信息和矩陣：與預(yù)期結(jié)果一致，增加景點(diǎn)成功。5.5增加一條路徑比如在景點(diǎn)0和4之間加一條長度為10的路徑，則在第0行第4列與第4行第0列元素應(yīng)為10。增加路徑前的矩陣： 增加路徑后的矩陣： 與預(yù)期結(jié)果一致，增加路徑成功。5.6更新圖信息比如要更新一個(gè)景點(diǎn)和一條路徑的信息，將景點(diǎn)信息：景點(diǎn)序號（

20、position）景點(diǎn)名稱(name)景點(diǎn)介紹(intoduction)1計(jì)算機(jī)樓計(jì)算機(jī)學(xué)院學(xué)生學(xué)習(xí)基地,樓高6層改為：景點(diǎn)序號（position）景點(diǎn)名稱(name)景點(diǎn)介紹(intoduction)1B#8男生宿舍更改頂點(diǎn)編號為0和3路徑長度，路徑由30改為15。更改后的圖中編號為1的信息應(yīng)變?yōu)椋壕包c(diǎn)序號（position）景點(diǎn)名稱(name)景點(diǎn)介紹(intoduction)1B#8男生宿舍矩陣中第0行第3列和第3行第0列元素應(yīng)由30變?yōu)?5.更改景點(diǎn)前的圖信息：更改路徑前的矩陣： 更新后的圖信息和矩陣：6、查找兩頂點(diǎn)間的所有路徑比如查找1,3兩點(diǎn)間的所有路徑，所有路徑為： 五 用戶手冊

21、1、進(jìn)入本系統(tǒng)后，隨即顯示系統(tǒng)主菜單頁面。用戶可在此菜單下輸入各子菜單對應(yīng)的數(shù)字，并按回車鍵，執(zhí)行相應(yīng)的子菜單命令。2、查詢、修改、增加、刪除景點(diǎn)以及景點(diǎn)間的路徑，都是通過輸入景點(diǎn)的編號來實(shí)現(xiàn)的，進(jìn)入主菜單時(shí)，用戶最好先選擇“1、學(xué)校景點(diǎn)介紹”和“2、打印鄰接矩陣”，方便用戶了解景點(diǎn)信息以及路徑信息。六 測試成果操作主界面查看淮工景點(diǎn)平面圖打印無向圖鄰接矩陣查詢兩頂點(diǎn)間的最短路徑按編號查詢景點(diǎn)信息查詢兩頂點(diǎn)間的所有路徑： 更改圖信息：退出系統(tǒng)七 附錄（源程序清單）#include <iostream>#include<malloc.h>#include<strin

22、g>#include<iomanip>using namespace std;#define max_ver_num 20#define OK 1#define FALSE 0#define Error -1#define A 1000#define TRUE 1typedef struct arcnode/設(shè)置邊的權(quán)值信息 int adj;/路徑權(quán)值arcnode,adjarcsmax_ver_nummax_ver_num;typedef struct verdata/設(shè)置景點(diǎn)信息int position;char name60;char introduction1000;

23、verdata;typedef struct mgraph verdata vexsmax_ver_num; adjarcs arcs; int vernum,arcnum;mgraph;/全局變量int visited20;int d35;mgraph g;int initgraph(mgraph& G)/校園導(dǎo)游圖的初始化int i,j;G.vernum=10;G.arcnum=20;/初始化景點(diǎn)平面圖for(i=0;i<G.vernum;i+)G.vexsi.position=i;strcpy(G.,"淮工主樓"); strcpy(G

24、.,"計(jì)算機(jī)樓");strcpy(G.,"行政樓"); strcpy(G.,"圖書館"); strcpy(G.,"文通樓"); strcpy(G.,"文淵樓");strcpy(G.,"大活中心"); strcpy(G.,"淮工西門"); strcpy(G.,"實(shí)驗(yàn)樓"); str

25、cpy(G.,"體育館");strcpy(G.roduction,"淮海工學(xué)院標(biāo)志建筑，樓高10層"); strcpy(G.roduction,"計(jì)算機(jī)學(xué)院學(xué)生學(xué)習(xí)基地,樓高6層");strcpy(G.roduction,"校領(lǐng)導(dǎo)日常工作之處，樓高5層"); strcpy(G.roduction,"樓高5層，藏書逾十萬"); strcpy(G.roduction,"文通樓，樓高

26、6層，學(xué)生學(xué)習(xí)自習(xí)地點(diǎn)"); strcpy(G.roduction,"文淵樓，樓高5層，教師辦公室");strcpy(G.roduction,"內(nèi)設(shè)大量娛樂設(shè)施，學(xué)生周末娛樂場所"); strcpy(G.roduction,"淮工西門是車站，學(xué)生在這里坐公交到達(dá)火車的站"); strcpy(G.roduction,"做實(shí)驗(yàn)的地點(diǎn)，樓高6層，內(nèi)有大量先進(jìn)實(shí)驗(yàn)儀器"); strcpy(G.roduction,"

27、學(xué)生體育鍛煉地點(diǎn)");/初始化邊矩陣for(i=0;i<G.vernum;i+)for(j=0;j<G.vernum;j+)G.arcsij.adj=A;G.arcs01.adj=15;G.arcs02.adj=25;G.arcs03.adj=30;G.arcs14.adj=15;G.arcs17.adj=20;G.arcs19.adj=40;G.arcs25.adj=10;G.arcs28.adj=15;G.arcs36.adj=30;G.arcs38.adj=20;G.arcs47.adj=10;G.arcs49.adj=60;G.arcs58.adj=25;G.ar

28、cs68.adj=50;G.arcs79.adj=35;G.arcs45.adj=20;G.arcs56.adj=25;G.arcs57.adj=30;G.arcs67.adj=15;G.arcs69.adj=20;G.arcs78.adj=40;G.arcs89.adj=10;G.arcs29.adj=15;G.arcs39.adj=30;G.arcs34.adj=20;G.arcs48.adj=10;G.arcs45.adj=60;G.arcs59.adj=25;G.arcs18.adj=50;G.arcs17.adj=35;for(j=0;j<G.vernum;j+)for(i=0

29、;i<G.vernum;i+)G.arcsij.adj=G.arcsji.adj;return 1;int locatevex(mgraph c,int v)/景點(diǎn)的定位int i;for(i=0;i<c.vernum;i+)if(v=c.vexsi.position) return i;return -1;void printmatrix(mgraph G)/打印圖的鄰接矩陣；int i,j;cout<<"對應(yīng)的矩陣為："<<endl;for(i=0;i<G.vernum;i+)for(j=0;j<G.vernum;j+)i

30、f(G.arcsij.adj<A)cout<<setiosflags(ios:left)<<setw(5)<<G.arcsij.adj;elsecout<<setiosflags(ios:left)<<setw(5)<<0;cout<<endl;/求最短路徑，弗洛伊德算法void shortestpath_Floyd(mgraph *G) int v,u,i,w,k,j,flag=1,p101010,D1010;/D路徑 for(v=0;v<G->vernum;v+)for(w=0;w<

31、G->vernum;w+) Dvw=G->arcsvw.adj; for(u=0;u<G->vernum;u+)pvwu=0; if(Dvw<A) pvwv=1;pvww=1; for(u=0;u<G->vernum;u+) for(v=0;v<G->vernum;v+) for(w=0;w<G->vernum;w+) if(Dvu+Duw<Dvw) Dvw=Dvu+Duw; for(i=0;i<G->vernum;i+) pvwi=pvui|puwi; while(flag) cout<<&quo

32、t;請輸入出發(fā)點(diǎn)編號:" cin>>k; cout<<"請輸入目的地的編號:"<<endl; cin>>j; if(k<0|k>G->vernum|j<0|j>G->vernum) cout<<"景點(diǎn)編號不存在!請重新輸入出發(fā)點(diǎn)和目的地的編號:" cout<<"請輸入出發(fā)點(diǎn)編號:" cin>>k; cout<<"請輸入目的地的編號:"<<endl; cin>

33、>j; if(k>=0&&k<G->vernum&&j>=0&&j<G->vernum) flag=0; printf("%s",G->); for(u=0;u<G->vernum;u+) if(pkju&&k!=u&&j!=u) printf("->%s",G->); printf("->%s",G->); pr

34、intf(" 總路線長%dmn",Dkj);/兩個(gè)景點(diǎn)間的所有路徑void Allpath(mgraph *G)int v,w,k,j,flag=1,p1010,D1010;while(flag) cout<<"請輸入出發(fā)點(diǎn)和目的地的編號:"<<endl; cout<<"請輸入出發(fā)點(diǎn)編號:" cin>>k; cout<<"請輸入目的地的編號:" cin>>j; if(k<0|k>G->vernum|j<0|j>G-

35、>vernum) cout<<"景點(diǎn)編號不存在!請重新輸入出發(fā)點(diǎn)和目的地的編號:"<<endl; cout<<"請輸入出發(fā)點(diǎn)編號:" cin>>k; cout<<"請輸入目的地的編號:"<<endl; cin>>j; if(k>=0&&k<G->vernum&&j>=0&&j<G->vernum) flag=0; for(v=0;v<G->vernum

36、;v+)for(w=0;w<G->vernum;w+)Dvw=G->arcsvw.adj;if(Dvw!=A) pvw=1; pwv=1;if(pkj=1)cout<<G->;cout<<"->"<<G->; cout<<"總路線長"<<Dkw+Dwj<<endl; for(w=0;w<G->vernum;w+) if(pkw=1&&pwj=1) cout<<G->

37、;;cout<<"->"<<G->;cout<<"->"<<G->;cout<<" 總路線長"<<Dkw+Dwj<<endl;for(v=0;v<G->vernum;v+)for(w=0;w<G->vernum;w+)if(pkv=1&&pvw=1&&pwj=1) cout<<G->vexsk.n

38、ame;cout<<"->"<<G->;cout<<"->"<<G->;cout<<"->"<<G->;cout<<" 總路線長"<<Dkv+Dwj+Dvw<<endl; void displaycampus(mgraph G)/顯示景點(diǎn)信息，顯示景點(diǎn)信息平面圖；int i;cout<<"景點(diǎn)

39、編號 "<<"景點(diǎn)名稱 "<<"景點(diǎn)簡介 "<<endl;for(i=0;i<G.vernum;i+)cout<<" "<<G.vexsi.position<<" "cout<<G.<<" "cout<<G.roduction<<" "<<endl;int creatgraph(mgraph

40、&G)/構(gòu)造無向圖的鄰接矩陣int i,n,m,distance,v0,v1;cout<<"請輸入矩陣對應(yīng)的頂點(diǎn)數(shù):" cin>>G.vernum;cout<<"請輸入矩陣對應(yīng)的邊數(shù):"cin>>G.arcnum;for(i=0;i<G.vernum;i+)cout<<"請輸入景點(diǎn)編號：" cin>>G.vexsi.position; cout<<"請輸入景點(diǎn)名稱："cin>>G.; c

41、out<<"請輸入景點(diǎn)簡介：" cin>>G.roduction;for(i=0;i<G.vernum;i+)for(int j=0;j<G.vernum;j+)G.arcsij.adj=0;for(i=0;i<G.arcnum;i+)cout<<"輸入第"<<i<<"條邊的起點(diǎn)編號:" cin>>v0;cout<<"輸入第"<<i<<"條邊的終點(diǎn)編號:"

42、; cin>>v1; cout<<"輸入第"<<i<<"條邊的長度編號:"cin>>distance;m=locatevex(G,v0);n=locatevex(G,v1);if(m>=0&&n>=0)G.arcsmn.adj=G.arcsnm.adj=distance;displaycampus(G); printmatrix(G);return 1;int DeleteVertex(mgraph &G)/刪除景點(diǎn)信息int i,j,v,m;cout<

43、<"請輸入要刪除的景點(diǎn)編號:"cin>>v;m=locatevex(G,v);int flag=1;while(flag)if(m<0)cout<<"無此景點(diǎn)，請重新輸入:" cin>>v;m=locatevex(G,v);if(m>0)for(i=m;i<G.vernum ;i+)strcpy(G.,G.vexs i+1.name);strcpy(G.roduction,G.vexsi+1.introduction);flag=0;for(i=m;i<

44、;G.vernum;i+)/刪除行for(j=0;j<G.vernum;j+)G.arcsij=G.arcsi+1j; for(i=m;i<G.vernum;i+)/刪除列 for(j=0;j<G.vernum;j+) G.arcsji=G.arcsji+1; G.vernum-; displaycampus(G); printmatrix(G); return 1;int DeleteplanArc(mgraph &G)/刪除圖一條邊信息；int i,j,v0,v1;int flag=1;while(flag) cout<<"請輸入要刪除的一條

45、邊對應(yīng)的兩個(gè)頂點(diǎn)編號:"<<endl;cin>>v0>>v1;if(v0<0|v0>G.vernum|v0<0|v1>G.vernum) cout<<"景點(diǎn)編號不存在!請重新輸入要刪除的一條邊對應(yīng)的兩個(gè)頂點(diǎn)編號:" cin>>v0>>v1;if(v0>=0&&v0<G.vernum&&v1>=0&&v1<G.vernum)flag=0; i=locatevex(G,v0);j=locatevex(G

46、,v1);G.arcsij.adj=A;G.arcsji.adj=A;G.arcnum-; displaycampus(G); printmatrix(G);return 1;int enverx(mgraph &G)/增加景點(diǎn)int i;cout<<"請輸入要添加的景點(diǎn)的信息："<<endl;cout<<"請輸入景點(diǎn)編號:" cin>>G.vexsG.vernum.position;cout<<"請輸入景點(diǎn)名稱:" cin>>G.vexsG.vernum

47、.name;cout<<"請輸入景點(diǎn)簡介:" cin>>G.vexsG.roduction;cout<<endl;G.vernum+;for(i=0;i<G.vernum;i+)G.arcsiG.vernum-1.adj=G.arcsiG.vernum-1.adj=A;displaycampus(G);printmatrix(G);return 1;int enarc(mgraph &G)/增加路徑int v0,v1,distance;cout<<"請輸入增加路徑的起始點(diǎn)編號:&qu

48、ot; cin>>v0;cout<<"請輸入增加路徑的終點(diǎn)編號:"<<endl; cin>>v1;cout<<"請輸入增加路徑長度"<<endl;cin>>distance;G.arcsv0v1.adj=G.arcsv1v0.adj=distance;displaycampus(G);printmatrix(G);return 1;void seaabout(mgraph G)/景點(diǎn)信息查詢；int n,flag=1;cout<<"請輸入要查詢的景點(diǎn)

49、編號："cin>>n;while(flag)if(n<0|n>G.vernum)cout<<"該景點(diǎn)不存在，請重新輸入：" cin>>n;elsecout<<"景點(diǎn)編號 "<<"景點(diǎn)名稱 "<<" 景點(diǎn)簡介 "<<endl;cout<<" "<<G.vexsn.position<<" "cout<<G.&

50、lt;<" "cout<<G.roduction<<" "<<endl;flag=0;int newgraph(mgraph &G)/更新景點(diǎn)的信息int n,m,t;cout<<"請輸入要更新的景點(diǎn)數(shù)："<<endl;cin>>n;while(n<0|n>G.vernum)cout<<"該景點(diǎn)不存在，請重新輸入："<<endl;cin>>n;for(int i=0

51、;i<n;i+)/修改景點(diǎn)信息cout<<"輸入景點(diǎn)的編號："<<endl;cin>>m;t=locatevex(G,m);cout<<"輸入景點(diǎn)的名稱："<<endl;cin>>G. ; cout<<"輸入景點(diǎn)的簡介："<<endl; cin>>G.roduction ;cout<<"請輸入要更改的邊數(shù)："<<endl;cin>>

52、;n;int distance,v0,v1;while(n<0|n>G.arcnum)cout<<"該路徑不存在，請重新輸入："<<endl;cin>>n;cout<<"輸入更新的路徑的信息："<<endl;for(i=0;i<n;i+)/修改路徑信息cout<<"起始景點(diǎn)編號v0:"<<endl; cin>>v0;cout<<"終點(diǎn)景點(diǎn)編號v1:"<<endl;cin>&

53、gt;v1;cout<<"路勁長度:"<<endl; cin>>distance;m=locatevex(G,v0);t=locatevex(G,v1);if(m>=0&&t>=0)G.arcsmt.adj=G.arcstm.adj=distance;displaycampus(G);printmatrix(G);return 1;int changegraph(mgraph G)/更改圖的信息int i; cout<<"1、重新建圖 2、刪除結(jié)點(diǎn) "<<endl;c

54、out<<"3、刪除邊 4、增加結(jié)點(diǎn) "<<endl;cout<<"5、增加邊 6、更新圖信息"<<endl;cout<<"7、打印鄰接矩陣 8、返回程序 "<<endl;while(1)cout<<"請輸入要進(jìn)行的操作:" cin>>i;switch(i)case 1:cout<<"重新建圖:"<<endl;creatgraph(g);break;case 2:cout<<"刪除結(jié)點(diǎn):"<<endl;DeleteVertex(g);break;case 3:cout<<"刪除邊:"<<endl;DeleteplanArc(g);break;case 4:cout<<"增加結(jié)點(diǎn):"<<endl;enverx(g);break;case 5:cout<<"增加邊:"<<endl