数据结构实验报告 班级：06软件工程 姓名：周邓雄 学号：06517037
实验四：图（内容：某公园导游图）
一、问题描述：
公园导游系统：给出一张某公园的导游图，游客通过终端询问可知︰从某一景到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。
二、设计描述：
1.输入导游图的算法（存储方法）.本程序特地设计函数void initgraph()用于实现键盘输入图的结构；
2.可访问导游图中任一景点的算法.为此设计了函数void vist(GraphMatrix graph)用于实现访问任一景点的信息； 3.最短路径从一景点到另一景点的算法。利用floyd算法-实现每一对景点间的最短路径。 并利用void outgraph()函数实现显示起始点和终点间的最短路径和其长度；
三、程序清单：
#include
#define MAXVEX 100
#define MAX 999 typedef char VexType;
数据结构实验报告 班级：06软件工程 姓名：周邓雄 学号：06517037
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;
数据结构实验报告 班级：06软件工程 姓名：周邓雄 学号：06517037
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< cout<<\请输入想查找起始点和终点:\ //输入要查找起始点和终点（本程序限于编号（int型）） cout< i=path.a[c][b]; //通过path.a[c][b]把路径长度赋给i 数据结构实验报告 班级：06软件工程 姓名：周邓雄 学号：06517037 cout<<\该路径总长为:\ cout< cout< for(;c!=b;c=path.nextvex[c][b]) //循环顺序输出路径始点和终点之间的景点编号 cout<<\ cout<<\ //再输出路径的最后一个编号 cout< void initgraph() //该函数用于实现键盘输入图的结构 { int i,m,j; printf(\请输入公园景点的个数：\ //图结点的个数赋给graph.n scanf(\graph.n=m; for(i=0;i printf(\请输入第%i个景点信息:\为了简明起见此程序结点顶点信息限于字符型 cin>>graph.vexs[i]; } printf(\请输入公园的邻接矩阵的信息\\n\循环输入图的邻接矩阵信息（也就是输入一个二维数组） for(i=0;i 数据结构实验报告 班级：06软件工程 姓名：周邓雄 学号：06517037 for(j=0;j printf(\请输入第%d行，第%d列的元素:\cin>>graph.arcs[i][j]; } } void vist(GraphMatrix graph) //函数用于实现访问任一景点的信息 { int i; cout< cout<<\你想知道哪个景点的信息：\注意输入的是景点的编号 cin>>i; cout< cout<<\景点信息查询结果为：\ cout< int jud() //用于判断是否继续执行特定的下一步程序 {int a; cout<<\还想继续查询?(1&0)\cin>>a; return a; } int main()
某数据结构课程设计公园导游图
