校园导游系统程序.docx

《校园导游系统程序.docx》由会员分享，可在线阅读，更多相关《校园导游系统程序.docx（20页珍藏版）》请在三一办公上搜索。

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

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

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

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

5、; strcpy(c.vexs2.introduction ,人文学院办公楼的住处，楼高3层); strcpy(c.vexs3.name ,管理学院: ); strcpy(c.vexs3.introduction ,MBA培训中心，楼高7层); strcpy(c.vexs4.name ,行政楼: ); strcpy(c.vexs4.introduction ,行政办公大楼，楼高5层); strcpy(c.vexs5.name,建设银行: ); strcpy(c.vexs5.introduction ,学生取款处，楼高1层); strcpy(c.vexs6.name ,体育馆: ); strcp

6、y(c.vexs6.introduction ,室内各类球类运动); strcpy(c.vexs7.name,外语学院: ); strcpy(c.vexs7.introduction ,各种外语教学，楼高6层); strcpy(c.vexs8.name ,双馨园食堂: ); strcpy(c.vexs8.introduction ,学生就餐地点); strcpy(c.vexs9.name, 博学楼: ); strcpy(c.vexs9.introduction , 计算机科学与技术学院大楼，楼高13层); strcpy(c.vexs10.name ,学生宿舍: ); strcpy(c.vexs

7、10.introduction ,若干栋，离中山园食堂近); strcpy(c.vexs11.name ,中山园食堂: ); strcpy(c.vexs11.introduction ,学生就餐处); strcpy(c.vexs12.name ,图书馆: ); strcpy(c.vexs12.introduction ,历史悠久，文化气氛好); strcpy(c.vexs13.name ,法学楼: ); strcpy(c.vexs13.introduction ,研修法学佳地); strcpy(c.vexs14.name ,贵大学生超市: ); strcpy(c.vexs14.introduc

8、tion ,买各种日用品的地方); strcpy(c.vexs15.name ,大礼堂: ); strcpy(c.vexs15.introduction ,文艺演出所在地); strcpy(c.vexs16.name ,慎思楼: ); strcpy(c.vexs16.introduction ,自习的好地方); strcpy(c.vexs17.name ,逸夫楼: ); strcpy(c.vexs17.introduction ,经济学院办公楼); strcpy(c.vexs18.name ,文化书院: ); strcpy(c.vexs18.introduction ,推动东西方文化交流的重要

9、桥梁); strcpy(c.vexs19.name ,派出所: ); strcpy(c.vexs19.introduction ,保卫学校安全); strcpy(c.vexs20.name ,贵州大学出版社: ); strcpy(c.vexs20.introduction ,发行各种图书); strcpy(c.vexs21.name ,贵州大学网球场: ); strcpy(c.vexs21.introduction ,打网球的地方); strcpy(c.vexs22.name ,化工学院: ); strcpy(c.vexs22.introduction ,各种实验的研究之地); strcpy(

10、c.vexs23.name ,贵州大学高等教育研究所: ); strcpy(c.vexs23.introduction ,关于高等教育的各种研究); strcpy(c.vexs24.name ,花溪海洋学校: ); strcpy(c.vexs24.introduction ,贵大内部学校); strcpy(c.vexs25.name ,贵州大学党校: ); strcpy(c.vexs25.introduction ,党员学习的地方); strcpy(c.vexs26.name ,校医院: ); strcpy(c.vexs26.introduction ,看小病的地方); strcpy(c.ve

11、xs27.name ,体育场: ); strcpy(c.vexs27.introduction ,田径远动地点); /依次输入边上的权值信息 for(i=0;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.arcs45.adj=70; c.arcs417.adj=200; c.

12、arcs57.adj=70; c.arcs69.adj=40; c.arcs718.adj=190; c.arcs811.adj=50; c.arcs912.adj=40; c.arcs1018.adj=70; c.arcs1112.adj=60; c.arcs1216.adj=50; c.arcs1314.adj=40; c.arcs1415.adj=50; c.arcs1516.adj=60; c.arcs1617.adj=60; c.arcs1718.adj=80; c.arcs1819.adj=60; c.arcs2021.adj=60; c.arcs36.adj=40; c.arcs

13、49.adj=70; c.arcs410.adj=80; c.arcs1114.adj=50; c.arcs1115.adj=50; c.arcs1322.adj=60; c.arcs1420.adj=90; c.arcs1521.adj=40; 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+)

14、 for(j=0;jc.vexnum ;j+) c.arcsji.adj =c.arcsij.adj ; FILE * pFile; pFile = fopen (myfile.txt,w); fwrite(c.vexs0.name,2,3,pFile); fwrite(c.vexs0.introduction,2,11,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs1.name,2,6,pFile); fwrite(c.vexs1.introduction,2,12,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs

15、2.name,2,5,pFile); fwrite(c.vexs2.introduction,2,15,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs3.name,2,5,pFile); fwrite(c.vexs3.introduction,2,10,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs4.name,2,4,pFile); fwrite(c.vexs4.introduction,2,11,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs5.name,2,5,pFil

16、e); fwrite(c.vexs5.introduction,2,10,pFile); fwrite(rn,2,1,pFile); /邻接矩阵是对称矩阵，对称赋值 fwrite(c.vexs6.name,2,4,pFile); fwrite(c.vexs6.introduction,2,8,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs7.name,2,5,pFile); fwrite(c.vexs7.introduction,2,11,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs8.name,2,6,pFil

17、e); fwrite(c.vexs8.introduction,2,6,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs9.name,2,4,pFile); fwrite(c.vexs9.introduction,2,17,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs10.name,2,5,pFile); fwrite(c.vexs10.introduction,2,11,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs11.name,2,6,pFile); fwrite(c.

18、vexs11.introduction,2,5,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs12.name,2,4,pFile); fwrite(c.vexs12.introduction,2,10,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs13.name,2,4,pFile); fwrite(c.vexs13.introduction,2,6,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs14.name,2,7,pFile); fwrite(c.vexs14.intr

19、oduction,2,9,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs15.name,2,4,pFile); fwrite(c.vexs15.introduction,2,7,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs16.name,2,10,pFile); fwrite(c.vexs16.introduction,2,6,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs17.name,2,4,pFile); fwrite(c.vexs17.introduction,2,

20、7,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs18.name,2,5,pFile); fwrite(c.vexs18.introduction,2,14,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs19.name,2,4,pFile); fwrite(c.vexs19.introduction,2,6,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs20.name,2,8,pFile); fwrite(c.vexs20.introduction,2,6,pFile); f

21、write(rn,2,1,pFile); fwrite(c.vexs21.name,2,8,pFile); fwrite(c.vexs21.introduction,2,6,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs22.name,2,5,pFile); fwrite(c.vexs22.introduction,2,9,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs23.name,2,12,pFile); fwrite(c.vexs23.introduction,2,11,pFile); fwrite(rn,2

22、,1,pFile); fwrite(c.vexs24.name,2,7,pFile); fwrite(c.vexs24.introduction,2,6,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs25.name,2,7,pFile); fwrite(c.vexs25.introduction,2,7,pFile); fwrite(rn,2,1,pFile); fwrite(c.vexs26.name,2,4,pFile); fwrite(c.vexs26.introduction,2,6,pFile); fwrite(rn,2,1,pFile); f

23、write(c.vexs27.name,2,4,pFile); fwrite(c.vexs27.introduction,2,6,pFile); fwrite(rn,2,1,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; return -1; /找到，返回顶点序号i /否则，返回-1 /(3) 、(4) 求两景点间的所有路径 / (3)

24、 打印序号为m,n景点间的长度不超过8个景点的路径 void path(mgraph c, int m,int n,int k) int s,x=0; int t=k+1; /t 记载路径上下一个中间顶点在d数组中的下标 if(dk=n & k8) /dk存储路径顶点。若dk是终点n且景点个数8，则输出该路径 /递归出口，找到一条路径 for(s=0;s,c.vexsds.name); /输出该路径。s=0 时为起点m printf(%s,c.vexsds.name); /输出最后一个景点名(即顶点n的名字，此时s=k) printf(nn); else s=0; while(sc.vexnu

25、m) /从第m个顶点，试探至所有顶点是 否有路径 if(c.arcsdks.adjInfinity) & (visiteds=0) /初态：顶点m到顶点s有边，且未被访问 visiteds=1; dk+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) 打印两景点间的景点个数不超过

26、8的所有路径。调用(3) int allpath(mgraph c) int k,i,j,m,n; printf(nn请输入你要查询的两个景点编号:nn); scanf(%d%d,&i,&j); printf(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); /调用(

27、3)。k=0，对应起点d0=m。k为d数组下标 return 1; / (5) 用迪杰斯特拉算法，求出一个景点到其他景点间的最短路径，并打印 void shortestpath_dij(mgraph c) /迪杰斯特拉算法，求从顶点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); wh

28、ile(v0c.vexnum) printf(n你所输入的景点编号不存在n); printf(请重新输入：); scanf(%d,&v0); /while for(v=0;vc.vexnum ;v+) finalv=0; /初始化各顶点访问标志 dv=c.arcsv0v.adj; /v0 到各顶点 v 的权值赋值给dv for(w=0;wc.vexnum ;w+) /初始化p数组，各顶点间的路径全部设置为空路径0 pvw=0; if(dvInfinity) /v0 到v 有边相连，修改pvv0的值为1 pvv0=1; pvv=1; /各顶点自己到自己要连通 /for dv0=0; /自己到自己

29、的权值设为0 finalv0=1; /v0的访问标志设为1，v 属于 s 集 for(i=1;ic.vexnum ;i+) /对其余c.vexnum-1个顶点w，依次求 v 到 w 的最短路径 min=Infinity; for(w=0;wc.vexnum ;w+) /在未被访问的顶点中，查找与 v0 最近的顶点v if(!finalw) if(dwmin) /v0 到 w (有边)的权值min v=w; min=dw; /if finalv=1; /v 的访问标志设置为1，v 属于s集 for(w=0;wc.vexnum ;w+) /修改v0 到其余各顶点w 的最短路径权值dw if(!fi

30、nalw&(min+c.arcsvw.adj dw) /若w 不属于s，且v 到w 有边相连 dw=min+c.arcsvw.adj; /修改v0 到w 的权值dw for(x=0;xc.vexnum ;x+) /所有v0 到v 的最短路径上的顶点x，都是v0 到w 的最短路径上的顶点 pwx=pvx; pww=1; /if /for for(v=0;vc.vexnum ;v+) /输出v0 到其它顶点v 的最短路径 if(v!=v0) printf(%s,c.vexsv0.name); /输出景点v0 的景点名 for(w=0;w%s,c.vexsw.name); printf(-%s,c.

31、vexsv.name); printf(n总路线长为%d米nn,dv); /for /shortestpath /(6)-(11)修改图的信息。包括建图、更新信息、删除、增加结点和边 /(6) 构造图的邻接矩阵 int creatgragh(mgraph &c) /建图。以图的邻接矩阵存储图 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+) /构造顶点向量(数组

32、) printf(请输入景点的编号：); scanf(%d,c.vexsi.position ); printf(n请输入景点的名称：); scanf(%s,c.vexsi.name ); 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.arcsn

33、m.adj =c.arcsmn.adj ; return 1; /creatgragh / (7) 更新图的部分信息。返回值: 1 int newgraph(mgraph &c) int changenum; /计数。用于记录要修改的对象的个数 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(

34、n请输入景点的编号：); scanf(%d,&m); t=locatevex(c,m); printf(n请输入景点的名称：); scanf(%s,c.vexst.name ); printf(n请输入景点的简介：); scanf(%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) 增加一条边。返回值：1 int enarc(mgraph&c) int m,n,dis