数据结构拯救007.docx
《数据结构拯救007.docx》由会员分享，可在线阅读，更多相关《数据结构拯救007.docx（16页珍藏版）》请在冰点文库上搜索。
数据结构拯救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到文件。
算法的实现：
程序的实现少不了必要的头文件，在这里我加入了一个以前从没用过的不是标准库里面的头文件。
#include
#include
#include
#include
#defineISLAND_DIAMETER15/*小岛的直径*/
#defineLAKE_BOUNDARY_X50/*小岛到湖边的距离，在x轴上*/
#defineLAKE_BOUNDARY_Y50/*小岛到湖边的距离，在y轴上*/
#defineINFINITY10000/*可以跳的步数的最大值*/航班信息
拯救007源程序：
#include
#include
#include
#include
#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;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（x<0）x=-x;/*取x的绝对值*/
if（y<0）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<（num<<1）;i++）/*一步便跳出的情况*/
fscanf（InFile,"%d",&x）;
*Bank=1;
}
elseif（num>0）/*007必须经过鳄鱼头上的情况*/
{
num+=2;
G=GraphNew（num）;
for（i=2;i{
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;ifscanf（InFile,"%d",&y）;
DequeClear（D）;
break;
}
else
Inject（i,D）;/*插入该点，并开始下一个检测*/
}
}
while（!
IsEmpty（D））/*只经过一个鳄鱼无法跳出，必须还要跳到其它鳄鱼的情况*/
{
V=Pop（D）;
for（i=2;i{
if（（G[i].Step>G[V].Step+1）
&&CheckForConnect（G,V,i,JamesJump））
{
G[i].Path=V;
G[i].Step=G[V].Step+1;
if（（G[i].Step&&CheckForEnd（G[i].X,G[i].Y,JamesJump））
*Bank=i;
else
Inject（i,D）;
}
}
}
}
returnG;
}
/******写出结果，即最短路径******/
voidwrite_result（FILE*OutFile,VertexBank,GraphG,DequeD）
{
unsignedintTimes,i;
VertexV;
switch（Bank）{
case0:
/*007无法跳出*/
fprintf（OutFile,"%d\n",-1）;
break;
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;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;
}
实训总结、体会：
经过这次的课程设计，我很深刻的意识到自己的编程能力还有待提高，发现自己还存在很多不会的问题，有些细节问题没有注意到，还得学会冷静思考，加强算法和C语言语法的学习。
其中对英语的要求也体现出来了，因为它说明错误的时候都是英语，遇到问题要及时去查相关的资料。
反复的调试程序，最好是多找几个同学来对你的程序进行调试并听他说对你的程序的建议。
要形成自己的编写程序与调试程序的风格，从每个细节出发，不放过每个知识点，注意与理论的联系和理论与实践的差别。
另外，得注意符号的使用，注意对字符的处理，特别是对指针的使用时很容易出错且调试过程不会报错，但最后的结果却不是你想要的。
程序在完成之后，当时你调试运行时没有错误，可能错误就恰好隐藏在你没有检查的地方，要更全面的检查，特别是几个选择合起来一起挨个执行一遍。
通过进一周的学习实训和课程设计，又一次体验了离开课堂的理论学习，做了一次真正实践与理论相结合的连接。
特别是所做的题目基本都不是课堂上所讲的例子，但却是每一步都是用到课堂的内容。
实训让我对懂得的知识做了进一步深入了解，让我对其的理解与记忆更深刻，对不懂的知识与不清楚的东西也做了一定的了解，也形成了一定的个人编程风格。
在这次的课程设计中，学到了许多新的知识，比如还知道了除了标准库外其他函数的用法，知道程序的框架对于写一个完整的程序来说是很重要的，写出了大体框架就等于完成了一半程序，但不管怎么样，继续努力也是必不可少的。
升级会员 