數據結構課程設計報告模板

《數據結構課程設計報告模板》由會員分享，可在線閱讀，更多相關《數據結構課程設計報告模板（28頁珍藏版）》請在裝配圖網上搜索。

1、校園導游系統設計一、設計要求1問題描述設計一個校園導游程序，為來訪的客人提供信息查詢服務。2需求分析（1）設計學校的校園平面圖。選取若干個有代表性的景點抽象成一個無向帶權圖（無向 網），以圖中頂點表示校內各景點，邊上的權值表示兩景點之間的距離。（2）存放景點代號、名稱、簡介等信息供用戶查詢。（3）為來訪客人提供圖中任意景點相關信息的查詢。（4）為來訪客人提供圖中任意景點之間的問路查詢。（5）可以為校園平面圖增加或刪除景點或邊，修改邊上的權值等。二、概要設計為了實現以上功能，可以從 3 個方面著手設計。1主界面設計 為了實現校園導游系統各功能的管理，首先設計一個含有多個菜單項的主控菜單子程序 以

2、鏈接系統的各項子功能，方便用戶使用本系統。本系統主控菜單運行界面如圖 7-10 所示。2存儲結構設計本系統采用圖結構類型（mgraph ）存儲抽象校園圖的信息。其中：各景點間的鄰接關系 用圖的鄰接矩陣類型（adjmatrix）存儲；景點（頂點）信息用結構數組（vexs）存儲，其中每 個數組元素是一個結構變量，包含景點編號、景點名稱及景點介紹三個分量；圖的頂點個數及 邊的個數由分量 vexnum、arcnum 表示，它們是整型數據。此外，本系統還設置了三個全局變量： visited 數組用于存儲頂點是否被訪問標志； d 數組用于存放邊上的權值或存儲查找路徑頂點的編號；campus是一個圖結構的全

3、局變量。3系統功能設計本系統除了要完成圖的初始化功能外還設置了 8 個子功能菜單。圖的初始化由函數 initgraph（ ）實現。依據讀入的圖的頂點個數和邊的個數，分別初始化圖結構中圖的頂點向量數 組和圖的鄰接矩陣。 8 個子功能的設計描述如下。（1）學校景點介紹學校景點介紹由函數 browsecompus（ ）實現。當用戶選擇該功能，系統即能輸出學校全部 景點的信息：包括景點編號、景點名稱及景點簡介。（ 2）查看瀏覽路線查看瀏覽路線由函數shortestpath_dij（）實現。該功能采用迪杰斯特拉（Dijkstra）算法實現。 當用戶選擇該功能，系統能根據用戶輸入的起始景點編號，求出從該景

4、點到其它景點的最短路 徑線路及距離。（3）查看兩景點間最短路徑查看兩景點間最短路徑由函數shortestpath_floyd()實現。該功能采用弗洛伊德(Floyd)算 法實現。當用戶選擇該功能，系統能根據用戶輸入的起始景點及目的地景點編號，查詢任意兩 個景點之間的最短路徑線路及距離。(4) 景點信息查詢景點信息查詢由函數seeabout()實現。該功能根據用戶輸入的景點編號輸出該景點的相關 信息。例如，景點編號、名稱等。(5) 更改圖的信息更改圖的信息功能由主調函數 changegraph( )及若干個子函數完成，可以實現圖的若干基 本操作。例如：增加新的景點、刪除邊、重建圖等。(6) 查詢

5、景點間可行路徑該功能是查詢兩景點間所有可行路徑，由函數allpath()和函數path()實現，其中path() 函數是直接遞歸函數。由于是無向網，如果網中的邊數很多，任意兩個景點間的所有路徑也會 有限多，但很多路徑是無實際意義的(有近路，為什么去走遠路呢？)。所以，本算法在求得 的兩景點間所有可行路徑中，限制只輸出路徑長度不超過 8個景點的路線。( 7 )打印鄰接矩陣該功能即輸出圖的鄰接矩陣的值，由函數printmatrix()實現。( 8 )退出即退出校園導游系統，由exit(0)函數實現。三、模塊設計1校園抽象圖設計 以湖北第二師范學院光谷校區主要景點為例，抽象完成的無向網如圖 7-7

6、所示。全校共抽 象出 28個景點， 39條道路。各景點分別用圖中的頂點表示，景點編號從 0-27；39條道路分 別用圖中的邊表示，邊上的權值表示景點之間的模擬距離。2模塊設計本程序包含3個模塊：主程序模塊、工作區模塊和無向網操作模塊。調用關系如圖7-8 所示。主程序模塊工作區模塊無向網操作模塊圖 7-8 模塊調用示意圖3系統子程序及功能設計 本系統共設置 18 個子程序，各子程序的函數名及功能說明如下。(1) mgraph initgraph( )/ 圖的初始化(2) int locatevex(mgraph c, int v)/ 查找景點在圖中的序號(3) void path(mgraph

7、c, int m,int n,int k) / 打印序號為 m,n 景點間的長度不超過 8 個景點的路徑(4) int allpath(mgraph c)/ 打印兩景點間的景點個數不超過 8 的所有路徑。調用 (3)(5) void shortestpath_dij(mgraph c) / 用 Dijkstra 算法，求一個景點到其他景點間的最短路徑，并打印 以下編號(6)(12)是圖的基本操作。包括：重建圖、更新信息、刪除、增加結點和邊等。6) int creatgragh(mgraph &c)/ 建圖。以圖的鄰接矩陣存儲圖7) int newgraph(mgraph &c)/ 更新圖的部分

8、信息。返回值：18) int enarc(mgraph&c)9) int envex(mgraph&c)10) int delvex(mgraph&c)11) int delarc(mgraph&c)12) void printmatrix(mgraph c)/ 增加一條邊。返回值：1/ 增加一個結點。返回值：1/ 刪除圖的一個頂點。返回值：1/ 刪除圖的一條邊。返回值：1/ 輸出圖的鄰接矩陣13) int changegraph(mgraph &c)14) void shortestpath_floyd(mgraph c)15) void seeabout(mgraph c)16) void

9、 browsecompus(mgraph c)17) void mainwork( )18) void main( )/ 圖操作的主調函數。返回值：1/ 用 Floyd 算法求任意兩景點間的最短路徑，并輸出/ 查詢景點的信息/ 顯示所有景點信息/ 工作區函數。操作區用戶界面/ 主函數。設定界面的顏色和大小，調用工作區模塊函數4函數主要調用關系圖校園導游系統 18個子程序之間的主要調用關系如圖 7-9所示。圖中數字是各函數的編號四、詳細設計1數據類型定義（1）無向帶權圖（無向網）的定義typedef struct arcell/邊的權值信息int adj;/權值arcell,adjmatrixM

10、axVertexNumMaxVertexNum;/圖的鄰接矩陣類型typedef struct vexsinfoint position;char name32;char introduction256;vexsinfo;typedef struct mgraphvexsinfo vexsMaxVertexNum;adjmatrix arcs;int vexnum,arcnum;mgraph;(2)全局變量定義int visited35;int d35;mgraph campus;2系統主要子程序詳細設計(1)主程序模塊設計 主函數。設定用戶操作界面的顏色和大小 void main( )sys

11、tem(color 1f);system(mode con: cols=140 lines=130); mainwork( );/頂點信息/景點的編號/景點的名稱/景點的介紹/圖結構信息/頂點向量(數組)/鄰接矩陣/分別指定頂點數和邊數/用于標志頂點是否已經訪問過 /用于存放權值或存儲路徑頂點編號 /圖變量(大學校園)調用工作區模塊函數。/屏幕顏色設定(2)用戶工作區模塊設計主要工作函數。操作區用戶界面設計。void mainwork( )int yourchoice;campus=initgraph( );printf(n 歡迎使用校園導游程序 printf(n歡迎來到湖北第二師范學院 !p

12、rintf(n 菜 單 選 擇-n);nn);nn);n);printf( 1. 學校景點介紹 2. 查看游覽路線printf(3. 查詢景點間最短路徑4. 景點信息查詢n);printf(5. 更改圖信息6. 查詢景點間可行路徑n);printf(7. 打印鄰接矩陣8. 退出n);printf(nn);printf(”請輸入你的選擇：”)；scanf(%d,&yourchoice);while(!(yourchoice=1|yourchoice=2|yourchoice=3|yourchoice=4|yourchoice=5|yourchoice=6 |yourchoice=7|yourch

13、oice=8)printf (輸入選擇不明確，請重新輸入n);scanf(%d, &yourchoice)；while(1)switch(yourchoice)1case 1:system(cls);browsecompus(campus);break;case 2:system(cls);shortestpath_dij(campus);break;case 3:system(cls);shortestpath_floyd(campus); break;case 4:system(cls);seeabout(campus);break;case 5:system(cls);changegra

14、ph(campus);break;case 6:system(cls);allpath(campus);break;case 7:system(cls);printmatrix(campus);break;case 8:system(cls);exit(0);break;default:break;printf(n-歡迎使用校園導游程序n);printf(n歡迎來到湖北第二師范學院!nn);printf(n菜單選擇nn);printf(1.學校景點介紹2. 查看游覽路線n);printf(3.查詢景點間最短路徑 4. 景點信息查詢n);printf(5.更改圖信息6. 查詢景點間可行路徑n);

15、printf(7.打印鄰接矩陣8. 退出n);printf(n-n);printf(n 請輸入你的選擇： ); scanf(%d, &yourchoice);/endwhile(1)/mainwork3)無向網操作主調模塊設計int changegraph(mgraph &c)int yourchoice;printf(n請問是要nn再次建圖(2)刪除結點(3)刪除邊n);printf(n (4)增加結點(5)增加邊(6)更新信息 nn (7)打印鄰接矩陣(8)返回? nn);scanf(%d,&yourchoice); printf(nn);while(!(yourchoice=1|your

16、choice=2|yourchoice=3|yourchoice=4|yourchoice=5|yourchoice=6 |yourchoice=7|yourchoice=8)printf(輸入選擇不明確，請重輸n);scanf(%d,&yourchoice);while(1)switch(yourchoice)1case 1:creatgragh(c);break;/重建圖，調用(6)case 2:delvex(c);break;/刪除頂點，調用(10)case 3:delarc(c);break;/刪除邊，調用(11)case 4:envex(c);break;/增加頂點，調用(9)cas

17、e 5:enarc(c);break;/增加邊，調用(8)case 6:newgraph(c);break;/更新圖的信息，調用(7)case 7:printmatrix(c);break;/輸出鄰接矩陣，調用(12)case 8:return 1;/ 返回主菜單(2)刪除結點(3)刪除邊 n);(6)更新信息 nn (7)打印鄰接矩陣(8)返回? nn);printf(n請問是要55 (1)再次建圖 printf(n (4)增加結點(5)增加邊scanf(%d,&yourchoice); printf(nn);while(!(yourchoice=1|yourchoice=2|yourcho

18、ice=3|yourchoice=4|yourchoice=5|yourchoice=6 |yourchoice=7|yourchoice=8)printf(輸入選擇不明確，請重輸n);scanf(%d,&yourchoice);/endwhile(1)return 1;/changegraph4)求兩景點間的所有路徑int allpath(mgraph c)/ 4. 求兩景點間的所有路徑算法中將路徑起始點編號m存入d 0數組元素中，并將其頂點訪問標志設置為1,即visitedm=l /然后調path()函數求由m出發到景點n的所有路徑。int k, i, j, m, n;printf(nn請

19、輸入你要查詢的兩個景點編號:nn);scanf(%d%d,&i,&j); printf(nn);visitedk=0; visitedm=1; path(c,m,n,0); return 1;m=locatevex(c,i);/調用 2，確定該頂點是否存在。若存在，返回該頂點編號n=locatevex(c,j);d0=m;for(k=0;kc.vexnum;k+)/存儲路徑起點 m (int d 數組是全局變量)/全部頂點訪問標志初值設為0 (int visited 數組是全局變量)第m個頂點訪問標志設置為1調用3。k=0，對應起點d0= =m。k為d數組下標/endallpathvoid p

20、ath(mgraph c, int m,int n,int k)/ 3.自遞歸調用函數。若頂點s是由m出發到景點n的路徑上的頂點，則調用自身，求由s出發的所/有可能到達頂點n的路徑。找到一條(遞歸出口)，輸出一條(限制只輸出景點個數=8的路徑)。/d數組存儲由m出發到景點n的路徑上的頂點編號，visited數組用于存放頂點是否被訪問的標志int s, x=0, t=k+1;/ t用于存放路徑上下一個頂點對應的d數組元素的下標if (dk=n & k8) 遞歸出口，找到一條路徑。若dk是終點n且景點個數=8,則輸出該路徑f or (s=0;s,c.vexsds.name);/輸出該路徑。 s=0

21、 時為起點 mprintf(%snn,c.vexsds.name);/輸出最后一個景點名(即頂點n的名字，此時s=k)elses=0;/從第m個頂點，試探至所有頂點是否有路徑while(sc.vexnum)if(c.arcsdks.adjInfinity) & (visiteds= =0) /初態：頂點 m 到頂點 s 有邊，且未被訪問visiteds=1;dk+1=s; path(c,m,n,t);/存儲頂點編號s至dk+1中/求從下標為t=k+1的第dt=s個頂點開始的路徑(遞歸調用),/同時打印出一條 m 至 n 的路徑visiteds=0; /將找到的路徑上頂點的訪問標志重新設置為 0

22、，以用于試探新的路徑 s+;/試探從下一個頂點 s 開始是否有到終點的路徑/endwhile/endelse/endpath（5）用迪杰斯特拉（Dijkstra）算法，求一個景點到其它景點間的最短路徑并打印void shortestpath_dij（mgraph c） / 5. 迪杰斯特拉算法，求從頂點 v0 到其余頂點的最短路經 p 及其帶權長度 dv （最短路經的距離）/ p數組用于存放兩頂點間是否有通路標志。若pvw= =1，則w是從vO到v的最短路經上的頂點。 / final 數組用于設置訪問標志。int v, w, i, min, t=O, x, flag=1, vO;/vo 為起始

23、景點的編號int final35, d35, p3535;printf（n 請輸入一個起始景點的編號：）;scanf(%d,&vO); printf(nn);while(vOc.vexnum)printf（n你所輸入的景點編號不存在n）;printf( 請重新輸入：);scanf(%d,&vO);/whilefor(v=O;vc.vexnum ;v+)finalv=O; dv=c.arcsvOv.adj;for(w=O;wc.vexnum ;w+)pvw=O;if(dvInfinity)pvvO=1;pvv=1;/fordvO=O;finalvO=1;/初始化各頂點訪問標志/vO 到各頂點 v

24、 的權值賦值給 dv/初始化p數組，各頂點間的路徑全部設置為空路徑0/vO到v有邊相連，修改pvvO的值為1/各頂點自己到自己要連通/自己到自己的權值設為 O/ vO的訪問標志設為1，v屬于s集對其余c.vexnum-1個頂點w，依次求v到w的最短路徑for(i=1;ic.vexnum ;i+)min=Infinity;for(w=O;wc.vexnum ;w+)if(!finalw)/在未被訪問的頂點中,查找與 vO 最近的頂點 vif(dwmin)v=w; min=dw;/ v0到w （有邊）的權值min/iffinalv=1;for(w=O;wc.vexnum ;w+)/ v 的訪問標志

25、設置為 1, v 屬于 s 集修改v0到其余各頂點w的最短路徑權值dwif(!finalw&(min+c.arcsvw.adj dw)若 w 不屬于 s,且 v 到 w 有邊相連dw=min+c.arcsvw.adj;for(x=0;xc.vexnum ;x+)pwx=pvx; pww=1;/if/forfor(v=0;vc.vexnum ;v+)/修改 v0 到 w 的權值 dw所有V0到v的最短路徑上的頂點X,都是V0到w的/最短路徑上的頂點/輸出 v0 到其它頂點 v 的最短路徑if(v!=v0)printf(%s,c.veXsv0.name);/輸出景點 v0 的景點名for（w=0;

26、w%s,c.vexsw.name);printf(%s,c.vexsv.name);printf(n 總路線長為d 米nn,dv);/for/shortestpath_dij（6）用弗洛伊德（floyd）算法，求兩景點間的最短路徑并打印void shortestpath_floyd(mgraph c) / 14. 用 floyd 算法,求各對頂點 v 和 w 間的最短路經 p 及其帶權長度 dvw/若pvwu= =1 ；則u是v到w的當前求得的最短路經上的頂點int i, j, k, v, u, w, d3535, p353535;for(v=O;vc.vexnum ;v+) /初始化各對頂點

27、 v, w 之間的起始距離 dvw 及路徑 pvw 數組 for(w=O;wc.vexnum ;w+)/dvw 中存放 v 至 w 間初始權值/初始化最短路徑 pvw 數組，第 3 分量全部清 0/如果 v 至 w 間有邊相連/ v 是 v 至 w 最短路徑上的頂點/ w 是 v 至 w 最短路徑上的頂點/求v至w的最短路徑及距離。dvw=c.arcsvw.adj;for(u=0;uc.vexnum ;u+)pvwu=0;if(dvwInfinity)pvwv=1;pvww=1;/if/for/endforfor(u=0;uc.vexnum ;u+)/對任意頂點U,試探其是否為V至w最短路徑上

28、的頂點for(v=0;vc.vexnum ;v+)for(w=0;wc.vexnUm ;w+) if(dvu+duwdvw)/從 v 經 u 到 w 的一條路徑更短 dvw=dvu+duw;/修改 v 至 w 的最短路徑長度for(i=0;ic.vexnum ;i+) /修改 v 至 w 的最短路徑數組。pvwi = pvui II puwi; 若i是v至u的最短路徑上的頂點，或i是u至w的/最短路徑上的頂點，則i是v至w的最短路徑上的頂點/endforprintf (n請輸入出發點和目的地編號：);scanf(%d%d,&k,&j); printf(nn);while(kc.vexnumII

29、jc.vexnum)printf(n 你所輸入的景點編號不存在！); printf(n 請重新輸入出發點和目的地編號： nn);/輸出出發景點名稱/輸出最短路徑上中間景點名稱/輸出目的地景點名稱scanf(%d%d,&k,&j); printf(nn printf(%s,c.vexsk.name );for(u=0;u%s,c.vexsu.name ); printf(-%s,c.vexsj.name ); printf(nnn 總長為d 米nnn,dkj);/shortestpath_floyd五、測試分析系統運行主界面如圖 7-10 所示。歡迎使用校園導游程序歡迎來到湖北第二師范學院？徑

30、路 行 線詢可 路查間 覽息點 .最 看點詢岀 畫_退 2 4 6 8菜徑路短紹最陣 介間息矩 點點信接 *,景圖那 校詢改印 善更打 丄 3 57.請輸入你的選擇:圖 7-10 校園導游系統主菜單 各子功能測試運行結果如下。1學校景點介紹在主菜單下，用戶輸入 1回車，運行結果如圖7-11所示。-6個、階悌鞍室1-6個建材系所在地，機房及多媒體教室若干6高 樓r4E層5E 進公高5E高 車辦樓高 樓 班院，樓S 盤于系-1 學業術樓高崖目 I I近、矍大樓田經近濟離齧游,所及461, I 站門化、公，準、身，院，型缶堂積區券于年3,區學區的院 交大文彖與棟學零面蚤機青生西語西華公校亠=晟政學外

31、心西學干業育皐藝工校國校2 辜語貢仃文室教離數若職體室可文教建外電近層 tB 大產 院2 ,S會內亂臨 I 術室縣堂-學1.樓S學、1-t血食理生大 5 t 型地生砰生斤- 奕學睪如大化 -:.iL-;- - r r 院 地咼較 % 亠壽 :堂樓堂 ，租近食，食 樓工翳樓卸層 亠邵地 i職門E化院院學樓 理-R 院4lnIMb 魯濟宿鞍 韋經生院室S 悌育 階體、一丄彳E 4!一上一幺亠上一用 、 . 南南文學與也辜系館廳窖、 西校言術政書育區學區業育逵口程_ 傘語藝行文體教南數中職體舍 舍宿院宿院 生書生學.堂學機宿學堂語堂壕 O區算工區鋰國雌醫驗 譙東g西第請校實圖 7-11 二師院光谷校

32、區景點名稱及簡介2查看瀏覽路線在主菜單下，用戶輸入.2 回車，根據屏幕提示輸入一個景點編號 4 回車后，系統會給出 由景點4到其余27個景點的最短瀏覽線路及最短距離。運行結果的截圖如圖 7-12所示。不足之處：線路的編排受景點編號的影響，有些可能不合理。:南正門情輸入一個起始景點的編號：4鄭爲S?院T藝術學院一一 體育場 :為丄0瞇認計職業學院一藝術學院一南區學生宿舍噩加漾學院fcgj? 1語言文化職業學院噩feg溝育科學學院噩feg蒙院外西南門圖 7-12 從一個景點出發的瀏覽路線圖3查看兩景點間最短路徑在主菜單下，用戶輸入 3回車，根據屏幕提示輸入一個出發景點編號及目的地景點編號 3 17

33、 回車后，運行結果如圖 7-13 所示。不足之處：線路的編排受景點編號的影響，有些可能不合理。請輸入出發點和目的地編號：3 1?藝術學院-一 體育場一數學與經濟管理學院一體育系一 -1食堂一噺圖書館總長為230米圖 7-13 任意兩個景點之間的最短瀏覽路線圖4景點信息查詢在主菜單下，用戶輸入 4回車，根據屏幕提示輸入一個要查詢的景點編號20回車后，運 行結果如圖 7-14 所示。不足之處：僅能根據景點編號進行查詢，可以增加根據景點名進行查詢的功能。請輸入要查詢的景點編號：20編號：20景點名稱：計算機學院介紹：計算機學院大樓，樓高5層圖 7-14 景點信息查詢5更改圖的信息 在主菜單下，用戶輸

34、入5回車后出現二級菜單界面，運行結果如圖 7-15 所示。再進一步 做選擇，可以實現圖的相關基本操作。請問是要灶 再次建圖2刪除結點3劇除邊増劑結點5増加邊更新信息打印鄰接矩陣8返回?圖 7-15 更改圖的信息6查詢景點間可行路徑 本算法在求得的兩景點間所有可行路徑中，限制只輸出路徑長度不超過 8 個景點的路線。 在主菜單下，用戶輸入6回車，根據屏幕提示輸入要查詢的兩個景點編號：5 17 回車后，運行 結果截圖如圖 7-16 所示。本功能由遞歸函數實現，所以當圖中的邊數過多時，可能造成死循 環而得不到正確結果。不足之處：線路的編排受景點編號的影響，有些可能不合理。請輸入你要查詢的兩個景點編號：

35、5 1?文學院一-行政樓-一藝術學院-一體育場-一數學與經濟管理學院一體育系一-1食堂-一新圖書館文學院一-行政樓一數學與經濟管理學院-一體育系一-職業學院教學大樓大禮堂、體育館i食堂-一新圖書館文學院一-行政樓一數學與經濟管理學院-一體育系一-1食堂一-新圖書館文學院一- 行政樓-一 中區學生宿舍2食堂潮圖書館圖 7-16 查詢兩景點間的可行路徑7打印鄰接矩陣 在主菜單下，用戶輸入7回車，即可輸出圖的鄰接矩陣的值。如圖 7-17所示。圖 7-17 圖的鄰接矩陣8退出在主菜單下，用戶輸入 8回車，即退出校園導游系統。六、 源程序清單#define Infinity 1000#define Ma

36、xVertexNum 35#define MAX 40#include#include#include#include#includetypedef struct arcell/邊的權值信息int adj;arcell, adjmatrixMaxVertexNumMaxVertexNum;/權值/圖的鄰接矩陣類型typedef struct vexsinfo/頂點信息int position;char name32;char introduction256;vexsinfo;typedef struct mgraph /圖結構信息vexsinfo vexsMaxVertexNum; adjma

37、trix arcs;int vexnum,arcnum;/景點的編號/景點的名稱/景點的介紹/頂點向量（數組）/鄰接矩陣/分別指定頂點數和邊數mgraph;/全局變量 int visited35;int d35; mgraph campus; / 1. 對圖初始化/用于標志是否已經訪問過/用于存放權值或存儲路徑頂點編號/圖變量（大學校園）mgraph initgraph( )int i=0,j=0;mgraph c;c.vexnum =28;c.arcnum =39;for(i=0;ic.vexnum ;i+) c.vexsi.position =i;/頂點個數/邊的個數/依次設置頂點編號/依

38、次輸入頂點信息strcpy（c.vexs0.name ,小西南門）;strcpy（c.vexs0.introduction ,離公交站近）;strcpy（c.vexs1.name ,學校南正門）;strcpy（c.vexs1.introduction ,學校大門、學校班車進出口）;strcpy（c.vexs2.name ,語言文化職業學院）;strcpy（c.vexs2.introduction ,語言文化職業學院辦公樓，樓高 6 層）;strcpy（c.vexs3.name ,藝術學院）;strcpy（c.vexs3.introduction ,音樂系、美術系，樓高 4 層）;strcpy（

39、c.vexs4.name ,行政樓）;strcpy（c.vexs4.introduction ,行政辦公大樓，樓高 5 層）;strcpy（c.vexs5.name,文學院）；strcpy（c.vexs5.introduction ,文學院，樓高 6層）;strcpy（c.vexs6.name ,體育場）；strcpy（c.vexs6.introduction ,室外標準田徑場）；strcpy（c.vexs7.name,教育科學學院）；strcpy（c.vexs7.introduction ,教心系、經管系，樓高 5 層）；strcpy（c.vexs8.name ,南區學生宿舍）；strcpy

40、（c.vexs8.introduction ,離西南門近）；strcpy（c.vexs9.name, 數學與經濟管理學院）；strcpy（c.vexs9.introduction ,數學與經濟管理學院大樓，樓高 4層）；strcpy（c.vexs10.name ,中區學生宿舍）；strcpy（c.vexs10.introduction ,若干棟，離學生 1、2 食堂近）；strcpy（c.vexs11.name ,職業學院教學大樓）；strcpy（c.vexs11.introduction ,職業學院教學大樓，樓高5層）；strcpy（c.vexs12.name ,體育系）；strcpy（c.

41、vexs12.introduction ,體育系，樓高 5 層）；strcpy（c.vexs13.name ,游泳館）；strcpy（c.vexs13.introduction ,室內小型游泳館）；strcpy（c.vexs14.name ,報告廳、階梯教室）；strcpy（c.vexs14.introduction ,可舉辦中、大型學術會議。有大小報告廳16 個、階梯教室 16 個）；strcpy（c.vexs15.name ,大禮堂、體育館）；strcpy（c.vexs15.introduction ,文藝演出所在地、室內運動場）；strcpy（c.vexs16.name ,1 食堂）；s

42、trcpy（c.vexs16.introduction ,教工食堂及學生 1 食堂在此）；strcpy（c.vexs17.name ,新圖書館）；strcpy（c.vexs17.introduction ,建筑面積 46000 平方米）；strcpy（c.vexs18.name ,2 食堂）；strcpy（c.vexs18.introduction ,學校東區，學生食堂）；strcpy（c.vexs19.name ,東區學生宿舍）;strcpy（c.vexs19.introduction ,離學生 2 食堂近）;strcpy（c.vexs20.name ,計算機學院）;strcpy（c.vex

43、s20.introduction ,計算機學院大樓，樓高 5 層）;strcpy（c.vexs21.name ,教工宿舍）;strcpy（c.vexs21.introduction ,學校青年教職工租住地）;strcpy（c.vexs22.name ,西區學生宿舍）;strcpy（c.vexs22.introduction ,離學生 3、4 食堂近）;strcpy（c.vexs23.name ,3 食堂）;strcpy（c.vexs23.introduction ,學校西區，學生食堂）;strcpy（c.vexs24.name ,外國語學院）;strcpy（c.vexs24.introduct

44、ion ,外國語學院大樓，樓高 5 層）;strcpy（c.vexs25.name ,4 食堂）;strcpy（c.vexs25.introduction ,學校西區，學生食堂，人氣較高）;strcpy（c.vexs26.name ,校醫院）;strcpy（c.vexs26.introduction ,看小病的地方）;strcpy（c.vexs27.name ,實驗樓）;strcpy（c.vexs27.introduction ,物電學院、化學與生命科學學院、機電系、建材系所在地，機房及多媒 體教室若干）;for（i=0;ic.vexnum ;i+）for（j=0;jc.vexnum ;j+）

45、c.arcs ij.adj =Infinity; /先初始化圖的鄰接矩陣c.arcs02.adj=50;c.arcs28.adj=40;c.arcs49.adj=70;c.arcs69.adj=40;c.arcs1018.adj=70;c.arcs1216.adj=50;c.arcs1420.adj=90;c.arcs1718.adj=80;c.arcs2223.adj=60;c.arcs03.adj=60;c.arcs34.adj=60;c.arcs410.adj=80;c.arcs718.adj=190;c.arcs1112.adj=60;c.arcs1314.adj=40;c.arcs1

46、516.adj=60;c.arcs1819.adj=60;c.arcs2225.adj=80;c.arcs14.adj=90;c.arcs36.adj=40;c.arcs417.adj=200;c.arcs811.adj=50;c.arcs1114.adj=50;c.arcs1322.adj=60;c.arcs1521.adj=40;c.arcs2021.adj=60;c.arcs2324.adj=60;c.arcs23.adj=60;c.arcs45.adj=70;c.arcs57.adj=70;c.arcs912.adj=40;c.arcs1115.adj=50;c.arcs1415.ad

47、j=50;c.arcs1617.adj=60;c.arcs2024.adj=80;c.arcs2426.adj=100;c.arcs2427.adj=100;c.arcs2526.adj=90;c.arcs2627.adj=90;for（i=0;ic.vexnum ;i+）/鄰接矩陣是對稱矩陣，對稱賦值for（j=0;jc.vexnum ;j+）c.arcsji.adj =c.arcsij.adj ;return c;/initgraph/ 2. 查找景點在圖中的序號 int locatevex（mgraph c,int v）int i;找到，返回頂點序號i/否則，返回-1for (i=0;i

48、c.vexnum ;i+) if (v=c.vexsi.position) return i;return -1;/ 3.查找并輸出序號為m,n景點間的長度不超過8個景點的路徑void path（mgraph c, int m,int n,int k）/源代碼參見：7.2.4 詳細設計 2.（4）/ 4. 查找兩景點間的景點的所有路徑。int allpath（mgraph c）/源代碼參見：7.2.4 詳細設計 2.（4）/ 5. 用迪杰斯特拉算法，求出一個景點到其他景點間的最短路徑，并打印void shortestpath_dij（mgraph c）/源代碼參見：7.2.4 詳細設計 2.（

49、5）/ 6-11修改圖的信息。包括建圖、更新信息、刪除、增加結點和邊/ 6. 構造圖的鄰接矩陣int creatgragh(mgraph &c)int i, j, m, n, v0,v1,distance;printf(”請輸入圖的頂點數和邊數:n); scanf(%d %d,&c.vexnum ,&c.arcnum ); printf(下面請輸入景點的信息：n);for(i=0;ic.vexnum ;i+)printf(”請輸入景點的編號：”)； scanf(%d,c.vexsi.position );printf(n 請輸入景點的名稱： );scanf(%s,c.vexsi.name );

50、printf(n 請輸入景點的簡介： ); scanf(%s,c.vexsi.introduction );for(i=0;ic.arcnum ;i+)for(j=0;jc.arcnum ;j+) c.arcsij.adj =Infinity;printf(”下面請輸入圖的邊的信息：n); for(i=1;i=0 & n=0)c.arcsmn.adj =distance;c.arcsnm.adj =c.arcsmn.adj ;return 1;/creatgragh/ 7. 更新圖的部分信息。返回值: 1int newgraph(mgraph &c)int changenum;/計數。用于記錄

51、要修改的對象的個數int i, m, n, t, distance, v0, v1;printf(n下面請輸入你要修改的景點的個數：n);scanf(%d,&changenum); while(changenumc.vexnum )printf(n 輸入錯誤！請重新輸入);scanf(%d,&changenum);for(i=0;ichangenum;i+)printf(n 請輸入景點的編號： );scanf(%d,&m);t=locatevex(c,m);printf(n 請輸入景點的名稱： );scanf(%s,c.vexst.name );printf(n 請輸入景點的簡介： );sca

52、nf(%s,c.vexst.introduction );printf(n 下面請輸入你要更新的邊數);scanf(%d,&changenum);while(changenumc.arcnum )printf(n 輸入錯誤！請重新輸入);scanf(%d,&changenum);printf(n 下面請輸入更新邊的信息： n);for(i=1;i=0&n=0)c.arcsmn.adj =distance;c.arcsnm.adj =c.arcsmn.adj ;return 1;/newgraph/ 8. 增加一條邊。返回值： 1int enarc(mgraph&c)int m, n, dist

53、ance;printf(n 請輸入邊的起點和終點編號,權值： );scanf(%d %d %d,&m,&n,&distance);while(mc.vexnum |nc.vexnum )printf( 輸入錯誤，請重新輸入： );scanf(%d %d,&m,&n);if(locatevex(c,m)0)printf(此結點d已刪除,m);return 1;if(locatevex(c,n)0)printf(此結點d已被刪除：”,n);return 1;c.arcsmn.adj =distance;c.arcsnm.adj =c.arcsmn.adj;/對稱賦值return 1;/enarc/ 9. 增加一個結點。返回值：1int envex(mgraph