數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--最短路徑：拯救-文庫吧
2025-01-03 15:48 本頁面
【正文】 (50,50)。湖中心的原型小島的圓心在(0,0),直徑是15。一些兇殘的鱷魚分布在湖中不同的位置?，F(xiàn)已知湖中鱷魚的位置(坐標(biāo))和James Bond可以調(diào)的最大距離，請你告訴James Bond一條最短的到達(dá)湖邊的路徑。他逃出去的路徑長度等于他跳的次數(shù)。輸入要求： 程序從“”，文件中讀取輸入信息，這個文件包含了多組輸入數(shù)據(jù)。每組輸入數(shù) 據(jù)的起始行中包含兩個整數(shù) n 和 d，n 是鱷魚的數(shù)量而且 n≤100，d 是007 可以跳的最大距離而且 d0。起始行下面的每一行是鱷魚的坐標(biāo)(x，y)，其中x，y 都是整數(shù)，而且沒有任何兩只鱷魚出現(xiàn)在同一個位置。 文件以一個負(fù)數(shù)結(jié)尾。 輸出要求： 程序結(jié)果輸出到 文件中。對于每組輸人數(shù)據(jù)，如果 007 可以逃脫，則輸出到 文件的內(nèi)容格式如下：第一行是 007 必須跳的最小的步數(shù)，然后下面按照跳出順序記錄跳出路徑上的鱷魚坐標(biāo)(x，y)，每行一個坐標(biāo)。如果 007不可能跳出去，則將1 寫人文件。如果這里有很多個最短的路徑，只需輸出其中的任意一種。 輸入例子： 4 10 /*第一組輸人數(shù)據(jù)*/ 最短路徑：拯救 007217 0 27 0 37 0 45 0 1 10 /*第二組輸入數(shù)據(jù)*/ 20 30 1 輸出例子： 5 /*對應(yīng)第一組數(shù)據(jù)的輸出 */ 17 0 27 0 37 0 45 0 1 /*對應(yīng)第二組數(shù)據(jù)的輸出*/2 系統(tǒng)需求分析 系統(tǒng)目標(biāo)告訴 James Bond 一條最短的到達(dá)湖邊的路徑。 主體功能假設(shè)湖是 100*100 的正方形，設(shè)湖的中心在(0,0),湖的東北角的坐標(biāo)是(50,50)。湖中心的原型小島的圓心在(0,0),直徑是 15。一些兇殘的鱷魚分布在湖中不同的位置?，F(xiàn)已知湖中鱷魚的位置(坐標(biāo))和 James Bond 可以調(diào)的最大距離，請你告訴 James Bond 一條最短的到達(dá)湖邊的路徑。他逃出去的路徑長度等于他跳的次數(shù)。 開發(fā)環(huán)境VC++3 系統(tǒng)需求分析(1)007被關(guān)的小島在湖的中心；(2)小島是圓形，圓心(0,0),而且直徑是15；(3)沒有兩只鱷魚在同一位置；(4)鱷魚的坐標(biāo)值都是整數(shù)。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告（2022）3(1)判斷007是否能夠直接從島上跳到湖岸：由已知條件可得，湖是一個正方形，變長為100，中心是在(0,0),四個頂點(diǎn)分別是(50,50),(50,50),(50,50),(50,50)。(5015/2)=,他就可以直接從小島跳到湖岸，而不是經(jīng)過鱷魚。(2)判斷007是否能夠從島上跳到湖中點(diǎn)A：，假設(shè)點(diǎn)A的坐標(biāo)是(x,y),007的步長是L，則當(dāng)點(diǎn)A到中心的(0,0)的距離小于等于007的步長加，即(3)判斷007是否能從點(diǎn)A跳到點(diǎn)B：假設(shè)007的步長是L，所以如果兩點(diǎn)之間的距離小于等于L，則判斷007可以沖A跳到B，即 ；其他情況是007不能從A點(diǎn)跳到B點(diǎn)。(4)判斷007是否能夠從點(diǎn)A跳到湖岸：當(dāng)從A點(diǎn)到湖岸的距離小于的ing與007 的步長的時(shí)候，說明他可以從A點(diǎn)跳到湖岸， 或 ；其他情況時(shí)007不能從A點(diǎn)跳到湖岸。主要數(shù)據(jù)結(jié)構(gòu)與算法見附錄Ⅰ。在執(zhí)行完算法read_case后，*Bank值可能有如下3種可能：(1)0，意味著007無法逃脫出去；(2)1,意味著007可以直接從島上跳出去，而不用經(jīng)過鱷魚的腦袋；(3)k,返回的k點(diǎn)是007經(jīng)過的最短路徑掏出鱷魚潭時(shí)經(jīng)過的最后一個頂點(diǎn)。可以根據(jù)G[k]的path參數(shù)來追蹤改點(diǎn)上的一點(diǎn)，由此類推可以得到007逃脫的最短路徑。本程序包含 3 個頭文件和 4 個 C 源程序文件，分別是：、、。程序內(nèi)容見附錄Ⅱ。4 測試 測試方案測試輸入：25 108 89 910 1011 1112 12最短路徑：拯救 007413 1314 1415 1516 1618 1820 2021 2123 2325 2527 2728 2829 2931 3133 3335 3538 3841 4144 4446 4647 4749 49 測試結(jié)果正確輸出：79 916 1623 2328 2835 3541 41實(shí)際輸出： 79 916 16數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告（2022）523 2328 2835 3541 415 分析與探討 測試結(jié)果分析 程序能夠正常運(yùn)行，輸入測試數(shù)據(jù)，能夠得到正確的結(jié)果，能對輸入的內(nèi)容進(jìn)行數(shù)據(jù)合法性檢測并進(jìn)行相應(yīng)的異常處理。 探討與改進(jìn)最短路徑定義：由圖的概念克制，在一個圖中，若從一個頂點(diǎn)到另一個頂點(diǎn)存在著一條路徑，則稱該路徑長度為該路徑上所有經(jīng)過的變的數(shù)目，他也等于該路徑上的頂點(diǎn)數(shù)減 ，每條徑上鎖經(jīng)過的邊數(shù)可能不同，把路徑上長度最短的那條路徑叫做最短路徑，其路徑長度叫做最短距離。上述問題之時(shí)隊(duì)無權(quán)圖而言,若是帶權(quán)圖，則把從一個頂點(diǎn)到另一條路徑上所有經(jīng)過的權(quán)值之和定義為該路徑的帶全路徑長度。把帶權(quán)路徑長度最短的那條路徑稱為該有權(quán)的最短路徑，起路徑長度稱為最短距離。6 小結(jié)經(jīng)過這幾天的課程設(shè)計(jì)，讓我受益良多，進(jìn)一步加深了多數(shù)據(jù)結(jié)構(gòu)這一門課程的理解，讓我的學(xué)習(xí)更進(jìn)一步。當(dāng)然能完成這次課程設(shè)計(jì)也離不開大家的幫助，老師的指導(dǎo)和同學(xué)的幫助。剛開始做這個的時(shí)候挺不情愿的，畢竟是上課，不過投入性不高，可是漸漸的隨著在實(shí)驗(yàn)中不斷遇到問題，然后努力解決問題，其中帶來了許多樂趣，也有很多成就感，讓我發(fā)現(xiàn)學(xué)習(xí)其實(shí)挺有趣的，有了興趣，才有動力，人才能前進(jìn)，在前進(jìn)的過程之中找到自己的不足，然后改正它，人才能走的更遠(yuǎn)站的更高。希望以后還有這樣的機(jī)會能夠鍛煉自己，和同學(xué)們協(xié)作，增加團(tuán)隊(duì)精神，以及自己獨(dú)立思考的能力。最短路徑：拯救 0076參考文獻(xiàn)[1]范策，周世平，胡嘵琨.《算法與數(shù)據(jù)結(jié)構(gòu)（C 語言版）》[M]. 北京：機(jī)械工業(yè)出版社，2022[2] 嚴(yán)蔚敏.《數(shù)據(jù)結(jié)構(gòu)（C 語言版）》. 北京：清華大學(xué)出版社，2022[3] 許卓群，楊冬青，唐世渭，張銘. 《數(shù)據(jù)結(jié)構(gòu)與算法》. 北京：高等教育出版社，2022[4] 徐孝凱. 《數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（第二版）》. 北京：清華大學(xué)出版社，2022數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告（2022）7附 錄附錄Ⅰ為了記錄007跳過的路徑，可定義如下結(jié)構(gòu)：typedef unsigned int Vertanca。typedef double Distanca。typedef struct GraphNodeRecord{ int x。 int y。 unsigned int Step。 Verex Path。}GraphNode。Typedef GrahNode *Graph。尋找跳出路徑的算法：/*讀入一組測試數(shù)據(jù)返回007跳過的路徑Graph，*Bank記錄最短到達(dá)湖岸的路徑。該算法實(shí)際上市應(yīng)用隊(duì)列圖進(jìn)行廣度搜索，以尋找到岸邊的最短路徑(最少的邊數(shù))，其中入隊(duì)列與出隊(duì)列函數(shù)分別是Inject()和Pop()*/Graph read_case(FILE *InFile, int num, Ver
法律信息相關(guān)推薦
鄂ICP備17016276號-1