数据结构实验报告实验十一.docx

1、数据结构实验报告实验十一深 圳 大 学 实 验 报 告 课程名称： 数据结构实验与课程设计 实验项目名称： 实验十一：最短路径 学院： 计算机与软件学院 专业： 指导教师： 蔡平 报告人： 文成 学号： 2011150259 班级： 5 实验时间： 2012-11-12 实验报告提交时间： 2012-11-19 教务部制一、实验目的与要求：目的：1掌握图形结构的输入方法。2掌握图形结构的说明，创建及图的存储表示。3掌握最短路径算法原理。4掌握最短路径的实现方法。二、实验内容：校园导航问题一、问题描述：设计深圳大学的平面图，至少包括8个以上的场所，每两个场所间可以有不同的路，且路长也可能不同。1

2、（必做）找出从一个场所出发到达其它场所的最佳路径（最短路径）。2（选做）找出从任意场所到达另一场所的最佳路径（最短路径）。二、基本要求1、设计校园平面图，在校园景点选8个以上的景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。2、为来访客人提供图中任意景点相关信息的查询。3、为来访客人提供景点的问路查询，如查询从深大正门到各景点之间的最短路径。（必做）4、为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。（选做）5、界面要求：有合理提示；每个功能可以设立菜单；根据提示，可以完成相关的功能要求三、实验步骤与过程：程序总流

3、程：输出地点信息对应的邻接矩阵：1 2 3 4 5 6 7 8 1 0 max 15 max 4 max 9 max2 max max max max 2 2 max max 3 15 max max max 5 max max max 4 max max 10 max max max max max 5 4 max 5 max max max max 5 6 max 2 max max max max 3 max7 9 2 max max max 3 max max 8 max max max max 5 max 6 max 源代码：#include#include#include cons

4、t int max=99;const int Weight88=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;class scenerypublic: int No; char *name; char *introduction

5、; void scenerySet(int no,char *pname,char *pintroduction) No=no; name=pname; introduction=pintroduction; scenery() scenery();class SZUpublic: scenery place8; int weight88; int dist8; /存放源点到其它各点的最短路径 int path8; /存放在最短路径上该该顶点的前一顶点号 int s8; /已求得的在最短路径上的顶点的顶点号 void shortestPath(int start,int end) for(in

6、t i=0;i8;i+) disti=weightstarti; si=0; if (i!=start & distimax) pathi=start; else pathi=max; sstart=1;diststart=0; for(i=0;i8;i+) int min=max; int u=start; for(int j=0;j8;j+) if(!sj & distjmin) u=j; min=distj; su=1; for (int w=0;w8;w+) if(!sw & weightuwmax & distu+weightuwdistw) distw=distu+weightuw

7、; pathw=u; if(end!=start) coutplacestart.name到placeend.name最短路程为distend: ; int pre=pathend; coutendl路径为：; int tempmax,k=0; while(pre!=max) tempk=pre; pre=pathpre; k+; while(k-) coutplacetempk.name; coutplaceend.nameendl; else cout终点、始点为同一个地方！; SZU() place0.scenerySet(1,深大正门,深圳大学的正门); place1.sceneryS

8、et(2,深大北门,深圳大学北边的门); place2.scenerySet(3,深大南门,深圳大学南边的门); place3.scenerySet(4,南区学生宿舍,大部分11级工科学生居住的地方); place4.scenerySet(5,教学楼,学生上课的地方); place5.scenerySet(6,文科楼,学生强身健体的主要地方); place6.scenerySet(7,元平体育馆,深圳大学的正门); place7.scenerySet(8,科技楼,研究科技的楼); for(int i=0;i8;i+) for(int j=0;j8;j+) weightij=Weightij;

9、SZU();void main() cout正在启动校园导航系统，请稍后.endl;Sleep(1500); cout加载中.;Sleep(500);cout启动完毕endl;Sleep(300); cout欢迎使用校园导航系统！endl;Sleep(1000); SZU szu; cout*校园导航系统*nn; cout 1.景点信息查询nn; cout 2.景点问路查询nn; cout 3.退出系统nn; cout*请选择一个操作(1/2/3)*nendl; int chooseMenu; coutchooseMenu; while(1) switch(chooseMenu) case 1

10、: cout-景点信息查询-endl; cout 1.深大正门 2.深大北门endl; cout 3.深大南门 4.南区学生宿舍endl; cout 5.教学楼 6.文科楼endl; cout 7.元平体育馆 8.科技楼endl; cout 0.返回上级目录 endl; cout-endl; while(1) coutchoosescenery; if(choosescenery=1) coutszu.placechoosescenery-1.name 简介：szu.placechoosescenery-1.introductionendl; else if(choosescenery=0)

11、break; else cout输入不合法，请重新输入：endl; continue; break; case 2: cout-景点问路查询-endl; cout 1.深大正门 2.深大北门endl; cout 3.深大南门 4.南区学生宿舍endl; cout 5.教学楼 6.文科楼endl; cout 7.元平体育馆 8.科技楼endl; cout-endl; int start,end,flag; while(1) coutstart; coutend; if(start=1 & end=1) szu.shortestPath(start-1,end-1); else cout输入不合法

12、，请重新输入：endl; continue; cout继续查询请输入1，返回上级目录请输入0.flag; while(flag) if(flag=1) break; else cout输入不合法，请重新输入：flag; if(flag=0) break; break; case 3: cout正在退出系统endl; Sleep(100); cout.endl; Sleep(300); cout.endl; Sleep(300); cout.endl; Sleep(300); cout成功退出。endl; Sleep(100); cout谢谢使用！endl; exit(0); default:

13、cout输入不合法，请重新输入：endl; break; coutendlchooseMenu; 4、实验结果及数据处理分析：初始界面：退出：景点信息查询：景点问路查询：实验基本达到实验要求。五、实验结论： 程序实现了两点的最短路径查询和单点周边查询，满足设计的基本要求，考虑了返回、重输入等细节。 实验让我了解数据结构及其分类、数据结构与算法的密切关系； 熟悉各种基本数据结构及其操作，学会根据实际问题来选择数据结构； 掌握设计算法的步骤和分析方法； 掌握数据结构在排序和查找等常用算法中的应用。指导教师批阅意见：成绩评定： 指导教师签字： 年 月 日备注：注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。 2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。