校园导游系统实验报告1.docx
《校园导游系统实验报告1.docx》由会员分享，可在线阅读，更多相关《校园导游系统实验报告1.docx（15页珍藏版）》请在冰点文库上搜索。
校园导游系统实验报告1
实习一校园导游程序
1、需求分析
该程序由C语言在visualc++环境下编写完成，由无向网的节点来表示校园景点，其边来表示景点之间的路径，且由一定的数据结构来存储景点的编号、名称及景点的详尽描述。
程序以字符的形式直观地展现学校的景点平面图，各景点之间的路径也同样由字符来呈现于屏幕之上。
游客可以使用该程序提供的以下功能：
能够查询一个景点到另一个景点的最短路径；可以查看从图内的任意景点到其他景点的路径和得到路径的长度；输入景点的编号可以获知该景点的详尽信息。
程序执行后，提示用户输入操作数，操作数类型为整数；当输入不在提供的操作数内时提示用户重新输入。
测试功能，选择操作数3，查询最短路径，输入如下形式1->8，回车即可，显示为这两个景点之间的路径上的景点，东西办公楼沁园->西教学楼，总长为290米；
当输入的景点的编号不存在时会提示景点编号不存在，并要求重新输入。
2、概要设计
为了完成程序的上述任务，需要定义图的抽象数据类型如下：
ADTGraph{
数据对象V：
V是具有相同特性的数据元素的集合
数据关系R：
R={VR}
VR={|v,w∈P（v，w），表示从v到w的弧，
P（v，w）定义了的意义或信息}
Creategraph（&G,V,VR）;
初始条件：
V是图的顶点集，VR是图中弧的集合。
操作结果：
按V和VR的定义构造图G。
LocateVex（G,u）;
初始条件：
图G存在，u和G中顶点有相同特征。
操作结果：
若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。
GetVex（G，v）；
初始条件：
图G存在，v是G中的某个顶点。
操作结果：
返回v的值。
FirstAdjVex（G，v）；
初始条件：
图G存在，v是G中的某个顶点。
操作结果：
返回v的第一个邻接顶点。
若没有邻接点则返回为空。
NextAdjVex（G，v，w）；
初始条件：
图G存在，v是G中的某个顶点。
操作结果：
返回v的（相对于w的）下一个邻接顶点。
若w是v的最后一个邻接点，则返回空。
本程序用到了8个函数，函数列表如下：
1）主函数main（）函数
2）对图中的节点进行初始化的InitGraph（）函数
3）显示景点平面图和操作提示的Menu（）函数
4）执行选择操作的功能的cmd（）函数
5）显示所有景点描述信息的Browser（）函数
6）实现迪杰斯特拉算法的ShortestPath_DIJ（）函数
7）实现弗洛伊德算法的Floyd（）函数
8）显示具体景点信息的Search（）函数
各函数之间的调用关系如下：
3、详细设计：
typedefstructArCell{
intadj;
}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct{//图中顶点表示主要景点，存放景点的编号、名称、简介等信息，
charname[30];
intnum;
charintroduction[100];
}infotype;
typedefstruct{
infotypevexs[MAX_VERTEX_NUM];
AdjMatrixarcs;
intvexnum,arcnum;
}MGraph;
MGraphG;
Creategraph（&G,V,VR）{
Initial（G）;//初始化G
}
GetVex（G，v）{
while（flag）{
printf（"请输入要查询的景点编号:
"）;
scanf（"%d",&k）;
while（k<0||k>=G->vexnum）{
printf（"景点编号不存在!
请重新输入景点编号:
"）;
scanf（"%d",&k）;
}
if（k>=0&&kvexnum）
flag=0;
}
printf（G->vexs[k].data）//输出查找的节点的信息
}
4、源程序代码：
#defineINFINITY10000/*无穷大*/
#defineMAX_VERTEX_NUM40//最大顶点数
#defineMAX40
#include
#include
#include
#include
#include
typedefstructArCell{
intadj;
}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct{//图中顶点表示主要景点，存放景点的编号、名称、景点描述等信息，
charname[30];
intnum;
charintroduction[100];
}infotype;
typedefstruct{
infotypevexs[MAX_VERTEX_NUM];
AdjMatrixarcs;
intvexnum,arcnum;
}MGraph;
MGraphb;
voidcmd（void）;
MGraphInitGraph（void）;
voidMenu（void）;
voidBrowser（MGraph*G）;
voidShortestPath_DIJ（MGraph*G）;
voidFloyd（MGraph*G）;
voidSearch（MGraph*G）;
intLocateVex（MGraph*G,char*v）;
voidmain（void）{//主函数
system（"colorec"）;
system（"modecon:
cols=110lines=30"）;
cmd（）;
}
voidcmd（void）{
inti;
b=InitGraph（）;
Menu（）;
scanf（"%d",&i）;
while（i!
=5）{
switch（i）{
case1:
system（"cls"）;Browser（&b）;Menu（）;break;
case2:
system（"cls"）;ShortestPath_DIJ（&b）;Menu（）;break;
case3:
system（"cls"）;Floyd（&b）;Menu（）;break;
case4:
system（"cls"）;Search（&b）;Menu（）;break;
default:
break;
}
scanf（"%d",&i）;
}}
MGraphInitGraph（void）{
MGraphG;
inti,j;
G.vexnum=10;
G.arcnum=24;
for（i=0;iG.vexs[i].num=i;
strcpy（G.vexs[0].name,"综合食堂"）;
strcpy（G.vexs[0].introduction,"新建标准化食堂"）;
strcpy（G.vexs[1].name,"东西办公楼"）;
strcpy（G.vexs[1].introduction,"全体教师办公场所，楼高12层，各种设施齐全"）;
strcpy（G.vexs[2].name,"7号学生宿舍楼"）;
strcpy（G.vexs[2].introduction,"数理系男生宿舍楼，设备优良,顶层夏热冬冷,时常断水"）;
strcpy（G.vexs[3].name,"医院"）;
strcpy（G.vexs[3].introduction,"校医院,设施不是很齐全，只能看小病，收费较贵"）;
strcpy（G.vexs[4].name,"图书馆"）;
strcpy（G.vexs[4].introduction,"藏书60万册,设施良好，2楼为电子阅览室，环境幽雅"）;
strcpy（G.vexs[5].name,"足球场"）;
strcpy（G.vexs[5].introduction,"现代化塑胶跑道,人造草坪,适宜锻炼身体的场所"）;
strcpy（G.vexs[6].name,"沁园"）;
strcpy（G.vexs[6].introduction,"绿树成荫,适宜休息和读书"）;
strcpy（G.vexs[7].name,"主教学楼"）;
strcpy（G.vexs[7].introduction,"学院最大的教学楼,共5层，环形建筑,适宜学习"）;
strcpy（G.vexs[8].name,"西教学楼"）;
strcpy（G.vexs[8].introduction,"学院第二大教学楼,环境较差"）;
strcpy（G.vexs[9].name,"多媒体楼"）;
strcpy（G.vexs[9].introduction,"多媒体教学场所,设施先进,环境良好"）;
for（i=0;ifor（j=0;jG.arcs[i][j].adj=INFINITY;
G.arcs[0][1].adj=120;G.arcs[0][2].adj=150;G.arcs[0][3].adj=195;G.arcs[1][6].adj=210;
G.arcs[1][3].adj=100;G.arcs[1][2].adj=180;G.arcs[1][7].adj=215;G.arcs[2][5].adj=350;
G.arcs[3][4].adj=100;G.arcs[3][6].adj=110;G.arcs[3][7].adj=175;G.arcs[4][6].adj=20;
G.arcs[5][6].adj=110;G.arcs[4][5].adj=100;G.arcs[4][9].adj=80;G.arcs[5][9].adj=150;
G.arcs[5][8].adj=200;G.arcs[6][8].adj=80;G.arcs[6][7].adj=60;G.arcs[6][9].adj=70;
G.arcs[7][9].adj=120;G.arcs[7][8].adj=80;G.arcs[8][9].adj=150;
for（i=0;ifor（j=0;jG.arcs[j][i].adj=G.arcs[i][j].adj;
returnG;
}
Sleep（2500）;
system（"cls"）;
}
voidShortestPath_DIJ（MGraph*G）{
intv,w,i,min,t=0,x,flag=1,v0;
intfinal[20],D[20],p[20][20];
while（flag）{
printf（"请输入一个起始景点编号:
"）;
scanf（"%d",&v0）;
while（v0<0||v0>=G->vexnum）{
printf（"景点编号不存在!
请重新输入景点编号:
"）;
scanf（"%d",&v0）;
}
if（v0>=0&&v0vexnum）
flag=0;
}
for（v=0;vvexnum;v++）{
final[v]=0;
D[v]=G->arcs[v0][v].adj;
for（w=0;wvexnum;w++）
p[v][w]=0;
if（D[v]p[v][v0]=1;p[v][v]=1;
}
}
D[v0]=0;final[v0]=1;
for（i=1;ivexnum;i++）{
min=INFINITY;
for（w=0;wvexnum;w++）
if（!
final[w]）
if（D[w]{v=w;min=D[w];}
final[v]=1;
for（w=0;wvexnum;w++）
if（!
final[w]&&（min+G->arcs[v][w].adjD[w]=min+G->arcs[v][w].adj;
for（x=0;xvexnum;x++）
p[w][x]=p[v][x];
p[w][w]=1;
}}
for（v=0;vvexnum;v++）
{if（v0!
=v）
{printf（"%s",G->vexs[v0].name）;
if（v0for（w=0;wvexnum;w++）{
if（p[v][w]&&w!
=v0&&v0printf（"-->%s",G->vexs[w].name）;
t++;}}
else{
for（w=G->vexnum-1;w>=0;w--）{
if（p[v][w]&&w!
=v0&&v0>v）
printf（"-->%s",G->vexs[w].name）;
t++;}}
if（t>G->vexnum-1&&v0!
=v）
printf（"总路线长%dm\n\n",D[v]）;
}}
Sleep（2500）;
system（"cls"）;
}
voidFloyd（MGraph*G）{
intv,u,i,w,k,j,flag=1,p[10][10][10],D[10][10];
for（v=0;vvexnum;v++）
for（w=0;wvexnum;w++）{
D[v][w]=G->arcs[v][w].adj;
for（u=0;uvexnum;u++）
p[v][w][u]=0;
if（D[v][w]p[v][w][v]=1;p[v][w][w]=1;
}}
for（u=0;uvexnum;u++）
for（v=0;vvexnum;v++）
for（w=0;wvexnum;w++）
if（D[v][u]+D[u][w]D[v][w]=D[v][u]+D[u][w];
for（i=0;ivexnum;i++）
p[v][w][i]=p[v][u][i]||p[u][w][i];
}
while（flag）
{
printf（"请输入出发点和目的地的编号,格式如:
（x->y）：
"）;
scanf（"%d->%d",&k,&j）;
while（k<0||k>=G->vexnum||j<0||j>=G->vexnum）{
printf（"景点编号不存在!
请重新输入出发点和目的地的编号:
"）;
scanf（"%d->%d",&k,&j）;
}
if（k>=0&&kvexnum&&j>=0&&jvexnum）
flag=0;
}
if（k>j）
{printf（"所走路径点：
%s-->",G->vexs[k].name）;
for（u=G->vexnum-1;u>0;u--）
if（p[k][j][u]&&k!
=u&&j!
=u&&k>j）
printf（"%s-->",G->vexs[u].name）;
printf（"%s",G->vexs[j].name）;
printf（"总路线长%dm\n",D[k][j]）;}
else
{printf（"%s",G->vexs[k].name）;
for（u=0;uvexnum;u++）
if（p[k][j][u]&&k!
=u&&j!
=u&&kprintf（"-->%s",G->vexs[u].name）;
printf（"-->%s",G->vexs[j].name）;
printf（"总路线长%dm\n",D[k][j]）;}
Sleep（2500）;
system（"cls"）;
}
voidSearch（MGraph*G）//查找函数。
{
intk,flag=1;
while（flag）
{
printf（"请输入要查询的景点编号:
"）;
scanf（"%d",&k）;
while（k<0||k>=G->vexnum）
{
printf（"景点编号不存在!
请重新输入景点编号:
"）;
scanf（"%d",&k）;
}
if（k>=0&&kvexnum）
flag=0;
}
printf（"┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n"）;
printf（"┃编号┃景点名称┃简介┃\n"）;
printf（"┃%-4d┃%-16s┃%-56s┃\n",G->vexs[k].num,G->vexs[k].name,G->vexs[k].introduction）;
printf（"┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n"）;
Sleep（2500）;
system（"cls"）;
}
5、使用说明和功能测试：
程序初始执行的界面如下：
输入操作数1，查看全校景点的文字描述：
输入操作数2，查看从一个景点到其余各景点的路径：
输入操作数3，显示从一个景点到指定景点的最短路径：
输入操作数4，可以查看具体景点的详尽的文字描述：
选择5，退出程序。
升级会员 