数据结构校园导游程序成稿Word文件下载.docx
《数据结构校园导游程序成稿Word文件下载.docx》由会员分享，可在线阅读，更多相关《数据结构校园导游程序成稿Word文件下载.docx（27页珍藏版）》请在冰点文库上搜索。
{
for（i=0;
i<
G.vexnum;
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（j=0;
j<
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;
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;
i<
N;
i++）
dist[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;
k<
k++）//调整dist[k]
if（dist[j]>
0）//vk是尚未到达的终点
if（-dist[j]+cost[j][k]<
dist[k]）
dist[k]=-dist[j]+cost[j][k];
//途经vj到达vk的距离更短
for（i=0;
if（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;
if（dist[i]>
=0&
&
dist[i]<
min）
{min=dist[i];
j=i;
return（j）;
第四个模块实现了求任意场所的问路查询功能，接收用户所输入的场所编号，并在计算机的最短路径集合中找到相关项的信息反馈给用户，此模块旨在求任意两个场所之间的最短路径；
本模块主要用了弗洛伊德算法实现，算法如下：
voidFloyd（MGraph*G）
for（v=0;
v<
G->
vexnum;
v++）
for（w=0;
w<
w++）
D[v][w]=G->
arcs[v][w].adj;
for（u=0;
u<
u++）
p[v][w][u]=0;
if（D[v][w]<
INFINITY）
p[v][w][v]=1;
p[v][w][w]=1;
if（D[v][u]+D[u][w]<
D[v][w]）
D[v][w]=D[v][u]+D[u][w];
p[v][w][i]=p[v][u][i]||p[u][w][i];
第五个模块实现了图形的插入删除更新功能，保证景点平面图及时更新准确为用户提供景点及路径信息；
此部分有两个算法如下：
MGraph*CreatUDN（MGraph*G）//初始化图形，接受用户输入
scanf（"
%d%d"
&
vexnum,&
arcnum）;
printf（"
请输入景点的编号:
、名称、简介:
\n"
景点编号:
"
scanf（"
%d"
vexs->
num）;
景点名称:
%s"
G->
vexs[i].name）;
景点简介:
introduction）;
G->
arcs[i][j].adj=INFINITY;
请输入路径长度:
arcnum;
k++）
第%d条边:
k+1）;
景点对（x,y）:
v1）;
v2）;
路径长度:
w）;
i=LocateVex（G,v1）;
j=LocateVex（G,v2）;
if（i>
j>
=0）
arcs[i][j].adj=w;
arcs[j][i]=G->
arcs[i][j];
intLocateVex（MGraph*G,char*v）
{
if（strcmp（v,G->
vexs[i].name）==0）
{c=i;
returnc;
2.4抽象数据类型的设计
本设计利用了图数据结构及图中几个重要的算法。
所以抽象数据类型如下：
ADTgraph{
数据对象V：
具有相同特性的数据元素的集合
数据关系R：
R={VR}
VR={<
v,w>
|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是无向的则还增添对称弧<
w,v>
。
DeletArc（&
G，v，w）;
//在G中删除弧<
v，w>
，若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（）
\n德州学院导游图\n"
┏━━━━━━━━━━━━━━━━━━━━┓\n"
┃1.浏览校园全景┃\n"
┃2.查看所有游览路线┃\n"
┃3.选择出发点和目的地┃\n"
┃4.查看所选景点信息┃\n"
｜5.用户完善校园景点平面图┃\n"
┃6.退出系统┃\n"
┗━━━━━━━━━━━━━━━━━━━━┛\n"
Option-:
另外各模块有自己的成员函数如下
第一模块成员函数有两个如下所示：
（1）初始化平面图
MGraphG;
inti,j;
G.vexnum=10;
G.arcnum=14;
strcpy（G.vexs[0].name,"
学院正门"
紧靠三省亭，环境优雅,有荷塘月色的意境"
（2）浏览函数展示校园平面全景图
intv;
┏━━┳━━━━━━━━┳━━━━━━━━━━━━┓\n"
┃编号┃景点名称┃简介┃\n"
v++）
┃%-4d┃%-16s┃%-56s┃\n"
vexs[v].num,G->
vexs[v].name,G->
vexs[v].introduction）;
┗━━┻━━━━━━━━┻━━━━━━━━━━━━┛\n"
第二个模块有自己的一个成员函数如下
intk,flag=1;
while（flag）
请输入要查询的景点编号:
k）;
if（k<
0||k>
vexnum）
景点编号不存在!
请重新输入景点编号:
if（k>
flag=0;
vexs[k].num,G->
vexs[k].name,G->
vexs[k].introduction）;
┗━━┻━━━━━━━━━━━━━━━━━━━━━┛\n"
}//Searchend
第三个模块是用实现单元颠倒其他各点的最短路径，成员函数为：
voidShortestPath_DIJ（MGraph*G）
intv,w,i,min,t=0,x,flag=1,v0;
intfinal[20],D[20],p[20][20];
请输入一个起始景点编号:
v0）;
if（v0<
0||v0>
if（v0>
v0<
final[v]=0;
D[v]=G->
arcs[v0][v].adj;
p[v][w]=0;
if（D[v]<
p[v][v0]=1;
p[v][v]=1;
D[v0]=0;
final[v0]=1;
for（i=1;
min=INFINITY;
if（!
final[w]）
if（D[w]<
min）{v=w;
min=D[w];
final[v]=1;
final[w]&
（min+G->
arcs[v][w].adj<
D[w]））
D[w]=min+G->
for（x=0;
x<
x++）
p[w][x]=p[v][x];
p[w][w]=1;
if（v0!
=v）
vexs[v0].name）;
if（p[v][w]&
w!
=v0）
-->
vexs[w].name）;
升级会员 