數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告最短路徑拯救

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告最短路徑：拯救007專業(yè)物聯(lián)網(wǎng)工程學(xué)生姓名班級學(xué)號指導(dǎo)教師完成日期2016年1月13日專心-專注-專業(yè)目 錄數(shù)據(jù)結(jié)構(gòu)程序課程的設(shè)計1、 課程設(shè)計目的及要求 1）設(shè)計題目看過007系列電影的人們一定很熟悉James Bond這個世界上最著名的特工了。在電影“Live and Let Die”中James Bond被一組毒品販子抓住并且關(guān)到湖中心的一個小島上，而湖中有很多兇猛的鱷魚。這時James Bond做出了最驚心動魄的事情來逃脫他跳到了最近的鱷魚的頭上，在鱷魚還沒有反應(yīng)過來的時候，他又跳到了另一只鱷魚的頭上最后他終于安全地跳到了湖岸上。假設(shè)湖是1

2、00100的正方形，設(shè)湖的中心在（0，0），湖的東北角的坐標(biāo)是（50，50）。湖中心的圓形小島的圓心在（0，0），直徑是15。一些兇猛的鱷魚分布在湖中不同的位置?，F(xiàn)已知湖中鱷魚的位置（坐標(biāo)）和James Bond可以跳的最大距離，請你告訴James Bond一條最短的到達(dá)湖邊的路徑。他逃出去的路徑的長度等于他跳的次數(shù)。2）輸入要求程序從“input.txt”文件中讀取輸入信息，這個文件包含了多組輸入數(shù)據(jù)。每組輸入數(shù)據(jù)的起始行中包含兩個整數(shù)n和d，n是鱷魚的數(shù)量而且n100，d是007可以跳的最大距離而且d0。起始行下面的每一行是鱷魚的坐標(biāo)（x，y），其中x, y都是整數(shù)，而且沒有任何兩只鱷魚出

3、現(xiàn)在同一個位置。input.txt文件以一個負(fù)數(shù)結(jié)尾。3）輸出要求程序輸出結(jié)果輸出到output.txt文件中。對于每組輸入數(shù)據(jù)，如果007可以逃脫，則輸出到output.txt文件的內(nèi)容格式如下：第一行是007必須跳的最小的步數(shù)，然后下面按照跳出順序記錄跳出路徑上的鱷魚坐標(biāo)（x，y），每行一個坐標(biāo)。如果007不可能跳出去，則將-1寫入文件。如果這里有很多個最短的路徑，只需輸出其中的任意一種2、課題總體設(shè)計2.1設(shè)計分析1.明確題目中的已知條件(1)007被關(guān)的小島在湖的中心；(2)小島是圓形，圓心在（0，0），而且直徑是15；(3)沒有兩只鱷魚在同一個位置；(4)鱷魚的坐標(biāo)值都是整數(shù)。2.一

4、些判斷007是否能跳出的細(xì)節(jié)(1)判斷007是否能夠直接從島上跳到湖岸：由已知條件可得，湖是一個正方形，邊長為100，中心是在（0，0），四個頂點分別是（50，50）,(50,-50),(-50,-50),(-50,50)。而湖中小島的直徑是15.所以如果007可以跳大于等于（50-15/2）=42.5，他就可以直接從小島跳到湖岸，而不用經(jīng)過鱷魚。(2)判斷007是否能夠直接從島上跳到湖中點A：已知半徑是7.5，假設(shè)點A的坐標(biāo)是（x,y），007的步長是L，則當(dāng)點A到中心（0，0）的距離小于等于007的步長加上小島的半徑7.5的時候就能確定007可以從島上跳到點A，即：x*x+y*y=(L+7

5、.5)*(L+7.5)。(3)判斷007是否能夠從點A跳到點B：假設(shè)007的步長是L所以如果兩點之間的距離小于等于L，則判斷007可以從A跳到B，即（A.x-B.x）2+(A.y-B.y)2=50或|A.y|+L=50；其他情況時007不能從A點跳到湖岸。 2. 系統(tǒng)流程圖開始初始化路徑能否直接跳出？跳出有無鱷魚？能否從島上跳上該點？記錄該點能否跳出該點？記錄該點插入該點，檢測下一點結(jié)束判斷能否跳出，并比其他短3、詳細(xì)設(shè)計 主要數(shù)據(jù)結(jié)構(gòu)與算法： 為了記錄007跳過的路徑，可定義為如下結(jié)構(gòu)：typedef unsigned int Vertez;typedef double Distance;t

6、ypedef struct GraphNodeRecordint X; /*x軸坐標(biāo)*/int Y; /*y軸坐標(biāo)*/unsigned int Step; /*記錄到本節(jié)點一共跳了多少步*/Vertex Path; /*指向本節(jié)點的父節(jié)點，即跳到本節(jié)點之間007所在節(jié)點*/GraphNode;typedef GraphNode*Grapha;尋找跳出路徑的算法：/*讀出一組測試數(shù)據(jù)返回007跳過的路徑Graph，*Bank記錄最短到達(dá)湖岸的路徑。該算法實際上是應(yīng)用隊列對圖驚醒廣度搜索，以尋找到岸邊的最短路徑，其中入隊列與出隊列函數(shù)分別是Inject()和Pop()*/Graph read_ca

7、se(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”,&JamesJump);/*讀取步長*/ if(Bond can jumo to the bank directly) *Bank=1; /*直接跳出的情況*/ else if (num0) /*007必須經(jīng)過鱷魚頭上的情況*/ num+=2; G=GraphNew”(num);

8、 for(i=2;inum;i+) /*第3個node開始是鱷魚*/ if(Bond can jump to Gi from island) /*判斷是否能從島上跳上該點*/ Gi.Path=1; Gi.Step=1; /*一步*/ if(Bond can jump to bankfrom Gi) /*判斷該點是否能跳出*/ *Bank =i; /*007可以跳出，記錄該點*/ Skip other crocodile break; else Inject(i,D);/*插入該點，并開始下一個檢測*/while(!IsEmpty(D) /*只經(jīng)過一只鱷魚無法跳出，必須還要跳到其他鱷魚的情況*/

9、 V=Pop(D);for(i=2;istep of v+1) Gi.Path=V; Gi.Step= GV.Step+1;/*把i點練到v點后面*/ if(bond can jump from ito bank and the path is shorter than others) *Bank=i; else Inject(i,D); return G;在執(zhí)行完算法read_case后，*Bank值可能如下3種可能：（1）0，意味著007無法逃脫出去；（2）1，意味著007可以直接從島上跳出去，而不用經(jīng)過鱷魚的腦袋；（3）k，返回的第k點是007經(jīng)過最短路徑逃出鱷魚潭是經(jīng)過的最后一個頂點。

10、可以根據(jù)Gk的path參數(shù)來追蹤該點的上一點，由此類推可以得到007逃脫的最短路徑。4、圖像文件5、調(diào)試與測試5.1）調(diào)試打開工程文件，如圖1所示：（圖一打開工程）運行，出現(xiàn)如圖2所示：（圖二運行）5.2）測試方法：007步長很大，以至于可以直接跳出，例如：431007不可能逃出去的情況（根本就沒有鱷魚），例如：11一般情況的例子，例如：4 1017 027 037 045 01020 30 1最短路徑有多條，只需要輸出任意一種即可，例如：25 108 89 910 1011 1112 1213 1314 1415 1516 1618 1820 2023 2325 2527 2728 2829

11、 2931 3133 3335 3538 3841 4144 4446 4647 4749 49 輸出結(jié)果：79 916 1623 2328 2835 3541 41input.txt文件中，名稱不正確、空文件、缺少部分輸入等不規(guī)范情況，例如：5 1010 10-25 3030 30注：缺少鱷魚點（應(yīng)有5個鱷魚點）和文件結(jié)尾符（-1）。下面給出一個較復(fù)雜的測試用例和期望輸出結(jié)果。65 108 109 811 1011 1412 1216 1318 1514 1815 2215 1516 2316 3018 1818 3520 2023 23 25 3727 2728 4029 2231 31（

12、轉(zhuǎn)右行）33 3335 1840 1538 3841 4124 4844 4446 4647 4749 49-49 -19-40 -18-44 -10-39 -5-38 0-32 5-32 0-28 11-25 7-18 0-17 -2-19 3（轉(zhuǎn)右行）-12 0-10 -10-13 -1318 -2520 -4811 -22-29 18-40 40-40 -4040 -4049 -4935 -3727 -3022 -2214 -228 -1010 -18-23 29-20 20-21 23-18 19-10 15-10期望輸出結(jié)果：78 1016 1320 2027 2731 3128 4

13、05.3）測試：在input輸入測試數(shù)據(jù)，如圖3所示：（圖3 輸入測試數(shù)據(jù)）5.4）測試的結(jié)果：在output查看測試結(jié)果，如圖4所示：（圖4 測試結(jié)果）6、小 結(jié)經(jīng)過這次的課程設(shè)計，我很深刻的意識到自己的編程能力還有待提高，發(fā)現(xiàn)自己還存在很多不會的問題，有些細(xì)節(jié)問題沒有注意到，還得學(xué)會冷靜思考，加強(qiáng)算法和C語言語法的學(xué)習(xí)。其中對英語的要求也體現(xiàn)出來了，因為它說明錯誤的時候都是英語，遇到問題要及時去查相關(guān)的資料。反復(fù)的調(diào)試程序，最好是多找?guī)讉€同學(xué)來對你的程序進(jìn)行調(diào)試并聽他說對你的程序的建議。要形成自己的編寫程序與調(diào)試程序的風(fēng)格，從每個細(xì)節(jié)出發(fā)，不放過每個知識點，注意與理論的聯(lián)系和理論與實踐的差

14、別。另外，得注意符號的使用，注意對字符的處理，特別是對指針的使用時很容易出錯且調(diào)試過程不會報錯，但最后的結(jié)果卻不是你想要的。程序在完成之后，當(dāng)時你調(diào)試運行時沒有錯誤，可能錯誤就恰好隱藏在你沒有檢查的地方，要更全面的檢查，特別是幾個選擇合起來一起挨個執(zhí)行一遍。通過進(jìn)一周的學(xué)習(xí)實訓(xùn)和課程設(shè)計，又一次體驗了離開課堂的理論學(xué)習(xí)，做了一次真正實踐與理論相結(jié)合的連接。特別是所做的題目基本都不是課堂上所講的例子，但卻是每一步都是用到課堂的內(nèi)容。實訓(xùn)讓我對懂得的知識做了進(jìn)一步深入了解，讓我對其的理解與記憶更深刻，對不懂的知識與不清楚的東西也做了一定的了解，也形成了一定的個人編程風(fēng)格。在這次的課程設(shè)計中，學(xué)到了

15、許多新的知識，比如還知道了除了標(biāo)準(zhǔn)庫外其他函數(shù)的用法，知道程序的框架對于寫一個完整的程序來說是很重要的，寫出了大體框架就等于完成了一半程序，但不管怎么樣，繼續(xù)努力也是必不可少的。7、參考文獻(xiàn)【1】數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 何欽銘 馮雁 陳越 著 浙江大學(xué)出版社 2015-2【2】數(shù)據(jù)結(jié)構(gòu)（C語言版） 著 2011-118、源程序清單#include Graph.h#include Deque.h#include error.h#include #include /*讀入一個case返回一個Graph，*Bank 記錄最短到達(dá)河岸的路徑*/Graph read_case(FILE *InFile, in

16、t num, Vertex* Bank, Deque D)Graph G = NULL;Distance JamesJump;Vertex V;int x, y;int i, Times;*Bank = 0;fscanf(InFile, %lf, &JamesJump);if(CheckForEnd(0, 0, JamesJump + ISLAND_DIAMETER/2.0)for(i = 0; i (num 0) /* 007必須經(jīng)過鱷魚頭上的情況 */num += 2;G = GraphNew(num);for(i = 2; i num; i+) /* 第三個node開始是鱷魚 */fsc

17、anf(InFile, %d, &x);fscanf(InFile, %d, &y);Gi.X = x;Gi.Y = y;if(CheckForStart(x, y, JamesJump) /*判斷是否能跳上該點*/Gi.Path = 1; /*007可以跳到 */Gi.Step = 1; /* 一步 */if(CheckForEnd(x, y, JamesJump) /* 判斷該點是否能跳出 */*Bank = i; /* 007可以跳出 */Times = (num - i - 1) 1;for(i = 0; i Times; i+) /* 不必檢驗其他鱷魚 */fscanf(InFile

18、, %d, &y);DequeClear(D);break;elseInject(i, D); /* 插入該點，并開始下一個檢測 */while(!IsEmpty(D) /*只經(jīng)過一個鱷魚無法跳出，必須還要跳到其它鱷魚的情況 */V = Pop(D);for(i = 2; i GV.Step + 1)& CheckForConnect(G, V, i, JamesJump)Gi.Path = V;Gi.Step = GV.Step + 1;if(Gi.Step G*Bank.Step)& CheckForEnd(Gi.X, Gi.Y, JamesJump)*Bank = i;elseInjec

19、t(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無法跳出 */fprintf(OutFile, %dn, -1);break;case 1: /* 007可以直接跳出 */fprintf(OutFile, %dn, 1);break;default: Times = GBank.Step + 1;/* 跳的步數(shù) */while(Bank != 1)/* 跟蹤路徑 */Push(Bank, D);Bank = GBank.Pat