【正文】 ewNode。 NewNode = malloc(sizeof(struct NodeRecord))。 /* 創(chuàng)建新節(jié)點 */ CHECK(NewNode)。 NewNodeElement = X。 NewNodeNext = NULL。 DRearNext = NewNode。 DRear = NewNode。 } 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(const char *msg)。 endif include 最短路徑：拯救 007 18 include include /******打印錯誤信息，并退出程序 ******/ void Error(const char *msg) { if(NULL != msg) fprintf(stderr,%s\n,msg)。 exit(1)。 } /******打印警告信息，但并不退出程序 ******/ void Warning(const char *msg) { if(NULL != msg) fprintf(stderr,%s\n,msg)。 } include 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。 數(shù)據(jù)結構課程設計報告（ 2021） 19 fscanf(InFile, %lf, amp。JamesJump)。 if(CheckForEnd(0, 0, JamesJump + ISLAND_DIAMETER/)) { for(i = 0。 i (num 1)。 i++) /*一步便跳出的情況 */ fscanf(InFile, %d, amp。x)。 *Bank = 1。 } else if(num 0) /* 007 必須經過鱷魚頭上的情況 */ { num += 2。 G = GraphNew(num)。 for(i = 2。 i num。 i++) /* 第三個 node 開始是鱷魚 */ { fscanf(InFile, %d, amp。x)。 fscanf(InFile, %d, amp。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。 i Times。 i++) /* 不必檢驗其他鱷魚 */ fscanf(InFile, %d, amp。y)。 DequeClear(D)。 break。 } else Inject(i, D)。 /* 插入該點，并開始下一個檢測 */ } } 最短路徑：拯救 007 20 while(!IsEmpty(D)) /*只經過一個鱷魚無法跳出，必須還要跳到其它鱷魚的情況 */ { V = Pop(D)。 for(i = 2。 i num。 i++) /* 從這只鱷魚跳到其他各個鱷 魚 */ { if((G[i].Step G[V].Step + 1) amp。amp。 CheckForConnect(G, V, i, JamesJump)) { G[i].Path = V。 G[i].Step = G[V].Step + 1。 if((G[i].Step G[*Bank].Step) amp。amp。 CheckForEnd(G[i].X, G[i].Y, JamesJump)) *Bank = i。 else Inject(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, %d\n, 1)。 break。 case 1: /* 007 可以直接跳出 */ fprintf(OutFile, %d\n, 1)。 break。 數(shù)據(jù)結構課程設計報告（ 2021） 21 default: Times = G[Bank].Step + 1。/* 跳的步數(shù) */ while(Bank != 1)/* 跟蹤路徑 */ { Push(Bank, D)。 Bank = G[Bank].Path。 } fprintf(OutFile, %d\n, Times)。/* 輸出 */ for(i = 1。 i Times。 i++) { V = Pop(D)。 fprintf(OutFile, %d , G[V].X)。 fprintf(OutFile, %d\n, G[V].Y)。 } } } int main(int argc, char *argv[]) { FILE *in, *out。 Deque D。 int VertexNum。 Graph G = NULL。 Vertex Bank = 0。 in = fopen(, r)。 if(NULL == in) { fprintf(stderr, Can not open )。 exit(1)。 } out = fopen(, w)。 if(NULL == out) { fprintf(stderr, Can not open )。 fclose(in)。 最短路徑：拯救 007 22 exit(1)。 } D= DequeNew()。 while((EOF != fscanf(in, %d, amp。VertexNum)) amp。amp。 (0 = VertexNum)) { G = read_case(in, VertexNum, amp。Bank, D)。 /* 讀文件直到結尾 */ write_result(out, Bank, G, D)。 if(G) GraphDelete(G)。 } fclose(in)。 fclose(out)。 DequeDelete(D)。 return 0。 }