某数据结构课程设计公园导游图_数据结构公园导游图
某数据结构课程设计公园导游图由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构公园导游图”。
数据结构实验报告
班级：06软件工程
姓名：周邓雄
学号：06517037
实验四：图（内容：某公园导游图）
一、问题描述：
公园导游系统：给出一张某公园的导游图，游客通过终端询问可知︰从某一景到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。
二、设计描述：
1.输入导游图的算法（存储方法）.本程序特地设计函数void initgraph()用于实现键盘输入图的结构；
2.可访问导游图中任一景点的算法.为此设计了函数void vist(GraphMatrix graph)用于实现访问任一景点的信息； 3.最短路径从一景点到另一景点的算法。利用floyd算法-实现每一对景点间的最短路径。并利用void outgraph()函数实现显示起始点和终点间的最短路径和其长度；
三、程序清单：
#include using namespace std;#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 n;i++)
for(j = 0;j 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 n;k++)
for(i = 0;i n;i++)
for(j = 0;j 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
//输入要查找起始点和终点（本程序限于编号（int型））cout>c;cin>>b;i=path.a[c][b];
//通过path.a[c][b]把路径长度赋给i 数据结构实验报告
班级：06软件工程
姓名：周邓雄
学号：06517037
cout
//输出路径长度 cout
//此处输出路径的第一个编号
c=path.nextvex[c][b];
for(;c!=b;c=path.nextvex[c][b])
//循环顺序输出路径始点和终点之间的景点编号 cout
//再输出路径的最后一个编号
cout
//该函数用于实现键盘输入图的结构 { int i,m,j;printf(“请输入公园景点的个数：”);
//图结点的个数赋给graph.n scanf(“%d”,&m);graph.n=m;for(i=0;i
//循环输入结点顶点信息 { printf(“请输入第%i个景点信息:”,i);//为了简明起见此程序结点顶点信息限于字符型 cin>>graph.vexs[i];} printf(“请输入公园的邻接矩阵的信息n”);//循环输入图的邻接矩阵信息（也就是输入一个二维数组）for(i=0;i
班级：06软件工程
姓名：周邓雄
学号：06517037
for(j=0;j
printf(“请输入第%d行，第%d列的元素:”,i+1,j+1);cin>>graph.arcs[i][j];} } void vist(GraphMatrix graph)
//函数用于实现访问任一景点的信息 {
int i;
cout
cout
cin>>i;
cout
cout
cout
cout
//用于判断是否继续执行特定的下一步程序 {int a;cout>a;return a;} int main()数据结构实验报告
班级：06软件工程
姓名：周邓雄
学号：06517037
{
int i,j;
initgraph();
//initgraph()函数来实现键盘输入图的结构
floyd(&graph, &path);
cout
for(i = 0;i
{
for(j = 0;j
//为了验证下面运算结果的方便，循环输出nextvex[i][j]数组
printf(“%d ”, path.nextvex[i][j]);
//nextvex[i][j]存放vi到vj最短路径上vi的后继顶点的下标值
putchar('n');
}
cout
outgraph();
while(jud())
outgraph();
//outgraph()函数用于实现显示起始点和终点间的最短路径和其长度
vist(graph);
//函数用于实现访问任一景点的信息
cout
while(jud())
vist(graph);
cout
return 0;} 数据结构实验报告
班级：06软件工程
姓名：周邓雄
学号：06517037
验四：图（内容：某公园导游图）
.问题描述 ①
给出一张某公园的导游图，游客通过终端询问可知：
（1）从某一景点到另一景点的最短路径。
（2）游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览景点，最后回到出口（出口就在入口处旁边）。
.要求 ②
将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值给游客。
.实现提示 ③
（1）第一问实际是最短路径问题，如果有几条路径长度相同，可选择途径景点较少的路径提供给游客。
（2）第二问可采用深度优先搜索，如果有多种路径可选择，则选择带权路径最小的路线提供给游客。
.选做内容 ④
可以把各种路径都显示给游客，由游客自己选择游览路线。数据结构实验报告
班级：06软件工程
姓名：周邓雄
学号：06517037
课程设计任务书2013～2014学年第 1 学期学生姓名：专业班级：2012网络工程（1）班 指导教师：冯珊工作部门：计算机学院一、课程设计题目: 公园导游图二、课程设计内容给出一张某公园的导......
课 程 设 计 任 务 书信息 学院 信息管理与信息系统 专业 09级1班 班 孙鹏一、二、课程设计题目： 迷宫求解、一元多项式 课程设计主要参考资料： 数据结构（C语言版） 严蔚敏、吴伟......
数据结构课程设计题目（2013年）一、必做题 1、图书管理系统（线性表） [问题描述]设计一个程序，记录并统计图书使用情况。 [基本要求] （1）图书信息包括图书ID号，图书名，出版社名，出版年月......
课程设计题目1、运动会分数统计任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或......
《数据结构》课程设计报告学 号 姓 名 班 级 指导教师XXX XXX XXX XXX 安徽工业大学计算机学院2014年6月利用栈实现迷宫问题的求解一、问题描述以一个M*N的长方阵表示迷宫，0......
