數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(迷宮問(wèn)題

1、課 程 設(shè) 計(jì) 報(bào) 告課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 課題名稱 迷宮問(wèn)題 專 業(yè) 班 級(jí) 學(xué) 號(hào) 姓 名 指導(dǎo)教師 2012年 6月 9日課程設(shè)計(jì)任務(wù)書(shū)課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 課 題 迷宮問(wèn)題 專業(yè)班級(jí) 學(xué)生姓名 學(xué) 號(hào) 指導(dǎo)老師 審 批 任務(wù)書(shū)下達(dá)日期： 2012年 6月 9日任務(wù)完成日期： 2012年 6月 16日一、設(shè)計(jì)內(nèi)容與設(shè)計(jì)要求1設(shè)計(jì)內(nèi)容：1）問(wèn)題描述以一個(gè)M*N的長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和墻壁。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出米有通路的結(jié)論。2）基本要求a.實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類型，然后編寫(xiě)一個(gè)求解迷宮的非遞歸程序。求得

2、的通路以三元組（i，j，d）的形式輸出，其中：（i，j）指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一個(gè)坐標(biāo)的方向。b.編寫(xiě)遞歸形式的算法，求得迷宮中所有可能的通路。3）測(cè)試數(shù)據(jù)迷宮的測(cè)試數(shù)據(jù)如下：左上角（1,1）為入口，右下角（8,9）為出口。0010001000100010000011010111001000010000010001010111100111000101110000004）實(shí)現(xiàn)提示計(jì)算機(jī)解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某一個(gè)方向進(jìn)行探索，若能走通，則繼續(xù)往前進(jìn)；否則，沿著原路退回，換一個(gè)方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出

3、口，則設(shè)定的迷宮沒(méi)有通路。可以二維數(shù)組存儲(chǔ)迷宮數(shù)據(jù)，通常設(shè)定入口點(diǎn)的下標(biāo)為（1，1），出口點(diǎn)的下標(biāo)為（m，n）。為處理方便起見(jiàn)，可在迷宮的四周加一圈障礙。對(duì)于迷宮中任一位置，均可約定有東、南、西、北四個(gè)方向可通。2設(shè)計(jì)要求：l 課程設(shè)計(jì)報(bào)告規(guī)范1)需求分析a.程序的功能。b.輸入輸出的要求。2)概要設(shè)計(jì)a. 程序由哪些模塊組成以及模塊之間的層次結(jié)構(gòu)、各模塊的調(diào)用關(guān)系；每個(gè)模塊的功能。b. 課題涉及的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫(kù)結(jié)構(gòu)；即要存儲(chǔ)什么數(shù)據(jù)，這些數(shù)據(jù)是什么樣的結(jié)構(gòu)，它們之間有什么關(guān)系等。3)詳細(xì)設(shè)計(jì)a.采用C語(yǔ)言定義相關(guān)的數(shù)據(jù)類型。b.寫(xiě)出各模塊的類C碼算法。c.畫(huà)出各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的

4、流程圖。4)調(diào)試分析以及設(shè)計(jì)體會(huì)a.測(cè)試數(shù)據(jù)：準(zhǔn)備典型的測(cè)試數(shù)據(jù)和測(cè)試方案，包括正確的輸入及輸出結(jié)果和含有錯(cuò)誤的輸入及輸出結(jié)果。b.程序調(diào)試中遇到的問(wèn)題以及解決問(wèn)題的方法。c.課程設(shè)計(jì)過(guò)程經(jīng)驗(yàn)教訓(xùn)、心得體會(huì)。5)使用說(shuō)明用戶使用手冊(cè)：說(shuō)明如何使用你編寫(xiě)的程序，詳細(xì)列出每一步的操作步驟。6)書(shū)寫(xiě)格式見(jiàn)附帶說(shuō)明。7)附錄a.參考書(shū)目b.源程序清單（帶注釋）l 考核方式指導(dǎo)老師負(fù)責(zé)驗(yàn)收程序的運(yùn)行結(jié)果，并結(jié)合學(xué)生的工作態(tài)度、實(shí)際動(dòng)手能力、創(chuàng)新精神和設(shè)計(jì)報(bào)告等進(jìn)行綜合考評(píng)，并按優(yōu)秀、良好、中等、及格和不及格五個(gè)等級(jí)給出每位同學(xué)的課程設(shè)計(jì)成績(jī)。具體考核標(biāo)準(zhǔn)包含以下幾個(gè)部分： 平時(shí)出勤 （占10%） 系統(tǒng)需

5、求分析、功能設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)及程序總體結(jié)構(gòu)合理與否（占10%） 程序能否完整、準(zhǔn)確地運(yùn)行，個(gè)人能否獨(dú)立、熟練地調(diào)試程序（占40%） 設(shè)計(jì)報(bào)告（占30%）注意：不得抄襲他人的報(bào)告（或給他人抄襲），一旦發(fā)現(xiàn)，成績(jī)?yōu)榱惴帧?獨(dú)立完成情況（占10%）。l 課程驗(yàn)收要求 運(yùn)行所設(shè)計(jì)的系統(tǒng)。 回答有關(guān)問(wèn)題。 提交課程設(shè)計(jì)報(bào)告紙質(zhì)稿。 提交源程序、設(shè)計(jì)報(bào)告文檔電子稿。 依內(nèi)容的創(chuàng)新程度，完善程序情況及對(duì)程序講解情況打分。二、進(jìn)度安排附：課程設(shè)計(jì)報(bào)告裝訂順序：封面、任務(wù)書(shū)、目錄、正文、評(píng)分、附件（A4大小的圖紙及程序清單）。 正文的格式:一級(jí)標(biāo)題用3號(hào)黑體,二級(jí)標(biāo)題用四號(hào)宋體加粗,正文用小四號(hào)宋體;行距為2

6、2。正文的內(nèi)容:一、課題的主要功能；二、課題的功能模塊的劃分（要求畫(huà)出模塊圖）；三、主要功能的實(shí)現(xiàn)（至少要有一個(gè)主要模塊的流程圖）；四、程序調(diào)試；五、總結(jié)；六、附件（所有程序的原代碼，要求對(duì)程序?qū)懗霰匾淖⑨專?。正文總字?jǐn)?shù)要求在5000字以上（不含程序原代碼）。 目錄一、 任務(wù)書(shū)2二、 基本算法7三、 需求分析7a. 程序的功能7b. 輸入輸出的要求7c. 程序算法分析8四、 概要設(shè)計(jì)8i. 設(shè)計(jì)中非遞歸程序的模塊結(jié)構(gòu)圖8ii. 程序的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫(kù)結(jié)構(gòu)分析9iii. 試探方向的設(shè)計(jì)10iv. 達(dá)某點(diǎn)，以避免發(fā)生死循環(huán)11五、 詳細(xì)設(shè)計(jì)11a. 偽碼設(shè)計(jì)11b. mgpath（）流程圖12六

7、、 調(diào)試分析13七、 總結(jié)14八、 評(píng)分表16九、 附錄（源代碼清單）17一、基本算法走迷宮的過(guò)程可以模擬為一個(gè)搜索的過(guò)程：每到一處，總讓它按東、東南、南、西南、西、西北、北、東北8個(gè)方向順序試探下一個(gè)位置；如果某方向可以通過(guò)，并且不曾到達(dá)，則前進(jìn)一步，在新位置上繼續(xù)進(jìn)行搜索；如果8個(gè)方向都走不通或曾經(jīng)到達(dá)過(guò)，則退回一步，在原來(lái)的位置上繼續(xù)試探下一位置。每前進(jìn)或后退一步，都要進(jìn)行判斷：若前進(jìn)到了出口處，則說(shuō)明找到了一條通路；若退回到了入口處，則說(shuō)明不存在通路。用一個(gè)字符類型的二維數(shù)組表示迷宮，數(shù)組中每個(gè)元素取值“0”（表示通路）或“1”（表示墻壁）。迷宮的入口點(diǎn)在位置（1，1）處，出口點(diǎn)在位置

8、（m,m）處。設(shè)計(jì)一個(gè)模擬走迷宮的算法，為其尋找一條從入口點(diǎn)到出口點(diǎn)的通路。二維數(shù)組的第0行、第m+1行、第0列、第m+1列元素全置成“1”， 表示迷宮的邊界；第1行第1列元素和第m行第m列元素置成“0”， 表示迷宮的入口和出口；其余元素值用隨機(jī)函數(shù)產(chǎn)生。假設(shè)當(dāng)前所在位置是（x,y）。沿某個(gè)方向前進(jìn)一步，它可能到達(dá)的位置最多有8個(gè)。如果用二維數(shù)組move記錄8個(gè)方向上行下標(biāo)增量和列下標(biāo)增量，則沿第i個(gè)方向前進(jìn)一步，可能到達(dá)的新位置坐標(biāo)可利用move數(shù)組確定： x=x+movei0 y=y+movei1從迷宮的入口位置開(kāi)始，沿圖示方向順序依次進(jìn)行搜索。在搜索過(guò)程中，每前進(jìn)一步，在所到位置處做標(biāo)記

9、“h”（表示這個(gè)位置在通路上），并將該位置的坐標(biāo)壓入棧中。每次后退的時(shí)候，先將當(dāng)前所在位置處的通路標(biāo)記“h”改成死路標(biāo)記“”（表示這個(gè)位置曾到達(dá)過(guò)但走不通，以后不要重復(fù)進(jìn)入），然后將該位置的坐標(biāo)從棧頂彈出。搜索到出口位置時(shí)，數(shù)組中那些值為“h”的元素形成一條通路。二、需求分析a.程序的功能。(i) 實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類型，以非遞歸算法求取所有通路和最短路徑(ii)以一個(gè)遞歸算法，對(duì)任意輸入的迷宮矩陣（1代表不通，0代表通路）求出所有通路 b.輸入輸出的要求。(i) 求得的通路以三元組（i，j，d）的形式輸出，其中：（i，j）指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一個(gè)坐標(biāo)的方向。（ii）輸

10、出迷宮示意圖c、程序算法分析1.迷宮的建立：迷宮中存在通路和障礙，為了方便迷宮的創(chuàng)建，可用0表示通路，用1表示障礙，這樣迷宮就可以用0、1矩陣來(lái)描述，2.迷宮的存儲(chǔ)：迷宮是一個(gè)矩形區(qū)域，可以使用二維數(shù)組表示迷宮，這樣迷宮的每一個(gè)位置都可以用其行列號(hào)來(lái)唯一指定，但是二維數(shù)組不能動(dòng)態(tài)定義其大小，我們可以考慮先定義一個(gè)較大的二維數(shù)組mazeM+2N+2,然后用它的前m行n列來(lái)存放元素，即可得到一個(gè)mn的二維數(shù)組，這樣(0,0)表示迷宮入口位置，(m-1,n-1)表示迷宮出口位置。注：其中M，N分別表示迷宮最大行、列數(shù)，本程序M、N的缺省值為39、39，當(dāng)然，用戶也可根據(jù)需要，調(diào)整其大小。3.迷宮路徑

11、的搜索：首先從迷宮的入口開(kāi)始，如果該位置就是迷宮出口，則已經(jīng)找到了一條路徑，搜索工作結(jié)束。否則搜索其上、下、左、右位置是否是障礙，若不是障礙，就移動(dòng)到該位置，然后再?gòu)脑撐恢瞄_(kāi)始搜索通往出口的路徑；若是障礙就選擇另一個(gè)相鄰的位置，并從它開(kāi)始搜索路徑。為防止搜索重復(fù)出現(xiàn)，則將已搜索過(guò)的位置標(biāo)記為2，同時(shí)保留搜索痕跡，在考慮進(jìn)入下一個(gè)位置搜索之前，將當(dāng)前位置保存在一個(gè)棧中，如果所有相鄰的非障礙位置均被搜索過(guò)，且未找到通往出口的路徑，則表明不存在從入口到出口的路徑。這實(shí)現(xiàn)的是廣度優(yōu)先遍歷的算法，如果找到路徑，則為最短路徑。三、概要設(shè)計(jì)i）設(shè)計(jì)中非遞歸程序的模塊結(jié)構(gòu)圖圖中方框表示函數(shù)，方框中指出函數(shù)名，

12、箭頭方向表示函數(shù)間的調(diào)用關(guān)系，虛線方框表示文件的組成main（）mapath（）mgpath（）：求解迷宮問(wèn)題，即輸出從（1，1）到（M，N）的全部路徑和最短路徑（包含最短路徑長(zhǎng)度）。當(dāng)找到一條路徑時(shí)，不使用return語(yǔ)句退出，而是出棧一次，重新回溯走另一條路徑，并用minlen記錄最短路徑長(zhǎng)度，Path數(shù)組記錄最短路徑。ii）程序的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫(kù)結(jié)構(gòu)分析設(shè)迷宮為m行n列，利用mazemn來(lái)表示一個(gè)迷宮，mazeij=0或1; 其中：0表示通路，1表示不通，當(dāng)從某點(diǎn)向下試探時(shí)，中間點(diǎn)有4個(gè)方向可以試探，（見(jiàn)圖）而四個(gè)角點(diǎn)有2個(gè)方向，其它邊緣點(diǎn)有3個(gè)方向，為使問(wèn)題簡(jiǎn)單化我們用mazem+2n

13、+2來(lái)表示迷宮，而迷宮的四周的值全部為1。這樣做使問(wèn)題簡(jiǎn)單了，每個(gè)點(diǎn)的試探方向全部為4，不用再判斷當(dāng)前點(diǎn)的試探方向有幾個(gè)，同時(shí)與迷宮周圍是墻壁這一實(shí)際問(wèn)題相一致。如圖3.4表示的迷宮是一個(gè)68的迷宮。入口坐標(biāo)為（1，1），出口坐標(biāo)為（m，n）。入口(1,1) 012345678n90111111111111011101111210010111113100000001141001101111511000100016101100010171111111111m 出口 (6,8) 圖1 用mazem+2n+2表示的迷宮迷宮的定義如下：#define m 6 /* 迷宮的實(shí)際行 */#define n

14、 8 /* 迷宮的實(shí)際列 */int maze m+2n+2 ;iii試探方向的設(shè)計(jì) 示迷宮的情況下，每個(gè)點(diǎn)有4個(gè)方向去試探，如當(dāng)前點(diǎn)的坐標(biāo)(x , y)，與其相鄰的4個(gè)點(diǎn)的坐標(biāo)都可根據(jù)與該點(diǎn)的相鄰方位而得到，如圖2所示。因?yàn)槌隹谠冢╩，n），因此試探順序規(guī)定為：從當(dāng)前位置向前試探的方向?yàn)閺恼龞|沿順時(shí)針?lè)较蜻M(jìn)行。為了簡(jiǎn)化問(wèn)題，方便的求出新點(diǎn)的坐標(biāo)，將從正東開(kāi)始沿順時(shí)針進(jìn)行的這4個(gè)方向（用0，1，2，3表示東、南、西、北）的坐標(biāo)增量放在一個(gè)結(jié)構(gòu)數(shù)組move 4 中，在move 數(shù)組中，每個(gè)元素有兩個(gè)域組成，x：橫坐標(biāo)增量，y：縱坐標(biāo)增量。Move數(shù)組如圖3所示。move數(shù)組定義如下：typede

15、f struct int x ; /行int y ; /列 item ; item move4 ;這樣對(duì)move的設(shè)計(jì)會(huì)很方便地求出從某點(diǎn) (x，y) 按某一方向 v (0v3) 到達(dá)的新點(diǎn)（i，j）的坐標(biāo)：i =x + movev.x ，j = y + movev.y 。(x，y)圖2 與點(diǎn)(x，y)相鄰的4個(gè)點(diǎn)及坐標(biāo)(x，y+1)(x，y-1)(x+1，y)(x-1，y)xy00111020-13-10圖3 增量數(shù)組moveiii、棧的設(shè)計(jì)當(dāng)?shù)竭_(dá)了某點(diǎn)而無(wú)路可走時(shí)需返回前一點(diǎn)，再?gòu)那耙稽c(diǎn)開(kāi)始向下一個(gè)方向繼續(xù)試探。因此，壓入棧中的不僅是順序到達(dá)的各點(diǎn)的坐標(biāo)，而且還要有從前一點(diǎn)到達(dá)本點(diǎn)的方向，

16、即每走一步棧中記下的內(nèi)容為(行，列，來(lái)的方向)。對(duì)于圖1所示迷宮，依次入棧為：top 3,4,0 3,3,0 3,2,1 2,2,0 2,1,1 1,1,0棧中每一組數(shù)據(jù)是所到達(dá)的每點(diǎn)的坐標(biāo)及從該點(diǎn)沿哪個(gè)方向向下走的，對(duì)于圖3迷宮，走的路線為：(1,1)0(2,1)1(2,2)0(3,2)1(3,3)0(3,4)0（下腳標(biāo)表示方向），當(dāng)無(wú)路可走，則應(yīng)回溯，對(duì)應(yīng)的操作是出棧，沿下一個(gè)方向即方向繼續(xù)試探。棧中元素是一個(gè)由行、列、方向組成的三元組，棧元素的設(shè)計(jì)如下：typedef structint x , y , d ;/* 橫縱坐標(biāo)及方向*/datatype ;棧的定義為： SeqStack s

17、 ;iv、達(dá)某點(diǎn)，以避免發(fā)生死循環(huán)：一種方法是另外設(shè)置一個(gè)標(biāo)志數(shù)組markmn，它的所有元素都初始化為0，一旦到達(dá)了某一點(diǎn) ( i , j )之后，使mark i j 置1，下次再試探這個(gè)位置時(shí)就不能再走了。另一種方法是當(dāng)?shù)竭_(dá)某點(diǎn)（i , j）后使maze i j 置 -1，以便區(qū)別未到達(dá)過(guò)的點(diǎn)，同樣也能起到防止走重復(fù)點(diǎn)的目的，此處采用后一方法，算法結(jié)束前可恢復(fù)原迷宮。四、詳細(xì)設(shè)計(jì)a.偽碼設(shè)計(jì)(1) 棧初始化;(2) 將入口點(diǎn)坐標(biāo)及到達(dá)該點(diǎn)的方向（設(shè)為-1）入棧(3) while (棧不空) 棧頂元素（x , y , d）出棧 ;求出下一個(gè)要試探的方向d+ ; while （還有剩余試探方向時(shí)

18、） if （d方向可走）則 （x , y , d）入棧 ; 求新點(diǎn)坐標(biāo) (i, j ) ;將新點(diǎn)（i , j）切換為當(dāng)前點(diǎn)（x , y） ; if ( (x ,)= =(,n) ) 結(jié)束 ; else 重置 d=0 ; else d+ ; 算法如下： int path(int &maze，int m, int n, int move) /m,n為 maze的一、二維長(zhǎng)度，move為結(jié)構(gòu)體數(shù)組存放了試探的4個(gè)方向坐標(biāo) SeqStack s ; datetype temp ; int x, y, d, i, j ; temp.x=1 ; temp.y=1 ; temp.d=-1 ; Push_Se

19、qStack (s，temp) ;阿 while (! Empty_SeqStack (s ) ) Pop_SeqStack (s,temp) ;x=temp.x ; y=temp.y ; d=temp.d+1 ;while (d4) i=x+moved.x ; j=y+moved.y ;if ( mazeij= =0 ) temp=x, y, d ;Push_SeqStack ( s, temp ) ;x=i ; y=j ; mazexy= -1 ;if (x= =m&y= =n) return 1 ; /*迷宮有路*/else d=0 ; else d+ ; /*while (d4)*/

20、/*while (! Empty_SeqStack (s ) )*/ return 0 ;/*迷宮無(wú)路*/ 棧中保存的就是一條迷宮的通路。bmgpath（）流程圖開(kāi)始棧不為空比較輸出最短路徑回溯無(wú)路可走輸出路徑讓該結(jié)點(diǎn)不可走找到下一個(gè)可走結(jié)點(diǎn)是否找到出口五、調(diào)試分析a、迷宮的測(cè)試數(shù)據(jù)如下：左上角（1,1）為入口，右下角（8,9）為出口。001000100010001000001101011100100001000001000101011110011100010111000000b、 程序調(diào)試截圖i) 遞歸算法程序求所有路徑，預(yù)設(shè)測(cè)試迷宮，輸出迷宮圖黑色方塊代表墻壁ii) 運(yùn)行程序得出所有通路，

21、以圖的方式輸出，圓圈代表路徑（程序截圖如右）iii）輸入上表給出的測(cè)試矩陣，運(yùn)行源代碼清單1，以三元組輸出所有通路，及最短路徑，程序運(yùn)行截圖（如上）六、總結(jié)經(jīng)過(guò)一個(gè)星期的課程設(shè)計(jì)，過(guò)程曲折可謂一語(yǔ)難盡。整天都是對(duì)著電腦，不然就是翻閱資料。在此期間我失落過(guò)，也曾一度熱情高漲。點(diǎn)點(diǎn)滴滴令我回味無(wú)長(zhǎng)。這次課程設(shè)計(jì)使我體會(huì)到只有做到細(xì)心耐心，恒心才能做好事情。這次的課程設(shè)計(jì)，加強(qiáng)了我們動(dòng)手、思考和解決問(wèn)題的能力。鞏固和加深了對(duì)數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運(yùn)用本課程所學(xué)知識(shí)的能力。培養(yǎng)了我選用參考書(shū)，查閱手冊(cè)及文獻(xiàn)資料的能力。培養(yǎng)獨(dú)立思考，深入研究，分析問(wèn)題、解決問(wèn)題的能力。通過(guò)實(shí)際編譯系統(tǒng)的分析設(shè)計(jì)、編程

22、調(diào)試，掌握應(yīng)用軟件的分析方法和工程設(shè)計(jì)方法。通過(guò)課程設(shè)計(jì)，培養(yǎng)了我嚴(yán)肅認(rèn)真的工作作風(fēng)，逐步建立正確的生產(chǎn)觀念、經(jīng)濟(jì)觀念和全局觀念。而且做課程設(shè)計(jì)同時(shí)也是對(duì)課本知識(shí)的鞏固和加強(qiáng)，平時(shí)看課本時(shí)，有些問(wèn)題就不是很能理解，做完課程設(shè)計(jì)，那些問(wèn)題就迎刃而解了。而且還可以記住很多東西。認(rèn)識(shí)來(lái)源于實(shí)踐，實(shí)踐是認(rèn)識(shí)的動(dòng)力和最終目的，實(shí)踐是檢驗(yàn)真理的唯一標(biāo)準(zhǔn)。所以這個(gè)期末測(cè)試之后的課程設(shè)計(jì)對(duì)我們的作用是非常大的。這次的課程設(shè)計(jì)使我懂得了理論與實(shí)際相結(jié)合是很非常重要的，只有理論知識(shí)是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識(shí)與實(shí)踐相結(jié)合起來(lái)，從理論中得出結(jié)論，才能真正為社會(huì)服務(wù)，從而提高自己的實(shí)際動(dòng)手能力和獨(dú)立思考的能力。

23、在整個(gè)設(shè)計(jì)過(guò)程中，構(gòu)思是很花費(fèi)時(shí)間的。調(diào)試時(shí)經(jīng)常會(huì)遇到這樣那樣的錯(cuò)誤，有的是因?yàn)榇中脑斐傻恼Z(yǔ)法錯(cuò)誤。當(dāng)然，很多也時(shí)用錯(cuò)了方法，總是實(shí)現(xiàn)不了。同時(shí)在設(shè)計(jì)的過(guò)程中發(fā)現(xiàn)了自己的不足之處，對(duì)以前所學(xué)過(guò)的知識(shí)理解得不夠深刻，掌握得不夠牢固。根據(jù)我在課程設(shè)計(jì)中遇到得問(wèn)題，我將在以后的學(xué)習(xí)過(guò)程中注意以下幾點(diǎn)： 1、認(rèn)真上好專業(yè)實(shí)驗(yàn)課，多在實(shí)踐中鍛煉自己。2、寫(xiě)程序的過(guò)程中要考慮周到，嚴(yán)密。3、在做設(shè)計(jì)的時(shí)候要有信心，有耐心，切勿浮躁。4、認(rèn)真的學(xué)習(xí)課本知識(shí)，掌握課本中的知識(shí)點(diǎn)，并在此基礎(chǔ)上學(xué)會(huì)靈活運(yùn)用。5、在課余時(shí)間里多寫(xiě)程序，熟練掌握在調(diào)試程序的過(guò)程中所遇到的常見(jiàn)錯(cuò)誤，以便能節(jié)省調(diào)試程序的時(shí)間。每個(gè)實(shí)驗(yàn)通

24、常都要花費(fèi)很久的時(shí)間才能理清一個(gè)程序的思路，而且要不斷的調(diào)試程序才能把程序調(diào)試正確，同時(shí)還要做到界面的輸出也是需要美化的。這次課程設(shè)計(jì)終于順利完成了，在設(shè)計(jì)中遇到了很多專業(yè)知識(shí)問(wèn)題，最后在老師的辛勤指導(dǎo)下，也完成了課程設(shè)計(jì)。通過(guò)這次的課程設(shè)計(jì)，讓我更加了解到數(shù)據(jù)結(jié)構(gòu)的重要性。以及它對(duì)我們專業(yè)的發(fā)展發(fā)揮的作用。對(duì)我們而言，知識(shí)上的收獲很重要，但精神上的豐收更加可喜。讓我知道了學(xué)無(wú)止境的道理。我們每一個(gè)人永遠(yuǎn)不能滿足于現(xiàn)有的成就，人生就像在爬山，一座山峰的后面還有更高的山峰在等著你。挫折是一份財(cái)富，經(jīng)歷是一份擁有。這次課程設(shè)計(jì)必將成為我人生旅途上一個(gè)非常美好的回憶！同時(shí)在做課程設(shè)計(jì)時(shí)要能夠從多方面

25、去考慮，去研究，用多種算法去實(shí)現(xiàn)要求。此次課程設(shè)計(jì)，學(xué)到了很多課內(nèi)學(xué)不到的東西，比如獨(dú)立思考解決問(wèn)題，出現(xiàn)差錯(cuò)的隨機(jī)應(yīng)變，這些都讓我受益非淺，今后的制作應(yīng)該能夠更輕松，自己也都能夠解決并高質(zhì)量的完成項(xiàng)目。評(píng)分表理學(xué)院課程設(shè)計(jì)評(píng)分表課題名稱： 迷宮問(wèn)題 項(xiàng) 目評(píng) 價(jià)設(shè)計(jì)方案的合理性與創(chuàng)造性設(shè)計(jì)與調(diào)試結(jié)果設(shè)計(jì)說(shuō)明書(shū)的質(zhì)量答辯陳述與回答問(wèn)題情況課程設(shè)計(jì)周表現(xiàn)情況綜合成績(jī) 教師簽名： 日 期： 附錄A、參考書(shū)目1、數(shù)據(jù)結(jié)構(gòu)教程（第3版）李春葆 尹為民 編著 清華大學(xué)出版社出版2、數(shù)據(jù)結(jié)構(gòu)教程（第三版）上級(jí)實(shí)驗(yàn)指導(dǎo)李春葆 尹為民 編著 清華大學(xué)出版社出版3、數(shù)據(jù)結(jié)構(gòu)（學(xué)習(xí)指導(dǎo)、實(shí)驗(yàn)指導(dǎo)、課程設(shè)計(jì)） 陳媛

26、 編著 機(jī)械工業(yè)出版社出版B、源程序清單（帶注釋）i）非遞歸算法求迷宮源程序/* 實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類型，然后編寫(xiě) * 一個(gè)求解迷宮的非遞歸程序。求得的通路以三元組 * （i，j，d）的形式輸出，其中：（i，j）指示迷宮中 * 的一個(gè)坐標(biāo)，d表示走到下一個(gè)坐標(biāo)的方向。 */#include #include #define M 9 /行數(shù)#define N 8/列數(shù)#define MaxSize 100/棧最多元素個(gè)數(shù)int mgM+2N+2 = /迷宮測(cè)試數(shù)據(jù)矩陣,左上角（1,1）為入口，右下角（9,8）為出口1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,

27、0,1,1,0,1,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,1,1,1,0,1,1,1,0,0,1,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,1,1,1,0,1,1,1,1,0,0,1,1,1,1,1,0,0,0,1,0,1,1,1,1,1,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1;struct int i;int j;int di; StackMaxSize,PathMaxSize;/定義棧和存放最短路徑的數(shù)組int top=-1;/棧頂指針int count=1;/路徑數(shù)計(jì)數(shù)int minlen=MaxSi

28、ze;/最短路徑長(zhǎng)度void mgpath()/路徑為:(1,1)-(M,N)int i,j,di,find,k;top+;/進(jìn)棧Stacktop.i=1;Stacktop.j=1;Stacktop.di=-1;mg11=-1;/初始結(jié)點(diǎn)進(jìn)棧while (top-1)/棧不空時(shí)循環(huán)i=Stacktop.i;j=Stacktop.j;di=Stacktop.di;if (i=M & j=N)/找到了出口,輸出路徑 printf(%4d: ,count+);for (k=0;k=top;k+) /以三元組輸出路徑printf(%d,%d,%d) ,Stackk.i,Stackk.j,Stackk.

29、di);if (k+1)%5=0) printf(nt);/輸出時(shí)每5個(gè)結(jié)點(diǎn)換一行printf(n);if (top+1minlen)/比較找最短路徑for (k=0;k=top;k+)Pathk=Stackk;minlen=top+1;mgStacktop.iStacktop.j=0;/讓該位置變?yōu)槠渌窂娇勺呓Y(jié)點(diǎn)top-; i=Stacktop.i;j=Stacktop.j;di=Stacktop.di;find=0;while (di4 & find=0)/找下一個(gè)可走結(jié)點(diǎn)di+;switch(di)case 0:i=Stacktop.i-1;j=Stacktop.j;break;cas

30、e 1:i=Stacktop.i;j=Stacktop.j+1;break;case 2:i=Stacktop.i+1;j=Stacktop.j;break;case 3:i=Stacktop.i,j=Stacktop.j-1;break;if (mgij=0) find=1;if (find=1)/找到了下一個(gè)可走結(jié)點(diǎn)Stacktop.di=di;/修改原棧頂元素的di值top+;Stacktop.i=i;Stacktop.j=j;Stacktop.di=-1;/下一個(gè)可走結(jié)點(diǎn)進(jìn)棧mgij=-1;/避免重復(fù)走到該結(jié)點(diǎn)else/沒(méi)有路徑可走,則退棧mgStacktop.iStacktop.j=

31、0; /讓該位置變?yōu)槠渌窂娇勺呓Y(jié)點(diǎn)top-;printf(最短路徑如下:n);printf(長(zhǎng)度: %dn,minlen);printf(路徑: );for (k=0;kminlen;k+)switch(Pathk.di)case 0:printf(%d,%d,%s) ,Pathk.i,Pathk.j,);break;case 1:printf(%d,%d,%s) ,Pathk.i,Pathk.j,);break;case 2:printf(%d,%d,%s) ,Pathk.i,Pathk.j,);break;case 3:printf(%d,%d,%s) ,Pathk.i,Pathk.j,);break;case-1: printf(%d,%d,%s)