}
/******将第一个元素出栈******/ ElemType Pop(Deque D) { Node Temp; ElemType Item; if(D->Front == D->Rear) { Error(\ 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(sizeof(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(\void Error(const char *msg); void Warning(const char *msg);
#endif
17
6. error.c
#include \#include
/******打印错误信息，并退出程序******/ void Error(const char *msg) { if(NULL != msg) fprintf(stderr,\ exit(-1); }
/******打印警告信息，但并不退出程序******/ void Warning(const char *msg) { if(NULL != msg) fprintf(stderr,\}
7. main.c
#include \#include \#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, \ if(CheckForEnd(0, 0, JamesJump + ISLAND_DIAMETER/2.0)) { for(i = 0; i < (num << 1); i++) /*一步便跳出的情况 */ fscanf(InFile, \ *Bank = 1; } else if(num > 0) /* 007必须经过鳄鱼头上的情况 */ {
18
*/
num += 2;
G = GraphNew(num);
for(i = 2; i < num; i++) /* 第三个node开始是鳄鱼 */ { fscanf(InFile, \ fscanf(InFile, \ 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; i < Times; i++) /* 不必检验其他鳄鱼 */ fscanf(InFile, \ DequeClear(D); break; } else
Inject(i, D); /* 插入该点，并开始下一个检测 */ } }
while(!IsEmpty(D)) /*只经过一个鳄鱼无法跳出，必须还要跳到其它鳄鱼的情况 {
V = Pop(D);
for(i = 2; i < num; 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 < G[*Bank].Step) && CheckForEnd(G[i].X, G[i].Y, JamesJump)) *Bank = i; else Inject(i, D); } }
19
}
} }
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, \ break;
case 1: /* 007可以直接跳出 */ fprintf(OutFile, \ break;
default: Times = G[Bank].Step + 1; /* 跳的步数 */ while(Bank != 1) /* 跟踪路径 */ { Push(Bank, D); Bank = G[Bank].Path; }
fprintf(OutFile, \/* 输出 */ for(i = 1; i < Times; i++) { V = Pop(D); fprintf(OutFile, \ fprintf(OutFile, \ } } }
int main(int argc, char *argv[]) { FILE *in, *out; Deque D; int VertexNum; Graph G = NULL; Vertex Bank = 0; in = fopen(\ \ if(NULL == in) {
20
fprintf(stderr, \ exit(-1); }
out = fopen(\ if(NULL == out) { fprintf(stderr, \ fclose(in); exit(-1); }
D = DequeNew();
while((EOF != fscanf(in, \ {
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;
}
21
*/
相关推荐：
loading