数据结构课程设计旅游景点咨询系统的设计与实现Word下载.docx
《数据结构课程设计旅游景点咨询系统的设计与实现Word下载.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计旅游景点咨询系统的设计与实现Word下载.docx（21页珍藏版）》请在冰点文库上搜索。
typedefstruct
{
VRTypeadj;
intinfo;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
VertexTypevexs[MAX_VERTEX_NUM];
AdjMatrixarcs;
intvexnum,arcnum;
}MGraph;
2.系统主要子程序详细设计
a.
voidCreateDN（MGraph*G）
{/*采用数组（邻接矩阵）表示法,构造有向网G*/
inti,j,k,w,c;
chars[MAX_INFO],*info;
VertexTypeva,vb;
printf（"
请输入景点个数以及景点间所有路径的个数（以空格隔开）"
）;
scanf（"
%d%d"
&
（*G）.vexnum,&
（*G）.arcnum）;
请输入%d个景点:
\n"
（*G）.vexnum）;
for（i=0;
i<
（*G）.vexnum;
++i）/*构造顶点向量*/
scanf（"
%s"
（*G）.vexs[i]）;
++i）/*初始化邻接矩阵*/
for（j=0;
j<
++j）
{
（*G）.arcs[i][j].adj=INFINITY;
/*网*/
（*G）.arcs[i][j].info=NULL;
}
请输入%d条景点间的路径,路径间的路程权值以及路径间到达方式（以0或1来表示到达方式,步行:
0,索道:
1,如:
光明顶迎客松301）:
\n"
（*G）.arcnum）;
for（k=0;
k<
（*G）.arcnum;
++k）
{
%s%s%d%d*c"
va,vb,&
w,&
c）;
/*%*c吃掉回车符*/
i=LocateVex（*G,va）;
j=LocateVex（*G,vb）;
（*G）.arcs[i][j].adj=（*G）.arcs[j][i].adj=w;
/*有向网*/
（*G）.arcs[i][j].info=（*G）.arcs[j][i].info=c;
/*有向*/
}
}
b.
m,char*str,char*buf）/*求任意两个景点之间的所有简单路径*/
for（inti=0;
m.vexnum;
i++）
{
visited[i]=false;
}
intx=LocateVex（m,str）;
inty=LocateVex（m,buf）;
/*从x出发到y*/
stack<
int>
s;
s.push（x）;
visited[x]=true;
inti=0;
intz=0;
//表示没有找到这两个点之间有路径
while（!
s.empty（））
intflag=0;
//取栈顶元素
intt=s.top（）;
for（;
{
if（m.arcs[t][i].adj!
=INFINITY&
&
visited[i]==false）
{
s.push（i）;
flag=1;
visited[i]=true;
/*找到简单路径*/
if（s.top（）==y）//到达终点
{
z=1;
//找到这样的路径
cout<
<
"
一条简单路径为:
endl;
{
stack<
s2;
//建立一个临时的栈
//创建一个数组存放路径下标
int*way=newint[s.size（）];
intcount=0;
while（!
{
s2.push（s.top（））;
s.pop（）;
}
//还原s同时输出路径
s2.empty（））
cout<
m.vexs[s2.top（）]<
"
;
way[count++]=s2.top（）;
s.push（s2.top（））;
s2.pop（）;
//计算路径长度，给出到达的方式
intnum=0;
到达方式:
for（intk=0;
s.size（）-1;
k++）
{
intx1=LocateVex（m,m.vexs[way[k]]）;
inty1=LocateVex（m,m.vexs[way[k+1]]）;
num+=m.arcs[x1][y1].adj;
if（m.arcs[x1][y1].info==0）
cout<
步行"
"
else
索道"
}
路程:
num<
}
cout<
//出栈
intp=s.top（）;
visited[p]=false;
s.pop（）;
//从p开始接着访问后面的邻接点
i=p+1;
break;
}
//跳出本次循环
i=0;
break;
}
}
if（flag==0）
//出栈
intp=s.top（）;
visited[p]=false;
s.pop（）;
//从p开始接着访问后面的邻接点
i=p+1;
if（z==0）
cout<
两景点不可达"
c.
//分配路径相关信息的存储空间
int**road=newint*[m.vexnum];
road[i]=newint[m.vexnum];
//初始化
for（intj=0;
j++）
if（j==0）
road[i][j]=x;
else
road[i][j]=-1;
//while（find_s[x]==true）
find_s[i]=false;
length[i]=m.arcs[x][i].adj;
if（m.arcs[x][i].adj!
=INFINITY）
{
road[i][1]=i;
}
find_s[x]=true;
length[x]=0;
rigth_length[x]=0;
for（intj=1;
intpose=find_min_length（m,length）;
intz=0;
//记录找到它的路径
while（road[pose][z]!
=-1&
z<
=m.vexnum）
{
z++;
}
//cout<
min_length="
length[pose]<
rigth_length[pose]=length[pose];
//将路径最短的关联的另一个顶点加入已找到路径的数组中
find_s[pose]=true;
//更新最短路径
for（inti=0;
{
//i点还没有找到最短路径
if（find_s[i]==false&
m.arcs[pose][i].adj+length[pose]<
length[i]）
{
length[i]=m.arcs[pose][i].adj+length[pose];
{
//记录中间节点
intz=0;
//记录找到它的路径
while（road[pose][z]!
=-1）
{
z++;
}
/*移位再插入,用pose更新*/
//
（1）复制
for（intk=0;
z;
{
road[i][k]=road[pose][k];
}
road[i][z]=i;
}
}
}
cout<
if（road[y][1]==-1）
return-1;
else
最短路径为:
intcount=0;
while（road[y][count]!
=-1&
count<
m.vexnum）
m.vexs[road[y][count]]<
count++;
count-1;
intx1=LocateVex（m,m.vexs[road[y][i]]）;
inty1=LocateVex（m,m.vexs[road[y][i+1]]）;
if（m.arcs[x1][y1].info==0）
else
returnrigth_length[y];
四、测试与分析
1.建立旅游景点咨询系统，根据提示依次输入景点，路径，以及到达方式。
2.求两个景点间的所有简单路径
在主菜单下选2，并输入任意两个景点名称，可以得到这两个景点间的所有简单路径。
3.求两个顶点间的最短路径
在主菜单下选3，并输任意的两个景点，可以得到这两个景点间的最短路径，输出最短路径并以此输出到达方式。
4.退出系统
退出程序。
五、附录
1.旅游景点咨询系统.h
#include<
iostream>
string>
stack>
usingnamespacestd;
#defineMAX_NAME50/*顶点字符串的最大长度+1*/
#defineMAX_INFO50/*相关信息字符串的最大长度+1*/
typedefintVRType;
typedefcharVertexType[MAX_NAME];
#defineINFINITY10000
#defineMAX_VERTEX_NUM20
intLocateVex（MGraphG,VertexTypeu）
{/*初始条件:
图G存在,u和G中顶点有相同特征*/
/*操作结果:
若G中存在顶点u,则返回该顶点在图中位置;
否则返回-1*/
inti;
G.vexnum;
++i）
if（strcmp（u,G.vexs[i]）==0）
returni;
return-1;
VertexType*GetVex（MGraphG,intv）
{/*初始条件:
图G存在，v是G中某个顶点的序号。
操作结果:
返回v的值*/
if（v>
=G.vexnum||v<
0）
exit（0）;
return&
G.vexs[v];
}
intFirstAdjVex（MGraphG,VertexTypev）
图G存在,v是G中某个顶点*/
返回v的第一个邻接顶点的序号。
若顶点在G中没有邻接顶点,则返回-1*/
inti,j=0,k;
k=LocateVex（G,v）;
/*k为顶点v在图G中的序号*/
j=INFINITY;
if（G.arcs[k][i].adj!
=j）
intNextAdjVex（MGraphG,VertexTypev,VertexTypew）
图G存在,v是G中某个顶点,w是v的邻接顶点*/
返回v的（相对于w的）下一个邻接顶点的序号,*/
/*若w是v的最后一个邻接顶点,则返回-1*/
inti,j=0,k1,k2;
k1=LocateVex（G,v）;
/*k1为顶点v在图G中的序号*/
k2=LocateVex（G,w）;
/*k2为顶点w在图G中的序号*/
for（i=k2+1;
if（G.arcs[k1][i].adj!
boolvisited[MAX_NAME];
升级会员 