校園導(dǎo)游系統(tǒng)程序

1、課題五：校園導(dǎo)游程序 1)問題描述用無向網(wǎng)表示你所在學(xué)校的校園景點平面圖，圖中頂點表示主要景點，存放景點的編號、名稱、簡介等信息，圖中的邊表示景點間的道路，存放路徑長度等信息。要求能夠回答有關(guān)景點介紹、游覽路徑等問題。2)基本要求（1） 查詢各景點的相關(guān)信息；（2） 查詢圖中任意兩個景點間的最短路徑。（3） 能夠?qū)D的信息保存到文件中，并指定文件打開。（4） 增加、刪除、更新有關(guān)景點和道路的信息。附加難度：有余力的同學(xué)可以考慮用圖形界面實現(xiàn)尋址的過程3) 設(shè)計思想核心數(shù)據(jù)結(jié)構(gòu)定義一個圖，將圖保存后，對圖進行面向指定節(jié)點到各個節(jié)點的最短路徑的操作?？梢栽傥募斜４娑鄠€導(dǎo)游圖，例如保存學(xué)校圖、蕪湖

2、市圖等文件。開始時選擇文件，將指定文件中的信息導(dǎo)入到內(nèi)存的圖中。#define Infinity 1000#define MaxVertexNum 35#define MAX 40#include#include#include#include#include#includetypedef struct arcell /邊的權(quán)值信息int adj; /權(quán)值arcell,adjmatrixMaxVertexNumMaxVertexNum; /圖的鄰接矩陣類型typedef struct vexsinfo /頂點信息int position; /景點的編號char name32; /景點的名稱ch

3、ar introduction256; /景點的介紹vexsinfo;typedef struct mgraph /圖結(jié)構(gòu)信息vexsinfo vexsMaxVertexNum; /頂點向量(數(shù)組)adjmatrix arcs; /鄰接矩陣int vexnum,arcnum; /分別指定頂點數(shù)和邊數(shù)mgraph;/全局變量int visited35; /用于標(biāo)志是否已經(jīng)訪問過int d35; /用于存放權(quán)值或存儲路徑頂點編號mgraph campus; /圖變量(大學(xué)校園)/ (1) 對圖初始化mgraph initgraph()int i=0,j=0;mgraph c;c.vexnum =2

4、8; /頂點個數(shù)c.arcnum =39; /邊的個數(shù)for(i=0;ic.vexnum ;i+) /依次設(shè)置頂點編號c.vexsi.position =i;/依次輸入頂點信息strcpy( ,正門: );strcpy(roduction ,學(xué)校大門，離公交站很近|rn);strcpy( ,學(xué)校后門門: );strcpy(roduction ,去往新區(qū)、學(xué)校班車進出口); strcpy( ,人文學(xué)院: );strcpy(roduction ,人文學(xué)院辦公樓的

5、住處，樓高3層); strcpy( ,管理學(xué)院: );strcpy(roduction ,MBA培訓(xùn)中心，樓高7層); strcpy( ,行政樓: );strcpy(roduction ,行政辦公大樓，樓高5層);strcpy(,建設(shè)銀行: );strcpy(roduction ,學(xué)生取款處，樓高1層); strcpy( ,體育館: );strcpy(roduction ,室內(nèi)各類球類運動); strcpy(c.

6、,外語學(xué)院: );strcpy(roduction ,各種外語教學(xué)，樓高6層);strcpy( ,雙馨園食堂: );strcpy(roduction ,學(xué)生就餐地點);strcpy(, 博學(xué)樓: );strcpy(roduction , 計算機科學(xué)與技術(shù)學(xué)院大樓，樓高13層);strcpy( ,學(xué)生宿舍: );strcpy(roduction ,若干棟，離中山園食堂近);strcpy(

7、,中山園食堂: );strcpy(roduction ,學(xué)生就餐處);strcpy( ,圖書館: );strcpy(roduction ,歷史悠久，文化氣氛好);strcpy( ,法學(xué)樓: );strcpy(roduction ,研修法學(xué)佳地);strcpy( ,貴大學(xué)生超市: );strcpy(roduction ,買各種日用品的地方);strcpy( ,大禮堂: );strcpy(c.vexs

8、15.introduction ,文藝演出所在地);strcpy( ,慎思樓（新圖書館）: );strcpy(roduction ,自習(xí)的好地方);strcpy( ,逸夫樓: );strcpy(roduction ,經(jīng)濟學(xué)院辦公樓);strcpy( ,文化書院: );strcpy(roduction ,推動?xùn)|西方文化交流的重要橋梁);strcpy( ,派出所: );strcpy(roduction

9、 ,保衛(wèi)學(xué)校安全);strcpy( ,貴州大學(xué)出版社: );strcpy(roduction ,發(fā)行各種圖書);strcpy( ,貴州大學(xué)網(wǎng)球場: );strcpy(roduction ,打網(wǎng)球的地方); strcpy( ,化工學(xué)院: );strcpy(roduction ,各種實驗的研究之地); strcpy( ,貴州大學(xué)高等教育研究所: );strcpy(roduction ,關(guān)于高等教育的各

10、種研究);strcpy( ,花溪海洋學(xué)校: );strcpy(roduction ,貴大內(nèi)部學(xué)校);strcpy( ,貴州大學(xué)黨校: );strcpy(roduction ,黨員學(xué)習(xí)的地方);strcpy( ,校醫(yī)院: );strcpy(roduction ,看小病的地方);strcpy( ,體育場: );strcpy(roduction ,田徑遠動地點);/依次輸入邊上的權(quán)值信息 for(i=0

11、;ic.vexnum ;i+)for(j=0;jc.vexnum ;j+)c.arcs ij.adj =Infinity; /先初始化圖的鄰接矩陣 /部分弧長c.arcs02.adj=50; c.arcs03.adj=60; c.arcs14.adj=90; c.arcs23.adj=60; c.arcs28.adj=40; c.arcs34.adj=60; c.arcs36.adj=40; c.arcs45.adj=70; c.arcs49.adj=70; c.arcs410.adj=80; c.arcs417.adj=200;c.arcs57.adj=70; c.arcs69.adj=40

12、; c.arcs718.adj=190; c.arcs811.adj=50; c.arcs912.adj=40; c.arcs1018.adj=70; c.arcs1112.adj=60; c.arcs1114.adj=50; c.arcs1115.adj=50; c.arcs1216.adj=50; c.arcs1314.adj=40; c.arcs1322.adj=60; c.arcs1415.adj=50; c.arcs1420.adj=90; c.arcs1516.adj=60; c.arcs1521.adj=40; c.arcs1617.adj=60;c.arcs1718.adj=8

13、0; c.arcs1819.adj=60;c.arcs2021.adj=60; c.arcs2024.adj=80; c.arcs2223.adj=60; c.arcs2225.adj=80;c.arcs2324.adj=60; 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 ; FILE * pFile; pFil

14、e = fopen (myfile.txt,w); fwrite(,2,3,pFile); fwrite(roduction,2,11,pFile); fwrite(rn,2,1,pFile); fwrite(,2,6,pFile); fwrite(roduction,2,12,pFile); fwrite(rn,2,1,pFile); fwrite(,2,5,pFile); fwrite(roduction,2,15,pFile); fwrite(rn,2

15、,1,pFile); fwrite(,2,5,pFile); fwrite(roduction,2,10,pFile); fwrite(rn,2,1,pFile); fwrite(,2,4,pFile); fwrite(roduction,2,11,pFile); fwrite(rn,2,1,pFile); fwrite(,2,5,pFile); fwrite(roduction,2,10,pFile); fwrite(rn,2,1,pFile); fwri

16、te(,2,4,pFile); fwrite(roduction,2,8,pFile); fwrite(rn,2,1,pFile); fwrite(,2,5,pFile); fwrite(roduction,2,11,pFile); fwrite(rn,2,1,pFile); fwrite(,2,6,pFile); fwrite(roduction,2,6,pFile); fwrite(rn,2,1,pFile); fwrite(,2

17、,4,pFile); fwrite(roduction,2,17,pFile); fwrite(rn,2,1,pFile); fwrite(,2,5,pFile); fwrite(roduction,2,11,pFile); fwrite(rn,2,1,pFile); fwrite(,2,6,pFile); fwrite(roduction,2,5,pFile); fwrite(rn,2,1,pFile); fwrite(,2,4,pFile);

18、fwrite(roduction,2,10,pFile); fwrite(rn,2,1,pFile); fwrite(,2,4,pFile); fwrite(roduction,2,6,pFile); fwrite(rn,2,1,pFile); fwrite(,2,7,pFile); fwrite(roduction,2,9,pFile); fwrite(rn,2,1,pFile); fwrite(,2,4,pFile); fwrite(c.ve

19、roduction,2,7,pFile); fwrite(rn,2,1,pFile); fwrite(,2,10,pFile); fwrite(roduction,2,6,pFile); fwrite(rn,2,1,pFile); fwrite(,2,4,pFile); fwrite(roduction,2,7,pFile); fwrite(rn,2,1,pFile); fwrite(,2,5,pFile); fwrite(rod

20、uction,2,14,pFile); fwrite(rn,2,1,pFile); fwrite(,2,4,pFile); fwrite(roduction,2,6,pFile); fwrite(rn,2,1,pFile); fwrite(,2,8,pFile); fwrite(roduction,2,6,pFile); fwrite(rn,2,1,pFile); fwrite(,2,8,pFile); fwrite(roduction,2,6,

21、pFile); fwrite(rn,2,1,pFile); fwrite(,2,5,pFile); fwrite(roduction,2,9,pFile); fwrite(rn,2,1,pFile); fwrite(,2,12,pFile); fwrite(roduction,2,11,pFile); fwrite(rn,2,1,pFile); fwrite(,2,7,pFile); fwrite(roduction,2,6,pFile); fw

22、rite(rn,2,1,pFile); fwrite(,2,7,pFile); fwrite(roduction,2,7,pFile); fwrite(rn,2,1,pFile); fwrite(,2,4,pFile); fwrite(roduction,2,6,pFile); fwrite(rn,2,1,pFile); fwrite(,2,4,pFile); fwrite(roduction,2,6,pFile); fwrite(rn,2,1,

23、pFile); fclose (pFile); return c;/initgraph/ (2) 查找景點在圖中的序號int locatevex(mgraph c,int v)int i;for(i=0;ic.vexnum ;i+)if(v=c.vexsi.position)return i; /找到，返回頂點序號i return -1; /否則，返回-1/(3) 、(4) 求兩景點間的所有路徑/ (3) 打印序號為m,n景點間的長度不超過8個景點的路徑void path(mgraph c, int m,int n,int k) int s,x=0;int t=k+1; /t 記載路徑上下一個

24、中間頂點在d數(shù)組中的下標(biāo)if(dk=n & k8) /dk存儲路徑頂點。若dk是終點n且景點個數(shù)8，則輸出該路徑 /遞歸出口，找到一條路徑 for(s=0;s,); /輸出該路徑。s=0 時為起點m printf(%s,); /輸出最后一個景點名(即頂點n的名字，此時s=k) printf(nn); else s=0; while(sc.vexnum) /從第m個頂點，試探至所有頂點是 否有路徑 if(c.arcsdks.adjInfinity) & (visiteds=0) /初態(tài)：頂點m到頂點s有邊，且未被訪問 visiteds=1; d

25、k+1=s; /存儲頂點編號s 至dk+1中 path(c,m,n,t); /求從下標(biāo)為t=k+1的第dt個頂點開始的路徑(遞歸調(diào)用)，同時打印出一條m至n的路徑 visiteds=0; /將找到的路徑上頂點的訪問標(biāo)志重新設(shè)置為0，以用于試探新的路徑s+; /試探從下一個頂點 s 開始是否有到終點的路徑 /endwhile /endelse/endpath/(4) 打印兩景點間的景點個數(shù)不超過8的所有路徑。調(diào)用(3)int allpath(mgraph c) int k,i,j,m,n; printf(nn請輸入你要查詢的兩個景點編號:nn); scanf(%d%d,&i,&j); print

26、f(nn); m=locatevex(c,i); /調(diào)用(2)，確定該頂點是否存在。若存在，返回該頂點編號 n=locatevex(c,j); d0=m; /存儲路徑起點m (int d數(shù)組是全局變量) for(k=0;kc.vexnum;k+) /全部頂點訪問標(biāo)志初值設(shè)為0 visitedk=0; visitedm=1; /第m個頂點訪問標(biāo)志設(shè)置為1 path(c,m,n,0); /調(diào)用(3)。k=0，對應(yīng)起點d0=m。k為d數(shù)組下標(biāo) return 1;/ (5) 用迪杰斯特拉算法，求出一個景點到其他景點間的最短路徑，并打印void shortestpath_dij(mgraph c) /迪

27、杰斯特拉算法，求從頂點v0到其余頂點的最短路經(jīng)及其帶權(quán)長度dv /若pvw為1，則w是從v0到v的最短路經(jīng)上的頂點 /finalv類型用于設(shè)置訪問標(biāo)志int v,w,i,min,t=0,x,flag=1,v0; /vo為起始景點的編號int final35,d35,p3535;printf(n請輸入一個起始景點的編號：);scanf(%d,&v0); printf(nn);while(v0c.vexnum) printf(n你所輸入的景點編號不存在n); printf(請重新輸入：); scanf(%d,&v0);/whilefor(v=0;vc.vexnum ;v+)finalv=0; /初

28、始化各頂點訪問標(biāo)志dv=c.arcsv0v.adj; /v0 到各頂點 v 的權(quán)值賦值給dvfor(w=0;wc.vexnum ;w+) /初始化p數(shù)組，各頂點間的路徑全部設(shè)置為空路徑0pvw=0;if(dvInfinity) /v0 到v 有邊相連，修改pvv0的值為1pvv0=1;pvv=1; /各頂點自己到自己要連通/fordv0=0; /自己到自己的權(quán)值設(shè)為0finalv0=1; /v0的訪問標(biāo)志設(shè)為1，v 屬于 s 集for(i=1;ic.vexnum ;i+) /對其余c.vexnum-1個頂點w，依次求 v 到 w 的最短路徑min=Infinity;for(w=0;wc.vex

29、num ;w+) /在未被訪問的頂點中，查找與 v0 最近的頂點vif(!finalw)if(dwmin) /v0 到 w (有邊)的權(quán)值minv=w;min=dw;/iffinalv=1; /v 的訪問標(biāo)志設(shè)置為1，v 屬于s集for(w=0;wc.vexnum ;w+) /修改v0 到其余各頂點w 的最短路徑權(quán)值dwif(!finalw&(min+c.arcsvw.adj dw) /若w 不屬于s，且v 到w 有邊相連dw=min+c.arcsvw.adj; /修改v0 到w 的權(quán)值dwfor(x=0;xc.vexnum ;x+) /所有v0 到v 的最短路徑上的頂點x，都是v0 到w 的

30、最短路徑上的頂點pwx=pvx;pww=1;/if/forfor(v=0;vc.vexnum ;v+) /輸出v0 到其它頂點v 的最短路徑if(v!=v0) printf(%s,); /輸出景點v0 的景點名for(w=0;w%s,); printf(-%s,); printf(n總路線長為%d米nn,dv);/for/shortestpath/(6)-(11)修改圖的信息。包括建圖、更新信息、刪除、增加結(jié)點和邊 /(6) 構(gòu)造圖的鄰接矩陣 int creatgragh(mgraph &c) /建圖。以圖的鄰接矩陣存儲

31、圖 int i,j,m,n;int v0,v1;int distance;printf(請輸入圖的頂點數(shù)和邊數(shù): n);scanf(%d %d,&c.vexnum ,&c.arcnum );printf(下面請輸入景點的信息：n);for(i=0;ic.vexnum ;i+) /構(gòu)造頂點向量(數(shù)組)printf(請輸入景點的編號：);scanf(%d,c.vexsi.position );printf(n請輸入景點的名稱：); scanf(%s, );printf(n請輸入景點的簡介：);scanf(%s,roduction );for(i=0;i

32、c.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; /計數(shù)。用于記錄要修改的對象的個數(shù)int i,m,n,t,distance,v0,v1;printf(n下面請輸入你要修改的

33、景點的個數(shù)：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, );printf(n請輸入景點的簡介：);scanf(%s,roduction );printf(n下面請輸入你要更新的邊數(shù));scanf(%d,&change

34、num);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,distance;printf(n請輸入邊的起點和終點編號,權(quán)值：); scanf(%d %d %d,&m,&n,&distance);while(mc

35、.vexnum |nc.vexnum )printf(輸入錯誤，請重新輸入：);scanf(%d %d,&m,&n);if(locatevex(c,m)0)printf(此結(jié)點%d已刪除,m);return 1;if(locatevex(c,n)0)printf(此結(jié)點%d已被刪除：,n);return 1;c.arcsmn.adj =distance; c.arcsnm.adj =c.arcsmn.adj; /對稱賦值return 1;/enarc/ (9) 增加一個結(jié)點。返回值：1int envex(mgraph&c)int i;printf(請輸入你要增加結(jié)點的信息：);printf(n

36、編號：);scanf(%d,&c.vexsc.vexnum .position );printf(名稱：);scanf(%s,c.vexsc.vexnum .name );printf(簡介：);scanf(%s,c.vexsc.vexnum .introduction) ;c.vexnum +;for(i=0;ic.vexnum;i+) /對原鄰接矩陣新增加的一行及一列進行初始化c.arcs c.vexnum -1i.adj=Infinity; /最后一行(新增的一行)c.arcs ic.vexnum -1.adj=Infinity; /最后一列(新增的一列)return 1;/envex

37、/ (10) 刪除圖的一個頂點。返回值：1int delvex(mgraph&c)int i=0,j;int m;int v;if(c.vexnum =0)printf(圖中已無頂點);return 1;printf(n下面請輸入你要刪除的景點編號：);scanf(%d,&v);while(vc.vexnum )printf(n輸入錯誤！請重新輸入);scanf(%d,&v);m=locatevex(c,v);if(m0)printf(此頂點 %d 已刪除,v);return 1;for(i=m;ic.vexnum-1 ;i+)/對頂點信息所在順序表進行刪除m 點的操作strcpy(c.vex

38、 ,c.vexs i+1.name );strcpy(roduction ,c.vexs i+1.introduction );/對原鄰接矩陣，刪除該頂點到其余頂點的鄰接關(guān)系。分別刪除相應(yīng)的行和列for(i=m;ic.vexnum-1 ;i+) /行for(j=0;jc.vexnum ;j+) /列c.arcs ij=c.arcs i+1j; /二維數(shù)組，從第m+1行開始依次往前移一行。即刪除第m 行for(i=m;ic.vexnum-1 ;i+)for(j=0;jc.vexnum ;j+) c.arcs ji=c.arcs ji+1; /二維數(shù)組，從第m+

39、1列開始依次往前移一列。即刪除第m 列c.vexnum -;return 1;/delvex /(11) 刪除圖的一條邊。返回值：1 int delarc(mgraph&c)int m,n;int v0,v1;if(c.arcnum =0)printf(圖中已無邊，無法刪除。);return 1;printf(n下面請輸入你要刪除的邊的起點和終點編號：);scanf(%d %d,&v0,&v1); m=locatevex(c,v0);if(m0)printf(此 %d 頂點已刪除,v0);return 1;n=locatevex(c,v1);if(n0)printf(此 %d 頂點已刪除,v1);return 1;c.arcs mn.adj =Infinity; /修改鄰接矩陣對應(yīng)的權(quán)值 c.arcs nm.adj =Infinity;c.arcnum -;return 1;/delarc/ (12) 輸出圖的鄰接矩陣的值void printmatrix(mgraph c)int i,j,k=0; /k 用于計數(shù)，控制換行for(i=0;ic.vexnum ;i+)for(j=0;jc.vexnum ;j+)if(c.arcsij.adj =Infinity)printf(-);elseprintf(%4d,c.arcsij.ad