1.问题描述
课程设计 5.5 校园导游系统
设计一个校园导游程序,为来访的客人提供信息查询服务。
2.需求分析
(1)设计学校的校园平面图。选取若干个有代表性的景点抽象成一个无向带权图(无向网),以图中顶点表示校内各景点,边上的权值表示两景点之间的距离。
(2)存放景点代号、名称、简介等信息供用户查询。
(3)为来访客人提供图中任意景点相关信息的查询。
(4)为来访客人提供图中任意景点之间的问路查询。
(5)可以为校园平面图增加或删除景点或边,修改边上的权值等。
为了实现以上功能,可以从3个方面着手设计。
1.主界面设计
为了实现校园导游系统各功能的管理,首先设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能,方便用户使用本系统。本系统主控菜单运行界面如图7-10所示。
2.存储结构设计
本系统采用图结构类型(mgraph)存储抽象校园图的信息。其中:各景点间的邻接关系用图的邻接矩阵类型(adjmatrix)存储;景点(顶点)信息用结构数组(vexs)存储,其中每个数组元素是一个结构变量,包含景点编号、景点名称及景点介绍三个分量;图的顶点个数及边的个数由分量vexnum、arcnum表示,它们是整型数据。
此外,本系统还设置了三个全局变量:visited[ ] 数组用于存储顶点是否被访问标志;d[ ]数组用于存放边上的权值或存储查找路径顶点的编号;campus是一个图结构的全局变量。
3.系统功能设计
本系统除了要完成图的初始化功能外还设置了8个子功能菜单。图的初始化由函数initgraph( )实现。依据读入的图的顶点个数和边的个数,分别初始化图结构中图的顶点向量数组和图的邻接矩阵。8个子功能的设计描述如下。
(1)学校景点介绍
学校景点介绍由函数browsecompus( )实现。当用户选择该功能,系统即能输出学校全部景点的信息:包括景点编号、景点名称及景点简介。
(2)查看浏览路线
查看浏览路线由函数shortestpath_dij( )实现。该功能采用迪杰斯特拉(Dijkstra)算法实现。当用户选择该功能,系统能根据用户输入的起始景点编号,求出从该景点到其它景点的最短路径线路及距离。
(3)查看两景点间最短路径
查看两景点间最短路径由函数shortestpath_floyd( )实现。该功能采用弗洛伊德(Floyd)算法实现。当用户选择该功能,系统能根据用户输入的起始景点及目的地景点编号,查询任意两个景点之间的最短路径线路及距离。
(4)景点信息查询
景点信息查询由函数seeabout( )实现。该功能根据用户输入的景点编号输出该景点的相关信息。例如,景点编号、名称等。
(5)更改图的信息
更改图的信息功能由主调函数changegraph( )及若干个子函数完成,可以实现图的若干基本操作。例如:增加新的景点、删除边、重建图等。
(6)查询景点间可行路径
该功能是查询两景点间所有可行路径,由函数allpath( )和函数path( )实现,其中path( )函数是直接递归函数。由于是无向网,如果网中的边数很多,任意两个景点间的所有路径也会有限多,但很多路径是无实际意义的(有近路,为什么去走远路呢?)。所以,本算法在求得的两景点间所有可行路径中,限制只输出路径长度不超过8个景点的路线。
(7)打印邻接矩阵
该功能即输出图的邻接矩阵的值,由函数printmatrix( )实现。
(8)退出
即退出校园导游系统,由exit(0)函数实现。
Mygraph.h
#define Infinite 214748367
#include<queue>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cstring>
#define rg register ll
#define inf 2147483647
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define maxn 100005
#define lb(x) (x&(-x))
const double eps = 1e-6;
using namespace std;
typedef struct //定义用于存放权值的结构体
{
int path; //路径长度
}ArCell,AdjMatrix[MaxInfoNum][MaxInfoNum];
typedef struct
{
char siteName[30]; // 用于存放景点名称
int siteIdentifier; //用于存放景点编号
char siteInfo[200]; //用于存放景点信息
}infoType;
typedef struct
{
infoType siteArray[MaxInfoNum]; // 景点数组 ,用于存放景点名及景点信息
AdjMatrix pathArray; // 路径数组
int siteNumber; // 景点数量
int pathNumber; // 路径总数量
}MGraph;
struct edge
{
ll v,w,next;
}e[(200000<<1)+5];
MGraph G;
MGraph InitGraph(void) //初始化图中的信息
{
int i,j;
G.siteNumber = 10; //景点数量
G.pathNumber = 16; //路 径 数量
for(i=1;i<=G.siteNumber;i++)
G.siteArray[i].siteIdentifier = i; //对景点进行对应编号
strcpy(G.siteArray[1].siteName,"海韵园");
strcpy(G.siteArray[1].siteInfo,"135、20路公交可直达");
strcpy(G.siteArray[2].siteName,"厦大西村");
strcpy(G.siteArray[2].siteInfo,"厦大西门,毗邻明培体育馆、囊萤楼、化学与化工学院院楼");
strcpy(G.siteArray[3].siteName,"思明校区图书馆");
strcpy(G.siteArray[3].siteInfo,"自习圣地");
strcpy(G.siteArray[4].siteName,"白城校门");
strcpy(G.siteArray[4].siteInfo,"靠近环岛路、毗邻外文学院、人文学院");
strcpy(G.siteArray[5].siteName,"芙蓉餐厅");
strcpy(G.siteArray[5].siteInfo,"毗邻芙蓉隧道、网红餐厅");
strcpy(G.siteArray[6].siteName,"上弦场");
strcpy(G.siteArray[6].siteInfo,"毗邻建南大会堂、嘉庚楼群,是中心地带");
strcpy(G.siteArray[7].siteName,"嘉庚铜像");
strcpy(G.siteArray[7].siteInfo,"毗邻演武场,位于西村入口处,校主遗像,其志长存!");
strcpy(G.siteArray[8].siteName,"颂恩楼");
strcpy(G.siteArray[8].siteInfo,"思明校区重要教学场所、最大办公楼");
strcpy(G.siteArray[9].siteName,"三家村学生广场");
strcpy(G.siteArray[9].siteInfo,"社团活动、晚会集会、校招、志愿者活动举行地及活动发布栏公示处");
strcpy(G.siteArray[10].siteName,"思源谷");
strcpy(G.siteArray[10].siteInfo,"毗邻建南自来水厂,高尔夫球场,风景宜人");
for(i = 1;i<=G.siteNumber;i++) //使用循环对路径进行赋值,对于没有 直 接 路 径 的 ,赋值为无穷大
for(j = 1;j<=G.siteNumber;j++)
G.pathArray[i][j].path = Infinite;
G.pathArray[1][2].path = 2000;
G.pathArray[1][3].path = 2300;
G.pathArray[1][9].path = 950;
G.pathArray[2][4].path = 1600;
G.pathArray[2][5].path = 1500;
G.pathArray[3][6].path = 600;
G.pathArray[3][7].path = 1400;
G.pathArray[3][8].path = 1000;
G.pathArray[4][5].path = 200;
G.pathArray[4][6].path = 800;
G.pathArray[5][7].path = 2000;
G.pathArray[5][8].path = 1200;
G.pathArray[6][7].path = 900;
G.pathArray[6][10].path = 1700;
G.pathArray[8][9].path = 600;
for(i = 1;i<=G.siteNumber;i++) //所构造的图为无向图,故相反方向路径相同
for(j = 1;j<=G.siteNumber;j++)
G.pathArray[j][i].path = G.pathArray[i][j].path;
return G;
}
void Floyd(MGraph *G) //使用弗洛伊德算法2求出最短路径
{
int v,u,i,w,k,j;
int flag = 1; //用于标记输入数据是否正确 , 若输入数据符合要求 ,则将 flag 置为0
int p[17][17][17],D[17][17];
for(v = 1;v <= G->siteNumber;v++)
for(w = 1;w<=G->siteNumber;w++)
{
D[v][w] = G->pathArray[v][w].path; //将路径数据存放至数组 D[v][w] 中
for(u = 1;u<=G->siteNumber;u++)
p[v][w][u]=0; //该三维数组用于存放两景点之间是否有直接路径,若有则记为1,无则记为0
if(D[v][w] < InfiniteNum)
{
p[v][w][v] = 1;p[v][w][w] = 1;
}
}
for(u = 1;u<=G->siteNumber;u++)
for(v = 1;v<=G->siteNumber;v++)
for(w = 1;w<=G->siteNumber;w++)
if(D[v][u] + D[u][w]<D[v][w]) // 如果两点之间直接路径大于间接路径 , 则将该两点之间路径置为间接路径
{
D[v][w] = D[v][u]+D[u][w];
for(i = 1;i<=G->siteNumber;i++)
p[v][w][i] = p[v][u][i]||p[u][w][i]; //获取两点之间路径所经过的景点编号
}
while(flag)
{
printf(" 请输入出发点和目的地的编号:");
scanf("%d%d",&k,&j);
if(k<=0||k>G->siteNumber||j<=0||j>G->siteNumber)
{
printf(" 景点编号不存在!请重新输入:");
scanf("%d\n%d",&k,&j);
}
if(k==j)
{
printf(" 出发点和目的地一样!请重新输入:");
scanf("%d\n%d",&k,&j);
}
if(k>0&&k<=G->siteNumber&&j>0&&j<=G->siteNumber)
flag=0; //输入的数据合法,故将 flag = 0
}
//printf("\n最短游览路线:%s",G->siteArray[k].siteName);
int dian[maxn],tot=0,vis[maxn];
queue<int>q;
memset(dian,0,sizeof(dian));
memset(vis,0,sizeof(vis));
dian[++tot]=k,dian[++tot]=j;
for(u = G->pathNumber;u>=0; u--)
{
if(p[k][j][u]&&k!=u&&j!=u)
{
dian[++tot]=u;
}
}
rg tep=k;
q.push(tep),vis[tep]=1;
/*for(rg i=1;i<=tot;i++)
{
cout<<dian[i]<<endl;
}*/
while(tep!=j)
{
//cout<<tep<<endl;
ll minn=inf;
for(int i=1;i<=tot;i++)
{
if(!vis[dian[i]])
minn=min(D[tep][dian[i]],minn);
}
//cout<<minn<<endl;
for(int i=1;i<=tot;i++)
{
if(dian[i]!=tep&&minn==D[tep][dian[i]]&&!vis[dian[i]])
{
//cout<<dian[i]<<endl;
q.push(dian[i]);
vis[dian[i]]=1;
tep=dian[i];
break;
}
}
}
while(!q.empty())
{
q.size()!=1?cout<<G->siteArray[q.front()].siteName<<"->":cout<<G->siteArray[q.front()].siteName<<endl;
q.pop();
}
/*if(k>j){
for(u = G->siteNumber;u>0;u--)
if(p[k][j][u] && k!=u && j!=u)
printf("-->%s",G->siteArray[u].siteName);}
if(k<j){
for(u=1;u<=G->siteNumber;u++)
if(p[k][j][u] && k!=u && j!=u)
printf("-->%s",G->siteArray[u].siteName);}
printf("-->%s",G->siteArray[j].siteName);
printf(" 总路线长%dm\n",D[k][j]);*/
}
void MainGraph(MGraph *G)
{
int i;
printf("**************************厦门大学校园导游系统 *****************************\n");
printf("\n");
printf(" -----------输入命令后最短路径或景点信息显示于屏幕上方------------ \n");
printf("\n");
printf(" 编号 景点名称 \n");
for(i = 1;i <= G->siteNumber; i++ ){
printf(" %-4d % -12s \n",G->siteArray[i].siteIdentifier,G->siteArray[i].siteName);
}
printf("\n");
printf(" \n");
printf(" 编号 功 能 \n");
printf(" \n");
printf(" 1 查 找 两 景 点 间 最 短 路径 \n");
printf(" \n");
printf(" 2 查 看 景 点 信 息 \n");
printf(" \n");
printf(" 3 退 出 系 统 \n");
printf(" \n");
printf(" 请输入您的操作编号:");
}
void SearchGraph(MGraph *G) //用于查询景点信息 ,以列表方式输出
{
int k,flag=1;
while(flag)
{
printf(" 请输入要查询的景点编号:");
scanf("%d",&k);
if(k<=0||k>G->siteNumber) //输入景点编号不合法时提示错误
{
printf(" 景点编号不存在!请重新输入景点编号:");
scanf("%d",&k);
}
if(k>0&&k<=G->siteNumber) // 输入合法时将 flag 置为 0
flag=0;
}
printf(" \n");
printf(" 编号 景点名称 简介 \n");
printf(" %-4d %-16s %-62s \n",G->siteArray[k].siteIdentifier,G->siteArray[k].siteName,G->siteArray[k].siteInfo); //输出景点信息
}
void ShowGraph(MGraph *G) // 将图中的信息打印出来
{
int i;
printf(" 编号 景点名称 \n");
for(i = 1;i<=G->siteNumber;i++)
printf(" %-4d %-12s \n",G->siteArray[i].siteIdentifier,G->siteArray[i].siteName);
}
ll n,m,ans,cnt,tot;
ll dis[maxn],vis[maxn],head[maxn];
typedef pair<int,int>pii;
priority_queue<pii,vector<pii>,greater<pii> >q;
vector<pair<int,char *> >v;
inline void add(ll u,ll v,ll w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
void mst ()
{
dis[1]=0;
q.push(make_pair(0,1));
while(!q.empty()&&tot<n)
{
//cout<<ans<<endl;
ll d=q.top().first,u=q.top().second;
q.pop();
if(vis[u])continue;
tot++;
ans+=d;
v.push_back(make_pair(u,G.siteArray[u].siteName));
vis[u]=1;
for(rg i=head[u];~i;i=e[i].next)
{
if(e[i].w<dis[e[i].v])
{
dis[e[i].v]=e[i].w;
q.push(make_pair(dis[e[i].v],e[i].v));
}
}
//cout<<tot<<endl;
}
cout<<"游览厦门大学上述十个景点的最小生成树权值为:";
tot==n?cout<<ans:cout<<-1<<endl;
cout<<"单位(m)"<<endl<<"顺序为:"<<endl;
ll cnt=0;
for(auto it:v)
{
cnt++;
cout<<cnt<<" "<<it.second<<endl;
}
return ;
}
inline void work()
{
n=10,m=16;
memset(dis,-inf,sizeof(dis));
memset(head,-1,sizeof(head));
add(1,2,2000),add(2,1,2000);
add(1,3,2300),add(3,1,2300);
add(1,9,950),add(9,1,950);
add(2,4,1600),add(4,2,1600);
add(2,5,1500),add(5,2,1500);
add(3,6,600),add(6,3,600);
add(3,7,1400),add(7,3,1400);
add(3,8,1000),add(8,3,1000);
add(4,5,200),add(5,4,200);
add(4,6,800),add(6,4,800);
add(5,7,2000),add(7,5,2000);
add(5,8,1200),add(8,5,1200);
add(6,7,900),add(7,6,900);
add(6,10,1700),add(10,6,1700);
add(8,9,600),add(9,8,600);
mst();
}
main.cpp
#define InfiniteNum 2147483647 //定义一个无穷大数
#define MaxInfoNum 100
#include<stdlib.h>
#include<string.h>
#include"Mygraph.h" //调用头文件
inline ll read()
{
char ch = getchar(); ll s = 0, w = 1;
while (ch < 48 || ch>57) { if (ch == '-')w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
return s * w;
}
inline void write(ll x)
{
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10);
putchar(x % 10 + 48);
} //定义景点数据最大容量
int main()
{
MGraph g; //创 建 图
int i;
g = InitGraph(); //初始化校园地图
MainGraph(&g); //调用显示主界面函数
scanf("%d",&i);
while(i!=3)
{
switch(i)
{
case 1:ShowGraph(&g);Floyd(&g);MainGraph(&g);break;
case 2:ShowGraph(&g);SearchGraph(&g);MainGraph(&g);break;
case 3:exit(0);break;
default:break;
}
scanf("%d",&i);
}
printf("欢迎下次继续使用 !\n\n");
work();
while(1)getchar();
}
附件:样图