課程設(shè)計--最短路徑拯救007

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：23 大小：205.50KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩22頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》報告　　最短路徑—拯救007 　　目錄　　一、簡介3　　二、算法說明4<p

2、>　　三、測試結(jié)果7　　參考文獻14　　一、簡介　　最短路徑是，在一個圖中，若從一個頂點到另一個頂點存在著一條路徑（這里只討論無回路的簡單路徑），則稱該條路徑長度為為該路徑上所有經(jīng)過的邊的數(shù)

3、目，它也等于該路徑上的頂點數(shù)減1。由于從一個頂點到另一個頂點可能存在著多條路徑，在每條路徑上所經(jīng)過的邊數(shù)可能不同，把路徑長度最短（經(jīng)過的邊數(shù)最少）的那條路徑叫做最短路徑，其路徑長度叫做最短距離。這是對無權(quán)圖而言的，若圖是帯權(quán)圖，則把從一個頂點vi到vj的一條路徑上所有經(jīng)過邊的權(quán)值之和定義為該路徑的帶權(quán)路徑長度。把帶權(quán)路徑長度最短的那條路徑稱為該有權(quán)圖的最短路徑，其路徑長度稱為最短距離。　　Dij

4、ksra算法：如何求解從一個頂點到其余每個頂點的最短路徑呢？狄克斯特拉于1959年提出了解決此問題的一種按路徑長度的遞增次序產(chǎn)生最短路徑的算法。基本思想是，從圖中給定源點到其他各個頂點之間客觀上應(yīng)個存在一條最短路徑，在這組最短路徑中，按其長度的遞增次序求出到不同頂點的最短路徑和路徑長度。　　圖是一種較線性結(jié)構(gòu)和樹形結(jié)構(gòu)更為復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，這種復(fù)雜性主要來自數(shù)據(jù)元素之間的復(fù)雜關(guān)系。在圖結(jié)構(gòu)中

5、，任何兩個數(shù)據(jù)元素之間都可能存在關(guān)系，一般用頂點表示數(shù)據(jù)元素，而用頂點之間的連線表示數(shù)據(jù)元素之間的關(guān)系。圖的二元組定義為：G=(V,E)。其中V是非空的頂點集合，E是V上的二元關(guān)系集合。　　題目內(nèi)容：　　看過007系列的電影的人們一定很熟悉Jams Bond這個世界上最著名的特工了。在電影“Live And

6、 Let Die”中Jams Bond被一組毒品販子抓住并且關(guān)到湖中心的一個小島上，而湖中有很多兇猛的鱷魚。這時Jams Bond做出了一個最驚心動魄的事情來逃脫——他跳到了最近的鱷魚的頭上，在鱷魚還沒有反映過來的時候，他有跳到另一支鱷魚的頭上.。。。。。。最后他終于安全地跳到了湖岸上。　　假設(shè)湖是100*100的正方形，設(shè)湖的中心在（0，0），湖的東北角的坐標(biāo)是（50，50）。湖中心的圓環(huán)小島

7、的圓心在（0，0），直徑是15.。一些兇殘的鱷魚分布在湖中不同的位置?，F(xiàn)已知的湖中的鱷魚的位置和Jams Bond可以跳的最大距離，請你告訴Jams Bondyitiao 最短的到達湖邊的路徑。他逃出去的路徑長度等于他跳的次數(shù)。　　二、算法說明　　程序從“input.txt”文件中讀取輸入信息，這個文件包含了多組輸入

8、數(shù)據(jù)。每組輸入數(shù)據(jù)的起始行中包含了兩個整數(shù)n和d，n是鱷魚的數(shù)量而且n<=100，d是007可以跳的最大距離而且d>0。起始行下面的每一行是鱷魚的坐標(biāo)（x,y），其中x,y都是整數(shù)，而且沒有任何兩只鱷魚出現(xiàn)在同一位置。Input.txt文件以一個負數(shù)結(jié)尾。　　輸出要求：　　程序結(jié)果輸出到output.tx

9、t文件中。對于每組輸入數(shù)據(jù)，如果007可以逃脫，則輸出到output.txt文件的內(nèi)容格式如下：第一行是007必須跳的最小步數(shù)，然后按照跳出順序記錄跳出路徑上的鱷魚坐標(biāo)（x,y），每行一個坐標(biāo)。如果007不可能跳出去，則將-1寫入文件。如果這里有很多個最短路徑，只需輸入其中的任意一種。　　輸入例子：　　10

10、 /*第一組輸入數(shù)據(jù)*/　　17 0　　27 0　　37 0　　45 0　　1

11、 10 /*第二組輸入數(shù)據(jù)*/　　20 30　　-1　　輸出例子：　　/*對應(yīng)第一組數(shù)據(jù)的輸出*/<

12、;b>　　17 0　　27 0　　45 0　　-1 /*對應(yīng)第二組數(shù)據(jù)的輸出*/　　提示：將每個鱷魚看作圖中的每一個頂點。如果007可以從A點跳到B點，則

13、A和B之間就有一條邊。　　主要數(shù)據(jù)結(jié)構(gòu)與算法：　　為了記錄007跳過的路徑，可定義為如下結(jié)構(gòu)：　　typedef unsigned int Vertez;　　typedef double Distance;　　typedef st

14、ruct GraphNodeRecord{　　int X; /*x軸坐標(biāo)*/　　int Y; /*y軸坐標(biāo)*/　　unsigned int Step; /*記錄到本節(jié)點一共跳了多少步*/　　Ver

15、tex Path; /*指向本節(jié)點的父節(jié)點，即跳到本節(jié)點之間007所在節(jié)點*/　　}GraphNode;　　typedef GraphNode*Grapha;　　尋找跳出路徑的算法：　　/*讀出一組測試數(shù)據(jù)返回007跳過的路徑Graph，*Bank記錄最短到達

16、湖岸的路徑。該算法實際上是應(yīng)用隊列對圖驚醒廣度搜索，以尋找到岸邊的最短路徑，其中入隊列與出隊列函數(shù)分別是Inject()和Pop()*/　　Graph read_case(FILE * InFile,int num,Vertex* Bank,Deque D)　　{ 　　G

17、raph G=NULL;　　Distance JamesJump;　　Vertex V;　　int x,y;　　int i,Times;　　*Bank =

18、 0; /*初始化跳出的路徑的記錄*/　　fscanf(Infile,”%lf”,&JamesJump);/*讀取步長*/　　if(Bond can jumo to the bank directly)　　{　　*

19、Bank=1; /*直接跳出的情況*/　　}　　else if (num>0) /*007必須經(jīng)過鱷魚頭上的情況*/　　{　　num+=2;

20、　　G=GraphNew”(num);　　for(i=2;i<num;i++) /*第3個node開始是鱷魚*/　　{　　if(Bond can jump to G[i] from island) /*判斷是否能從島上跳上

21、該點*/　　{　　G[i].Path=1;　　G[i].Step=1; /*一步*/　　if(Bond can jump to bankfrom G[i]) /*判斷該點是否能跳出*/<p&g

22、t;　　{　　*Bank =i; /*007可以跳出，記錄該點*/　　Skip other crocodile　　break;　　}</p&

23、gt;　　else　　Inject(i,D);/*插入該點，并開始下一個檢測*/　　}　　}　　while(!IsEmpty(D))

24、 /*只經(jīng)過一只鱷魚無法跳出，必須還要跳到其他鱷魚的情況*/　　{ 　　V=Pop(D);　　for(i=2;i<num;i++)/*從這只鱷魚跳到其他各只鱷魚*/

25、{　　if(bond can jump from v to i,and step of i>step of v+1)　　{　　G[i].Path=V;　　G[i].Step= G[V].Step+1;/*把i

26、點練到v點后面*/　　if(bond can jump from ito bank and the path is shorter than others)　　*Bank=i;　　else　　In

27、ject(i,D);　　}　　}　　}　　}　　return

28、 G;　　}　　在執(zhí)行完算法read_case后，*Bank值可能如下3種可能：　?。?）0，意味著007無法逃脫出去；　?。?）1，意味著007可以直接從島上跳出去，而不用經(jīng)過鱷魚的腦袋；

29、　?。?）k，返回的第k點是007經(jīng)過最短路徑逃出鱷魚潭是經(jīng)過的最后一個頂點。可以根據(jù)G[k]的path參數(shù)來追蹤該點的上一點，由此類推可以得到007逃脫的最短路徑。　　三、測試結(jié)果　　對于本程序，需要應(yīng)用各種類型的測試用例來進行測試。一般來說，可以設(shè)計一下幾種類型的測試用例。

30、　　?007步長很大，以至于可以直接跳出，例如：　　43　　1　　?007不可能逃出去的情況（根本就沒有鱷魚），例如：　　1</p&

31、gt;　　1　　?一般情況的例子，例如：　　4 10　　17 0　　27 0

32、;　　37 0　　45 0　　10　　20 30　　1

33、　　?最短路徑有多條，只需要輸出任意一種即可，例如：　　25 10　　8 8　　9 9

34、　10 10　　11 11　　12 12　　13 13　　14 14

35、　　15 15　　16 16　　18 18　　20 20　　23 23&

36、lt;/b>　　25 25　　27 27　　28 28　　29 29<p&g

37、t;　　31 31　　33 33　　35 35　　38 38　　41 41

38、;　　44 44　　46 46　　47 47　　49 49<b&

39、gt;　　輸出結(jié)果：　　7　　9 9　　16 16　　23 23&l

40、t;p>　　28 28　　35 35　　41 41　　?input.txt文件中，名稱不正確、空文件、缺少部分輸入等不規(guī)范情況，例如：<b&

41、gt;　　5 10　　10 10　　-25 30　　30 30　　注：缺少鱷魚點（應(yīng)有5個鱷魚點）和文件結(jié)尾符（-1）。</

42、p>　　運行結(jié)果：　　輸入數(shù)據(jù)：　　0 43　　0 1　　4 10<

43、/b>　　17 0　　27 0　　37 0　　45 0

44、　　1 10　　20 30　　25 10　　8 8　　9 9

45、;　　10 10　　11 11　　12 12　　13 13　　14 14</

46、p>　　15 15　　16 16　　18 18　　20 20　　23 23

47、　　25 25　　27 27　　28 28　　29 29&

48、lt;b>　　31 31　　33 33　　35 35　　38 38　　41 41</p&

49、gt;　　44 44　　46 46　　47 47　　49 49　　10 20&l

50、t;/b>　　10 10　　20 20　　10 30　　輸出結(jié)果<

51、b>　　1　　-1　　5　　17 0　　27 0&l

52、t;b>　　37 0　　45 0　　-1　　7　　9 9<p&g

53、t;　　16 16　　23 23　　28 28　　35 35　　41 41<

54、/p>　　3　　10 10　　10 30　　3　　-10 -10</

55、b>　　-10 -30　　3　　-10 -10　　-30 -10<

56、b>　　3　　10 10　　30 10　　3　　10 10<p&

57、gt;　　10 30　　-1　　7　　10 10　　10 15

58、　　20 15　　22 22　　31 20　　40 20　　-1</b&g

59、t;　　7　　-10 -8　　-15 -15　　四、分析與探討　　1.明確題目

60、中的已知條件　　(1)007被關(guān)的小島在湖的中心；　　(2)小島是圓形，圓心在（0，0），而且直徑是15；　　(3)沒有兩只鱷魚在同一個位置；　　(4)鱷魚的坐標(biāo)值都是整數(shù)。　　2.一些判斷007是否能跳出的細節(jié)

61、;　　(1)判斷007是否能夠直接從島上跳到湖岸：由已知條件可得，湖是一個正方形，邊長為100，中心是在（0，0），四個頂點分別是（50，50）,(50,-50),(-50,-50),(-50,50)。而湖中小島的直徑是15.所以如果007可以跳大于等于（50-15/2）=42.5，他就可以直接從小島跳到湖岸，而不用經(jīng)過鱷魚。　　(2)判斷007是否能夠直接從島上跳到湖中點

62、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)*(L+7.5)。　　(3)判斷007是否能夠從點A跳到點B：假設(shè)007的步長是L所以如果兩點之間的距離小于等于L，則判斷007可以從A跳到B，即（A.x-B.x）^2+(A.y

63、-B.y)^2<=L*L；其他情況時007不能從A點跳到B點。　　(4)判斷007是否能夠從點A跳到湖岸：當(dāng)從A點到湖岸的距離小于等于007的步長的時候，說明他可以從A點跳到湖岸，|A.x|+L>=50或|A.y|+L>=50；其他情況時007不能從A點跳到湖岸。　　五、小結(jié)

64、　　經(jīng)歷了這次課程設(shè)計實踐，我感觸頗深。此前一直錯誤的以為做課程設(shè)計其實是件很簡單的事情，根本不需要興師動眾而且花費那么長的時間，兩三天足矣。在此錯誤認識的引導(dǎo)下，也就沒怎么把它當(dāng)回事，只打算隨隨便便應(yīng)付一下，完工交差。但是等到真正親歷后才發(fā)現(xiàn)原來自己是多么的愚蠢可笑，自己的想法又是多么的幼稚、荒謬。　　做的過程并不順利，而其中的種種遭遇更是讓我反省良久。一路堅持下來，其中的艱

65、辛也許只有經(jīng)歷過才能真正體會。不過，經(jīng)過一番實踐后，當(dāng)看到自己親手做的東西就那么真實的擺在眼前，曾經(jīng)的心血與付出終于有了回報，那份激動與喜悅的心情又豈是三言兩語說得清楚的！“如人飲水，冷暖自知”，現(xiàn)在我是真的體會到了。　　總的來說，我覺得這次設(shè)計實踐收獲頗豐，于今后的學(xué)業(yè)、步入社會后參加工作乃至做人做事都是一筆不小的財富！通過這次課程設(shè)計，我懂得了實踐的重要性、團隊合作精神的可貴以及做事前的充足

66、準備與做事過程中的堅持和細心謹慎對于高質(zhì)高效地完成一項工作的特殊意義。任何事情都有一個循序漸進的過程，知難而進、勇往直前，只有這樣才有可能領(lǐng)略險峰的無限風(fēng)光。治學(xué)、做人又何嘗不是如此呢？　　先說實踐。關(guān)于實踐，前人曾留有十二字箴言：“實踐是檢驗真理的唯一標(biāo)準”，經(jīng)過這次課程設(shè)計，我所理解的實踐已遠不只此。人說“愛過才知情深，醉過方知酒濃”，我以為，只有實踐才會出真知，沒有實踐，任何理論、見解都是

67、蒼白無力的。眼之所見、心之所想大多數(shù)時候并不就是手之所為。在動手嘗試之前，我可以算是一個眼高手低的人。課程設(shè)計的題目下來了，共有三個可供選擇。相較之下我選了做“拯救007”，本以為這是最簡單的，基本上可以不費多大心力即輕松搞定。因此開始的幾天里也沒怎么刻意著手這件事情。事實卻是，等到我真正做了才發(fā)現(xiàn)隨著問題的不斷出現(xiàn)和為此而查閱許多相關(guān)的資料，花了那么多的時間與精力，做的過程還是如此的困難重重，并且做出來的東西也并非盡善盡美。方知許多事

68、情并非都如人所想，不實踐、不參與是無論如何也不會明白的。實踐之重要正在于此！這段小小的經(jīng)歷使我感觸很深，也教會我在以后的學(xué)習(xí)與工作中不要再眼高手低，任何事情都需親自嘗試后再做定斷。牢記“眼之所見、心之所想非手之所為也！”　　接下來再說著手前的準備。三國時諸葛亮草船借箭有賴“萬事俱備，只欠東風(fēng)”，而我的設(shè)計能順利進行也必須有充足的準備作為后盾。只可惜在一開始的時候由于并不很重視因此也未意識到這一點

69、，導(dǎo)致做的過程中停停找找、找找停停，嚴重影響了設(shè)計進度和效率，并且這種臨陣磨槍式的做法也使得準備很不充分，往往是急需要用的東西找也找不到，如某控件類的方法如何使用、其原型或者參數(shù)的類型與意義為何等等。這樣一來，自然會遇到重重困難。我想，如果在動手之前已經(jīng)做好了充足準備，必然會少遇到很多麻煩，也不會一度出現(xiàn)舉步維艱的情況。當(dāng)然了，這次還只是一個小小的設(shè)計，如果換成是某個大型系統(tǒng)的設(shè)計豈不是無法想象？所以這次經(jīng)歷也算是給了我一個教訓(xùn)：千萬不

70、要打無準備的仗！早準備方保無虞。　　說到了準備，也得說說做事過程中的堅持與細心謹慎。很難想象如果沒有堅持到底的勇氣和不懈的努力，當(dāng)一個人面對困難時能迎難而上并一路堅持走下來。當(dāng)初我選定這個設(shè)計課題時正是考慮到它簡單、易完成（當(dāng)然事實并非如此），不過后來做的時候不斷出現(xiàn)新的問題，而且有些還是從理論上無法解釋的，這時我就在想算了吧，這么難搞，還是換別的做。正好其他同學(xué)做的在網(wǎng)上找到了很多原本的版本，

71、因而做起來就不費吹灰之力。當(dāng)時幾乎就在一念之間轉(zhuǎn)了方向，好在隨后終于做成功了一部分功能。這點小小的成功讓我體會到了自己動手的樂趣與成功后的喜悅，在此激勵之下，幸而堅持了下來?；匚镀渲械钠D辛，盡享成功的喜悅，縱是雛鷹試翼之作，畢竟自己所為，比之其他同學(xué)照搬別人的代碼以完成任務(wù)卻不知到底做了什么、又有什么收獲，不是更有意義嗎？能夠堅持即已成功一半。世上無難事，唯恐少堅持！　　此外，在做的過程中不可能

72、是一帆風(fēng)順的，必然免不了頻繁出錯。這一方面是由于輸入時的粗心大意造成的，另一方面則是編寫的代碼本身的問題。對于前者，如果能在操作時做到細心謹慎，當(dāng)然可以避免。即便免不了輸入錯誤，在調(diào)試的過程中也應(yīng)細心謹慎，惟其如此，方可免去許多麻煩，保證軟件設(shè)計的質(zhì)量與效率。由于要不斷的調(diào)試，而VC6.0對于用戶所作的改動會自動保存，因此就可能出現(xiàn)保存了修改后錯誤的結(jié)果，反而將前面做好的調(diào)試無誤的內(nèi)容覆蓋掉的情況。如果沒有時時保持細心謹慎的態(tài)度，及時對

73、調(diào)試無誤的結(jié)果加以保存，將可能遭遇前　　功盡棄的“滅頂之災(zāi)”。不管怎樣，時時處處細心謹慎，方保順利無虞。我想，無論是治學(xué)還是工作或是為人，這　　樣的一種態(tài)度都是至關(guān)重要的。　　由于是初次設(shè)計，僅憑自己一人之力是很難完成的，所以大家或借助于網(wǎng)絡(luò)，或借助于參考書籍、期刊資料等。我也不例外，和幾位同學(xué)一起研究設(shè)計方案及

74、具體實現(xiàn)方法，并跑了好幾趟圖書館，查資料，抄筆記，上網(wǎng)搜索資料，終于在大家的通力合作之下完成了這個項目。一起做的過程大家朝著一個共同的目標(biāo)努力，分工協(xié)作，互相交流，提出不同的想法，不斷完善，不斷進步，一個一個的問題迎刃而解，一個一個的功能不斷做出來。最后，集體的勞動終于換來了豐碩的成果（盡管并不完美）。這次經(jīng)歷使我懂得了團隊合作精神的可貴。不僅如此，我覺得這次合作的過程真的是很愉快，很讓人回味和懷念！我想將來參加工作后這種合作還會有，參

75、與合作，倡導(dǎo)這種合作精神是很可貴和重要的。社會的進步使得人們面臨的問題越來越復(fù)雜，迫使人們尋求集體的智慧、團隊的力量來解決它們。個人的力量終究是有限的，也不可能獨立完成所有的事情，每個人都有義務(wù)和必要學(xué)會與別人溝通、交流，學(xué)會合作，參與合作，在合作的過程中培養(yǎng)這樣一種意識。對于將來的工作，這也是有重要意義的。　　最后，值得一提的是編輯這份電子文稿，也使我學(xué)會了使用更多的Word功能。雖然不是本次

76、設(shè)計的正題，但畢竟也算是一種收獲吧。能夠多學(xué)一點知識，總算也是一種成就。　　課程設(shè)計即將結(jié)束，一個個挑燈夜戰(zhàn)、激烈討論的夜晚也已過去?；仡櫿麄€過程，更清楚的認識到知識的欠缺，而自己所學(xué)的VC++知識只能算是皮毛，還有更多的東西需要我去研究，去掌握。盡管如此，我也不會退縮、停滯不前，因為通過這次設(shè)計實踐，我已初識VC++的廬山真面目。這才是最重要的。相信經(jīng)過此次課程設(shè)計，日后將會有所改進。此外，我

77、還要感謝所有幫助過我的老師、同學(xué)，感謝你們在這幾天里給我的幫助與鼓勵。正是因為你們的幫助與鼓勵，我才能很好的完成這一次的課程設(shè)計，才能學(xué)到這么多的知識；也正是因為你們的幫助與鼓勵，我真正認識到了團隊力量的偉大，“團結(jié)就是力量?！备兄x你們，謝謝。　　參考文獻　　[1] 劉振安,劉燕君.C程序設(shè)計課程設(shè)計[M].[北京]

78、機械工業(yè)出版社,2004年9月　　[2] 譚浩強.C程序設(shè)計（第三版）.清華大學(xué)出版社,2005年7月　　[3] 嚴蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)出版社,1997年4月　　[4] 李志球《實用C語言程序設(shè)計教程》北京：電子工業(yè)出版社，1999　　[5] 王

79、立柱：C/C++與數(shù)據(jù)結(jié)構(gòu) 北京：清華大學(xué)出版社，2002　　[6] 吳文虎《程序設(shè)計基礎(chǔ)》北京：清華大學(xué)出版社，2003　　[7] 郭福順，王曉芬，李蓮治《數(shù)據(jù)結(jié)構(gòu)》（修訂本），大連理工大學(xué)出版社，1997　　[8] 潘道才，陳一華《數(shù)據(jù)結(jié)構(gòu)》，電子科技大學(xué)出版社，1994&l

80、t;p>　　附錄：　　源代碼　　本程序包含3個頭文件和4個C源程序文件，分別是：Graph.h Graph.c Deque.h Deque.c 　　error.h error.c main.c </p&g

81、t;　　1.Graph.h　　#ifndef _GRAPH_H_　　#define _GRAPH_H_　　#define ISLAND_DIAMETER 15 /* 小島的直徑 */　　#define L

82、AKE_BOUNDARY_X50/* 小島到湖邊的距離，在x軸上 */　　#define LAKE_BOUNDARY_Y50/* 小島到湖邊的距離，在y軸上 */　　#define INFINITY10000 /* 可以跳的步數(shù)的最大值 */　　typedef unsigned int Ver

83、tex;　　typedef double Distance;　　typedef struct GraphNodeRecord{　　int X; /* x軸坐標(biāo) */　　int Y; /* y軸坐標(biāo) */<

84、;p>　　unsigned int Step; /*跳至該點的步數(shù) */　　Vertex Path; /*記錄上一個點 */　　} GraphNode;　　typedef GraphNode *Graph;　　Graph

85、 GraphNew(int NodeNum);　　void GraphDelete(Graph G);　　/* 判斷007是否能從起始處跳至該點(x, y) */　　int CheckForStart(int x, int y, Distance d);　　/* 判斷00

86、7是否能從該點跳至河岸 */　　int CheckForEnd(int x, int y, Distance d);　　/* 判斷007是否能從點i跳至點j */ 　　int CheckForConnect(Graph g, Vertex i, Vertex j, Distance d);

87、　　#endif　　2.Graph.c　　#include "Graph.h"　　#include "error.h"　　#include

88、 <stdlib.h>　　/******創(chuàng)建新的Graph******/　　Graph GraphNew(int NodeNum)　　{　　Graph G;&l

89、t;p>　　int i;　　if(NodeNum <= 0)return NULL;　　G = malloc(NodeNum * sizeof(GraphNode)); /* 分配空間 */　　CHECK(G);</

90、p>　　for(i = 0; i < NodeNum; i++) /* 初始化 */　　{　　G[i].X = 0;　　G[i].Y = 0;　　G[i].Step =

91、 INFINITY; 　　G[i].Path = 0;　　}　　return G;　　}　　/******刪除一個G

92、raph)******/　　void GraphDelete(Graph G)　　{　　if(G)free(G);　　}　　/*******判斷007是否

93、能從起始處跳至該點(x, y)，步長是d******/　　int CheckForStart(int x, int y, Distance d)　　{　　double t;　　t = (ISLAN

94、D_DIAMETER + (d * 2.0));　　return (x*x + y*y) <= t*t/4.0; 　　/* x^2 + y^2 <= (ISLAND_DIAMETER/2.0 + d)^2 */　　}

95、　　/*******判斷007是否能從該點跳至河岸，步長是d******/　　int CheckForEnd(int x, int y, Distance d)　　{　　if(x < 0)x = -x; /* 取x的絕對值 */</

96、p>　　if(y < 0)y = -y; /* 取y的絕對值 */　　return (d >= LAKE_BOUNDARY_X - x)/* 由于湖是個正方形，只需檢查這兩個距離*/　　|| (d >= LAKE_BOUNDARY_Y - y);<

97、;p>　　}　　/*******判斷007是否能從點i跳至點j，步長是d******/　　int CheckForConnect(Graph g, Vertex i, Vertex j, Distance d)　　{</p&g

98、t;　　int x, y;　　x = g[i].X - g[j].X;　　y = g[i].Y - g[j].Y;　　return x*x + y*y <= d*d;　　}</b&g

99、t;　　3.Deque.h　　#ifndef _DEQUE_H_　　#define _DEQUE_H_　　typedef unsigned int ElemType; /* 在本程序中ElemType指定為int */

100、　　/* 鏈表形式 */　　typedef struct NodeRecord{　　ElemType Element;　　struct NodeRecord *Next; /* 指向下一個node */

101、;　　} *Node; 　　typedef struct DequeRecord{ 　　Node Front, Rear; /* 分別指向Deque的前后兩個點 */　　} *Deque;　　D

102、eque DequeNew();　　void DequeDelete(Deque D); 　　void DequeClear(Deque D); 　　int IsEmpty(Deque D); 　　void Push(ElemType X, Dequ

103、e D); 　　ElemType Pop(Deque D); 　　void Inject(ElemType X, Deque D); 　　#endif　　Deque.c

104、　　#include "Deque.h"　　#include "error.h"　　#include <stdlib.h>　　/******創(chuàng)建新的Deque******/　　Deque Deque

105、New()　　{　　Deque D;　　D = malloc(sizeof(struct DequeRecord));　　CHECK(D);

106、;　　D->Front = D->Rear = malloc(sizeof(struct NodeRecord)); /* 空的頭 */　　CHECK(D->Front);　　D->Front->Element = 0; /* 初始化 */

107、　　D->Rear->Next = NULL;　　return D;　　}　　/******刪除Deque******/　　void Deq

108、ueDelete(Deque D)　　{　　if(D)　　{　　while(D->Front) <b&g

109、t;　　{　　D->Rear = D->Front->Next;　　free(D->Front);　　D->Front = D->Rear;　　}<

110、p>　　free(D);　　}　　}　　/******DequeClear刪除所有的節(jié)點除了頭節(jié)點******/　　void DequeClear(De

111、que D)　　{　　if(D)　　{　　while(D->Front->Next) /* 刪除第一個節(jié)點 */

112、　　{　　D->Rear = D->Front->Next->Next;　　free(D->Front->Next);　　D->Front->Next = D->Rear;<

113、p>　　}　　D->Rear = D->Front;　　}　　}　　/******判斷Deque是否為空******/

114、　　int IsEmpty(Deque D)　　{　　return D->Front == D->Rear;　　}　　/******將X元素壓占到D中******/

115、　　void Push(ElemType X, Deque D) 　　{ 　　Node NewNode; 　　NewNode = malloc(sizeof(struct NodeRecord)); /* 建立新的節(jié)點 */

116、 　　CHECK(NewNode);　　NewNode->Element = X; 　　NewNode->Next = D->Front->Next; 　　if(D->Front == D->Rear)

117、 /* 如果D為空 */　　D->Rear = NewNode;　　D->Front->Next = NewNode;/* 壓棧 */ 　　}　　/******將第一個元素出棧******/</p&

118、gt;　　ElemType Pop(Deque D) 　　{ 　　Node Temp; 　　ElemType Item; 　　if(D->Front == D->Rear)&l

119、t;p>　　{　　Error("Deque is empty");　　return 0; 　　}　　else </p

120、>　　{ 　　Temp = D->Front->Next;/* 得到第一個元素 */ 　　D->Front->Next = Temp->Next; /* 重置第一個元素 */　　if(Temp == D-&g

121、t;Rear)/* 如果只有一個元素 */　　D->Rear = D->Front;/* 將D置空 */ 　　Item = Temp->Element; 　　free(Temp);　　return Item; </p&g

122、t;　　} 　　}　　/******插入元素X至D末尾******/ 　　void Inject(ElemType X, Deque D) 　　{ &l

123、t;/b>　　Node NewNode;　　NewNode = malloc(sizeof(struct NodeRecord)); /* 創(chuàng)建新節(jié)點 */ 　　CHECK(NewNode);　　NewNode->Element = X;

124、;　　NewNode->Next = NULL;　　D->Rear->Next = NewNode;　　D->Rear = NewNode; 　　}　　5.error.h &l

125、t;/p>　　# ifndef ___DS_PROJ_2_ERROR_H___　　# define ___DS_PROJ_2_ERROR_H___　　#define CHECK(X) if(NULL == (X))Error("Out of space!!!")

126、void Error(const char *msg);　　void Warning(const char *msg);　　#endif　　error.c 　　#include "er

127、ror.h"　　#include <stdio.h>　　#include <stdlib.h>　　/******打印錯誤信息，并退出程序******/ 　　void Error(const char *msg)&l

128、t;p>　　{　　if(NULL != msg)　　fprintf(stderr,"%s\n",msg);　　exit(-1);　　}

129、;　　/******打印警告信息，但并不退出程序******/　　void Warning(const char *msg)　　{　　if(NULL != msg)　　fprintf(stde

130、rr,"%s\n",msg);　　}　　main.c　　#include "Graph.h"　　#include "Deque.h"&l

131、t;/p>　　#include "error.h"　　#include <stdlib.h>　　#include <stdio.h>　　/******讀入一個case返回一個Graph，*Bank 記錄最短到達河岸的路徑******/<

132、/p>　　Graph read_case(FILE *InFile, int num, Vertex* Bank, Deque D)　　{　　Graph G = NULL;　　Distance JamesJump;<p

133、>　　Vertex V;　　int x, y;　　int i, Times;　　*Bank = 0;　　fscanf(InFile, "%lf", &JamesJ

134、ump);　　if(CheckForEnd(0, 0, JamesJump + ISLAND_DIAMETER/2.0))　　{　　for(i = 0; i < (num << 1); i++) /*一步便跳出的情況 */<

135、p>　　fscanf(InFile, "%d", &x);　　*Bank = 1;　　}　　else if(num > 0) /* 007必須經(jīng)過鱷魚頭上的情況 */<p

136、>　　{　　num += 2;　　G = GraphNew(num);　　for(i = 2; i < num; i++) /* 第三個node開始是鱷魚 */&l

137、t;b>　　{　　fscanf(InFile, "%d", &x);　　fscanf(InFile, "%d", &y);　　G[i].X = x;　　G[i].Y = y;</p&g

138、t;　　if(CheckForStart(x, y, JamesJump)) /*判斷是否能跳上該點*/　　{　　G[i].Path = 1; /*007可以跳到 */　　G[i].Step = 1;

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

課程設(shè)計--最短路徑拯救007

文檔簡介

溫馨提示

最新文檔

評論

課程設(shè)計--最短路徑拯救007

文檔簡介

溫馨提示

最新文檔

評論

免費下載