资源描述：
《数据结构课程设计--最短路径：拯救》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、数据结构课程设计报告（2011）数据结构课程设计报告(2011--2012年度第1学期)最短路径：拯救007专业计算机科学与技术（网络工程）学生姓名赵宝文班级B计算机102学号1010704227指导教师田明完成日期2012年1月14日1数据结构课程设计报告（2011）目录1概述11.1课程设计目的11.2课程设计内容12系统需求分析22.1系统目标22.2主体功能22.3开发环境23系统需求分析23.1设计分析23.2系统功能模块划分34测试34.1测试方案34.2测试结果45分析与探讨55.1测试结果分析
2、55.2探讨与改进56小结5参考文献6附录7附录Ⅰ7附录Ⅱ113数据结构课程设计报告（2011）最短路径:拯救0071概述1.1课程设计目的图结构是一种较为复杂的数据结构。对图结构最主要、最基本的操作是图的遍历。典型的遍历方法主要是深度遍历与广度遍历，即深度优先搜索和广度优先搜索。图结构也是一种具有广泛应用的数据结构。图的应用问题主要可归结为：求图中顶点间的最短路径、图的关键路径、图的拓扑排序、图的最小生成树等。本课程设计通过“拯救007”案例回顾图的最短路径的基本知识和基本方法。1.2课程设计内容看过007
3、系列电影的人们一旦很熟悉JanesBond这个世界上最著名的特工了。在电影“LiveandLetDie”中JamesBond被异族毒贩子捉住并且关单哦湖中心的一个小岛上，而湖中有很多凶猛的鳄鱼。这时JamesBond做出了最惊心动魄的事情来逃脱——他跳到了最近的鳄鱼头上，在鳄鱼还没有反应过来的时候，他又跳到；额另一只鳄鱼的头上……最后他终于安全的跳到了湖岸上。假设湖是100*100的正方形，设湖的中心在(0,0),湖的东北角的坐标是(50,50)。湖中心的原型小岛的圆心在(0,0),直径是15。一些凶残的鳄鱼
4、分布在湖中不同的位置。现已知湖中鳄鱼的位置(坐标)和JamesBond可以调的最大距离，请你告诉JamesBond一条最短的到达湖边的路径。他逃出去的路径长度等于他跳的次数。输入要求：程序从“input.txt”，文件中读取输入信息，这个文件包含了多组输入数据。每组输入数据的起始行中包含两个整数n和d，n是鳄鱼的数量而且n≤100，d是007可以跳的最大距离而且d>0。起始行下面的每一行是鳄鱼的坐标(x，y)，其中x，y都是整数，而且没有任何两只鳄鱼出现在同一个位置。input.txt文件以一个负数结尾。输出
5、要求：程序结果输出到output.txt文件中。对于每组输人数据，如果007可以逃脱，则输出到output.txt文件的内容格式如下：第一行是007必须跳的最小的步数，然后下面按照跳出顺序记录跳出路径上的鳄鱼坐标(x，y)，每行一个坐标。如果007不可能跳出去，则将-1写人文件。如果这里有很多个最短的路径，只需输出其中的任意一种。输入例子：410/*第一组输人数据*/21数据结构课程设计报告（2011）170270370450110/*第二组输入数据*/2030-1输出例子：5/*对应第一组数据的输出*/17
6、0270370450-1/*对应第二组数据的输出*/2系统需求分析2.1系统目标告诉JamesBond一条最短的到达湖边的路径。2.2主体功能假设湖是100*100的正方形，设湖的中心在(0,0),湖的东北角的坐标是(50,50)。湖中心的原型小岛的圆心在(0,0),直径是15。一些凶残的鳄鱼分布在湖中不同的位置。现已知湖中鳄鱼的位置(坐标)和JamesBond可以调的最大距离，请你告诉JamesBond一条最短的到达湖边的路径。他逃出去的路径长度等于他跳的次数。2.3开发环境VC++6.03系统需求分析3.
7、1设计分析1.明确题目中的已知条件(1)007被关的小岛在湖的中心；(2)小岛是圆形，圆心(0,0),而且直径是15；(3)没有两只鳄鱼在同一位置；(4)鳄鱼的坐标值都是整数。2.一些判断007是否跳出的细节21数据结构课程设计报告（2011）(1)判断007是否能够直接从岛上跳到湖岸：由已知条件可得，湖是一个正方形，变长为100，中心是在(0,0),四个顶点分别是(50,50),(50,-50),(-50,-50),(-50,50)。而湖中小岛的直径是15.所以如果007可以跳大于(50-15/2)=42.
8、5,他就可以直接从小岛跳到湖岸，而不是经过鳄鱼。(2)判断007是否能够从岛上跳到湖中点A：已知小岛的半径是7.5，假设点A的坐标是(x,y),007的步长是L，则当点A到中心的(0,0)的距离小于等于007的步长加上小岛的半径7.5的时候就能确定007可以从岛上跳到点A，即(3)判断007是否能从点A跳到点B：假设007的步长是L，所以如果两点之间的距离小于等于L，则判断007可以冲A跳到B，即；
