数据结构实验报告实验十一.docx
- 文档编号:1665473
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:18
- 大小:115.13KB
数据结构实验报告实验十一.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日内。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 报告 十一