1、 数据结构数据结构课程设计报告课程设计报告 ( 2011 - 2012 年度第年度第 1 学期学期) 最短路径：拯救最短路径：拯救007007 专业专业 计算机科学与技术（网络工程）计算机科学与技术（网络工程） 学生姓名学生姓名 班级班级 学号学号 指导教师指导教师 完成日期完成日期 2012 年年 1 月月 14 日日 最短路径：拯救 007 目目 录录 1 概 述 1 1.1 课程设计目的 1 1.2 课程设计内容 1 2 系统需求分析 2 2.1 系统目标 2 2.2 主体功能 2 2.3 开发环境 2 3 系统需求分析 2 3.1 设计分析 . 2 3.2 系统功能模块划分 . 3 4
2、 测试 3 4.1 测试方案 3 4.2 测试结果 4 5 分析与探讨 . 5 5.1 测试结果分析 5 5.2 探讨与改进 5 6 小结 5 参考文献. 6 附 录. 7 附录 7 附录 11 数据结构课程设计报告（2011） 1 最短路径最短路径: :拯救拯救007007 1 概 述 1.1 课程设计目的 图结构是一种较为复杂的数据结构。对图结构最主要、最基本的操作是图的遍 历。 典型的遍历方法主要是深度遍历与广度遍历， 即深度优先搜索和广度优先搜索。 图结构也是一种具有广泛应用的数据结构。图的应用问题主要可归结为：求图中顶 点间的最短路径、图的关键路径、图的拓扑排序、图的最小生成树等。本
3、课程设计 通过“拯救 007”案例回顾图的最短路径的基本知识和基本方法。 1.2 课程设计内容 看过007系列电影的人们一旦很熟悉Janes Bond这个世界上最著名的特工了。 在电影“Live and Let Die”中James Bond被异族毒贩子捉住并且关单哦湖中心的 一个小岛上，而湖中有很多凶猛的鳄鱼 。这时James Bond做出了最惊心动魄的事 情来逃脱他跳到了最近的鳄鱼头上， 在鳄鱼还没有反应过来的时候， 他又跳到； 额另一只鳄鱼的头上最后他终于安全的跳到了湖岸上。 假设湖是100*100的正方形，设湖的中心在(0,0),湖的东北角的坐标是 (50,50)。湖中心的原型小岛的圆
4、心在(0,0),直径是15。一些凶残的鳄鱼分布在湖 中不同的位置。现已知湖中鳄鱼的位置(坐标)和James Bond可以调的最大距离，请 你告诉James Bond一条最短的到达湖边的路径。他逃出去的路径长度等于他跳的次 数。 输入要求： 程序从“input.txt”，文件中读取输入信息，这个文件包含了多组输入数据。每组 输入数 据的起始行中包含两个整数 n和 d，n是鳄鱼的数量而且 n100，d 是 007 可以跳的最大距离而且 d0。起始行下面的每一行是鳄鱼的坐标(x，y)，其中 x，y 都是整数，而且没有任何两只鳄鱼出现在同一个位置。input.txt 文件以一个负数结 尾。 输出要求：
5、 程序结果输出到 output.txt 文件中。对于每组输人数据，如果 007 可以逃脱， 则输出到 output.txt 文件的内容格式如下：第一行是 007 必须跳的最小的步数，然 后下面按照跳出顺序记录跳出路径上的鳄鱼坐标(x，y)，每行一个坐标。如果 007 不可能跳出去，则将-1 写人文件。如果这里有很多个最短的路径，只需输出其中的 任意一种。 输入例子： 最短路径：拯救 007 2 4 10 /*第一组输人数据*/ 17 0 27 0 37 0 45 0 1 10 /*第二组输入数据*/ 20 30 -1 输出例子： 5 /*对应第一组数据的输出*/ 17 0 27 0 37 0
6、45 0 -1 /*对应第二组数据的输出*/ 2 系统需求分析 2.1 系统目标 告诉 James Bond 一条最短的到达湖边的路径。 2.2 主体功能 假设湖是 100*100 的正方形，设湖的中心在(0,0),湖的东北角的坐标是 (50,50)。湖中心的原型小岛的圆心在(0,0),直径是 15。一些凶残的鳄鱼分布在湖 中不同的位置。现已知湖中鳄鱼的位置(坐标)和 James Bond 可以调的最大距离， 请你告诉 James Bond 一条最短的到达湖边的路径。他逃出去的路径长度等于他跳 的次数。 2.3 开发环境 VC+6.0 3 系统需求分析 3.1 设计分析 1.明确题目中的已知条件 (1)007被关的小岛在湖的中心； (2)小岛是圆形，圆心(0,0),而且直径是15； (3)没有两只鳄鱼在同一位置； (4)鳄鱼的坐标值都是整数。 数据结构课程设计报告（2011） 3 2.一些判断007是否跳出的细节 (1)判断007是否能够直接从岛上跳到湖岸：
