數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--最短路徑：拯救(編輯修改稿)
2025-07-08 22:52 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 找跳出路徑的算法： /*讀入一組測(cè)試數(shù)據(jù)返回 007跳過(guò)的路徑 Graph， *Bank記錄最短到達(dá)湖岸的路徑。該算法實(shí)際上市應(yīng)用隊(duì)列圖進(jìn)行廣度搜索，以尋找到岸邊的最短路徑 (最少的邊數(shù) )，其中入隊(duì)列與出隊(duì)列函數(shù)分別是 Inject()和 Pop()*/ 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, amp。JamesJump)。 if(CheckForEnd(0, 0, JamesJump + ISLAND_DIAMETER/)) { for(i = 0。 i (num 1)。 i++) /*一步便跳出的情況 */ fscanf(InFile, %d, amp。x)。 *Bank = 1。 最短路徑：拯救 007 8 } else if(num 0) /* 007必須經(jīng)過(guò)鱷魚頭上的情況 */ { num += 2。 G = GraphNew(num)。 for(i = 2。 i num。 i++) /* 第三個(gè) node開始是鱷魚 */ { 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)其他鱷魚 */ fscanf(InFile, %d, amp。y)。 DequeClear(D)。 break。 } else Inject(i, D)。 /* 插入該點(diǎn)，并開始下一個(gè)檢測(cè) */ } } while(!IsEmpty(D)) /*只經(jīng)過(guò)一個(gè)鱷魚無(wú)法跳出，必須還要跳到其它鱷魚的情況 */ { V = Pop(D)。 for(i = 2。 i num。 i++) /* 從這只鱷魚跳到其他各個(gè)鱷魚 */ 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告（ 2021） 9 { 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。 } /******寫出結(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。 default: Times = G[Bank].Step + 1。/* 跳的步數(shù) */ while(Bank != 1)/* 跟蹤路徑 */ { 最短路徑：拯救 007 10 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)。 exit(1)。 } D= DequeNew()。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告（ 2021） 11 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。 } 附錄 Ⅱ ifndef_GRAPH_H_ define_GRAPH_H_ define ISLAND_DIAMETER 15 /* 小島的直徑 */ define LAKE_BOUNDARY_X50/* 小島到湖邊的距離，在 x軸上 */ define LAKE_BOUNDARY_Y50/* 小島到湖邊的距離，在 y軸上 */ define INFINITY10000 /* 可以跳的步數(shù)的最大值 */ typedef unsigned int Vertex。 typedef double Distance。 typedef struct GraphNodeRecord{ int X。 /* x 軸坐標(biāo) */ int Y。 /* y 軸坐標(biāo) */ unsigned int Step。 /*跳至該點(diǎn)的步數(shù) */ Vertex Path。 /*記錄上一個(gè)點(diǎn) */ } GraphNode。 typedef GraphNode *Graph。 最短路徑：拯救 007 12 Graph GraphNew(int NodeNum)。 void GraphDelete(Graph G)。 /* 判斷 007 是否能從起始處跳至該點(diǎn) (x, y) */ int CheckForStart(int x, int y, Distance d)。 /* 判斷 007 是否能從該點(diǎn)跳至河岸 */ int CheckForEnd(int x, int y, Distanc
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1