《数据结构拯救(共14页).doc》由会员分享，可在线阅读，更多相关《数据结构拯救(共14页).doc（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上中国地质大学数据结构课程设计4号题：最短路径，拯救007班 级： 班姓 名：杉学号：指导老师： 2014 年 1 月 11 日实训目的：通过具体的课程设计，熟悉数据结构中最基础和最重要的部分：单链表，及其各种操作和实际应用。在设计的过程中，掌握数据结构的思想，并运用于具体问题的解决之中。加深对数据结构课程中理论和实践相结合的认识。实训任务及要求：看过007系列电影的人们一定很熟悉James Bond这个著名的特工。在电影”Live and Let Die”中James Bond被一组毒品贩子捉住并且关到湖中心的一个小岛上，而湖中有很多凶猛的鳄鱼。这时James Bon
2、d做出了最惊心动魄的事情来逃脱他跳到了最近的鳄鱼的头上，在鳄鱼还没有反应过来的时候，他又跳到了另一只鳄鱼的头上最后他终于安全地跳到了湖岸上。假设湖是100100的正方形，设湖的中心在(0,0)，湖的东北角的坐标是(50,50)。湖中心的圆形小岛的圆心在(0,0)，直径是15。一些凶残的鳄鱼分布在湖中不同的位置。现已知湖中鳄鱼的位置（坐标）和James Bond可以跳的最大距离，请你告诉James Bond一条最短的到达湖边的路径。他逃出去的路径的长度等于他跳的次数。 要求：（1）输入要求：程序从文件中读取输入信息，文件中包括的多组输入数据。每组输入数据包括鳄鱼的数量、007可以跳的最大距离、鳄
3、鱼的坐标（没有两只鳄鱼出现在同一个位置）。（2）输出要求：程序结果输出到文件中。对于每组输入数据，如果007可以逃脱，则输出007必须跳的最小的步数，然后按照跳出顺序记录跳出路径上的鳄鱼坐标；如果007不能逃脱，则输出-1到文件。算法的实现： 程序的实现少不了必要的头文件，在这里我加入了一个以前从没用过的不是标准库里面的头文件。#include#include#include #include #define ISLAND_DIAMETER 15 /* 小岛的直径 */#define LAKE_BOUNDARY_X 50 /* 小岛到湖边的距离，在x轴上 */#define LAKE_BOUN
4、DARY_Y 50 /* 小岛到湖边的距离，在y轴上 */#define INFINITY 10000 /* 可以跳的步数的最大值 */航班信息拯救007源程序：#include#include#include #include #define ISLAND_DIAMETER 15 /* 小岛的直径 */#define LAKE_BOUNDARY_X 50 /* 小岛到湖边的距离，在x轴上 */#define LAKE_BOUNDARY_Y 50 /* 小岛到湖边的距离，在y轴上 */#define INFINITY 10000 /* 可以跳的步数的最大值 */typedef unsigned
5、 int Vertex;typedef 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, in
6、t y, Distance d);/* 判断007是否能从该点跳至河岸 */int CheckForEnd(int x, int y, Distance d);/* 判断007是否能从点i跳至点j */ int CheckForConnect(Graph g, Vertex i, Vertex j, Distance d);typedef unsigned int ElemType; /* 在本程序中ElemType指定为int */* 链表形式 */typedef struct NodeRecordElemType Element; struct NodeRecord *Next; /* 指
7、向下一个node */ *Node; typedef struct 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); #define CHECK(X) if(NULL = (
8、X)Error(Out of space!)void Error(const char *msg);void Warning(const char *msg);/*创建新的Graph*/Graph GraphNew(int NodeNum)Graph G;int i;if(NodeNum = 0)return NULL;G =(GraphNodeRecord *) malloc(NodeNum * sizeof(GraphNode); /* 分配空间 */ CHECK(G);for(i = 0; i NodeNum; i+) /* 初始化 */Gi.X = 0;Gi.Y = 0;Gi.Step
9、 = 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); return (x*x + y*y) = t*t/4.0; /* x2 + y2 = (ISLAND_DIAMETER/2.0 + d)2 */*判断007是否能从该点跳至河岸，步长是d*/int
10、 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, Vertex i, Vertex j, Distance d)int x, y;x = gi.X - gj.X;y = gi.Y - gj.Y;return x*x + y*y Front = D-Rea
11、r =(NodeRecord *) 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(D-Front);D-Front = D-Rear;free(D);/*DequeClear删除所有的节点除了头节点*/void DequeClear(Deque
12、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, Deque D) Node NewNode; NewNode =(NodeRecord *) malloc(sizeof(struct NodeRecord);
13、/* 建立新的节点 */ 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 = D-Rear)Error(Deque is empty);return 0; else Temp = D-Front-Next; /
14、* 得到第一个元素 */ 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 =(NodeRecord *) malloc(sizeof(struct NodeRecord); /* 创建新节点 */ CHECK(NewNo
15、de);NewNode-Element = X; NewNode-Next = NULL;D-Rear-Next = NewNode;D-Rear = NewNode; /*打印错误信息，并退出程序*/ 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);/*读入一个case返回一个Graph，*Bank 记录最短到达河岸的路径
16、*/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) /* 007必须经过鳄鱼头上的情况 */num += 2;G = GraphNew(num); for(i =
17、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; /* 007可以跳出 */Times = (num - i - 1) 1;for(i = 0; i Tim
18、es; 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 = GV.Step + 1;if(Gi.Step G*Bank.Step) & CheckForEnd(Gi
19、.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可以直接跳出 */fprintf(OutFile, %dn, 1);break;default: Times
20、= 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, *out;Deque D;int VertexNum;Graph G = NULL;Ve
21、rtex 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, Verte
22、xNum, &Bank, D); /* 读文件直到结尾 */write_result(out, Bank, G, D);if(G)GraphDelete(G);fclose(in);fclose(out);DequeDelete(D);return 0;实训总结、体会：经过这次的课程设计，我很深刻的意识到自己的编程能力还有待提高，发现自己还存在很多不会的问题，有些细节问题没有注意到，还得学会冷静思考，加强算法和C语言语法的学习。其中对英语的要求也体现出来了，因为它说明错误的时候都是英语，遇到问题要及时去查相关的资料。反复的调试程序，最好是多找几个同学来对你的程序进行调试并听他说对你的程序的建议
23、。要形成自己的编写程序与调试程序的风格，从每个细节出发，不放过每个知识点，注意与理论的联系和理论与实践的差别。另外，得注意符号的使用，注意对字符的处理，特别是对指针的使用时很容易出错且调试过程不会报错，但最后的结果却不是你想要的。程序在完成之后，当时你调试运行时没有错误，可能错误就恰好隐藏在你没有检查的地方，要更全面的检查，特别是几个选择合起来一起挨个执行一遍。通过进一周的学习实训和课程设计，又一次体验了离开课堂的理论学习，做了一次真正实践与理论相结合的连接。特别是所做的题目基本都不是课堂上所讲的例子，但却是每一步都是用到课堂的内容。实训让我对懂得的知识做了进一步深入了解，让我对其的理解与记忆更深刻，对不懂的知识与不清楚的东西也做了一定的了解，也形成了一定的个人编程风格。在这次的课程设计中，学到了许多新的知识，比如还知道了除了标准库外其他函数的用法，知道程序的框架对于写一个完整的程序来说是很重要的，写出了大体框架就等于完成了一半程序，但不管怎么样，继续努力也是必不可少的。专心-专注-专业