数据结构课程设计拯救(共15页).doc

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

1、精选优质文档-倾情为你奉上数据结构课程设计最短路径：拯救007专业XX学生姓名XX班级XX学号XX问题描述与分析课程设计目的图结构是一种较为复杂的数据结构。对图结构最主要、最基本的操作是图的遍历。典型的遍历方法主要是深度遍历和广度遍历，即深度优先搜索和广度优先搜索。图结构也是一种具有广泛应用的数据结构。图的应用问题主要可归结为：求图中顶点间的最短路径、图的关键路径、图的拓扑排序、图的最小生成树等。本课程设计通过“拯救007”案例回顾图的最短路径的基本知识和基本方法。课程设计内容 看过007系列的电影的人们一定很熟悉Jams Bond这个世界上最著名的特工了。在电影“Live And Let D

2、ie”中Jams Bond被一组毒品贩子抓住并且关到湖中心的一个小岛上，而湖中有很多凶猛的鳄鱼。这时Jams Bond做出了一个最惊心动魄的事情来逃脱他跳到了最近的鳄鱼的头上，在鳄鱼还没有反映过来的时候，他有跳到另一支鳄鱼的头上最后他终于安全地跳到了湖岸上。 假设湖是100*100的正方形，设湖的中心在（0，0），湖的东北角的坐标是（50，50）。湖中心的圆环小岛的圆心在（0，0），直径是15.。一些凶残的鳄鱼分布在湖中不同的位置。现已知的湖中的鳄鱼的位置和Jams Bond可以跳的最大距离，请你告诉Jams Bondyitiao 最短的到达湖边的路径。他逃出去的路径长度等于他跳的次数。程序从

3、“input.txt”文件中读取输入信息，这个文件包含了多组输入数据。每组输入数据的起始行中包含了两个整数n和d，n是鳄鱼的数量而且n0。起始行下面的每一行是鳄鱼的坐标（x,y），其中x,y都是整数，而且没有任何两只鳄鱼出现在同一位置。Input.txt文件以一个负数结尾。输出要求：程序结果输出到output.txt文件中。对于每组输入数据，如果007可以逃脱，则输出到output.txt文件的内容格式如下：第一行是007必须跳的最小步数，然后按照跳出顺序记录跳出路径上的鳄鱼坐标（x,y），每行一个坐标。如果007不可能跳出去，则将-1写入文件。如果这里有很多个最短路径，只需输入其中的任意一种

4、。输入例子：4 10 /*第一组输入数据*/ 17 0 27 0 37 0 45 0 1 10 /*第二组输入数据*/ 20 30 -1 输出例子：5 /*对应第一组数据的输出*/ 17 0 27 0 45 0 -1 /*对应第二组数据的输出*/ 提示：将每个鳄鱼看作图中的每一个顶点。如果007可以从A点跳到B点，则A和B之间就有一条边。设计分析1. 明确题目中的已知条件（1）007被关的小岛在湖的中心；（2） 小岛是圆形，圆心（0,0），而直径是15；（3） 没有两只鳄鱼在同一位置；（4） 鳄鱼的坐标值都是整数。2.一些判断007是否跳出的细节 (1)判断007是否能够直接从岛上跳到湖岸由已

5、知条件可得湖是一个正方形变长为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即 (3)判断007是否能从点A跳到点B假设007的步长是L所以如果两点之间的距离小于等于L则判断007可以冲A跳到B

6、即 其他情况是007不能从A点跳到B点。 (4)判断007是否能够从点A跳到湖岸当从A点到湖岸的距离小于的ing与007 的步长的时候说明他可以从A点跳到湖岸 或 其他情况时007不能从A点跳到湖岸。主要数据结构与算法见附录。 在执行完算法read_case后*Bank值可能有如下3种可能 (1)0意味着007无法逃脱出去 (2)1,意味着007可以直接从岛上跳出去而不用经过鳄鱼的脑袋 (3)k,返回的k点是007经过的最短路径掏出鳄鱼潭时经过的最后一个顶点。可以根据Gk的path参数来追踪改点上的一点由此类推可以得到007逃脱的最短路径。 3.2系统功能模块划分 本程序包含3个头文件和4个C

7、源程序文件分别是Graph.h、Graph.c、Deque.h、Deque.c、error.h、error.c、main.c。程序内容见附录。 4 测试 4.1 测试方案 测试输入 25 10 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 18 18 20 20 21 21 23 23 25 25 27 27 28 28 29 29 31 31 33 33 35 35 38 38 41 41 44 44 46 46 47 47 49 49 4.2 测试结果 正确输出 7 9 9 16 16 23 23 28 28 35 35 41 41 实

8、际输出 7 9 9 16 16 23 23 28 28 35 35 41 41 5 分析与探讨 5.1 测试结果分析 程序能够正常运行输入测试数据能够得到正确的结果能对输入的内容进行数据合法性检测并进行相应的异常处理。 5.2 探讨与改进 最短路径定义由图的概念克制在一个图中若从一个顶点到另一个顶点存在着一条路径则称该路径长度为该路径上所有经过的变的数目他也等于该路径上的顶点数减1.有余从一个顶点到另一个顶点可呢该村在这多条路径每条径上锁经过的边数可能不同把路径上长度最短的那条路径叫做最短路径其路径长度叫做最短距离。 上述问题之时队无权图而言,若是带权图则把从一个顶点到另一条路径上所有经过的权

9、值之和定义为该路径的带全路径长度。把带权路径长度最短的那条路径称为该有权的最短路径起路径长度称为最短距离。 6 小结 经过这几天的课程设计让我受益良多进一步加深了多数据结构这一门课程的理解让我的学习更进一步。当然能完成这次课程设计也离不开大家的帮助老师的指导和同学的帮助。 刚开始做这个的时候挺不情愿的毕竟是上课不过投入性不高可是渐渐的随着在实验中不断遇到问题然后努力解决问题其中带来了许多乐趣也有很多成就感让我发现学习其实挺有趣的有了兴趣才有动力人才能前进在前进的过程之中找到自己的不足然后改正它人才能走的更远站的更高。 希望以后还有这样的机会能够锻炼自己和同学们协作增加团队精神以及自己独立思考的

10、能力。 参考文献 1范策周世平胡哓琨.算法与数据结构C语言版M. 北京机械工业出版社2004 2 严蔚敏.数据结构C语言版. 北京清华大学出版社2004 3 许卓群杨冬青唐世渭张铭. 数据结构与算法. 北京高等教育出版社2004 4 徐孝凯. 数据结构实用教程第二版. 北京清华大学出版社2006 附 录 附录 为了记录007跳过的路径可定义如下结构 typedef unsigned int Vertanca; typedef double Distanca; typedef struct GraphNodeRecord int x; int y; unsigned int Step; Vere

11、x Path; GraphNode; Typedef GrahNode *Graph; 寻找跳出路径的算法 /*读入一组测试数据返回007跳过的路径Graph*Bank记录最短到达湖岸的路径。该算法实际上市应用队列图进行广度搜索以寻找到岸边的最短路径(最少的边数)其中入队列与出队列函数分别是Inject()和Pop()*/ Graph read_case(FILE *InFile, int num, Vertex* Bank, Deque D) Graph G = NULL; Distance JamesJump; Vertex V; int x, y; int i, Times; *Bank

12、 = 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开始是鳄鱼 */ fscanf(InFile, %d, &x); fscanf(InFile, %d, &y); Gi.X = x; Gi.Y = y; if(CheckForStart(x, y, Jame

13、sJump) /*判断是否能跳上该点*/ 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, %d, &y); DequeClear(D); break; else Inject(i, D); /* 插入该点并开始下一个检测 */ while(!IsE

14、mpty(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; else Inject(i, D); return G; /*写出结果即最短路径*/ void write_result(FILE *OutFile, Ve

15、rtex 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 != 1)/* 跟踪路径 */ Push(Bank, D); Bank = GBank.Path; fprintf(

16、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(NULL = in) fprintf(stderr, Can not open inp

17、ut.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) GraphDelet

18、e(G); fclose(in); fclose(out); DequeDelete(D); return 0; 附录1.Graph.h#ifndef_GRAPH_H_#define_GRAPH_H_#define ISLAND_DIAMETER 15 /* 小岛的直径 */#define LAKE_BOUNDARY_X50/* 小岛到湖边的距离，在x轴上 */#define LAKE_BOUNDARY_Y50/* 小岛到湖边的距离，在y轴上 */#define INFINITY10000 /* 可以跳的步数的最大值 */typedef unsigned int Vertex;typedef

19、double Distance;typedef struct GraphNodeRecordint X; /* x轴坐标 */int Y; /* y轴坐标 */unsigned int Step; /*跳至该点的步数 */Vertex Path; /*记录上一个点 */ GraphNode;typedef GraphNode *Graph;Graph GraphNew(int NodeNum);void GraphDelete(Graph G);/* 判断007是否能从起始处跳至该点(x, y) */int CheckForStart(int x, int y, Distance d);/*

20、判断007是否能从该点跳至河岸 */int CheckForEnd(int x, int y, Distance d);/* 判断007是否能从点i跳至点j */ int CheckForConnect(Graph g, Vertex i, Vertex j, Distance d);#endif2.Graph.c#include Graph.h#include error.h#include /*创建新的Graph*/Graph GraphNew(int NodeNum)Graph G;int i;if(NodeNum = 0)return NULL;G = malloc(NodeNum *

21、 sizeof(GraphNode); /* 分配空间 */CHECK(G);for(i = 0; i NodeNum; i+) /* 初始化 */Gi.X = 0;Gi.Y = 0;Gi.Step = INFINITY; Gi.Path = 0;return G;/*删除一个Graph)*/void GraphDelete(Graph G)if(G)free(G);/*判断007是否能从起始处跳至该点(x, y)，步长是d*/int CheckForStart(int x, int y, Distance d)double t;t = (ISLAND_DIAMETER + (d * 2.0)

22、;return (x*x + y*y) = t*t/4.0; /* x2 + y2 = (ISLAND_DIAMETER/2.0 + d)2 */*判断007是否能从该点跳至河岸，步长是d*/int CheckForEnd(int x, int y, Distance d)if(x 0)x = -x; /* 取x的绝对值 */if(y = LAKE_BOUNDARY_X - x)/* 由于湖是个正方形，只需检查这两个距离*/| (d = LAKE_BOUNDARY_Y - y);/*判断007是否能从点i跳至点j，步长是d*/int CheckForConnect(Graph g, Verte

23、x i, Vertex j, Distance d)int x, y;x = gi.X - gj.X;y = gi.Y - gj.Y;return x*x + y*y = d*d;3.Deque.h#ifndef_DEQUE_H_#define_DEQUE_H_typedef unsigned int ElemType; /* 在本程序中ElemType指定为int */* 链表形式 */typedef struct NodeRecordElemType Element; struct NodeRecord *Next; /* 指向下一个node */ *Node; typedef struc

24、t DequeRecord Node Front, Rear; /* 分别指向Deque的前后两个点 */ *Deque;Deque DequeNew();void DequeDelete(Deque D); void DequeClear(Deque D); int IsEmpty(Deque D); void Push(ElemType X, Deque D); ElemType Pop(Deque D); void Inject(ElemType X, Deque D); #endif4.Deque.c#include Deque.h#include error.h#include /*

25、创建新的Deque*/Deque DequeNew()Deque D;D = malloc(sizeof(struct DequeRecord);CHECK(D);D-Front = D-Rear = malloc(sizeof(struct NodeRecord); /* 空的头 */CHECK(D-Front);D-Front-Element = 0; /* 初始化 */D-Rear-Next = NULL;return D;/*删除Deque*/void DequeDelete(Deque D)if(D)while(D-Front) D-Rear = D-Front-Next;free(

26、D-Front);D-Front = D-Rear;free(D);/*DequeClear删除所有的节点除了头节点*/void DequeClear(Deque D)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是否为空*/int IsEmpty(Deque D)return D-Front = D-Rear;/*将X元素压占到D中*/void Push(ElemType X,

27、 Deque D) Node NewNode; NewNode = malloc(sizeof(struct NodeRecord); /* 建立新的节点 */ CHECK(NewNode);NewNode-Element = X; NewNode-Next = D-Front-Next; if(D-Front = D-Rear) /* 如果D为空 */D-Rear = NewNode;D-Front-Next = NewNode;/* 压栈 */ /*将第一个元素出栈*/ElemType Pop(Deque D) Node Temp; ElemType Item; if(D-Front =

28、D-Rear)Error(Deque is empty);return 0; else Temp = D-Front-Next;/* 得到第一个元素 */ D-Front-Next = Temp-Next; /* 重置第一个元素 */if(Temp = D-Rear)/* 如果只有一个元素 */D-Rear = D-Front;/* 将D置空 */ Item = Temp-Element; free(Temp);return Item; /*插入元素X至D末尾*/ void Inject(ElemType X, Deque D) Node NewNode;NewNode = malloc(si

29、zeof(struct NodeRecord); /* 创建新节点 */ CHECK(NewNode);NewNode-Element = X; NewNode-Next = NULL;D-Rear-Next = NewNode;D-Rear = NewNode; 5.error.h#ifndef_ _ _DS_PROJ_2_ERROR_H_ _ _#define_ _ _DS_PROJ_2_ERROR_H_ _ _#define CHECK(X) if(NULL = (X)Error(Out of space!)void Error(const char *msg);void Warning

30、(const char *msg);#endif6.error.c#include error.h#include #include /*打印错误信息，并退出程序*/ void Error(const char *msg)if(NULL != msg)fprintf(stderr,%sn,msg);exit(-1);/*打印警告信息，但并不退出程序*/void Warning(const char *msg)if(NULL != msg)fprintf(stderr,%sn,msg);7.main.c#include Graph.h#include Deque.h#include error.

31、h#include #include /*读入一个case返回一个Graph，*Bank 记录最短到达河岸的路径*/Graph read_case(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(CheckForEnd(0, 0, JamesJump + ISLAND_DIAMETER/2.0)for(i = 0; i (num 0)

32、/* 007必须经过鳄鱼头上的情况 */num += 2;G = GraphNew(num);for(i = 2; i num; i+) /* 第三个node开始是鳄鱼 */fscanf(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

33、; /* 007可以跳出 */Times = (num - i - 1) 1;for(i = 0; i Times; i+) /* 不必检验其他鳄鱼 */fscanf(InFile, %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 =

34、GV.Step + 1;if(Gi.Step G*Bank.Step)& CheckForEnd(Gi.X, Gi.Y, JamesJump)*Bank = i;elseInject(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可以直接跳出

35、 */fprintf(OutFile, %dn, 1);break;default: Times = GBank.Step + 1;/* 跳的步数 */while(Bank != 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,

36、 *out;Deque D;int VertexNum;Graph G = NULL;Vertex Bank = 0;in = fopen(input.txt, r);if(NULL = 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;专心-专注-专业