数据结构课程设计拯救007

1数据结构课程设计最短路径：拯救007专业XX学生姓名XX班级XX学号XX问题描述与分析课程设计目的图结构是一种较为复杂的数据结构。对图结构最主要、最基本的操作是图的遍历。典型的遍历方法主要是深度遍历和广度遍历，即深度优先搜索和广度优先搜索。图结构也是一种具有广泛应用的数据结构。图的应用问题主要可归结为：求图中顶点间的最短路径、图的关键路径、图的拓扑排序、图的最小生成树等。本课程设计通过“拯救007”案例回顾图的最短路径的基本知识和基本方法。课程设计内容看过007系列的电影的人们一定很熟悉JamsBond这个世界上最著名的特工了。在电影“LiveAndLetDie”中JamsBond被一组毒品贩子抓住并且关到湖中心的一个小岛上，而湖中有很多凶猛的鳄鱼。这时JamsBond做出了一个最惊心动魄的事情来逃脱——他跳到了最近的鳄鱼的头上，在鳄鱼还没有反映过来的时候，他有跳到另一支鳄鱼的头上······最后他终于安全地跳到了湖岸上。假设湖是100*100的正方形，设湖的中心在（0，0），湖的东北角的坐标是（50，50）。湖中心的圆环小岛的圆心在（0，0），直径是15.。一些凶残的鳄鱼分布在湖中不同的位置。现已知的湖中的鳄鱼的位置和JamsBond可以跳的最大距离，请你告诉JamsBondyitiao最短的到达湖边的路径。他逃出去的路径长度等于他跳的次数。程序从“input.txt”文件中读取输入信息，这个文件包含了多组输入数据。每组输入数据的起始行中包含了两个整数n和d，n是鳄鱼的数量而且n=100，d是007可以跳的最大距离而且d0。起始行下面的每一行是鳄鱼的坐标（x,y），其中x,y都是整数，而且没有任何两只鳄鱼出现在同一位置。Input.txt文件以一个负数结尾。输出要求：程序结果输出到output.txt文件中。对于每组输入数据，如果007可以逃脱，则输出到output.txt文件的内容格式如下：第一行是007必须跳的最小步数，然后按照跳出顺序记录跳出路径上的鳄鱼坐标（x,y），每行一个坐标。如果007不可能跳出去，则将-1写入文件。如果这里有很多个最短路径，只需输入其中的任意一种。输入例子：410/*第一组输入数据*/170270370450110/*第二组输入数据*/2030-1输出例子：5/*对应第一组数据的输出*/170270450-1/*对应第二组数据的输出*/提示：将每个鳄鱼看作图中的每一个顶点。如果007可以从A点跳到B点，则A和B之间就有一条边。设计分析31.明确题目中的已知条件（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是否能够从岛上跳到湖中点A7.5A的坐标是(x,y),007的步长是LA到中心的(0,0)的距离小于等于007的步长加上小岛的半径7.5的时候就能确定007可以从岛上跳到点A(3)判断007是否能从点A跳到点B007的步长是L离小于等于L007可以冲A跳到B007不能从A点跳到B点。(4)判断007是否能够从点AA点到湖岸的距离小于的ing与007A或007不能从A点跳到湖岸。主要数据结构与算法见附录Ⅰ。在执行完算法read_case*Bank值可能有如下3(1)0味着007(2)1,意味着007(3)k,返回的k点是007经过的最短路径掏出鳄鱼潭时经过的最后一个顶点。可以根据G[k]的path007逃脱的最短路径。3.2系统功能模块划分本程序包含3个头文件和4个CGraph.h、Graph.c、Deque.h、Deque.c、error.h、error.c、main.c。程序内容见附录Ⅱ。4测试4.1测试方案测试251088991010111112121313141415151616181820202121232325252727282829293131333335353838414144444646474749494.2测试结果79916162323282835354141实际输出799161623232828353541415分析与探讨5.1测试结果分析行数据合法性检测并进行相应的异常处理。5.2探讨与改进上的顶点数减1.经过的边数可能不同做最短距离。上述问题之时队无权图而言,有经过的权值之和定义为该路径的带全路径长度。把带权路径长度最短的那条路径6小结师的指导和同学的帮助。渐渐的自己独立思考的能力。5参考文献[1].C[M].2004[2]严蔚敏.C.2004[3].《数据结构与算法》.2004[4]徐孝凯..2006附录附录Ⅰ为了记录007typedefunsignedintVertanca;typedefdoubleDistanca;typedefstructGraphNodeRecord{intx;inty;unsignedintStep;VerexPath;}GraphNode;TypedefGrahNode*Graph;/*读入一组测试数据返回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(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,JamesJump))/*判断是否能跳上该点*/{G[i].Path=1;/*007可以跳到*/G[i].Step=1;/*一步*/if(CheckForEnd(x,y,JamesJump))/*判断该点是否能跳出*/{*Bank=i;/*007可以跳出*/Times=(num-i-1)1;for(i=0;iTimes;i++)/*不必检验其他鳄鱼*/fscanf(InFile,%d,&y);DequeClear(D);break;}elseInject(i,D);/**/}}while(!IsEmpty(D))/*情况*/{V=Pop(D);for(i=2;inum;i++)/*从这只鳄鱼跳到其他各个鳄鱼*/{if((G[i].StepG[V].Step+1)&&CheckForConnect(G,V,i,JamesJump)){G[i].Path=V;G[i].Step=G[V].Step+1;if((G[i].StepG[*Bank].Step)&&CheckForEnd(G[i].X,G[i].Y,JamesJump))*Bank=i;elseInject(i,D);}}}}returnG;}/************/voidwrite_result(FILE*OutFile,VertexBank,GraphG,DequeD){unsignedintTimes,i;VertexV;switch(Bank){case0:/*007无法跳出*/fprintf(OutFile,%d\n,-1);7break;case1:/*007可以直接跳出*/fprintf(OutFile,%d\n,1);break;default:Times=G[Bank].Step+1;/*跳的步数*/while(Bank!=1)/*跟踪路径*/{Push(Bank,D);Bank=G[Bank].Path;}fprintf(OutFile,%d\n,Times);/*输出*/for(i=1;iTimes;i++){V=Pop(D);fprintf(OutFile,%d,G[V].X);fprintf(OutFile,%d\n,G[V].Y);}}}intmain(intargc,char*argv[]){FILE*in,*out;DequeD;intVertexNum;GraphG=NULL;VertexBank=0;in=fopen(input.txt,r);if(NULL==in){fprintf(stderr,Cannotopeninput.txt);exit(-1);}out=fopen(output.txt,w);if(NULL==out){fprintf(stderr,Cannotopenoutput.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);return0;}附录Ⅱ1.Graph.h#ifndef_GRAPH_H_#define_GRAPH_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);#endif2.Graph.c#includeGraph.h#includeerror.h#includestdlib.h/******创建新的Graph******/GraphGraphNew(intNodeNum){GraphG;inti;if(NodeNum=0)returnNULL;G=malloc(NodeNum*sizeof(GraphNode));/*分配空间*/CHECK(G);for(i=0;iNodeNum;i++)/*初始化*/9{G[i].X=0;G[i].Y=0;G[i].Step=INFINITY;G[i].Pa