鹽城工學院數(shù)據(jù)結構課程設計拯救007

1、 數(shù)據(jù)結構課程設計題目：最短路徑拯救007問題專業(yè)計算機科學與技術（物聯(lián)網(wǎng)技術應用）學生姓名*班級B計算機125班學號12107045*指導教師王翠香完成日期2014年1月10日目 錄1 簡介32算法說明33測試結果64分析與探討95小結9參考文獻12附 錄13一、簡介最短路徑是，在一個圖中，若從一個頂點到另一個頂點存在著一條路徑（這里只討論無回路的簡單路徑），則稱該條路徑長度為為該路徑上所有經(jīng)過的邊的數(shù)目，它也等于該路徑上的頂點數(shù)減1。由于從一個頂點到另一個頂點可能存在著多條路徑，在每條路徑上所經(jīng)過的邊數(shù)可能不同，把路徑長度最短（經(jīng)過的邊數(shù)最少）的那條路徑叫做最短路徑，其路徑長度叫做最短距離

2、。這是對無權圖而言的，若圖是帯權圖，則把從一個頂點vi到vj的一條路徑上所有經(jīng)過邊的權值之和定義為該路徑的帶權路徑長度。把帶權路徑長度最短的那條路徑稱為該有權圖的最短路徑，其路徑長度稱為最短距離。Dijksra算法：如何求解從一個頂點到其余每個頂點的最短路徑呢？狄克斯特拉于1959年提出了解決此問題的一種按路徑長度的遞增次序產(chǎn)生最短路徑的算法。基本思想是，從圖中給定源點到其他各個頂點之間客觀上應個存在一條最短路徑，在這組最短路徑中，按其長度的遞增次序求出到不同頂點的最短路徑和路徑長度。圖是一種較線性結構和樹形結構更為復雜的非線性數(shù)據(jù)結構，這種復雜性主要來自數(shù)據(jù)元素之間的復雜關系。在圖結構中，任

3、何兩個數(shù)據(jù)元素之間都可能存在關系，一般用頂點表示數(shù)據(jù)元素，而用頂點之間的連線表示數(shù)據(jù)元素之間的關系。圖的二元組定義為：G=(V,E)。其中V是非空的頂點集合，E是V上的二元關系集合。 題目內容：看過007系列的電影的人們一定很熟悉Jams Bond這個世界上最著名的 特工了。在電影“Live And Let Die”中Jams Bond被一組毒品販子抓住并且關到湖中心的一個小島上，而湖中有很多兇猛的鱷魚。這時Jams Bond做出了一個最驚心動魄的事情來逃脫他跳到了最近的鱷魚的頭上，在鱷魚還沒有反映過來的時候，他有跳到另一支鱷魚的頭上.。最后他終于安全地跳到了湖岸上。 假設湖是100*100的

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

5、尾。 輸出要求： 程序結果輸出到output.txt文件中。對于每組輸入數(shù)據(jù)，如果007可以逃脫，則輸出到output.txt文件的內容格式如下：第一行是007必須跳的最小步數(shù)，然后按照跳出順序記錄跳出路徑上的鱷魚坐標（x,y），每行一個坐標。如果007不可能跳出去，則將-1寫入文件。如果這里有很多個最短路徑，只需輸入其中的任意一種。 輸入例子：4 10 /*第一組輸入數(shù)據(jù)*/17 027 037 045 01 10 /*第二組輸入數(shù)據(jù)*/20 30-1 輸出例子：5 /*對應第一組數(shù)據(jù)的輸出*/17 027 045 0-1 /*對應第二組數(shù)據(jù)的輸出*/提示：將每個鱷魚看作圖中的每一個頂點。如

6、果007可以從A點跳到B點，則A和B之間就有一條邊。主要數(shù)據(jù)結構與算法： 為了記錄007跳過的路徑，可定義為如下結構：typedef unsigned int Vertez;typedef double Distance;typedef struct GraphNodeRecordint X; /*x軸坐標*/int Y; /*y軸坐標*/unsigned int Step; /*記錄到本節(jié)點一共跳了多少步*/Vertex Path; /*指向本節(jié)點的父節(jié)點，即跳到本節(jié)點之間007所在節(jié)點*/GraphNode;typedef GraphNode*Grapha;尋找跳出路徑的算法：/*讀出一組

7、測試數(shù)據(jù)返回007跳過的路徑Graph，*Bank記錄最短到達湖岸的路徑。該算法實際上是應用隊列對圖驚醒廣度搜索，以尋找到岸邊的最短路徑，其中入隊列與出隊列函數(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”,&JamesJump);/*讀取步長*/ if(Bond

8、 can jumo to the bank directly) *Bank=1; /*直接跳出的情況*/ else if (num0) /*007必須經(jīng)過鱷魚頭上的情況*/ num+=2; G=GraphNew”(num); 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可以跳出，記錄該點

9、*/ Skip other crocodile break; else Inject(i,D);/*插入該點，并開始下一個檢測*/while(!IsEmpty(D) /*只經(jīng)過一只鱷魚無法跳出，必須還要跳到其他鱷魚的情況*/ 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í)行完算法re

10、ad_case后，*Bank值可能如下3種可能：（1）0，意味著007無法逃脫出去；（2）1，意味著007可以直接從島上跳出去，而不用經(jīng)過鱷魚的腦袋；（3）k，返回的第k點是007經(jīng)過最短路徑逃出鱷魚潭是經(jīng)過的最后一個頂點。可以根據(jù)Gk的path參數(shù)來追蹤該點的上一點，由此類推可以得到007逃脫的最短路徑。三、測試結果 對于本程序，需要應用各種類型的測試用例來進行測試。一般來說，可以設計一下幾種類型的測試用例。 007步長很大，以至于可以直接跳出，例如：0 43- 1007不可能逃出去的情況（根本就沒有鱷魚），例如：0 1- 1一般情況的例子，例如： 4 10 17 027 037 045 0

11、1 1020 30- 1最短路徑有多條，只需要輸出任意一種即可，例如： 25 10 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 18 18 20 20 23 23 25 25 27 27 28 2829 2931 3133 3335 3538 3841 4144 4446 4647 4749 49 輸出結果： 7 9 916 1623 2328 2835 3541 41input.txt文件中，名稱不正確、空文件、缺少部分輸入等不規(guī)范情況，例如： 5 10 10 10-25 3030 30注：缺少鱷魚點（應有5個鱷魚點）和文件結尾符（-1

12、）。運行結果：輸入數(shù)據(jù)： 0 430 14 1017 027 037 045 01 1020 3025 108 89 910 1011 1112 1213 1314 1415 1516 1618 1820 2023 2325 2527 2728 2829 2931 3133 3335 3538 3841 4144 4446 4647 4749 4910 2010 1020 2010 30輸出結果1-1517 027 037 045 0-179 916 1623 2328 2835 3541 41310 1010 303-10 -10-10 -303-10 -10-30 -10310 1030

13、10310 1010 30-1710 1010 1520 1522 2231 2040 20-17-10 -8-15 -15四、分析與探討1.明確題目中的已知條件(1)007被關的小島在湖的中心；(2)小島是圓形，圓心在（0，0），而且直徑是15；(3)沒有兩只鱷魚在同一個位置；(4)鱷魚的坐標值都是整數(shù)。2.一些判斷007是否能跳出的細節(jié)(1)判斷007是否能夠直接從島上跳到湖岸：由已知條件可得，湖是一個正方形，邊長為100，中心是在（0，0），四個頂點分別是（50，50）,(50,-50),(-50,-50),(-50,50)。而湖中小島的直徑是15.所以如果007可以跳大于等于（50-1

14、5/2）=42.5，他就可以直接從小島跳到湖岸，而不用經(jīng)過鱷魚。(2)判斷007是否能夠直接從島上跳到湖中點A：已知半徑是7.5，假設點A的坐標是（x,y），007的步長是L，則當點A到中心（0，0）的距離小于等于007的步長加上小島的半徑7.5的時候就能確定007可以從島上跳到點A，即：x*x+y*y=(L+7.5)*(L+7.5)。(3)判斷007是否能夠從點A跳到點B：假設007的步長是L所以如果兩點之間的距離小于等于L，則判斷007可以從A跳到B，即（A.x-B.x）2+(A.y-B.y)2=50或|A.y|+L=50；其他情況時007不能從A點跳到湖岸。五、小結經(jīng)歷了這次課程設計實踐

15、，我感觸頗多。發(fā)覺自己的編程能力還是需要提高，看著課程設計指導書上的代碼，首先在意思的讀取上存在困難。我知道這是作為一個合格計算機專業(yè)的學生身上所不應該有點。所以我在課程設計之初的時間里，一直很著急，也很努力地去弄清楚其中蘊含的知識?？梢哉f是功夫不負有心人，5天后我順利地上交了屬于自己的一份較為滿意的課程設計報告。做的過程并不順利，而其中的種種遭遇更是讓我反省良久。一路堅持下來，其中的艱辛也許只有經(jīng)歷過才能真正體會。不過，經(jīng)過一番實踐后，當看到自己親手做的東西就那么真實的擺在眼前，曾經(jīng)的心血與付出終于有了回報，那份激動與喜悅的心情又豈是三言兩語說得清楚的！“如人飲水，冷暖自知”，現(xiàn)在我是真的體

16、會到了。總的來說，我覺得這次設計實踐收獲頗豐，于今后的學業(yè)、步入社會后參加工作乃至做人做事都是一筆不小的財富！通過這次課程設計，我懂得了實踐的重要性、團隊合作精神的可貴以及做事前的充足準備與做事過程中的堅持和細心謹慎對于高質高效地完成一項工作的特殊意義。任何事情都有一個循序漸進的過程，知難而進、勇往直前，只有這樣才有可能領略險峰的無限風光。治學、做人又何嘗不是如此呢？ 先說實踐。關于實踐，前人曾留有十二字箴言：“實踐是檢驗真理的唯一標準”，經(jīng)過這次課程設計，我所理解的實踐已遠不只此。人說“愛過才知情深，醉過方知酒濃”，我以為，只有實踐才會出真知，沒有實踐，任何理論、見解都是蒼白無力的。眼之所見

17、、心之所想大多數(shù)時候并不就是手之所為。在動手嘗試之前，我可以算是一個眼高手低的人。課程設計的題目下來了，共有三個可供選擇。相較之下我選了做“拯救007”，本以為這是最簡單的，基本上可以不費多大心力即輕松搞定。因此開始的幾天里也沒怎么刻意著手這件事情。事實卻是，等到我真正做了才發(fā)現(xiàn)隨著問題的不斷出現(xiàn)和為此而查閱許多相關的資料，花了那么多的時間與精力，做的過程還是如此的困難重重，并且做出來的東西也并非盡善盡美。方知許多事情并非都如人所想，不實踐、不參與是無論如何也不會明白的。實踐之重要正在于此！這段小小的經(jīng)歷使我感觸很深，也教會我在以后的學習與工作中不要再眼高手低，任何事情都需親自嘗試后再做定斷。

18、牢記“眼之所見、心之所想非手之所為也！”接下來再說著手前的準備。三國時諸葛亮草船借箭有賴“萬事俱備，只欠東風”，而我的設計能順利進行也必須有充足的準備作為后盾。只可惜在一開始的時候由于并不很重視因此也未意識到這一點，導致做的過程中停停找找、找找停停，嚴重影響了設計進度和效率，并且這種臨陣磨槍式的做法也使得準備很不充分，往往是急需要用的東西找也找不到，如某控件類的方法如何使用、其原型或者參數(shù)的類型與意義為何等等。這樣一來，自然會遇到重重困難。我想，如果在動手之前已經(jīng)做好了充足準備，必然會少遇到很多麻煩，也不會一度出現(xiàn)舉步維艱的情況。當然了，這次還只是一個小小的設計，如果換成是某個大型系統(tǒng)的設計豈

19、不是無法想象？所以這次經(jīng)歷也算是給了我一個教訓：千萬不要打無準備的仗！早準備方保無虞。說到了準備，也得說說做事過程中的堅持與細心謹慎。很難想象如果沒有堅持到底的勇氣和不懈的努力，當一個人面對困難時能迎難而上并一路堅持走下來。當初我選定這個設計課題時正是考慮到它簡單、易完成（當然事實并非如此），不過后來做的時候不斷出現(xiàn)新的問題，而且有些還是從理論上無法解釋的，這時我就在想算了吧，這么難搞，還是換別的做。正好其他同學做的在網(wǎng)上找到了很多原本的版本，因而做起來就不費吹灰之力。當時幾乎就在一念之間轉了方向，好在隨后終于做成功了一部分功能。這點小小的成功讓我體會到了自己動手的樂趣與成功后的喜悅，在此激勵

20、之下，幸而堅持了下來?；匚镀渲械钠D辛，盡享成功的喜悅，縱是雛鷹試翼之作，畢竟自己所為，比之其他同學照搬別人的代碼以完成任務卻不知到底做了什么、又有什么收獲，不是更有意義嗎？能夠堅持即已成功一半。世上無難事，唯恐少堅持！此外，在做的過程中不可能是一帆風順的，必然免不了頻繁出錯。這一方面是由于輸入時的粗心大意造成的，另一方面則是編寫的代碼本身的問題。對于前者，如果能在操作時做到細心謹慎，當然可以避免。即便免不了輸入錯誤，在調試的過程中也應細心謹慎，惟其如此，方可免去許多麻煩，保證軟件設計的質量與效率。由于要不斷的調試，而VC6.0對于用戶所作的改動會自動保存，因此就可能出現(xiàn)保存了修改后錯誤的結果，

21、反而將前面做好的調試無誤的內容覆蓋掉的情況。如果沒有時時保持細心謹慎的態(tài)度，及時對調試無誤的結果加以保存，將可能遭遇前功盡棄的“滅頂之災”。不管怎樣，時時處處細心謹慎，方保順利無虞。我想，無論是治學還是工作或是為人，這樣的一種態(tài)度都是至關重要的。由于是初次設計，僅憑自己一人之力是很難完成的，所以大家或借助于網(wǎng)絡，或借助于參考書籍、期刊資料等。我也不例外，和幾位同學一起研究設計方案及具體實現(xiàn)方法，并跑了好幾趟圖書館，查資料，抄筆記，上網(wǎng)搜索資料，終于在大家的通力合作之下完成了這個項目。一起做的過程大家朝著一個共同的目標努力，分工協(xié)作，互相交流，提出不同的想法，不斷完善，不斷進步，一個一個的問題迎

22、刃而解，一個一個的功能不斷做出來。最后，集體的勞動終于換來了豐碩的成果（盡管并不完美）。這次經(jīng)歷使我懂得了團隊合作精神的可貴。不僅如此，我覺得這次合作的過程真的是很愉快，很讓人回味和懷念！我想將來參加工作后這種合作還會有，參與合作，倡導這種合作精神是很可貴和重要的。社會的進步使得人們面臨的問題越來越復雜，迫使人們尋求集體的智慧、團隊的力量來解決它們。個人的力量終究是有限的，也不可能獨立完成所有的事情，每個人都有義務和必要學會與別人溝通、交流，學會合作，參與合作，在合作的過程中培養(yǎng)這樣一種意識。對于將來的工作，這也是有重要意義的。最后，值得一提的是編輯這份電子文稿，也使我學會了使用更多的Word

23、功能。雖然不是本次設計的正題，但畢竟也算是一種收獲吧。能夠多學一點知識，總算也是一種成就。課程設計即將結束，一個個挑燈夜戰(zhàn)、激烈討論的夜晚也已過去?；仡櫿麄€過程，更清楚的認識到知識的欠缺，而自己所學的C語言知識只能算是皮毛，還有更多的東西需要我去研究，去掌握。盡管如此，我也不會退縮、停滯不前，因為通過這次設計實踐，我已初識C語言的廬山真面目。這才是最重要的。相信經(jīng)過此次課程設計，日后將會有所改進。此外，我還要感謝所有幫助過我的老師、同學，感謝你們在這幾天里給我的幫助與鼓勵。正是因為你們的幫助與鼓勵，我才能很好的完成這一次的課程設計，才能學到這么多的知識；也正是因為你們的幫助與鼓勵，我真正認識到

24、了團隊力量的偉大，“團結就是力量?！备兄x你們，謝謝。 參考文獻1 劉振安,劉燕君.C程序設計課程設計M.北京機械工業(yè)出版社,2004年9月2 譚浩強.C程序設計（第三版）.清華大學出版社,2005年7月3 嚴蔚敏,吳偉民.數(shù)據(jù)結構（C語言版）.清華大學出版社,1997年4月4 李志球實用C語言程序設計教程 北京：電子工業(yè)出版社，19995 王立柱：C/C+與數(shù)據(jù)結構 北京：清華大學出版社，20026 吳文虎 程序設計基礎 北京：清華大學出版社，20037 郭福順，王曉芬，李蓮治 數(shù)據(jù)結構（修訂本），大連理工大學出版社，19978 潘道才，陳一華 數(shù)據(jù)結構，電子科技大學出版社，1994附錄：源代

25、碼本程序包含3個頭文件和4個C源程序文件，分別是：Graph.h Graph.c Deque.h Deque.c error.h error.c main.c #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 V

26、ertex;typedef double Distance;typedef struct GraphNodeRecordint X; /* x軸坐標 */int Y; /* y軸坐標 */unsigned int Step; /*跳至該點的步數(shù) */Vertex Path; /*記錄上一個點 */ GraphNode;typedef GraphNode *Graph;Graph GraphNew(int NodeNum);void GraphDelete(Graph G);/* 判斷007是否能從起始處跳至該點(x, y) */int CheckForStart(int x, int y, D

27、istance d);/* 判斷007是否能從該點跳至河岸 */int CheckForEnd(int x, int y, Distance d);/* 判斷007是否能從點i跳至點j */ int CheckForConnect(Graph g, Vertex i, Vertex j, Distance d);#endif#include Graph.h#include error.h#include /*創(chuàng)建新的Graph*/Graph GraphNew(int NodeNum)Graph G;int i;if(NodeNum = 0)return NULL;G = malloc(Node

28、Num * sizeof(GraphNode); /* 分配空間 */CHECK(G);for(i = 0; i NodeNum; i+) /* 初始化 */Gi.X = 0;Gi.Y = 0;Gi.Step = INFINITY; Gi.Path = 0;return G;/*刪除一個Graph)*/void GraphDelete(Graph G)if(G)free(G);/*判斷007是否能從起始處跳至該點(x, y)，步長是d*/int CheckForStart(int x, int y, Distance d)double t;t = (ISLAND_DIAMETER + (d *

29、 2.0);return (x*x + y*y) = t*t/4.0; /* x2 + y2 = (ISLAND_DIAMETER/2.0 + d)2 */*判斷007是否能從該點跳至河岸，步長是d*/int CheckForEnd(int x, int y, Distance d)if(x 0)x = -x; /* 取x的絕對值 */if(y = LAKE_BOUNDARY_X - x)/* 由于湖是個正方形，只需檢查這兩個距離*/| (d = LAKE_BOUNDARY_Y - y);/*判斷007是否能從點i跳至點j，步長是d*/int CheckForConnect(Graph g,

30、Vertex i, Vertex j, Distance d)int x, y;x = gi.X - gj.X;y = gi.Y - gj.Y;return x*x + y*y = d*d;#ifndef _DEQUE_H_#define _DEQUE_H_typedef unsigned int ElemType; /* 在本程序中ElemType指定為int */* 鏈表形式 */typedef struct NodeRecordElemType Element; struct NodeRecord *Next; /* 指向下一個node */ *Node; typedef struct

31、DequeRecord Node Front, Rear; /* 分別指向Deque的前后兩個點 */ *Deque;Deque DequeNew();void DequeDelete(Deque D); void DequeClear(Deque D); int IsEmpty(Deque D); void Push(ElemType X, Deque D); ElemType Pop(Deque D); void Inject(ElemType X, Deque D); #endif4. Deque.c#include Deque.h#include error.h#include /*創(chuàng)

32、建新的Deque*/Deque DequeNew()Deque D;D = malloc(sizeof(struct DequeRecord);CHECK(D);D-Front = D-Rear = malloc(sizeof(struct NodeRecord); /* 空的頭 */CHECK(D-Front);D-Front-Element = 0; /* 初始化 */D-Rear-Next = NULL;return D;/*刪除Deque*/void DequeDelete(Deque D)if(D)while(D-Front) D-Rear = D-Front-Next;free(D

33、-Front);D-Front = D-Rear;free(D);/*DequeClear刪除所有的節(jié)點除了頭節(jié)點*/void DequeClear(Deque D)if(D)while(D-Front-Next) /* 刪除第一個節(jié)點 */D-Rear = D-Front-Next-Next;free(D-Front-Next);D-Front-Next = D-Rear;D-Rear = D-Front;/*判斷Deque是否為空*/int IsEmpty(Deque D)return D-Front = D-Rear;/*將X元素壓占到D中*/void Push(ElemType X,

34、Deque D) Node NewNode; NewNode = malloc(sizeof(struct NodeRecord); /* 建立新的節(jié)點 */ CHECK(NewNode);NewNode-Element = X; NewNode-Next = D-Front-Next; if(D-Front = D-Rear) /* 如果D為空 */D-Rear = NewNode;D-Front-Next = NewNode;/* 壓棧 */ /*將第一個元素出棧*/ElemType Pop(Deque D) Node Temp; ElemType Item; if(D-Front = D

35、-Rear)Error(Deque is empty);return 0; else Temp = D-Front-Next;/* 得到第一個元素 */ D-Front-Next = Temp-Next; /* 重置第一個元素 */if(Temp = D-Rear)/* 如果只有一個元素 */D-Rear = D-Front;/* 將D置空 */ Item = Temp-Element; free(Temp);return Item; /*插入元素X至D末尾*/ void Inject(ElemType X, Deque D) Node NewNode;NewNode = malloc(siz

36、eof(struct NodeRecord); /* 創(chuàng)建新節(jié)點 */ CHECK(NewNode);NewNode-Element = X; NewNode-Next = NULL;D-Rear-Next = NewNode;D-Rear = NewNode; 5.error.h # 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

37、*msg);#endif6. error.c #include error.h#include #include /*打印錯誤信息，并退出程序*/ void Error(const char *msg)if(NULL != msg)fprintf(stderr,%sn,msg);exit(-1);/*打印警告信息，但并不退出程序*/void Warning(const char *msg)if(NULL != msg)fprintf(stderr,%sn,msg);7. main.c#include Graph.h#include Deque.h#include error.h#include

38、 #include /*讀入一個case返回一個Graph，*Bank 記錄最短到達河岸的路徑*/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, &JamesJump);if(CheckForEnd(0, 0, JamesJump + ISLAND_DIAMETER/2.0)for(i = 0; i (num 0) /* 007必須經(jīng)

39、過鱷魚頭上的情況 */num += 2;G = GraphNew(num);for(i = 2; i num; i+) /* 第三個node開始是鱷魚 */fscanf(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+)