数据结构拯救007

中国地质大学数据结构课程设计4号题：最短路径，拯救007班级：193121班姓名：杉学号：指导老师：2014年1月11日实训目的：通过具体的课程设计，熟悉数据结构中最基础和最重要的部分：单链表，及其各种操作和实际应用。在设计的过程中，掌握数据结构的思想，并运用于具体问题的解决之中。加深对数据结构课程中理论和实践相结合的认识。实训任务及要求：看过007系列电影的人们一定很熟悉JamesBond这个著名的特工。在电影”LiveandLetDie”中JamesBond被一组毒品贩子捉住并且关到湖中心的一个小岛上，而湖中有很多凶猛的鳄鱼。这时JamesBond做出了最惊心动魄的事情来逃脱——他跳到了最近的鳄鱼的头上，在鳄鱼还没有反应过来的时候，他又跳到了另一只鳄鱼的头上……最后他终于安全地跳到了湖岸上。假设湖是100×100的正方形，设湖的中心在(0,0)，湖的东北角的坐标是(50,50)。湖中心的圆形小岛的圆心在(0,0)，直径是15。一些凶残的鳄鱼分布在湖中不同的位置。现已知湖中鳄鱼的位置（坐标）和JamesBond可以跳的最大距离，请你告诉JamesBond一条最短的到达湖边的路径。他逃出去的路径的长度等于他跳的次数。要求：（1）输入要求：程序从文件中读取输入信息，文件中包括的多组输入数据。每组输入数据包括鳄鱼的数量、007可以跳的最大距离、鳄鱼的坐标（没有两只鳄鱼出现在同一个位置）。（2）输出要求：程序结果输出到文件中。对于每组输入数据，如果007可以逃脱，则输出007必须跳的最小的步数，然后按照跳出顺序记录跳出路径上的鳄鱼坐标；如果007不能逃脱，则输出-1到文件。算法的实现：程序的实现少不了必要的头文件，在这里我加入了一个以前从没用过的不是标准库里面的头文件。#includeiostream.h#includeconio.h#includestdlib.h#includestdio.h#defineISLAND_DIAMETER15/*小岛的直径*/#defineLAKE_BOUNDARY_X50/*小岛到湖边的距离，在x轴上*/#defineLAKE_BOUNDARY_Y50/*小岛到湖边的距离，在y轴上*/#defineINFINITY10000/*可以跳的步数的最大值*/航班信息拯救007源程序：#includeiostream.h#includeconio.h#includestdlib.h#includestdio.h#defineISLAND_DIAMETER15/*小岛的直径*/#defineLAKE_BOUNDARY_X50/*小岛到湖边的距离，在x轴上*/#defineLAKE_BOUNDARY_Y50/*小岛到湖边的距离，在y轴上*/#defineINFINITY10000/*可以跳的步数的最大值*/typedefunsignedintVertex;typedefdoubleDistance;typedefstructGraphNodeRecord{intX;/*x轴坐标*/intY;/*y轴坐标*/unsignedintStep;/*跳至该点的步数*/VertexPath;/*记录上一个点*/}GraphNode;typedefGraphNode*Graph;GraphGraphNew(intNodeNum);voidGraphDelete(GraphG);/*判断007是否能从起始处跳至该点(x,y)*/intCheckForStart(intx,inty,Distanced);/*判断007是否能从该点跳至河岸*/intCheckForEnd(intx,inty,Distanced);/*判断007是否能从点i跳至点j*/intCheckForConnect(Graphg,Vertexi,Vertexj,Distanced);typedefunsignedintElemType;/*在本程序中ElemType指定为int*//*链表形式*/typedefstructNodeRecord{ElemTypeElement;structNodeRecord*Next;/*指向下一个node*/}*Node;typedefstructDequeRecord{NodeFront,Rear;/*分别指向Deque的前后两个点*/}*Deque;DequeDequeNew();voidDequeDelete(DequeD);voidDequeClear(DequeD);intIsEmpty(DequeD);voidPush(ElemTypeX,DequeD);ElemTypePop(DequeD);voidInject(ElemTypeX,DequeD);#defineCHECK(X)if(NULL==(X))Error(Outofspace!!!)voidError(constchar*msg);voidWarning(constchar*msg);/******创建新的Graph******/GraphGraphNew(intNodeNum){GraphG;inti;if(NodeNum=0)returnNULL;G=(GraphNodeRecord*)malloc(NodeNum*sizeof(GraphNode));/*分配空间*/CHECK(G);for(i=0;iNodeNum;i++)/*初始化*/{G[i].X=0;G[i].Y=0;G[i].Step=INFINITY;G[i].Path=0;}returnG;}/******删除一个Graph)******/voidGraphDelete(GraphG){if(G)free(G);}/*******判断007是否能从起始处跳至该点(x,y)，步长是d******/intCheckForStart(intx,inty,Distanced){doublet;t=(ISLAND_DIAMETER+(d*2.0));return(x*x+y*y)=t*t/4.0;/*x^2+y^2=(ISLAND_DIAMETER/2.0+d)^2*/}/*******判断007是否能从该点跳至河岸，步长是d******/intCheckForEnd(intx,inty,Distanced){if(x0)x=-x;/*取x的绝对值*/if(y0)y=-y;/*取y的绝对值*/return(d=LAKE_BOUNDARY_X-x)/*由于湖是个正方形，只需检查这两个距离*/||(d=LAKE_BOUNDARY_Y-y);}/*******判断007是否能从点i跳至点j，步长是d******/intCheckForConnect(Graphg,Vertexi,Vertexj,Distanced){intx,y;x=g[i].X-g[j].X;y=g[i].Y-g[j].Y;returnx*x+y*y=d*d;}/******创建新的Deque******/DequeDequeNew(){DequeD;D=(DequeRecord*)malloc(sizeof(structDequeRecord));CHECK(D);D-Front=D-Rear=(NodeRecord*)malloc(sizeof(structNodeRecord));/*空的头*/CHECK(D-Front);D-Front-Element=0;/*初始化*/D-Rear-Next=NULL;returnD;}/******删除Deque******/voidDequeDelete(DequeD){if(D){while(D-Front){D-Rear=D-Front-Next;free(D-Front);D-Front=D-Rear;}free(D);}}/******DequeClear删除所有的节点除了头节点******/voidDequeClear(DequeD){if(D){while(D-Front-Next)/*删除第一个节点*/{D-Rear=D-Front-Next-Next;free(D-Front-Next);D-Front-Next=D-Rear;}D-Rear=D-Front;}}/******判断Deque是否为空******/intIsEmpty(DequeD){returnD-Front==D-Rear;}/******将X元素压占到D中******/voidPush(ElemTypeX,DequeD){NodeNewNode;NewNode=(NodeRecord*)malloc(sizeof(structNodeRecord));/*建立新的节点*/CHECK(NewNode);NewNode-Element=X;NewNode-Next=D-Front-Next;if(D-Front==D-Rear)/*如果D为空*/D-Rear=NewNode;D-Front-Next=NewNode;/*压栈*/}/******将第一个元素出栈******/ElemTypePop(DequeD){NodeTemp;ElemTypeItem;if(D-Front==D-Rear){Error(Dequeisempty);return0;}else{Temp=D-Front-Next;/*得到第一个元素*/D-Front-Next=Temp-Next;/*重置第一个元素*/if(Temp==D-Rear)/*如果只有一个元素*/D-Rear=D-Front;/*将D置空*/Item=Temp-Element;free(Temp);returnItem;}}/******插入元素X至D末尾******/voidInject(ElemTypeX,DequeD){NodeNewNode;NewNode=(NodeRecord*)malloc(sizeof(structNodeRecord));/*创建新节点*/CHECK(NewNode);NewNode-Element=X;NewNode-Next=NULL;D-Rear-Next=NewNode;D-Rear=NewNode;}/******打印错误信息，并退出程序******/voidError(constchar*msg){if(NULL!=msg)fprintf(stderr,%s\n,msg);exit(-1);}/******打印警告信息，但并不退出程序******/voidWarning(constchar*msg){if(NULL!=msg)fprintf(stderr,%s\n,msg);};/******读入一个case返回一个Graph，*Bank记录最短到达河岸的路径******/Graphread_case(FILE*InFile,intnum,Vertex*Bank,DequeD){GraphG=NULL;DistanceJamesJump;VertexV;intx,y;inti,Times;*Bank=0;fscanf(InFile,%lf,&JamesJump);if(CheckForEnd(0,0,JamesJump+ISLAND_DIAMETER/2.0)){for(i=0;i(num1);i++)/*一步便跳出的情况*/fscanf(InFile,%d,&x);*Bank=1;}elseif(num0)/*007必须经过鳄鱼头上的情况*/{num+=2;G=GraphNew(num);for(i=2;inum;i++)/*第三个node开始是鳄鱼*/{fscanf(InFile,%d,&x);fscanf(InFile,%d,&y);G[i].X=x;G[i].Y=y;if(CheckForStart(x,y,Ja