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

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

2、><b>　　三、測(cè)試結(jié)果7</b></p><p><b>　　參考文獻(xiàn)14</b></p><p><b>　　一、簡(jiǎn)介</b></p><p>　　最短路徑是，在一個(gè)圖中，若從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)存在著一條路徑（這里只討論無(wú)回路的簡(jiǎn)單路徑），則稱(chēng)該條路徑長(zhǎng)度為為該路徑上所有經(jīng)過(guò)的邊的數(shù)

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

4、ksra算法：如何求解從一個(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)度。</p><p>　　圖是一種較線性結(jié)構(gòu)和樹(shù)形結(jié)構(gòu)更為復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，這種復(fù)雜性主要來(lái)自數(shù)據(jù)元素之間的復(fù)雜關(guān)系。在圖結(jié)構(gòu)中

5、，任何兩個(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)系集合。</p><p><b>　　題目?jī)?nèi)容：</b></p><p>　　看過(guò)007系列的電影的人們一定很熟悉Jams Bond這個(gè)世界上最著名的 特工了。在電影“Live And

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

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

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

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

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

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

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

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

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

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

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

17、raph G=NULL;</p><p>　　Distance JamesJump;</p><p><b>　　Vertex V;</b></p><p><b>　　int x,y;</b></p><p>　　int i,Times;</p><p>　　*Bank =

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

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

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

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

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

23、gt;<p><b>　　else</b></p><p>　　Inject(i,D);/*插入該點(diǎn)，并開(kāi)始下一個(gè)檢測(cè)*/</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　while(!IsEmpty(D))

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

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

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

27、ject(i,D);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　return

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

29、<p>　　（3）k，返回的第k點(diǎn)是007經(jīng)過(guò)最短路徑逃出鱷魚(yú)潭是經(jīng)過(guò)的最后一個(gè)頂點(diǎn)?？梢愿鶕?jù)G[k]的path參數(shù)來(lái)追蹤該點(diǎn)的上一點(diǎn)，由此類(lèi)推可以得到007逃脫的最短路徑。</p><p><b>　　三、測(cè)試結(jié)果</b></p><p>　　對(duì)于本程序，需要應(yīng)用各種類(lèi)型的測(cè)試用例來(lái)進(jìn)行測(cè)試。一般來(lái)說(shuō)，可以設(shè)計(jì)一下幾種類(lèi)型的測(cè)試用例。</p>

30、<p>　　?007步長(zhǎng)很大，以至于可以直接跳出，例如：</p><p><b>　　43</b></p><p><b>　　1</b></p><p>　　?007不可能逃出去的情況（根本就沒(méi)有鱷魚(yú)），例如：</p><p><b>　　1</b></p&

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

32、;<p><b>　　37 0</b></p><p><b>　　45 0</b></p><p><b>　　10</b></p><p><b>　　20 30</b></p><p><b>　　1</b>

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

34、　10 10</b></p><p><b>　　11 11</b></p><p><b>　　12 12</b></p><p><b>　　13 13</b></p><p><b>　　14 14</b></p>

35、<p><b>　　15 15</b></p><p><b>　　16 16</b></p><p><b>　　18 18</b></p><p><b>　　20 20</b></p><p><b>　　23 23&

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

37、t;<b>　　31 31</b></p><p><b>　　33 33</b></p><p><b>　　35 35</b></p><p><b>　　38 38</b></p><p><b>　　41 41</b>

38、;</p><p><b>　　44 44</b></p><p><b>　　46 46</b></p><p><b>　　47 47</b></p><p><b>　　49 49</b></p><p><b&

39、gt;　　輸出結(jié)果：</b></p><p><b>　　7</b></p><p><b>　　9 9</b></p><p><b>　　16 16</b></p><p><b>　　23 23</b></p>&l

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

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

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

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

44、　　1 10</b></p><p><b>　　20 30</b></p><p><b>　　25 10</b></p><p><b>　　8 8</b></p><p><b>　　9 9</b></p><p>

45、;<b>　　10 10</b></p><p><b>　　11 11</b></p><p><b>　　12 12</b></p><p><b>　　13 13</b></p><p><b>　　14 14</b></

46、p><p><b>　　15 15</b></p><p><b>　　16 16</b></p><p><b>　　18 18</b></p><p><b>　　20 20</b></p><p><b>　　23 23

47、</b></p><p><b>　　25 25</b></p><p><b>　　27 27</b></p><p><b>　　28 28</b></p><p><b>　　29 29</b></p><p>&

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

49、gt;<p><b>　　44 44</b></p><p><b>　　46 46</b></p><p><b>　　47 47</b></p><p><b>　　49 49</b></p><p><b>　　10 20&l

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

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

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

53、t;<b>　　16 16</b></p><p><b>　　23 23</b></p><p><b>　　28 28</b></p><p><b>　　35 35</b></p><p><b>　　41 41</b><

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

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

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

57、gt;<b>　　10 30</b></p><p><b>　　-1</b></p><p><b>　　7</b></p><p><b>　　10 10</b></p><p><b>　　10 15</b></p>

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

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

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

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

62、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)。</p><p>　　(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

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

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

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

66、準(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é)、做人又何嘗不是如此呢？</p><p>　　先說(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)解都是

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

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

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

70、要打無(wú)準(zhǔn)備的仗！早準(zhǔn)備方保無(wú)虞。</p><p>　　說(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)上找到了很多原本的版本，

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

72、是一帆風(fēng)順的，必然免不了頻繁出錯(cuò)。這一方面是由于輸入時(shí)的粗心大意造成的，另一方面則是編寫(xiě)的代碼本身的問(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ì)于用戶(hù)所作的改動(dòng)會(huì)自動(dòng)保存，因此就可能出現(xiàn)保存了修改后錯(cuò)誤的結(jié)果，反而將前面做好的調(diào)試無(wú)誤的內(nèi)容覆蓋掉的情況。如果沒(méi)有時(shí)時(shí)保持細(xì)心謹(jǐn)慎的態(tài)度，及時(shí)對(duì)

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

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

75、與合作，倡導(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)的工作，這也是有重要意義的。</p><p>　　最后，值得一提的是編輯這份電子文稿，也使我學(xué)會(huì)了使用更多的Word功能。雖然不是本次

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

77、還要感謝所有幫助過(guò)我的老師、同學(xué)，感謝你們?cè)谶@幾天里給我的幫助與鼓勵(lì)。正是因?yàn)槟銈兊膸椭c鼓勵(lì)，我才能很好的完成這一次的課程設(shè)計(jì)，才能學(xué)到這么多的知識(shí)；也正是因?yàn)槟銈兊膸椭c鼓勵(lì)，我真正認(rèn)識(shí)到了團(tuán)隊(duì)力量的偉大，“團(tuán)結(jié)就是力量。”感謝你們，謝謝。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 劉振安,劉燕君.C程序設(shè)計(jì)課程設(shè)計(jì)[M].[北京]

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

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

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

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

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

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

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

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

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

87、<p><b>　　#endif</b></p><p><b>　　2.Graph.c</b></p><p>　　#include "Graph.h"</p><p>　　#include "error.h"</p><p>　　#include

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

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

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

91、 INFINITY; </p><p>　　G[i].Path = 0;</p><p><b>　　}</b></p><p><b>　　return G;</b></p><p><b>　　}</b></p><p>　　/******刪除一個(gè)G

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

93、能從起始處跳至該點(diǎn)(x, y)，步長(zhǎng)是d******/</p><p>　　int CheckForStart(int x, int y, Distance d)</p><p><b>　　{</b></p><p><b>　　double t;</b></p><p>　　t = (ISLAN

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

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

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

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

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

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

100、</p><p>　　/* 鏈表形式 */</p><p>　　typedef struct NodeRecord{</p><p>　　ElemType Element;</p><p>　　struct NodeRecord *Next; /* 指向下一個(gè)node */</p><p><b>

101、;　　} *Node; </b></p><p>　　typedef struct DequeRecord{ </p><p>　　Node Front, Rear; /* 分別指向Deque的前后兩個(gè)點(diǎn) */</p><p><b>　　} *Deque;</b></p><p>　　D

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

103、e D); </p><p>　　ElemType Pop(Deque D); </p><p>　　void Inject(ElemType X, Deque D); </p><p><b>　　#endif</b></p><p><b>　　Deque.c</b></p>

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

105、New()</p><p><b>　　{</b></p><p><b>　　Deque D;</b></p><p>　　D = malloc(sizeof(struct DequeRecord));</p><p><b>　　CHECK(D);</b></p>

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

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

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

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

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

111、que D)</p><p><b>　　{</b></p><p><b>　　if(D)</b></p><p><b>　　{</b></p><p>　　while(D->Front->Next) /* 刪除第一個(gè)節(jié)點(diǎn) */</p>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

136、><b>　　{</b></p><p><b>　　num += 2;</b></p><p>　　G = GraphNew(num);</p><p>　　for(i = 2; i < num; i++) /* 第三個(gè)node開(kāi)始是鱷魚(yú) */</p><p>&l

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

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