数据结构课程设计报告最短路径拯救(共22页).doc

《数据结构课程设计报告最短路径拯救(共22页).doc》由会员分享，可在线阅读，更多相关《数据结构课程设计报告最短路径拯救(共22页).doc（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上数据结构课程设计报告最短路径：拯救007专业物联网工程学生姓名班级学号指导教师完成日期2016年1月13日专心-专注-专业目 录数据结构程序课程的设计1、 课程设计目的及要求 1）设计题目看过007系列电影的人们一定很熟悉James Bond这个世界上最著名的特工了。在电影“Live and Let Die”中James Bond被一组毒品贩子抓住并且关到湖中心的一个小岛上，而湖中有很多凶猛的鳄鱼。这时James Bond做出了最惊心动魄的事情来逃脱他跳到了最近的鳄鱼的头上，在鳄鱼还没有反应过来的时候，他又跳到了另一只鳄鱼的头上最后他终于安全地跳到了湖岸上。假设湖是1

2、00100的正方形，设湖的中心在（0，0），湖的东北角的坐标是（50，50）。湖中心的圆形小岛的圆心在（0，0），直径是15。一些凶猛的鳄鱼分布在湖中不同的位置。现已知湖中鳄鱼的位置（坐标）和James Bond可以跳的最大距离，请你告诉James Bond一条最短的到达湖边的路径。他逃出去的路径的长度等于他跳的次数。2）输入要求程序从“input.txt”文件中读取输入信息，这个文件包含了多组输入数据。每组输入数据的起始行中包含两个整数n和d，n是鳄鱼的数量而且n100，d是007可以跳的最大距离而且d0。起始行下面的每一行是鳄鱼的坐标（x，y），其中x, y都是整数，而且没有任何两只鳄鱼出

3、现在同一个位置。input.txt文件以一个负数结尾。3）输出要求程序输出结果输出到output.txt文件中。对于每组输入数据，如果007可以逃脱，则输出到output.txt文件的内容格式如下：第一行是007必须跳的最小的步数，然后下面按照跳出顺序记录跳出路径上的鳄鱼坐标（x，y），每行一个坐标。如果007不可能跳出去，则将-1写入文件。如果这里有很多个最短的路径，只需输出其中的任意一种2、课题总体设计2.1设计分析1.明确题目中的已知条件(1)007被关的小岛在湖的中心；(2)小岛是圆形，圆心在（0，0），而且直径是15；(3)没有两只鳄鱼在同一个位置；(4)鳄鱼的坐标值都是整数。2.一

4、些判断007是否能跳出的细节(1)判断007是否能够直接从岛上跳到湖岸：由已知条件可得，湖是一个正方形，边长为100，中心是在（0，0），四个顶点分别是（50，50）,(50,-50),(-50,-50),(-50,50)。而湖中小岛的直径是15.所以如果007可以跳大于等于（50-15/2）=42.5，他就可以直接从小岛跳到湖岸，而不用经过鳄鱼。(2)判断007是否能够直接从岛上跳到湖中点A：已知半径是7.5，假设点A的坐标是（x,y），007的步长是L，则当点A到中心（0，0）的距离小于等于007的步长加上小岛的半径7.5的时候就能确定007可以从岛上跳到点A，即：x*x+y*y=(L+7

5、.5)*(L+7.5)。(3)判断007是否能够从点A跳到点B：假设007的步长是L所以如果两点之间的距离小于等于L，则判断007可以从A跳到B，即（A.x-B.x）2+(A.y-B.y)2=50或|A.y|+L=50；其他情况时007不能从A点跳到湖岸。 2. 系统流程图开始初始化路径能否直接跳出？跳出有无鳄鱼？能否从岛上跳上该点？记录该点能否跳出该点？记录该点插入该点，检测下一点结束判断能否跳出，并比其他短3、详细设计 主要数据结构与算法： 为了记录007跳过的路径，可定义为如下结构：typedef unsigned int Vertez;typedef double Distance;t

6、ypedef struct GraphNodeRecordint X; /*x轴坐标*/int Y; /*y轴坐标*/unsigned int Step; /*记录到本节点一共跳了多少步*/Vertex Path; /*指向本节点的父节点，即跳到本节点之间007所在节点*/GraphNode;typedef GraphNode*Grapha;寻找跳出路径的算法：/*读出一组测试数据返回007跳过的路径Graph，*Bank记录最短到达湖岸的路径。该算法实际上是应用队列对图惊醒广度搜索，以寻找到岸边的最短路径，其中入队列与出队列函数分别是Inject()和Pop()*/Graph read_ca

7、se(FILE * InFile,int num,Vertex* Bank,Deque D) Graph G=NULL; Distance JamesJump; Vertex V; int x,y; int i,Times; *Bank = 0; /*初始化跳出的路径的记录*/ fscanf(Infile,”%lf”,&JamesJump);/*读取步长*/ if(Bond can jumo to the bank directly) *Bank=1; /*直接跳出的情况*/ else if (num0) /*007必须经过鳄鱼头上的情况*/ num+=2; G=GraphNew”(num);

8、 for(i=2;inum;i+) /*第3个node开始是鳄鱼*/ if(Bond can jump to Gi from island) /*判断是否能从岛上跳上该点*/ Gi.Path=1; Gi.Step=1; /*一步*/ if(Bond can jump to bankfrom Gi) /*判断该点是否能跳出*/ *Bank =i; /*007可以跳出，记录该点*/ Skip other crocodile break; else Inject(i,D);/*插入该点，并开始下一个检测*/while(!IsEmpty(D) /*只经过一只鳄鱼无法跳出，必须还要跳到其他鳄鱼的情况*/

9、 V=Pop(D);for(i=2;istep of v+1) Gi.Path=V; Gi.Step= GV.Step+1;/*把i点练到v点后面*/ if(bond can jump from ito bank and the path is shorter than others) *Bank=i; else Inject(i,D); return G;在执行完算法read_case后，*Bank值可能如下3种可能：（1）0，意味着007无法逃脱出去；（2）1，意味着007可以直接从岛上跳出去，而不用经过鳄鱼的脑袋；（3）k，返回的第k点是007经过最短路径逃出鳄鱼潭是经过的最后一个顶点。

10、可以根据Gk的path参数来追踪该点的上一点，由此类推可以得到007逃脱的最短路径。4、图像文件5、调试与测试5.1）调试打开工程文件，如图1所示：（图一打开工程）运行，出现如图2所示：（图二运行）5.2）测试方法：007步长很大，以至于可以直接跳出，例如：431007不可能逃出去的情况（根本就没有鳄鱼），例如：11一般情况的例子，例如：4 1017 027 037 045 01020 30 1最短路径有多条，只需要输出任意一种即可，例如：25 108 89 910 1011 1112 1213 1314 1415 1516 1618 1820 2023 2325 2527 2728 2829

11、 2931 3133 3335 3538 3841 4144 4446 4647 4749 49 输出结果：79 916 1623 2328 2835 3541 41input.txt文件中，名称不正确、空文件、缺少部分输入等不规范情况，例如：5 1010 10-25 3030 30注：缺少鳄鱼点（应有5个鳄鱼点）和文件结尾符（-1）。下面给出一个较复杂的测试用例和期望输出结果。65 108 109 811 1011 1412 1216 1318 1514 1815 2215 1516 2316 3018 1818 3520 2023 23 25 3727 2728 4029 2231 31（

12、转右行）33 3335 1840 1538 3841 4124 4844 4446 4647 4749 49-49 -19-40 -18-44 -10-39 -5-38 0-32 5-32 0-28 11-25 7-18 0-17 -2-19 3（转右行）-12 0-10 -10-13 -1318 -2520 -4811 -22-29 18-40 40-40 -4040 -4049 -4935 -3727 -3022 -2214 -228 -1010 -18-23 29-20 20-21 23-18 19-10 15-10期望输出结果：78 1016 1320 2027 2731 3128 4

13、05.3）测试：在input输入测试数据，如图3所示：（图3 输入测试数据）5.4）测试的结果：在output查看测试结果，如图4所示：（图4 测试结果）6、小 结经过这次的课程设计，我很深刻的意识到自己的编程能力还有待提高，发现自己还存在很多不会的问题，有些细节问题没有注意到，还得学会冷静思考，加强算法和C语言语法的学习。其中对英语的要求也体现出来了，因为它说明错误的时候都是英语，遇到问题要及时去查相关的资料。反复的调试程序，最好是多找几个同学来对你的程序进行调试并听他说对你的程序的建议。要形成自己的编写程序与调试程序的风格，从每个细节出发，不放过每个知识点，注意与理论的联系和理论与实践的差

14、别。另外，得注意符号的使用，注意对字符的处理，特别是对指针的使用时很容易出错且调试过程不会报错，但最后的结果却不是你想要的。程序在完成之后，当时你调试运行时没有错误，可能错误就恰好隐藏在你没有检查的地方，要更全面的检查，特别是几个选择合起来一起挨个执行一遍。通过进一周的学习实训和课程设计，又一次体验了离开课堂的理论学习，做了一次真正实践与理论相结合的连接。特别是所做的题目基本都不是课堂上所讲的例子，但却是每一步都是用到课堂的内容。实训让我对懂得的知识做了进一步深入了解，让我对其的理解与记忆更深刻，对不懂的知识与不清楚的东西也做了一定的了解，也形成了一定的个人编程风格。在这次的课程设计中，学到了

15、许多新的知识，比如还知道了除了标准库外其他函数的用法，知道程序的框架对于写一个完整的程序来说是很重要的，写出了大体框架就等于完成了一半程序，但不管怎么样，继续努力也是必不可少的。7、参考文献【1】数据结构课程设计 何钦铭 冯雁 陈越 著 浙江大学出版社 2015-2【2】数据结构（C语言版） 著 2011-118、源程序清单#include Graph.h#include Deque.h#include error.h#include #include /*读入一个case返回一个Graph，*Bank 记录最短到达河岸的路径*/Graph read_case(FILE *InFile, in

16、t num, Vertex* Bank, Deque D)Graph G = NULL;Distance JamesJump;Vertex V;int x, y;int i, Times;*Bank = 0;fscanf(InFile, %lf, &JamesJump);if(CheckForEnd(0, 0, JamesJump + ISLAND_DIAMETER/2.0)for(i = 0; i (num 0) /* 007必须经过鳄鱼头上的情况 */num += 2;G = GraphNew(num);for(i = 2; i num; i+) /* 第三个node开始是鳄鱼 */fsc

17、anf(InFile, %d, &x);fscanf(InFile, %d, &y);Gi.X = x;Gi.Y = y;if(CheckForStart(x, y, JamesJump) /*判断是否能跳上该点*/Gi.Path = 1; /*007可以跳到 */Gi.Step = 1; /* 一步 */if(CheckForEnd(x, y, JamesJump) /* 判断该点是否能跳出 */*Bank = i; /* 007可以跳出 */Times = (num - i - 1) 1;for(i = 0; i Times; i+) /* 不必检验其他鳄鱼 */fscanf(InFile

18、, %d, &y);DequeClear(D);break;elseInject(i, D); /* 插入该点，并开始下一个检测 */while(!IsEmpty(D) /*只经过一个鳄鱼无法跳出，必须还要跳到其它鳄鱼的情况 */V = Pop(D);for(i = 2; i GV.Step + 1)& CheckForConnect(G, V, i, JamesJump)Gi.Path = V;Gi.Step = GV.Step + 1;if(Gi.Step G*Bank.Step)& CheckForEnd(Gi.X, Gi.Y, JamesJump)*Bank = i;elseInjec

19、t(i, D);return G;/*写出结果，即最短路径*/void write_result(FILE *OutFile, Vertex Bank, Graph G, Deque D)unsigned int Times, i;Vertex V;switch(Bank)case 0: /* 007无法跳出 */fprintf(OutFile, %dn, -1);break;case 1: /* 007可以直接跳出 */fprintf(OutFile, %dn, 1);break;default: Times = GBank.Step + 1;/* 跳的步数 */while(Bank !=

20、1)/* 跟踪路径 */Push(Bank, D);Bank = GBank.Path;fprintf(OutFile, %dn, Times);/* 输出 */for(i = 1; i Times; i+)V = Pop(D);fprintf(OutFile, %d , GV.X);fprintf(OutFile, %dn, GV.Y);int main(int argc, char *argv)FILE *in, *out;Deque D;int VertexNum;Graph G = NULL;Vertex Bank = 0;in = fopen(input.txt, r);if(NUL

21、L = in)fprintf(stderr, Can not open input.txt);exit(-1);out = fopen(output.txt, w);if(NULL = out)fprintf(stderr, Can not open output.txt);fclose(in);exit(-1);D= DequeNew();while(EOF != fscanf(in, %d, &VertexNum) & (0 = VertexNum)G = read_case(in, VertexNum, &Bank, D); /* 读文件直到结尾 */write_result(out, Bank, G, D);if(G)GraphDelete(G);fclose(in);fclose(out);DequeDelete(D);return 0;