实验三广外校园导游系统的设计与实现.doc

广外校园导游系统的设计与实现
广东外语外贸大学 电气1206 吴俊辉

一、设计要求
设计一个校园导游程序，为来访的客人提供各种信息查询服务。
2、需求分析
⑴设计学校的校园平面图。选取若干个有代表性的景点抽象成一个无向带权图（无向网），所含景点不少于30个。以图中顶点表示校内各景点，边上的权值表示两景点之间的距离。
⑵存放景点代号、名称、简介等信息供用户查询。
⑶为来访客人提供图中任意景点相关信息的查询。
⑷为来访客人提供图中任意景点之间的问路查询。
⑸可以为校园平面图增加或删除景点或边，修改边上的权值等。

二、概要设计
校园旅游模型是由景点和景点之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的结点代表景点，用图的边代表景点之间的路径。所以首先应设计一个图类。结点值代表景点信息，边的权值代表景点间的距离。结点值及边的权值用顺序表存储，所以需要设计一个顺序表类。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个代码，用结构体类型实现。计算路径长度和最短路线时可用弗洛伊德算法实现。最后用while选择语句选择执行浏览景点信息或查询最短路径。
1、主界面设计
输出每个景点
2、 存储结构设计
用类描述，封装顶点信息
本系统采用图结构类型（mgraph）存储抽象校园图的信息。其中，各景点间的邻接关系用图邻接矩阵类型（adimatrix）存储；景点（顶点）信息用结构数组(vexs)存储，其中每个数组元素是一个结构变量，包含景点编号、景点名称及景点介绍三个分量；图的顶点个数及边的条数由分量vexnum、arcnum表示，它们是整型数据。
此外，本系统还设置了三个全局变量：visited[]数组用于存储顶点是否被访问标志；d[]数组用于存放边上的权值或存储查找路径顶点的编号；campus是一个结构的全局变量。
3、系统功能设计
⑴学校景点介绍
学校景点介绍由函数outputname();实现。当用户选择该功能，系统即能输出学校全部景点的信息：包括景点编号、景点名称
⑵查看浏览线路
查看浏览线路由函数floyed()实现。当用户选择该功能，系统能根据用户输入的起始景点编号，求出从该景点到其他景点的最短路径线路及距离。
⑶查询景点间最短路径
查询景点间最短路径由函数floyed()实现。该功能采用弗洛伊德(Floyd) 算法实现。当用户选择该功能，系统能根据用户输入的起始景点及目的景点编号，查询任意两个景点之间的最短路径线路及距离。
⑷景点信息查询
景点信息查询由函数outputname();
实现。该功能根据用户输入的景点编号输出该景点的相关信息。
⑸更改图信息
更改图的信息功能由主调函数void modify(graph g);
及若干子函数完成，可以实现图的若干基本操作。如增加新的景点、删除边、重建图等。(6)输出邻接矩阵
输出图的邻接矩阵，由函数void output_1();实现。
⑻退出
即退出校园导游系统，由按0函数实现。

PS：算法见附件.cpp
算法运用类class graph描述，对数据进行封装，用容器vector修改内容，但是一开始没有想到，后来就看没有时间就没有修改了，否则可以让算法更加灵活，把输出的矩阵放在文件中，可以防止cmd见面的繁杂。
总体算法还是缺少最优性，限于时间，暂时于此了。
操作结果如图：
代码：
//电六吴俊辉20121003736
#include<iostream>
#include<fstream>
#include<iomanip>
#include<vector>
#include<string>
using namespace std;
#define INFINITY 9999
const int n=30;//顶点数
const int e=51;//边数
//#define MAX 32767
class graph
{
private:
int vex[n];
char*name[n][20]; //景点名字
int arc[n][n]; //景点距离
int path[n][n]; //记录路径
int D[n][n]; //记录两点间的最短路径
public:
void creat();//建立邻接矩阵
void output_1();//输出邻接矩阵
void floyed();//佛洛依德求最短路径
void Name();//景点命名
void output_2(int i,int j);//输出最短路径
void outputname();//输出景点
void detail(int m);//景点详细信息
void modify(graph g);//修改顶点
};
void graph::Name () //给每个顶点命名
{
int i;
for(i=0;i<n;i++)
name[i][20]=NULL;
name[0][20]="南苑栋 ";name[1][20]="风采园（三饭）";name[2][20]="学生活动中心*中国银行";name[3][20]="水榭*又康超市";name[4][20]="师苑*数码港 ";
name[5][20]="友苑 ";name[6][20]="博雅园（二饭)";name[7][20]="文采园（一饭) ";name[8][20]="北苑栋 ";name[9][20]="后勤喽*保卫处";
name[10][20]="校医室 ";name[11][20]="隧道口 ";name[12][20]="中环广外公交站";name[13][20]="教学楼A栋 ";name[14][20]="教学楼E、F栋 ";
name[15][20]="凤凰山坡 ";name[16][20]="八角楼 ";name[17][20]="校办公楼 ";name[18][20]="院系办公楼 ";name[19][20]="实验楼ABCDE ";
name[20][20]="语心湖 ";name[21][20]="B8学术报告厅 ";name[22][20]="艺术楼 ";name[23][20]="大会堂 ";name[24][20]="图书馆 ";
name[25][20]="操场 ";name[26][20]="游泳池 ";name[27][20]="网球场 ";name[28][20]="体育馆 ";name[29][20]="正校门 ";
}
void graph::detail(int m) //每个景点的具体信息
{
if(m<1||m>30){cout<<"没有此顶点"<<endl;return;}
cout<<name[m-1][20]<<"：";
switch(m)
{
case 1:cout<<"信息男生宿舍，后面是内环，前面是法学院男生宿舍和经贸学院男生宿舍，与广中医广药中大宿舍相望，后面有大学城体育馆"<<endl;break;
case 2:cout<<"老二饭，新三饭，饭菜比较难吃，懒得没办法时大家都会去那里吃，但是价格还好，二楼好贵，一楼家常"<<endl;break;
case 3:cout<<"生活动中心楼下的中行里面的ATM可以无存折存款及用银行卡转账。各种学生活动会在此举行。好多人排队的，最好早上点取钱。"<<endl;break;
case 4:cout<<"云山水榭，有点浪漫，在学活下面，有KTV，咖啡店，网吧，有点贵啊！健身房，女生之家等……超市，真的又坑，好贵啊，不过品种齐全！"<<endl;break;
case 5:cout<<"主要居住老师。数码港主要销售一些跟电脑等有关的高科技产品。学生可以免费修电脑，当然，是不换硬件的时候。"<<endl;break;
case 6:cout<<"主要居住学校的外来人员。招待所等。"<<endl;break;
case 7:cout<<"第一层是大众饭堂，入口处有糖水供应。二楼则是套餐地带。晚上七点之后，这里还提供各式各样的宵夜。好多学生部门晚上来这里开会。"<<endl;break;
case 8:cout<<"第一层以大众菜式为主。二楼除了大众菜式，还有一些炒饭，粉面等以及套餐，价钱在元-7元。环境较好，女生多。饭菜也比较好吃。"<<endl;break;
case 9:cout<<"女生宿舍楼，主要居住信息学院和艺术学院的女学生。楼下是创业园，不过很贵里面的东西！"<<endl;break;
case 10:cout<<"组成巡逻队协助校方维护校园安全。安全问题可以去那里解决的。"<<endl;break;
case 11:cout<<"位于保卫处旁边，目前本科生校内看病只需支付%的费用，可享受校外医疗报销。"<<endl;break;
case 12:cout<<"是连接生活区与教学区的一个通道，是各种不同类型的活动的举办场所。"<<endl;break;
case 13:cout<<"有多辆公车经过，是广外唯一的一个公交站。很便宜啊！"<<endl;break;
case 14:cout<<"是学习新知识的主要地方，拥有无数间教室，教室里面设施齐全，有多媒体，电视和空调等。前面早上有校巴。"<<endl;break;
case 15:cout<<"是学习新知识的主要地方，拥有无数间教室，教室里面设施齐全，有多媒体，电视和空调等。后面是语心湖"<<endl;break;
case 16:cout<<"阳春三月有满山坡的杜鹃花啊，好好看，特色！上面通常很幽静，很多情侣在那里约会的。"<<endl;break;
case 17:cout<<"多种会议比赛的场所"<<endl;break;
case 18:cout<<"是各学校政要的办公室所在地。"<<endl;break;
case 19:cout<<"是各学院老师的办公室所在地。"<<endl;break;
case 20:cout<<"实验楼E区：里面除了有电教室、电脑室外，还有灯光实验室、演播室等不同用途的教室。实验楼A区：里面除了有电教室、电脑室外，还有灯光实验室、演播室等不同用途的教室。"
<<"语心湖：位于教学楼和实验楼之间，湖水平静，更有四个来自香江野生动物世界的黑天鹅教学楼E栋：是学习新知识的主要地方，拥有无数间教室，教室里面设施齐全，有多媒体，电视和空调等。"
<<"教学楼D栋：是学习新知识的主要地方，拥有无数间教室，教室里面设施齐全，有多媒体，电视和空调等。"<<endl;break;
case 21:cout<<"位于教学楼和实验楼之间，湖水平静，更有四个来自香江野生动物世界的黑天鹅,下午散步的最佳去所，拍照的好背景"<<endl;break;
case 22:cout<<"是各种活动举办的场所。这里是学生课余生活的常到之处，多彩社团活动的绽放地方。"<<endl;break;
case 23:cout<<"主要是艺术生上课的地方。里面很多展品。"<<endl;break;
case 24:cout<<"是重要会议进行的地方，党课也是在这里上的。军训的理论课在这里上，超爽的有空调！"<<endl;break;
case 25:cout<<"图书馆除了中英文借阅区与杂志阅读区外，还有小时自习区。前面的大广场，休闲好地方，在最前面是学校正门"<<endl;break;
case 26:cout<<"内有排球场，篮球场和羽毛球场，外有足球场。"<<endl;break;
case 27:cout<<"是上游泳课和师生日常游泳的地方。"<<endl;break;
case 28:cout<<"当然是打网球的啦"<<endl;break;
case 29:cout<<"内设×㎡的比赛区域，另设多个观众座席，其中固定座席个，活动看台坐席个。亚运会排球的场馆，日常拿来打羽毛球。开学的教育就在这里啦！"<<endl;break;
case 30:cout<<"位于图书馆的前面，是广外的象征，虽然不是很宏伟，说明我们很婉约嘛！"<<endl;break;
}
}
void graph::outputname() //输出景点名字
{
cout<<" ^-^ 欢迎进入广外导游系统^-^"<<endl;
int i,count=1;
for(i=0;i<n;i++)
{cout<<setw(5)<<i+1<<"、"<<name[i][20]<<setw(5);
if(count%3==0)cout<<endl; //每行输出三个
++count;
}
cout<<endl;
}
void graph::creat() //建立邻接矩阵
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)arc[i][j]=INFINITY;//初始化邻接矩阵
arc[0][1]=50;arc[1][2]=160;arc[1][2]=30;arc[3][4]=20;arc[1][4]=120;arc[5][6]=20;arc[3][6]=70;arc[3][7]=120;arc[6][7]=40;arc[3][8]=90;
arc[7][8]=40;arc[7][9]=40;arc[9][10]=50;arc[3][11]=120;arc[7][11]=20;arc[8][11]=20;arc[11][13]=30;arc[13][12]=100;arc[7][12]=130;arc[6][12]=40;
arc[13][14]=30;arc[13][15]=50;arc[15][16]=45;arc[16][17]=35;arc[16][18]=38;arc[17][18]=44;arc[16][19]=87;arc[16][20]=33;arc[13][20]=56;arc[19][20]=21;
arc[19][21]=46;arc[14][21]=245;arc[21][22]=76;arc[14][23]=143;arc[14][23]=228;arc[23][24]=162;arc[13][14]=341;arc[19][24]=252;arc[9][24]=313;arc[24][25]=152;
arc[25][26]=43;arc[24][26]=73;arc[13][25]=355;arc[26][27]=25;arc[24][28]=245;arc[28][26]=198;arc[13][29]=445;arc[24][29]=210;arc[19][29]=165;arc[17][29]=198;
arc[28][29]=221;
for(i=0;i<n;i++)
for(j=0;j<n;j++){
if(arc[j][i]==INFINITY)
arc[j][i]=arc[i][j];
}
}
void graph::output_1() //输出校园景点间的距离
{
int i,j;
ofstream ofile;
ofile.open("顶点路径.txt");
cout<<"校园景点和距离路径："<<endl;
for(i=0;i<n;i++)
{for(j=0;j<n;j++)
ofile<<arc[i][j]<<" ";
ofile<<endl;
}
ofile.close();
}
void graph::floyed()//用算法排
{
int i,j,k;
for(i=0;i<n;i++) //初始化
for(j=0;j<n;j++){
D[i][j]=arc[i][j];
if(D[i][j]<INFINITY)path[i][j]=i; //若有弧，则改路径
else path[i][j]=-1;
}//初始化结束
for(i=0;i<n;i++) //求两点间的最小距离
for(j=0;j<n;j++)
for(k=0;k<n;k++)
if(D[j][i]+D[i][k]<D[j][k]){ //两点间更短的路径
D[j][k]=D[j][i]+D[i][k]; //更换路径值
path[j][k]=path[i][k]; //更改路径
}
}
void graph::output_2(int i,int j)
{
int c,k,u=0;
int stack[n];
cout<<"顶点"<<i+1<<"到顶点"<<j+1<<"的最短程"<<D[i][j]<<endl;
c=j;
while(i!=c){
stack[u]=path[i][c]; u++; //设置栈，顺序输出路径
c=path[i][c];
}
cout<<"路径是：";
while(u>0){k=stack[--u];
cout<<name[k][20]<<"->"; }//输出顺序
cout<<name[j][20];
}
void print(vector<int>v1,vector<string>a1)
{
int i;
for(i=0;i<v1.size();i++)
cout<<"新增景点"<<v1[i]<<"详情为："<<a1[i]<<endl;
}
void graph::modify(graph g)//修改信息
{
int i,j,k;
cout<<"为校园平面图增加边输入边的景点代码和距离选，删除景点选，删除边选，修改边上的权值选，退出选";
cin>>i;
while(i==1)
{cout<<"为校园平面图增加边输入边的景点代码和距离:";cin>>i>>j>>k;
arc[i-1][j-1]=k;
cout<<"是否继续操作此步骤？是选，否选：";cin>>i;
}
while(i==2){
cout<<"删除景点输入删除景点序号：:";cin>>i;
name[i-1][20]="无此景点";
cout<<"删除完毕"<<endl;
cout<<"是否继续操作此步骤？是选，否选：";cin>>i;
}
while(i==3){
cout<<"删除边输入边的景点：";cin>>i>>j;
arc[i-1][j-1]=INFINITY;cout<<"删除完毕"<<endl;
cout<<"是否继续操作此步骤？是选，否选：";cin>>i;
}
while(i==4){
cout<<"为校园平面图修改边上的权值输入边的景点代码和距离:";cin>>i>>j>>k;
arc[i-1][j-1]=k;
cout<<"是否继续操作此步骤？是选，否选：";cin>>i;
}
while(i==0)return;
g.floyed();
g.output_1();//输出景点路径到文件
}

void main()
{
cout<<setw(40)<<"@广外南校旅游景点@"<<endl<<endl;
int i,j,a,b,y,c,k;
vector<int>v1;//向量容器
string str;//字符串
vector<string>a1;
graph g; //定义对象
g.creat(); //景点的距离
g.floyed();
g.output_1();//输出景点路径到文件

//执行操作
cout<<"是否进入广外导游系统？是选，否选：";
cin>>y;
while(y)//while 1
{
g.Name(); //景点
g.outputname(); //输出每个景点
while(y)//while 2
{
cout<<"系统操作指南：选择你要查找景点的详细信息选，查找两景点的距离选，增加新顶点和信息选，为校园平面图增加或删除景点或边，修改边上的权值选:退出选：";
cin>>a;
while(a==1){
cout<<"选择你要查找的景点，按景点序号：";
cin>>b;
g.detail(b);
cout<<"查找景点的详细信息选，否则选：";cin>>a;
}//while(a==1)

while(a==2){
cout<<"选择你要查找的两景点的距离序号：";cin>>i>>j;
g.output_2(i-1,j-1);cout<<endl;
cout<<"继续查找两景点的距离选，否则选：";cin>>a;
}//while(a==2)

while(a==3){
cout<<"输入增加顶点个数：";cin>>c;
for(k=1;k<=c;k++)v1.push_back(k);
cout<<"输入每个景点信息：";
for(k=1;k<=c;k++)
{cout<<"输入第"<<k<<"个景点信息：";
cin>>str;a1.push_back(str);
}
print(v1,a1);
cout<<"继续增加新顶点和信息选，否则选：";cin>>a;
}//while(a==3)

while(a==4){
cout<<"为校园平面图增加或删除景点或边，修改边上的权值:";
g.modify(g);
cout<<"继续为校园平面图增加或删除景点或边，修改边上的权值选，否则选：";
cin>>a;
}//while(a==4)

cout<<"是否继续留在广外导游系统？是选，否选：";
cin>>y;
}//while 2
}//while 1
}
- 11 -