某数据结构课程设计公园导游图.doc

实验四：图（内容：某公园导游图）
一、问题描述：
公园导游系统：给出一张某公园的导游图，游客通过终端询问可知︰从某一景到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。

二、设计描述：

1.输入导游图的算法（存储方法）.本程序特地设计函数void initgraph()用于实现键盘输入图的结构；
2.可访问导游图中任一景点的算法.为此设计了函数void vist(GraphMatrix graph)用于实现访问任一景点的信息；
3.最短路径从一景点到另一景点的算法。利用floyd算法-实现每一对景点间的最短路径。
并利用void outgraph()函数实现显示起始点和终点间的最短路径和其长度；

三、程序清单：

#include<iostream>
using namespace std;
#include<stdio.h>
#define MAXVEX 100
#define MAX 999
typedef char VexType;
typedef float AdjType;
typedef struct //定义图结构
{
int n; /* 图的顶点个数 */
VexType vexs[MAXVEX]; /* 顶点信息 */
AdjType arcs[MAXVEX][MAXVEX]; /* 边信息 */
} GraphMatrix;
GraphMatrix graph; //定义一个图graph

typedef struct //定义最短路径ShortPath结构
{
AdjType a[MAXVEX][MAXVEX]; /* 关系矩阵A，存放每对顶点间最短路径长度 */
int nextvex[MAXVEX][MAXVEX];
/* nextvex[i][j]存放vi到vj最短路径上vi的后继顶点的下标值 */
} ShortPath;
ShortPath path; //定义路径path
void floyd(GraphMatrix * pgraph, ShortPath * ppath) //floyd算法-用于实现每一对景点间的最短路径
{
int i, j, k;
for (i = 0; i < pgraph->n; i++)
for (j = 0; j < pgraph->n; j++) {
if (pgraph->arcs[i][j] != MAX)
ppath->nextvex[i][j] = j;
else ppath->nextvex[i][j] = -1;
ppath->a[i][j] = pgraph->arcs[i][j];
}
for (k = 0; k < pgraph->n; k++)
for (i = 0; i < pgraph->n; i++)
for (j = 0; j < pgraph->n; j++) {
if ( ppath->a[i][k] >= MAX || ppath->a[k][j] >= MAX )
continue;
if ( ppath->a[i][j] > ppath->a[i][k]+ ppath->a[k][j] ) {
ppath->a[i][j] = ppath->a[i][k] + ppath->a[k][j];
ppath->nextvex[i][j] = ppath->nextvex[i][k];
}
}
}
void outgraph() //out()函数用于实现显示起始点和终点间的最短路径和其长度
{
int c,b,i;
cout<<endl;
cout<<"请输入想查找起始点和终点:"; //输入要查找起始点和终点（本程序限于编号（int型））
cout<<endl;
cin>>c;
cin>>b;
i=path.a[c][b]; //通过path.a[c][b]把路径长度赋给i
cout<<"该路径总长为:";
cout<<i<<endl; //输出路径长度
cout<<"所得路径顺序为";
cout<<c; //此处输出路径的第一个编号
c=path.nextvex[c][b];
for(;c!=b;c=path.nextvex[c][b]) //循环顺序输出路径始点和终点之间的景点编号
cout<<","<<c;
cout<<","<<b; //再输出路径的最后一个编号
cout<<endl;
}
void initgraph() //该函数用于实现键盘输入图的结构
{
int i,m,j;
printf("请输入公园景点的个数："); //图结点的个数赋给graph.n
scanf("%d",&m);
graph.n=m;
for(i=0;i<graph.n;i++) //循环输入结点顶点信息
{
printf("请输入第%i个景点信息:",i); //为了简明起见此程序结点顶点信息限于字符型
cin>>graph.vexs[i];
}
printf("请输入公园的邻接矩阵的信息\n");//循环输入图的邻接矩阵信息（也就是输入一个二维数组）
for(i=0;i<graph.n;i++)
for(j=0;j<graph.n;j++)
{
printf("请输入第%d行，第%d列的元素:",i+1,j+1); cin>>graph.arcs[i][j];
}
}
void vist(GraphMatrix graph) //函数用于实现访问任一景点的信息
{ int i;
cout<<endl;
cout<<"你想知道哪个景点的信息："; //注意输入的是景点的编号
cin>>i;
cout<<endl;
cout<<"景点信息查询结果为：";
cout<<graph.vexs[i]; //输出景点信息
cout<<endl;
}
int jud() //用于判断是否继续执行特定的下一步程序
{int a;
cout<<"还想继续查询?(1&0)";
cin>>a;
return a;

}
int main()
{
int i,j;
initgraph(); //initgraph()函数来实现键盘输入图的结构
floyd(&graph, &path);
cout<<"为了验证下面运算结果的方便，循环输出nextvex[i][j]数组";
for (i = 0; i < graph.n; i++)
{
for (j = 0; j < graph.n; j++) //为了验证下面运算结果的方便，循环输出nextvex[i][j]数组
printf("%d ", path.nextvex[i][j]); //nextvex[i][j]存放vi到vj最短路径上vi的后继顶点的下标值
putchar('\n');
}
cout<<endl;
outgraph();
while(jud())
outgraph(); //outgraph()函数用于实现显示起始点和终点间的最短路径和其长度
vist(graph); //函数用于实现访问任一景点的信息
cout<<endl;
while(jud())
vist(graph);
cout<<endl;
return 0;
}

验四：图（内容：某公园导游图）

①.问题描述

　　给出一张某公园的导游图，游客通过终端询问可知：

（1）从某一景点到另一景点的最短路径。

（2）游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览景点，最后回到出口（出口就在入口处旁边）。

②. 要求

　　将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值给游客　。

③.实现提示

（1）第一问实际是最短路径问题，如果有几条路径长度相同，可选择途径景点较少的路径提供给游客。

（2）第二问可采用深度优先搜索，如果有多种路径可选择，则选择带权路径最小的路线提供给游客。

④.选做内容

　　可以把各种路径都显示给游客，由游客自己选择游览路线。