校园导游系统程序

1、课题五：校园导游程序 1)问题描述用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。2)基本要求（1） 查询各景点的相关信息；（2） 查询图中任意两个景点间的最短路径。（3） 能够将图的信息保存到文件中，并指定文件打开。（4） 增加、删除、更新有关景点和道路的信息。附加难度：有余力的同学可以考虑用图形界面实现寻址的过程3) 设计思想核心数据结构定义一个图，将图保存后，对图进行面向指定节点到各个节点的最短路径的操作。可以再文件中保存多个导游图，例如保存学校图、芜湖

2、市图等文件。开始时选择文件，将指定文件中的信息导入到内存的图中。#define Infinity 1000#define MaxVertexNum 35#define MAX 40#include#include#include#include#include#includetypedef struct arcell /边的权值信息int adj; /权值arcell,adjmatrixMaxVertexNumMaxVertexNum; /图的邻接矩阵类型typedef struct vexsinfo /顶点信息int position; /景点的编号char name32; /景点的名称ch

3、ar introduction256; /景点的介绍vexsinfo;typedef struct mgraph /图结构信息vexsinfo vexsMaxVertexNum; /顶点向量(数组)adjmatrix arcs; /邻接矩阵int vexnum,arcnum; /分别指定顶点数和边数mgraph;/全局变量int visited35; /用于标志是否已经访问过int d35; /用于存放权值或存储路径顶点编号mgraph campus; /图变量(大学校园)/ (1) 对图初始化mgraph initgraph()int i=0,j=0;mgraph c;c.vexnum =2

4、8; /顶点个数c.arcnum =39; /边的个数for(i=0;ic.vexnum ;i+) /依次设置顶点编号c.vexsi.position =i;/依次输入顶点信息strcpy( ,正门: );strcpy(roduction ,学校大门，离公交站很近|rn);strcpy( ,学校后门门: );strcpy(roduction ,去往新区、学校班车进出口); strcpy( ,人文学院: );strcpy(roduction ,人文学院办公楼的

5、住处，楼高3层); strcpy( ,管理学院: );strcpy(roduction ,MBA培训中心，楼高7层); strcpy( ,行政楼: );strcpy(roduction ,行政办公大楼，楼高5层);strcpy(,建设银行: );strcpy(roduction ,学生取款处，楼高1层); strcpy( ,体育馆: );strcpy(roduction ,室内各类球类运动); strcpy(c.

6、,外语学院: );strcpy(roduction ,各种外语教学，楼高6层);strcpy( ,双馨园食堂: );strcpy(roduction ,学生就餐地点);strcpy(, 博学楼: );strcpy(roduction , 计算机科学与技术学院大楼，楼高13层);strcpy( ,学生宿舍: );strcpy(roduction ,若干栋，离中山园食堂近);strcpy(

7、,中山园食堂: );strcpy(roduction ,学生就餐处);strcpy( ,图书馆: );strcpy(roduction ,历史悠久，文化气氛好);strcpy( ,法学楼: );strcpy(roduction ,研修法学佳地);strcpy( ,贵大学生超市: );strcpy(roduction ,买各种日用品的地方);strcpy( ,大礼堂: );strcpy(c.vexs

8、15.introduction ,文艺演出所在地);strcpy( ,慎思楼（新图书馆）: );strcpy(roduction ,自习的好地方);strcpy( ,逸夫楼: );strcpy(roduction ,经济学院办公楼);strcpy( ,文化书院: );strcpy(roduction ,推动东西方文化交流的重要桥梁);strcpy( ,派出所: );strcpy(roduction

9、 ,保卫学校安全);strcpy( ,贵州大学出版社: );strcpy(roduction ,发行各种图书);strcpy( ,贵州大学网球场: );strcpy(roduction ,打网球的地方); strcpy( ,化工学院: );strcpy(roduction ,各种实验的研究之地); strcpy( ,贵州大学高等教育研究所: );strcpy(roduction ,关于高等教育的各

10、种研究);strcpy( ,花溪海洋学校: );strcpy(roduction ,贵大内部学校);strcpy( ,贵州大学党校: );strcpy(roduction ,党员学习的地方);strcpy( ,校医院: );strcpy(roduction ,看小病的地方);strcpy( ,体育场: );strcpy(roduction ,田径远动地点);/依次输入边上的权值信息 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数组中的下标if(dk=n & k8) /dk存储路径顶点。若dk是终点n且景点个数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) /初态：顶点m到顶点s有边，且未被访问 visiteds=1; d

25、k+1=s; /存储顶点编号s 至dk+1中 path(c,m,n,t); /求从下标为t=k+1的第dt个顶点开始的路径(递归调用)，同时打印出一条m至n的路径 visiteds=0; /将找到的路径上顶点的访问标志重新设置为0，以用于试探新的路径s+; /试探从下一个顶点 s 开始是否有到终点的路径 /endwhile /endelse/endpath/(4) 打印两景点间的景点个数不超过8的所有路径。调用(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); /调用(2)，确定该顶点是否存在。若存在，返回该顶点编号 n=locatevex(c,j); d0=m; /存储路径起点m (int d数组是全局变量) for(k=0;kc.vexnum;k+) /全部顶点访问标志初值设为0 visitedk=0; visitedm=1; /第m个顶点访问标志设置为1 path(c,m,n,0); /调用(3)。k=0，对应起点d0=m。k为d数组下标 return 1;/ (5) 用迪杰斯特拉算法，求出一个景点到其他景点间的最短路径，并打印void shortestpath_dij(mgraph c) /迪

27、杰斯特拉算法，求从顶点v0到其余顶点的最短路经及其带权长度dv /若pvw为1，则w是从v0到v的最短路经上的顶点 /finalv类型用于设置访问标志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、始化各顶点访问标志dv=c.arcsv0v.adj; /v0 到各顶点 v 的权值赋值给dvfor(w=0;wc.vexnum ;w+) /初始化p数组，各顶点间的路径全部设置为空路径0pvw=0;if(dvInfinity) /v0 到v 有边相连，修改pvv0的值为1pvv0=1;pvv=1; /各顶点自己到自己要连通/fordv0=0; /自己到自己的权值设为0finalv0=1; /v0的访问标志设为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 (有边)的权值minv=w;min=dw;/iffinalv=1; /v 的访问标志设置为1，v 属于s集for(w=0;wc.vexnum ;w+) /修改v0 到其余各顶点w 的最短路径权值dwif(!finalw&(min+c.arcsvw.adj dw) /若w 不属于s，且v 到w 有边相连dw=min+c.arcsvw.adj; /修改v0 到w 的权值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)修改图的信息。包括建图、更新信息、删除、增加结点和边 /(6) 构造图的邻接矩阵 int creatgragh(mgraph &c) /建图。以图的邻接矩阵存储

31、图 int i,j,m,n;int v0,v1;int 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, );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; /计数。用于记录要修改的对象的个数int i,m,n,t,distance,v0,v1;printf(n下面请输入你要修改的

33、景点的个数：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下面请输入你要更新的边数);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请输入边的起点和终点编号,权值：); 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(此结点%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&c)int i;printf(请输入你要增加结点的信息：);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 );/对原邻接矩阵，删除该顶点到其余顶点的邻接关系。分别删除相应的行和列for(i=m;ic.vexnum-1 ;i+) /行for(j=0;jc.vexnum ;j+) /列c.arcs ij=c.arcs i+1j; /二维数组，从第m+1行开始依次往前移一行。即删除第m 行for(i=m;ic.vexnum-1 ;i+)for(j=0;jc.vexnum ;j+) c.arcs ji=c.arcs ji+1; /二维数组，从第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; /修改邻接矩阵对应的权值 c.arcs nm.adj =Infinity;c.arcnum -;return 1;/delarc/ (12) 输出图的邻接矩阵的值void printmatrix(mgraph c)int i,j,k=0; /k 用于计数，控制换行for(i=0;ic.vexnum ;i+)for(j=0;jc.vexnum ;j+)if(c.arcsij.adj =Infinity)printf(-);elseprintf(%4d,c.arcsij.ad