数据结构课程设计报告 最短路径：拯救007

数据结构课程设计报告最短路径：拯救007专业物联网工程学生姓名班级学号指导教师完成日期2016年1月13日目录1、课程设计目的及要求.................................................................................................12、课题总体设计............................................................................................................23、详细设计....................................................................................................................44、图像文件....................................................................................................................75、调试与测试..............................................................................................................106、小结......................................................................................................................107、参考文献..................................................................................................................168、源程序清单..............................................................................................................17数据结构程序设计1数据结构程序课程的设计1、课程设计目的及要求1）设计题目看过007系列电影的人们一定很熟悉JamesBond这个世界上最著名的特工了。在电影“LiveandLetDie”中JamesBond被一组毒品贩子抓住并且关到湖中心的一个小岛上，而湖中有很多凶猛的鳄鱼。这时JamesBond做出了最惊心动魄的事情来逃脱——他跳到了最近的鳄鱼的头上，在鳄鱼还没有反应过来的时候，他又跳到了另一只鳄鱼的头上……最后他终于安全地跳到了湖岸上。假设湖是100×100的正方形，设湖的中心在（0，0），湖的东北角的坐标是（50，50）。湖中心的圆形小岛的圆心在（0，0），直径是15。一些凶猛的鳄鱼分布在湖中不同的位置。现已知湖中鳄鱼的位置（坐标）和JamesBond可以跳的最大距离，请你告诉JamesBond一条最短的到达湖边的路径。他逃出去的路径的长度等于他跳的次数。2）输入要求程序从“input.txt”文件中读取输入信息，这个文件包含了多组输入数据。每组输入数据的起始行中包含两个整数n和d，n是鳄鱼的数量而且n≤100，d是007可以跳的最大距离而且d0。起始行下面的每一行是鳄鱼的坐标（x，y），其中x,y都是整数，而且没有任何两只鳄鱼出现在同一个位置。input.txt文件以一个负数结尾。3）输出要求程序输出结果输出到output.txt文件中。对于每组输入数据，如果007可以逃脱，则输出到output.txt文件的内容格式如下：第一行是007必须跳的最小的步数，然后下面按照跳出顺序记录跳出路径上的鳄鱼坐标（x，y），每行一个坐标。如果007不可能跳出去，则将-1写入文件。如果这里有很多个最短的路径，只需输出其中的任意一种最短路径：拯救00722、课题总体设计2.1设计分析1.明确题目中的已知条件(1)007被关的小岛在湖的中心；(2)小岛是圆形，圆心在（0，0），而且直径是15；(3)没有两只鳄鱼在同一个位置；(4)鳄鱼的坐标值都是整数。2.一些判断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)*(L+7.5)。(3)判断007是否能够从点A跳到点B：假设007的步长是L所以如果两点之间的距离小于等于L，则判断007可以从A跳到B，即（A.x-B.x）^2+(A.y-B.y)^2=L*L；其他情况时007不能从A点跳到B点。(4)判断007是否能够从点A跳到湖岸：当从A点到湖岸的距离小于等于007的步长的时候，说明他可以从A点跳到湖岸，|A.x|+L=50或|A.y|+L=50；其他情况时007不能从A点跳到湖岸。数据结构程序设计32.２系统流程图开始初始化路径能否直接跳出？有无鳄鱼？能否从岛上跳上该点？能否跳出该点？记录该点插入该点，检测下一点判断能否跳出，并比其他短跳出记录该点结束ＹＹＹＹＹＮＮＮＮＮ最短路径：拯救00743、详细设计主要数据结构与算法：为了记录007跳过的路径，可定义为如下结构：typedefunsignedintVertez;typedefdoubleDistance;typedefstructGraphNodeRecord{intX;/*x轴坐标*/intY;/*y轴坐标*/unsignedintStep;/*记录到本节点一共跳了多少步*/VertexPath;/*指向本节点的父节点，即跳到本节点之间007所在节点*/}GraphNode;typedefGraphNode*Grapha;寻找跳出路径的算法：/*读出一组测试数据返回007跳过的路径Graph，*Bank记录最短到达湖岸的路径。该算法实际上是应用队列对图惊醒广度搜索，以寻找到岸边的最短路径，其中入队列与出队列函数分别是Inject()和Pop()*/Graphread_case(FILE*InFile,intnum,Vertex*Bank,DequeD){GraphG=NULL;DistanceJamesJump;VertexV;intx,y;inti,Times;*Bank=0;/*初始化跳出的路径的记录*/fscanf(Infile,”%lf”,&JamesJump);/*读取步长*/if(Bondcanjumotothebankdirectly){*Bank=1;/*直接跳出的情况*/}elseif(num0)/*007必须经过鳄鱼头上的情况*/数据结构程序设计5{num+=2;G=GraphNew”(num);for(i=2;inum;i++)/*第3个node开始是鳄鱼*/{if(BondcanjumptoG[i]fromisland)/*判断是否能从岛上跳上该点*/{G[i].Path=1;G[i].Step=1;/*一步*/if(BondcanjumptobankfromG[i])/*判断该点是否能跳出*/{*Bank=i;/*007可以跳出，记录该点*/Skipothercrocodilebreak;}elseInject(i,D);/*插入该点，并开始下一个检测*/}}while(!IsEmpty(D))/*只经过一只鳄鱼无法跳出，必须还要跳到其他鳄鱼的情况*/{V=Pop(D);for(i=2;inum;i++)/*从这只鳄鱼跳到其他各只鳄鱼*/{if(bondcanjumpfromvtoi,andstepofistepofv+1){G[i].Path=V;G[i].Step=G[V].Step+1;/*把i点练到v点后面*/if(bondcanjumpfromitobankandthepathisshorterthanothers)*Bank=i;else最短路径：拯救0076Inject(i,D);}}}}returnG;}在执行完算法read_case后，*Bank值可能如下3种可能：（1）0，意味着007无法逃脱出去；（2）1，意味着007可以直接从岛上跳出去，而不用经过鳄鱼的脑袋；（3）k，返回的第k点是007经过最短路径逃出鳄鱼潭是经过的最后一个顶点。可以根据G[k]的path参数来追踪该点的上一点，由此类推可以得到007逃脱的最短路径。数据结构程序设计74、图像文件最短路径：拯救0078数据结构程序设计9最短路径：拯救007105、调试与测试5.1）调试打开工程文件，如图1所示：（图一．打开工程）数据结构程序设计11运行，出现如图2所示：（图二．运行）5.2）测试方法：•007步长很大，以至于可以直接跳出，例如：431•007不可能逃出去的情况（根本就没有鳄鱼），例如：11•一般情况的例子，例如：4101702703704501020301•最短路径有多条，只需要输出任意一种即可，例如：251088最短路径：拯救007129910101111121213131414151516161818202023232525272728282929313133333535383841414444464647474949输出结果：79916162323282835354141•input.txt文件中，名称不正确、空文件、缺少部分输入等不规范情况，例如：5101010-25303030注：缺少鳄鱼点（应有5个鳄鱼点）和文件结尾符（-1）。下面给出一个较复杂的测试用例和期望输出结果。数据结构程序设计136510810981110111412121613181514181522151516231630181818352020232325372727284029223131（转右行）3333351840153838414124484444464647474949-49-19-40-18-44-10-39-5-380-325-320-2811-257-180-17-2-193（转右行）-120-10-10-13-1318-2520-4811-22-2918-4040-40-4040-4049-4935-3727-3022-2214-228-1010-18-2329-2020-2123-1819-1015-10期望输出结果：7810161320202727313128405.3）测试：在input输入测试数据，如图3所示：（图3输入测试数据）最短路径：拯救007145.4）测试的结果：在output查看测试结果，如图4所示：（图4测试结果）数据结构程序设计156、小结经过这次的课程设计，我很深刻的意识到自己的编程能力还有待提高，发现自己还存在很多不会的问题，有些细节问题没有注意到，还得学会冷静思考，加强算法和C语言语法的学习。其中对英语的要求也体现出来了，因为它说明错误的时候都是英语，遇到问题要及时去查相关的资料。反复的调试程序，最好是多找几个同学来对你的程序进行调试并听他说对你的程序的建议。要形成自己的编写程序与调试程序的风格，从每个细节出发，不放过每个知识点，注意与理论的联系和理论与实践的差别。另外，得注意符号的使用，注意对字符的处理，特别是对指针的使用时很容