校园导游系统程序.docx

校园导游系统程序课题五：校园导游程序 1)问题描述 用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。 2)基本要求 查询各景点的相关信息； 查询图中任意两个景点间的最短路径。 能够将图的信息保存到文件中，并指定文件打开。 增加、删除、更新有关景点和道路的信息。 附加难度：有余力的同学可以考虑用图形界面实现寻址的过程 3) 设计思想 核心数据结构定义一个图，将图保存后，对图进行面向指定节点到各个节点的最短路径的操作。可以再文件中保存多个导游图，例如保存学校图、芜湖市图等文件。开始时选择文件，将指定文件中的信息导入到内存的图中。 #define Infinity 1000 #define MaxVertexNum 35 #define MAX 40 #include<fstream> #include<stdio.h> #include<stdlib.h> #include<conio.h> #include<string.h> #include<iostream.h> typedef struct arcell /边的权值信息 int adj; /权值 arcell,adjmatrixMaxVertexNumMaxVertexNum; /图的邻接矩阵类型 typedef struct vexsinfo /顶点信息 int position; /景点的编号 char 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 i=0,j=0; mgraph c; c.vexnum =28; /顶点个数 c.arcnum =39; /边的个数 for(i=0;i<c.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 ,"人文学院: "); 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 ,"体育馆: "); strcpy(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.vexs10.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.introduction ,"买各种日用品的地方"); 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 ,"推动东西方文化交流的重要桥梁"); 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(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.vexs27.name ,"体育场: "); strcpy(c.vexs27.introduction ,"田径远动地点"); /依次输入边上的权值信息 for(i=0;i<c.vexnum ;i+) for(j=0;j<c.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.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.arcs49.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;i<c.vexnum ;i+) for(j=0;j<c.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.vexs2.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,pFile); 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,pFile); 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.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.introduction,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,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); fwrite("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,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); fwrite(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;i<c.vexnum ;i+) if(v=c.vexsi.position) return i; return -1; /找到，返回顶点序号i /否则，返回-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 记载路径上下一个中间顶点在d数组中的下标 if(dk=n && k<8) /dk存储路径顶点。若dk是终点n且景点个数<8，则输出该路径 /递归出口，找到一条路径 for(s=0;s<k;s+) printf("%s->",c.vexsds.name); /输出该路径。s=0 时为起点m printf("%s",c.vexsds.name); /输出最后一个景点名(即顶点n的名字，此时s=k) printf("nn"); else s=0; while(s<c.vexnum) /从第m个顶点，试探至所有顶点是 否有路径 if(c.arcsdks.adj<Infinity) && (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) 打印两景点间的景点个数不超过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;k<c.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) /迪杰斯特拉算法，求从顶点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(v0<0|v0>c.vexnum) printf("n你所输入的景点编号不存在n"); printf("请重新输入："); scanf("%d",&v0); /while for(v=0;v<c.vexnum ;v+) finalv=0; /初始化各顶点访问标志 dv=c.arcsv0v.adj; /v0 到各顶点 v 的权值赋值给dv for(w=0;w<c.vexnum ;w+) /初始化p数组，各顶点间的路径全部设置为空路径0 pvw=0; if(dv<Infinity) /v0 到v 有边相连，修改pvv0的值为1 pvv0=1; pvv=1; /各顶点自己到自己要连通 /for dv0=0; /自己到自己的权值设为0 finalv0=1; /v0的访问标志设为1，v 属于 s 集 for(i=1;i<c.vexnum ;i+) /对其余c.vexnum-1个顶点w，依次求 v 到 w 的最短路径 min=Infinity; for(w=0;w<c.vexnum ;w+) /在未被访问的顶点中，查找与 v0 最近的顶点v if(!finalw) if(dw<min) /v0 到 w (有边)的权值<min v=w; min=dw; /if finalv=1; /v 的访问标志设置为1，v 属于s集 for(w=0;w<c.vexnum ;w+) /修改v0 到其余各顶点w 的最短路径权值dw if(!finalw&&(min+c.arcsvw.adj <dw) /若w 不属于s，且v 到w 有边相连 dw=min+c.arcsvw.adj; /修改v0 到w 的权值dw for(x=0;x<c.vexnum ;x+) /所有v0 到v 的最短路径上的顶点x，都是v0 到w 的最短路径上的顶点 pwx=pvx; pww=1; /if /for for(v=0;v<c.vexnum ;v+) /输出v0 到其它顶点v 的最短路径 if(v!=v0) printf("%s",c.vexsv0.name); /输出景点v0 的景点名 for(w=0;w<c.vexnum ;w+) /对图中每个顶点w，试探w 是否是v0 到v 的最短路径上的顶点 if(pvw && w!=v0 && w!=v) /若w 是且w 不等于v0，则输出该景点 printf("->%s",c.vexsw.name); printf("->%s",c.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;i<c.vexnum ;i+) /构造顶点向量(数组) printf("请输入景点的编号："); scanf("%d",c.vexsi.position ); printf("n请输入景点的名称："); scanf("%s",c.vexsi.name ); printf("n请输入景点的简介："); scanf("%s",c.vexsi.introduction ); for(i=0;i<c.arcnum ;i+) /初始化邻接矩阵 for(j=0;j<c.arcnum ;j+) c.arcsij.adj =Infinity; printf("下面请输入图的边的信息：n"); for(i=1;i<=c.arcnum ;i+) /构造邻接矩阵 printf("n第%d条边的起点 终点 长度为：",i);/输入一条边的起点、终点及权值 scanf("%d %d %d",&v0,&v1,&distance); m=locatevex(c,v0); n=locatevex(c,v1); if(m>=0 && n>=0) c.arcsmn.adj =distance; c.arcsnm.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(changenum<0|changenum>c.vexnum ) printf("n输入错误！请重新输入"); scanf("%d",&changenum); for(i=0;i<changenum;i+) printf("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(changenum<0|changenum>c.arcnum ) printf("n输入错误！请重新输入"); scanf("%d",&changenum); printf("n下面请输入更新边的信息：n"); for(i=1;i<=changenum ;i+) printf("n修改的第%d条边的起点 终点 长度为：",i); scanf("%d %d %d",&v0,&v1,&distance); m=locatevex(c,v0); n=locatevex(c,v1); if(m>=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