數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--最短路徑：拯救-資料下載頁(yè)
2025-01-18 15:48本頁(yè)面
【正文】 ))。 /* 創(chuàng)建新節(jié)點(diǎn) */ 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 最短路徑：拯救 00718include include /******打印錯(cuò)誤信息，并退出程序******/ 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 /******讀入一個(gè) case 返回一個(gè) Graph，*Bank 記錄最短到達(dá)河岸的路徑******/ 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ù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告（2022）19fscanf(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 必須經(jīng)過(guò)鱷魚(yú)頭上的情況 */ { num += 2。 G = GraphNew(num)。 for(i = 2。 i num。 i++) /* 第三個(gè) node 開(kāi)始是鱷魚(yú) */ { fscanf(InFile, %d, amp。x)。 fscanf(InFile, %d, amp。y)。 G[i].X = x。 G[i].Y = y。 if(CheckForStart(x, y, JamesJump)) /*判斷是否能跳上該點(diǎn)*/ { G[i].Path = 1。 /*007 可以跳到 */ G[i].Step = 1。 /* 一步 */ if(CheckForEnd(x, y, JamesJump)) /* 判斷該點(diǎn)是否能跳出 */ { *Bank = i。 /* 007 可以跳出 */ Times = (num i 1) 1。 for(i = 0。 i Times。 i++) /* 不必檢驗(yàn)其他鱷魚(yú) */ fscanf(InFile, %d, amp。y)。 DequeClear(D)。 break。 } else Inject(i, D)。 /* 插入該點(diǎn)，并開(kāi)始下一個(gè)檢測(cè) */ } } 最短路徑：拯救 00720while(!IsEmpty(D)) /*只經(jīng)過(guò)一個(gè)鱷魚(yú)無(wú)法跳出，必須還要跳到其它鱷魚(yú)的情況 */ { V = Pop(D)。 for(i = 2。 i num。 i++) /* 從這只鱷魚(yú)跳到其他各個(gè)鱷魚(yú) */ { 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。 } /******寫(xiě)出結(jié)果，即最短路徑******/ void write_result(FILE *OutFile, Vertex Bank, Graph G, Deque D) { unsigned int Times, i。 Vertex V。 switch(Bank){ case 0: /* 007 無(wú)法跳出 */ fprintf(OutFile, %d\n, 1)。 break。 case 1: /* 007 可以直接跳出 */ fprintf(OutFile, %d\n, 1)。 break。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告（2022）21default: 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)。 最短路徑：拯救 00722exit(1)。 } D= DequeNew()。 while((EOF != fscanf(in, %d, amp。VertexNum)) amp。amp。 (0 = VertexNum)) { G = read_case(in, VertexNum, amp。Bank, D)。 /* 讀文件直到結(jié)尾 */ write_result(out, Bank, G, D)。 if(G) GraphDelete(G)。 } fclose(in)。 fclose(out)。 DequeDelete(D)。 return 0。
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1