鹽城工學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)拯救007

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

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

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

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

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

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

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

8、 can jumo to the bank directly) *Bank=1; /*直接跳出的情況*/ else if (num0) /*007必須經(jīng)過(guò)鱷魚頭上的情況*/ num+=2; G=GraphNew”(num); for(i=2;inum;i+) /*第3個(gè)node開始是鱷魚*/ if(Bond can jump to Gi from island) /*判斷是否能從島上跳上該點(diǎn)*/ Gi.Path=1; Gi.Step=1; /*一步*/ if(Bond can jump to bankfrom Gi) /*判斷該點(diǎn)是否能跳出*/ *Bank =i; /*007可以跳出，記錄該點(diǎn)

9、*/ Skip other crocodile break; else Inject(i,D);/*插入該點(diǎn)，并開始下一個(gè)檢測(cè)*/while(!IsEmpty(D) /*只經(jīng)過(guò)一只鱷魚無(wú)法跳出，必須還要跳到其他鱷魚的情況*/ V=Pop(D);for(i=2;istep of v+1) Gi.Path=V; Gi.Step= GV.Step+1;/*把i點(diǎn)練到v點(diǎn)后面*/ 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無(wú)法逃脫出去；（2）1，意味著007可以直接從島上跳出去，而不用經(jīng)過(guò)鱷魚的腦袋；（3）k，返回的第k點(diǎn)是007經(jīng)過(guò)最短路徑逃出鱷魚潭是經(jīng)過(guò)的最后一個(gè)頂點(diǎn)?？梢愿鶕?jù)Gk的path參數(shù)來(lái)追蹤該點(diǎn)的上一點(diǎn)，由此類推可以得到007逃脫的最短路徑。三、測(cè)試結(jié)果 對(duì)于本程序，需要應(yīng)用各種類型的測(cè)試用例來(lái)進(jìn)行測(cè)試。一般來(lái)說(shuō)，可以設(shè)計(jì)一下幾種類型的測(cè)試用例。 007步長(zhǎng)很大，以至于可以直接跳出，例如：0 43- 1007不可能逃出去的情況（根本就沒(méi)有鱷魚），例如：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 輸出結(jié)果： 7 9 916 1623 2328 2835 3541 41input.txt文件中，名稱不正確、空文件、缺少部分輸入等不規(guī)范情況，例如： 5 10 10 10-25 3030 30注：缺少鱷魚點(diǎn)（應(yīng)有5個(gè)鱷魚點(diǎn)）和文件結(jié)尾符（-1

12、）。運(yùn)行結(jié)果：輸入數(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輸出結(jié)果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被關(guān)的小島在湖的中心；(2)小島是圓形，圓心在（0，0），而且直徑是15；(3)沒(méi)有兩只鱷魚在同一個(gè)位置；(4)鱷魚的坐標(biāo)值都是整數(shù)。2.一些判斷007是否能跳出的細(xì)節(jié)(1)判斷007是否能夠直接從島上跳到湖岸：由已知條件可得，湖是一個(gè)正方形，邊長(zhǎng)為100，中心是在（0，0），四個(gè)頂點(diǎn)分別是（50，50）,(50,-50),(-50,-50),(-50,50)。而湖中小島的直徑是15.所以如果007可以跳大于等于（50-1

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

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

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

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

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

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

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

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

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

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

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

25、碼本程序包含3個(gè)頭文件和4個(gè)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軸坐標(biāo) */int Y; /* y軸坐標(biāo) */unsigned int Step; /*跳至該點(diǎn)的步數(shù) */Vertex Path; /*記錄上一個(gè)點(diǎn) */ GraphNode;typedef GraphNode *Graph;Graph GraphNew(int NodeNum);void GraphDelete(Graph G);/* 判斷007是否能從起始處跳至該點(diǎn)(x, y) */int CheckForStart(int x, int y, D

27、istance d);/* 判斷007是否能從該點(diǎn)跳至河岸 */int CheckForEnd(int x, int y, Distance d);/* 判斷007是否能從點(diǎn)i跳至點(diǎn)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;/*刪除一個(gè)Graph)*/void GraphDelete(Graph G)if(G)free(G);/*判斷007是否能從起始處跳至該點(diǎn)(x, y)，步長(zhǎng)是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是否能從該點(diǎn)跳至河岸，步長(zhǎng)是d*/int CheckForEnd(int x, int y, Distance d)if(x 0)x = -x; /* 取x的絕對(duì)值 */if(y = LAKE_BOUNDARY_X - x)/* 由于湖是個(gè)正方形，只需檢查這兩個(gè)距離*/| (d = LAKE_BOUNDARY_Y - y);/*判斷007是否能從點(diǎn)i跳至點(diǎn)j，步長(zhǎng)是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; /* 指向下一個(gè)node */ *Node; typedef struct

31、DequeRecord Node Front, Rear; /* 分別指向Deque的前后兩個(gè)點(diǎn) */ *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é)點(diǎn)除了頭節(jié)點(diǎn)*/void DequeClear(Deque D)if(D)while(D-Front-Next) /* 刪除第一個(gè)節(jié)點(diǎn) */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é)點(diǎn) */ CHECK(NewNode);NewNode-Element = X; NewNode-Next = D-Front-Next; if(D-Front = D-Rear) /* 如果D為空 */D-Rear = NewNode;D-Front-Next = NewNode;/* 壓棧 */ /*將第一個(gè)元素出棧*/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;/* 得到第一個(gè)元素 */ D-Front-Next = Temp-Next; /* 重置第一個(gè)元素 */if(Temp = D-Rear)/* 如果只有一個(gè)元素 */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é)點(diǎn) */ 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 /*打印錯(cuò)誤信息，并退出程序*/ 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 /*讀入一個(gè)case返回一個(gè)Graph，*Bank 記錄最短到達(dá)河岸的路徑*/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、過(guò)鱷魚頭上的情況 */num += 2;G = GraphNew(num);for(i = 2; i num; i+) /* 第三個(gè)node開始是鱷魚 */fscanf(InFile, %d, &x);fscanf(InFile, %d, &y);Gi.X = x;Gi.Y = y;if(CheckForStart(x, y, JamesJump) /*判斷是否能跳上該點(diǎn)*/Gi.Path = 1; /*007可以跳到 */Gi.Step = 1; /* 一步 */if(CheckForEnd(x, y, JamesJump) /* 判斷該點(diǎn)是否能跳出 */*Bank = i; /* 007可以跳出 */Times = (num - i - 1) 1;for(i = 0; i Times; i+)