数据结构校园导游程序成稿.docx
《数据结构校园导游程序成稿.docx》由会员分享，可在线阅读，更多相关《数据结构校园导游程序成稿.docx（27页珍藏版）》请在冰点文库上搜索。
数据结构校园导游程序成稿
校园导游程序
摘要随着高校校园的逐渐扩展，来访校园的人士逐渐增多，随着校园透明度的提高，各界人士对学术氛围的追求，越来越多的人走进了大学校园，走进了象牙塔，这片静土也以它崭新的面貌，迎接着所有的到来者。
高校校园旅游在掀起“羞答答的头盖“后，正悄然走向市场，当今高校在确立了旅游的市场可行性之后，随之而来的导游系统是势在必行，高校的旅游可以让人陶冶情操，也可以让人对学术产生浓厚的兴趣。
那么如何更好的更科学的更科学的组织好高校导游，如何更方便更便捷的把高校的校园展示给世人，就成为了一个需要解决的问题。
本设计基于图的结构，创建一个无向图，针对游客的实际需求，将重庆科技学院的景点编号、名称、介绍等信息放入到图的顶点当中并保存在景点文本文件当中，将两个景点的编号和它们之间的距离当作权值也保存到权值文本文件当中，利用迪杰斯特拉算法来求从一个景点到另一个景点的最短距离，利用strcmp（）;函数来查找景点，并显示出它的信息，从而解决了要查找景点信息和景点之间的最短路径的问题，最后按照显示屏上的提示进行相关的操作。
关键词：
无向图;查找信息;最短距离;校园导游咨询
1设计内容和要求
1.1设计内容
依据课程设计的要求，用无向网表示所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。
要求能够回答有关景点介绍、游览路径等问题。
1.2设计要求
本校园景点平面图设计的主要目的是为用户提供以下主要信息：
第一，为用户展示一个比较全面的校园全景图，让游客做到对所要浏览的校园心中有数，尽可能做到一目了然；第二，当游客置身于景点中时，可以为用户提供平面中某景点到其余各景点的浏览路线及其各自最短路径，以便使用户更好的完成自己的浏览计划，从而节省时间放松身心；第三，为用户提供平面图中任意场所的问路查询，即查询任意两个景点之间的一条最短的简单路径，旨在为用户的旅游大大提高效率；第四，为用户提供平面图中任意场所的相关信息的查询，简单介绍平面图中各景点的特点，概况和相关职能，让用户有选择的进行浏览；第五，为保证景点平面图的完整和准确，本设计提供了用户更新完善平面图的功能；最后本设计本着完整健壮的追求，设计了退出系统环节，让用户用的更舒心。
2概要设计
2.1程序模块图
图2-1模块图
2.2数据结构的设计
由于各个场所通过校园中的道路相连，各个场所和连接它们的道路构成了整个校园的地理环境，所以使用图这种数据结构对它们进行描述。
以图中顶点表示校园内的各个场所。
应包含场所名称、代号、简介等信息；以边表示连接各个场所的道路，应包含路径的代号、路径长度等信息。
一般情况下，校园的道路是双向通行的。
因此校园平面图可以看做一个无向网。
图的顶点和边均使用结构体类型，整个图的数据结构采用了带权的邻接矩阵的存储方式。
2.3算法的设计
本校园景点平面图设计从总体上主要划分了五个模块。
第一模块以表格形式显示校园平面图，平面图中应能够准确地标示场所名称，及其对应各个场所的简介信息；首先用二维数组初始化一个图形G，然后调用Browser（MGraph*G）函数调用并显示这个平面图，主要有以下两个算法
MGraphInitGraph（void）
{
for（i=0;i{
G.vexs[i].num=i;
strcpy（G.vexs[0].name,学院正门"）;
strcpy（G.vexs[0].introduction,"学校正大门很气派"）;
strcpy（G.vexs[1].name,"综合楼"）;
strcpy（G.vexs[1].introduction,"正对学校大门的，高层领导办公之地，平时学生的实验室所在地"）;
strcpy（G.vexs[2].name,"外语楼"）;
strcpy（G.vexs[2].introduction,"紧靠三省亭，环境优雅,有荷塘月色的意境"）;
strcpy（G.vexs[3].name,"图书馆"）;
strcpy（G.vexs[3].introduction,"藏书464.8万册,设施完备，5楼为电子阅览室，环境幽雅"）;
strcpy（G.vexs[4].name,"体育场"）;
strcpy（G.vexs[4].introduction,"现代化塑胶跑道,人造草坪,适宜锻炼身体的场所"）;
strcpy（G.vexs[5].name,"第二餐厅"）;
strcpy（G.vexs[5].introduction,"紧邻我们的图书馆，干净卫生，饭菜可口"）;
strcpy（G.vexs[6].name,"大学生活动中心"）;
strcpy（G.vexs[6].introduction,"大学生活动中心于2005年6月30日成立，挂靠学生工作处"）;
strcpy（G.vexs[7].name,"好邻居超市"）;
strcpy（G.vexs[7].introduction,"学校两大超市之一,日常生活用品，电子产品等应有尽有"）;
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;j{
G.arcs[i][j].adj=INFINITY;
G.arcs[0][1].adj=50;
G.arcs[0][2].adj=200;
G.arcs[0][6].adj=600;
G.arcs[1][7].adj=580;
G.arcs[2][3].adj=100;
G.arcs[3][4].adj=50;
G.arcs[3][6].adj=400;
G.arcs[4][5].adj=450;
G.arcs[4][8].adj=700;
G.arcs[5][8].adj=800;
G.arcs[6][7].adj=50;
G.arcs[6][9].adj=200;
G.arcs[7][8].adj=210;
G.arcs[8][9].adj=80;
}
for（i=0;ifor（j=0;j{
G.arcs[j][i].adj=G.arcs[i][j].adj;
returnG;
}
}//InitGraphend
voidBrowser（MGraph*G）
{
Printf（）
}
第二个模块实现了任意场所的信息查询功能，要求能够接受用户所输入的场所名称，并将场所的简介信息反馈给用户；本设计用Search函数实现本部分功能，算法如下；voidSearch（MGraph*G）
{
Printf（）
}
第三个模块功能为求单源点到其他各点的最短路径，计算并记录从某个景点到其他各个场所的各自所有最短路径；主要有迪杰斯特拉算法实现如下：
voiddijstra（intcost[][N],intv）
{intdist[N],i,j,w
for（i=0;idist[i]=cost[v][i];//初始化
dist[v]=-dist[v];
for（i=0;i{j=mincost（dist）;//找非0、非负且最小的dist[j]
if（j==0）;break;
dist[j]=-dist[j];//vj并入U中
for（k=0;kif（dist[j]>0）//vk是尚未到达的终点
if（-dist[j]+cost[j][k]dist[k]=-dist[j]+cost[j][k];//途经vj到达vk的距离更短
}
for（i=0;iif（dist[j]<0）
printf（“%d,%d:
%d\n”,v,i,-dist[i]）;
}
intmincost（intdist[]）
//在V-U集合中找顶点j，dist[j]是dist[]中的最小值
{inti,min,j;
min=MAX;j=0;
for（i=0;iif（dist[i]>=0&&dist[i]{min=dist[i];j=i;}
return（j）;
}
第四个模块实现了求任意场所的问路查询功能，接收用户所输入的场所编号，并在计算机的最短路径集合中找到相关项的信息反馈给用户，此模块旨在求任意两个场所之间的最短路径；本模块主要用了弗洛伊德算法实现，算法如下：
voidFloyd（MGraph*G）
{
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];
}
第五个模块实现了图形的插入删除更新功能，保证景点平面图及时更新准确为用户提供景点及路径信息；此部分有两个算法如下：
MGraph*CreatUDN（MGraph*G）//初始化图形，接受用户输入
{
scanf（"%d%d",&G->vexnum,&G->arcnum）;
printf（"请输入景点的编号:
、名称、简介:
\n"）;
for（i=0;ivexnum;i++）
{
printf（"景点编号:
"）;
scanf（"%d",&G->vexs->num）;
printf（"景点名称:
"）;
scanf（"%s",G->vexs[i].name）;
printf（"景点简介:
"）;
scanf（"%s",G->vexs->introduction）;
}
for（i=0;ivexnum;i++）
for（j=0;jvexnum;j++）
G->arcs[i][j].adj=INFINITY;
printf（"请输入路径长度:
\n"）;
for（k=0;karcnum;k++）
{
printf（"第%d条边:
\n",k+1）;
printf（"景点对（x,y）:
"）;
scanf（"%s",v1）;
scanf（"%s",v2）;
printf（"路径长度:
"）;
scanf（"%d",&w）;
i=LocateVex（G,v1）;
j=LocateVex（G,v2）;
if（i>=0&&j>=0）
{
G->arcs[i][j].adj=w;
G->arcs[j][i]=G->arcs[i][j];
}
}
returnG;
}
intLocateVex（MGraph*G,char*v）
{
for（i=0;ivexnum;i++）
if（strcmp（v,G->vexs[i].name）==0）
{c=i;break;}
returnc;
}
2.4抽象数据类型的设计
本设计利用了图数据结构及图中几个重要的算法。
所以抽象数据类型如下：
ADTgraph{
数据对象V：
具有相同特性的数据元素的集合
数据关系R：
R={VR}
VR={|v,w∈V，表示从v到w的弧}
基本操作P：
结构的建立：
CreatGraph（&G,V,VR）:
//按定义（V,VR）构造图
对顶点的访问操作:
LocateVex（G,u）;//若G中存在顶点u，则返回该顶点在图中“位置”；否则返回其它信息。
GetVex（G,v）;//返回v的值。
PutVex（&G,v,value）;//对v赋值value。
FirstAdjVex（G,v）;//返回v的“第一个邻接点”。
若该顶点在G中没有邻接点，则返回“空”。
NextAdjVex（G,v,w）;//返回v的（相对于w的）“下一个邻接点”。
若w是v的最后一个邻接点，则/返回“空”。
InsertVex（&G,v）;//在图G中增添新顶点v。
DeleteVex（&G，v）;//删除G中顶点v及其相关的弧。
InsertArc（&G，v，w）；//在G中增添弧,若G是无向的则还增添对称弧。
DeletArc（&G，v，w）;//在G中删除弧，若G是无向的则还删除对称弧。
}
3详细设计
3.1设计抽象数据类型对应的类定义
typedefstructArcCell{//弧的定义
VRTypeadj;//VRType是顶点关系类型。
对无权图，用1或0表示相邻否；//对带权图，则为权值类型。
InfoType*info;//该弧相关信息的指针
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct{//图的定义
VertexTypevexs[MAX_VERTEX_NUM];//顶点信息
AdjMatrixarcs;//弧的信息
intvexnum,arcnum;//顶点数，弧数
GraphKindkind;//图的种类标志
}MGraph;
3.2设计每个成员函数
在本设计这些函数中有一个公共成员函数：
voidMenu（）
{
printf（"\n德州学院导游图\n"）;
printf（"┏━━━━━━━━━━━━━━━━━━━━┓\n"）;
printf（"┃1.浏览校园全景┃\n"）;
printf（"┃2.查看所有游览路线┃\n"）;
printf（"┃3.选择出发点和目的地┃\n"）;
printf（"┃4.查看所选景点信息┃\n"）;
printf（"｜5.用户完善校园景点平面图┃\n"）;
printf（"┃6.退出系统┃\n"）;
printf（"┗━━━━━━━━━━━━━━━━━━━━┛\n"）;
printf（"Option-:
"）;
}
另外各模块有自己的成员函数如下
第一模块成员函数有两个如下所示：
（1）初始化平面图
MGraphInitGraph（void）
{
MGraphG;
inti,j;
G.vexnum=10;
G.arcnum=14;
for（i=0;i{
G.vexs[i].num=i;
strcpy（G.vexs[0].name,"学院正门"）;
strcpy（G.vexs[0].introduction,"学校正大门很气派"）;
strcpy（G.vexs[1].name,"综合楼"）;
strcpy（G.vexs[1].introduction,"正对学校大门的，高层领导办公之地，平时学生的实验室所在地"）;
strcpy（G.vexs[2].name,"外语楼"）;
strcpy（G.vexs[2].introduction,"紧靠三省亭，环境优雅,有荷塘月色的意境"）;
strcpy（G.vexs[3].name,"图书馆"）;
strcpy（G.vexs[3].introduction,"藏书464.8万册,设施完备，5楼为电子阅览室，环境幽雅"）;
strcpy（G.vexs[4].name,"体育场"）;
strcpy（G.vexs[4].introduction,"现代化塑胶跑道,人造草坪,适宜锻炼身体的场所"）;
strcpy（G.vexs[5].name,"第二餐厅"）;
strcpy（G.vexs[5].introduction,"紧邻我们的图书馆，干净卫生，饭菜可口"）;
strcpy（G.vexs[6].name,"大学生活动中心"）;
strcpy（G.vexs[6].introduction,"大学生活动中心于2005年6月30日成立，挂靠学生工作处"）;
strcpy（G.vexs[7].name,"好邻居超市"）;
strcpy（G.vexs[7].introduction,"学校两大超市之一,日常生活用品，电子产品等应有尽有"）;
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;j{
G.arcs[i][j].adj=INFINITY;
G.arcs[0][1].adj=50;
G.arcs[0][2].adj=200;
G.arcs[0][6].adj=600;
G.arcs[1][7].adj=580;
G.arcs[2][3].adj=100;
G.arcs[3][4].adj=50;
G.arcs[3][6].adj=400;
G.arcs[4][5].adj=450;
G.arcs[4][8].adj=700;
G.arcs[5][8].adj=800;
G.arcs[6][7].adj=50;
G.arcs[6][9].adj=200;
G.arcs[7][8].adj=210;
G.arcs[8][9].adj=80;
}
for（i=0;ifor（j=0;j{
G.arcs[j][i].adj=G.arcs[i][j].adj;
returnG;
}
}//InitGraphend
（2）浏览函数展示校园平面全景图
voidBrowser（MGraph*G）
{
intv;
printf（"┏━━┳━━━━━━━━┳━━━━━━━━━━━━┓\n"）;
printf（"┃编号┃景点名称┃简介┃\n"）;
for（v=0;vvexnum;v++）
printf（"┃%-4d┃%-16s┃%-56s┃\n",G->vexs[v].num,G->vexs[v].name,G->vexs[v].introduction）;
printf（"┗━━┻━━━━━━━━┻━━━━━━━━━━━━┛\n"）;
}
第二个模块有自己的一个成员函数如下
voidSearch（MGraph*G）
{
intk,flag=1;
while（flag）
{
printf（"请输入要查询的景点编号:
"）;
scanf（"%d",&k）;
if（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"）;
}//Searchend
第三个模块是用实现单元颠倒其他各点的最短路径，成员函数为：
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）;
if（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]final[v]=1;
for（w=0;wvexnum;w++）
if（!
final[w]&&（min+G->arcs[v][w].adj{
D[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）;
for（w=0;wvexnum;w++）
{
if（p[v][w]&&w!
=v0）
printf（"-->%s",G->vexs[w].name）;
升级会员 