數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--最短路徑：拯救-在線瀏覽
2025-03-07 15:48本頁(yè)面
【正文】 Ⅰ ........................................................................................................................................7附錄 Ⅱ ......................................................................................................................................11數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告（2022）1最短路徑 :拯救 0071 概 述 課程設(shè)計(jì)目的圖結(jié)構(gòu)是一種較為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。對(duì)圖結(jié)構(gòu)最主要、最基本的操作是圖的遍歷。圖結(jié)構(gòu)也是一種具有廣泛應(yīng)用的數(shù)據(jù)結(jié)構(gòu)。本課程設(shè)計(jì)通過(guò)“拯救 007”案例回顧圖的最短路徑的基本知識(shí)和基本方法。在電影“Live and Let Die”中James Bond被異族毒販子捉住并且關(guān)單哦湖中心的一個(gè)小島上，而湖中有很多兇猛的鱷魚(yú) 。假設(shè)湖是100*100的正方形，設(shè)湖的中心在(0,0),湖的東北角的坐標(biāo)是(50,50)。一些兇殘的鱷魚(yú)分布在湖中不同的位置。他逃出去的路徑長(zhǎng)度等于他跳的次數(shù)。每組輸入數(shù) 據(jù)的起始行中包含兩個(gè)整數(shù) n 和 d，n 是鱷魚(yú)的數(shù)量而且 n≤100，d 是007 可以跳的最大距離而且 d0。 文件以一個(gè)負(fù)數(shù)結(jié)尾。對(duì)于每組輸人數(shù)據(jù)，如果 007 可以逃脫，則輸出到 文件的內(nèi)容格式如下：第一行是 007 必須跳的最小的步數(shù)，然后下面按照跳出順序記錄跳出路徑上的鱷魚(yú)坐標(biāo)(x，y)，每行一個(gè)坐標(biāo)。如果這里有很多個(gè)最短的路徑，只需輸出其中的任意一種。 主體功能假設(shè)湖是 100*100 的正方形，設(shè)湖的中心在(0,0),湖的東北角的坐標(biāo)是(50,50)。一些兇殘的鱷魚(yú)分布在湖中不同的位置。他逃出去的路徑長(zhǎng)度等于他跳的次數(shù)。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告（2022）3(1)判斷007是否能夠直接從島上跳到湖岸：由已知條件可得，湖是一個(gè)正方形，變長(zhǎng)為100，中心是在(0,0),四個(gè)頂點(diǎn)分別是(50,50),(50,50),(50,50),(50,50)。(2)判斷007是否能夠從島上跳到湖中點(diǎn)A：，假設(shè)點(diǎn)A的坐標(biāo)是(x,y),007的步長(zhǎng)是L，則當(dāng)點(diǎn)A到中心的(0,0)的距離小于等于007的步長(zhǎng)加，即(3)判斷007是否能從點(diǎn)A跳到點(diǎn)B：假設(shè)007的步長(zhǎng)是L，所以如果兩點(diǎn)之間的距離小于等于L，則判斷007可以沖A跳到B，即 ；其他情況是007不能從A點(diǎn)跳到B點(diǎn)。主要數(shù)據(jù)結(jié)構(gòu)與算法見(jiàn)附錄Ⅰ?？梢愿鶕?jù)G[k]的path參數(shù)來(lái)追蹤改點(diǎn)上的一點(diǎn)，由此類推可以得到007逃脫的最短路徑。程序內(nèi)容見(jiàn)附錄Ⅱ。 探討與改進(jìn)最短路徑定義：由圖的概念克制，在一個(gè)圖中，若從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)存在著一條路徑，則稱該路徑長(zhǎng)度為該路徑上所有經(jīng)過(guò)的變的數(shù)目，他也等于該路徑上的頂點(diǎn)數(shù)減 ，每條徑上鎖經(jīng)過(guò)的邊數(shù)可能不同，把路徑上長(zhǎng)度最短的那條路徑叫做最短路徑，其路徑長(zhǎng)度叫做最短距離。把帶權(quán)路徑長(zhǎng)度最短的那條路徑稱為該有權(quán)的最短路徑，起路徑長(zhǎng)度稱為最短距離。當(dāng)然能完成這次課程設(shè)計(jì)也離不開(kāi)大家的幫助，老師的指導(dǎo)和同學(xué)的幫助。希望以后還有這樣的機(jī)會(huì)能夠鍛煉自己，和同學(xué)們協(xié)作，增加團(tuán)隊(duì)精神，以及自己獨(dú)立思考的能力。typedef double Distanca。 int y。 Verex Path。Typedef GrahNode *Graph。該算法實(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。 Vertex V。 int i, Times。 fscanf(InFile, %lf, amp。 if(CheckForEnd(0, 0, JamesJump + ISLAND_DIAMETER/)) { for(i = 0。 i++) /*一步便跳出的情況 */ fscanf(InFile, %d, amp。 *Bank = 1。 G = GraphNew(num)。 i num。x)。y)。 G[i].Y = y。 /*007可以跳到 */ G[i].Step = 1。 /* 007可以跳出 */ Times = (num i 1) 1。 i Times。y)。 break。 /* 插入該點(diǎn)，并開(kāi)始下一個(gè)檢測(cè) */ } } while(!IsEmpty(D)) /*只經(jīng)過(guò)一個(gè)鱷魚(yú)無(wú)法跳出，必須還要跳到其它鱷魚(yú)的情況 */ { V = Pop(D)。 i num。amp。 G[i].Step = G[V].Step + 1。amp。 else Inject(i, D)。 } /******寫(xiě)出結(jié)果，即最短路徑******/ void write_result(FILE *OutFile, Vertex Bank, Graph G, Deque D) { unsigned int Times, i。 switch(Bank){ case 0: /* 007無(wú)法跳出 */ fprintf(OutFile, %d\n, 1)。 case 1: /* 007可以直接跳出 */ fprintf(OutFile, %d\n, 1)。 default: Times = G[Bank].Step + 1。 Bank = G[Bank].Path。/* 輸出 */ for(i = 1。 i++) { V = Pop(D)。 fprintf(OutFile, %d\n, G[V].Y)。 Deque D。 Graph G = NULL。 in = fopen(, r)。 exit(1)。 if(NULL == out) { fprintf(stderr, Can not open )。 exit(1)。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告（2022）11while((EOF != fscanf(in, %d, amp。amp。Bank, D)。 if(G) GraphDelete(G)。 fclose(out)。 return 0。 typedef double Distance。 /* x 軸坐標(biāo) */ int Y。 /*跳至該點(diǎn)的步數(shù) */ Vertex Path。 typedef GraphNode *Graph。 void GraphDelete(Graph G)。 /* 判斷 007 是否能從該點(diǎn)跳至河岸 */ int CheckForEnd(int x, int y, Distance d)。 endif include include include /******創(chuàng)建新的 Graph******/ Graph GraphNew(int NodeNum) { Graph G。 if(NodeNum = 0)return NULL。 /* 分配空間 */ CHECK(G)。 i NodeNum。 G[i].Y = 0。 G
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1