数据结构实验报告实验十一.docx
《数据结构实验报告实验十一.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告实验十一.docx（18页珍藏版）》请在冰点文库上搜索。
数据结构实验报告实验十一
深圳大学实验报告
课程名称：
数据结构实验与课程设计
实验项目名称：
实验十一：
最短路径
学院：
计算机与软件学院
专业：
指导教师：
蔡平
报告人：
文成学号：
2011150259班级：
5
实验时间：
2012-11-12
实验报告提交时间：
2012-11-19
教务部制
一、实验目的与要求：
目的：
1．掌握图形结构的输入方法。
2．掌握图形结构的说明，创建及图的存储表示。
3．掌握最短路径算法原理。
4．掌握最短路径的实现方法。
二、实验内容：
校园导航问题
一、问题描述：
设计深圳大学的平面图，至少包括8个以上的场所，每两个场所间可以有不同的路，且路长也可能不同。
1．（必做）找出从一个场所出发到达其它场所的最佳路径（最短路径）。
2．（选做）找出从任意场所到达另一场所的最佳路径（最短路径）。
二、基本要求
1、设计校园平面图，在校园景点选8个以上的景点。
以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。
2、为来访客人提供图中任意景点相关信息的查询。
3、为来访客人提供景点的问路查询，如查询从深大正门到各景点之间的最短路径。
（必做）
4、为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。
（选做）
5、界面要求：
有合理提示；每个功能可以设立菜单；根据提示，可以完成相关的功能要求
三、实验步骤与过程：
程序总流程：
输出地点信息
对应的邻接矩阵：
12345678
10max15max4max9max
2maxmaxmaxmax22maxmax
315maxmaxmax5maxmaxmax
4maxmax10maxmaxmaxmaxmax
54max5maxmaxmaxmax5
6max2maxmaxmaxmax3max
792maxmaxmax3maxmax
8maxmaxmaxmax5max6max
源代码：
#include
#include
#include
constintmax=99;
constintWeight[8][8]={{0,max,15,max,4,max,9,max},
{max,0,max,max,max,2,2,max},
{15,max,0,10,5,max,max,max},
{max,max,10,0,8,max,max,max},
{4,max,5,max,0,max,max,5},
{max,2,max,max,max,0,3,max},
{9,2,max,max,max,3,0,6},
{max,max,max,max,5,max,6,0}};
classscenery
{
public:
intNo;
char*name;
char*introduction;
voidscenerySet（intno,char*pname,char*pintroduction）
{
No=no;
name=pname;
introduction=pintroduction;
}
scenery（）{}
~scenery（）{}
};
classSZU
{
public:
sceneryplace[8];
intweight[8][8];
intdist[8];//存放源点到其它各点的最短路径
intpath[8];//存放在最短路径上该该顶点的前一顶点号
ints[8];//已求得的在最短路径上的顶点的顶点号
voidshortestPath（intstart,intend）
{
for（inti=0;i<8;i++）
{
dist[i]=weight[start][i];
s[i]=0;
if（i!
=start&&dist[i]path[i]=start;
else
path[i]=max;
}
s[start]=1;dist[start]=0;
for（i=0;i<8;i++）
{
intmin=max;
intu=start;
for（intj=0;j<8;j++）
if（!
s[j]&&dist[j]{
u=j;
min=dist[j];
}
s[u]=1;
for（intw=0;w<8;w++）
if（!
s[w]&&weight[u][w]{
dist[w]=dist[u]+weight[u][w];
path[w]=u;
}
}
if（end!
=start）
{
cout<";
intpre=path[end];
cout<";
inttemp[max],k=0;
while（pre!
=max）
{
temp[k]=pre;
pre=path[pre];
k++;
}
while（k--）
{
cout<";
}
cout<}
else
cout<<"终点、始点为同一个地方！
！
";
}
SZU（）
{
place[0].scenerySet（1,"深大正门","深圳大学的正门"）;
place[1].scenerySet（2,"深大北门","深圳大学北边的门"）;
place[2].scenerySet（3,"深大南门","深圳大学南边的门"）;
place[3].scenerySet（4,"南区学生宿舍","大部分11级工科学生居住的地方"）;
place[4].scenerySet（5,"教学楼","学生上课的地方"）;
place[5].scenerySet（6,"文科楼","学生强身健体的主要地方"）;
place[6].scenerySet（7,"元平体育馆","深圳大学的正门"）;
place[7].scenerySet（8,"科技楼","研究科技的楼"）;
for（inti=0;i<8;i++）
for（intj=0;j<8;j++）
weight[i][j]=Weight[i][j];
}
~SZU（）{}
};
voidmain（）
{
cout<<"正在启动校园导航系统，请稍后..."<cout<<"加载中...";Sleep（500）;cout<<"启动完毕"<cout<<"欢迎使用校园导航系统！
"<SZUszu;
cout<<"*****************************校园导航系统*********************************\n\n";
cout<<"1.景点信息查询\n\n";
cout<<"2.景点问路查询\n\n";
cout<<"3.退出系统\n\n";
cout<<"*************************请选择一个操作（1/2/3）****************************\n"<intchooseMenu;
cout<<"请输入您要使用的功能：
";
cin>>chooseMenu;
while
（1）
{
switch（chooseMenu）
{
case1:
{
cout<<"------------------------景点信息查询-----------------------"<cout<<"1.深大正门"<<"2.深大北门"<cout<<"3.深大南门"<<"4.南区学生宿舍"<cout<<"5.教学楼"<<"6.文科楼"<cout<<"7.元平体育馆"<<"8.科技楼"<cout<<"0.返回上级目录"<cout<<"-----------------------------------------------------------"<while
（1）
{
cout<<"请输入您要查找的景点信息（输入0则返回）：
";
intchoosescenery;
cin>>choosescenery;
if（choosescenery<=8&&choosescenery>=1）
cout<"<elseif（choosescenery==0）
break;
else
{
cout<<"输入不合法，请重新输入：
"<continue;
}
}
break;
}
case2:
{
cout<<"------------------------景点问路查询-----------------------"<cout<<"1.深大正门"<<"2.深大北门"<cout<<"3.深大南门"<<"4.南区学生宿舍"<cout<<"5.教学楼"<<"6.文科楼"<cout<<"7.元平体育馆"<<"8.科技楼"<cout<<"-----------------------------------------------------------"<intstart,end,flag;
while
（1）
{
cout<<"请选择起点：
";
cin>>start;
cout<<"请选择终点：
";
cin>>end;
if（start<=8&&start>=1&&end<=8&&end>=1）
szu.shortestPath（start-1,end-1）;
else
{
cout<<"输入不合法，请重新输入：
"<continue;
}
cout<<"继续查询请输入1，返回上级目录请输入0."<cin>>flag;
while（flag）
{
if（flag==1）
break;
else
{
cout<<"输入不合法，请重新输入：
"<cin>>flag;
}
}
if（flag==0）
break;
}
break;
}
case3:
{
cout<<"正在退出系统"<Sleep（100）;
cout<<"............"<Sleep（300）;
cout<<"............"<Sleep（300）;
cout<<"............"<Sleep（300）;
cout<<"成功退出。
"<Sleep（100）;
cout<<"谢谢使用！
"<exit（0）;
}
default:
{
cout<<"输入不合法，请重新输入：
"<break;
}
}
cout<";
cin>>chooseMenu;
}
}
4、实验结果及数据处理分析：
初始界面：
退出：
景点信息查询：
景点问路查询：
实验基本达到实验要求。
五、实验结论：
程序实现了两点的最短路径查询和单点周边查询，满足设计的基本要求，考虑了返回、重输入等细节。
实验让我了解数据结构及其分类、数据结构与算法的密切关系；熟悉各种基本数据结构及其操作，学会根据实际问题来选择数据结构；掌握设计算法的步骤和分析方法；掌握数据结构在排序和查找等常用算法中的应用。
指导教师批阅意见：
成绩评定：
指导教师签字：
年月日
备注：
注：
1、报告内的项目或内容设置，可根据实际情况加以调整和补充。
2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。
升级会员 