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

1、<p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)說(shuō)明書</p><p>　　班級(jí) </p><p>　　小組成員:______成績(jī): _____</p><p>　　小組成員: 成績(jī): _____</p><p>　　小組成員: _成績(jī): _____</p><p>　　設(shè)計(jì)題目

2、:_____ 迷宮問(wèn)題 _______ </p><p>　　設(shè)計(jì)時(shí)間: 2013.7.1 至 2013.7.5 </p><p>　　指導(dǎo)教師:___ _____________ </p><p>　　評(píng) 語(yǔ):________________________________ </p&g

3、t;<p>　　_________________________________________ </p><p>　　_________________________________________ </p><p>　　_________________________________________ </p><p>　　評(píng)閱教師: _

4、____________</p><p><b>　　目錄</b></p><p><b>　　設(shè)計(jì)總說(shuō)明II</b></p><p>　　第1章 課程設(shè)計(jì)內(nèi)容和要求1</p><p><b>　　1.1問(wèn)題描述1</b></p><p><

5、;b>　　1.2設(shè)計(jì)要求1</b></p><p><b>　　1.3需求分析2</b></p><p>　　第2章 課程設(shè)計(jì)總體方案及分析3</p><p>　　2.1 問(wèn)題分析3</p><p>　　2.2 系統(tǒng)總體設(shè)計(jì)4</p><p>　　2.3系統(tǒng)詳細(xì)設(shè)計(jì)

6、6</p><p>　　第3章 程序運(yùn)行結(jié)果與分析11</p><p>　　3.1 調(diào)試分析11</p><p>　　3.2 測(cè)試結(jié)果11</p><p>　　第4章 心得總結(jié)20</p><p><b>　　參考文獻(xiàn)21</b></p><p><b&

7、gt;　　附錄22</b></p><p>　　設(shè)計(jì)總說(shuō)明：本課程設(shè)計(jì)是解決迷宮求解的問(wèn)題，從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個(gè)方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，需要用一個(gè)保存從入口到當(dāng)前位置的路徑的結(jié)構(gòu)。因此，在求迷宮通路的算法中要應(yīng)用“隊(duì)列”的思想假設(shè)“當(dāng)前位置”指的是“在搜索過(guò)程中的某一時(shí)刻所在圖中某個(gè)

8、方塊位置”，則求迷宮中一條路徑的算法的基本思想是：若當(dāng)前位置“可通”，則納入“當(dāng)前路徑”，并繼續(xù)朝“下一位置”探索，即切換“下一位置”為“當(dāng)前位置”，如此重復(fù)直至到達(dá)出口；若當(dāng)前位置“不可通”，則應(yīng)順著“來(lái)向”退回到“前一通道塊”，然后朝著除“來(lái)向”之外的其他方向繼續(xù)探索；若該通道塊的四周4個(gè)方塊均“不可通”，則應(yīng)從“當(dāng)前路徑”上刪除該通道塊。所謂“下一位置”指的是當(dāng)前位置四周4個(gè)方向（上、下、左、右）上相鄰的方塊。假設(shè)以隊(duì)列記錄“當(dāng)前

9、路徑”，則隊(duì)列中存放的是“當(dāng)前路徑上最后一個(gè)通道塊”。由此，“納入路徑”的操作即為“當(dāng)前位置入隊(duì)”；“從當(dāng)前路徑上刪除前一通道塊”的操作即為“出隊(duì)”。</p><p>　　關(guān)鍵詞：迷宮；窮舉；隊(duì)列。</p><p>　　第1章 課程設(shè)計(jì)內(nèi)容和要求</p><p><b>　　1.1問(wèn)題描述</b></p><p>　　

10、迷宮問(wèn)題是取自心理學(xué)的一個(gè)古典實(shí)驗(yàn)。在該實(shí)驗(yàn)中，把一只老鼠從一個(gè)無(wú)頂大盒子的門放入，在盒子中設(shè)置了許多墻，對(duì)行進(jìn)方向形成了多處阻擋。盒子僅有一個(gè)出口，在出口處放置一塊奶酪，吸引老鼠在迷宮中尋找道路以到達(dá)出口。對(duì)同一只老鼠重復(fù)進(jìn)行上述實(shí)驗(yàn)，一直到老鼠從入口走到出口，而不走錯(cuò)一步。老鼠經(jīng)過(guò)多次試驗(yàn)最終學(xué)會(huì)走通迷宮的路線。設(shè)計(jì)一個(gè)計(jì)算機(jī)程序?qū)θ我庠O(shè)定的矩形迷宮如下圖A所示，求出一條從入口到出口的通路，或得出沒(méi)有通路的論。  

11、;</p><p><b>　　圖1.1矩形迷宮圖</b></p><p><b>　　1.2設(shè)計(jì)要求</b></p><p>　　要求設(shè)計(jì)程序輸出如下：</p><p>　　(1) 建立一個(gè)大小為m×n的任意迷宮（迷宮數(shù)據(jù)可由用戶輸入或由程序自動(dòng)生成），并在屏幕上顯示出來(lái)；</p&

12、gt;<p>　　（2）找出一條通路的二元組（i,j）數(shù)據(jù)序列，（i,j）表示通路上某一點(diǎn) 的坐標(biāo)。</p><p>　　（3）用一種標(biāo)志（如數(shù)字8）在迷宮中標(biāo)出該條通路；</p><p>　?。?）在屏幕上輸出迷宮和通路；</p><p>　?。?）上述功能可用菜單選擇。</p><p&g

13、t;<b>　　1.3需求分析</b></p><p>　　1、用戶進(jìn)入菜單頁(yè)面選擇迷宮的狀態(tài)（1表示手動(dòng)生成迷宮，2表示自動(dòng)生成迷宮，3表示迷宮游戲，4表示退出）</p><p>　　2、運(yùn)用本迷宮系統(tǒng)，用戶可以根據(jù)自己的需求輸入所需的迷宮，其中0表示通路，1表示障礙。用戶可以自己定義迷宮并設(shè)置其中的障礙，以矩陣形式輸入，也可通過(guò)定義迷宮的行列數(shù)由系統(tǒng)自動(dòng)生成迷宮。

14、</p><p>　　3、本系統(tǒng)自帶一迷宮地圖可供用戶娛樂(lè)，用戶的最高成績(jī)可以被保存，下次進(jìn)入游戲系統(tǒng)可以刷新紀(jì)錄。</p><p>　　第2章 課程設(shè)計(jì)總體方案及分析</p><p><b>　　2.1 問(wèn)題分析</b></p><p><b>　　1.迷宮的建立</b></p>

15、<p>　　要建立迷宮首先就要建立存儲(chǔ)結(jié)構(gòu)，這里我們用數(shù)組的方式建立的。根據(jù)用戶輸入的迷宮的大?。ㄎ覀?cè)O(shè)置的最大值為40可以根據(jù)要求調(diào)解），迷宮中存在通路和障礙，為了方便迷宮的創(chuàng)建，可用0表示通路，用1表示障礙，這樣迷宮就可以用0、1矩陣來(lái)描述；</p><p><b>　　2.迷宮的存儲(chǔ)</b></p><p>　　迷宮是一個(gè)矩形區(qū)域，可以使用二維數(shù)組表示

16、迷宮，這樣迷宮的每一個(gè)位置都可以用其行列號(hào)來(lái)唯一指定，但是二維數(shù)組不能動(dòng)態(tài)定義其大小，我們可以考慮先定義一個(gè)較大的二維數(shù)組maze[M+2][N+2],然后用它的前m行n列來(lái)存放元素，即可得到一個(gè)m×n的二維數(shù)組，這樣(0,0)表示迷宮入口位置，(m-1,n-1)表示迷宮出口位置。</p><p>　　注：其中M，N分別表示迷宮最大行、列數(shù)，本程序M、N的缺省值為39、39，當(dāng)然，用戶也可根據(jù)需要，調(diào)整

17、其大小。</p><p><b>　　3.迷宮路徑的搜索</b></p><p>　　首先從迷宮的入口開(kāi)始，如果該位置就是迷宮出口，則已經(jīng)找到了一條路徑，搜索工作結(jié)束。否則搜索其上、下、左、右位置是否是障礙，若不是障礙，就移動(dòng)到該位置，然后再?gòu)脑撐恢瞄_(kāi)始搜索通往出口的路徑；若是障礙就選擇另一個(gè)相鄰的位置，并從它開(kāi)始搜索路徑。為防止搜索重復(fù)出現(xiàn)，則將已搜索過(guò)的位置標(biāo)記為

18、2，同時(shí)保留搜索痕跡，在考慮進(jìn)入下一個(gè)位置搜索之前，將當(dāng)前位置保存在一個(gè)隊(duì)列中，如果所有相鄰的非障礙位置均被搜索過(guò)，且未找到通往出口的路徑，則表明不存在從入口到出口的路徑。這實(shí)現(xiàn)的是廣度優(yōu)先遍歷的算法，如果找到路徑，則為最短路徑。</p><p>　　以矩陣 0 0 1 0 1 為例，來(lái)示范一下</p><p><b>　　1 0 0 1 0</b></p&g

19、t;<p><b>　　1 0 0 0 1</b></p><p><b>　　0 0 1 0 0</b></p><p>　　首先，將位置(0,0)(序號(hào)0)放入隊(duì)列中，其前節(jié)點(diǎn)為空，從它開(kāi)始搜索，其標(biāo)記變?yōu)?，由于其只有一個(gè)非障礙位置，所以接下來(lái)移動(dòng)到(0,1)(序號(hào)1)，其前節(jié)點(diǎn)序號(hào)為0，標(biāo)記變?yōu)?，然后從(0,1)移動(dòng)到(1

20、,1)(序號(hào)2)，放入隊(duì)列中，其前節(jié)點(diǎn)序號(hào)為1，(1,1)存在(1，2)(序號(hào)3)、(2，1)(序號(hào)4)兩個(gè)可移動(dòng)位置，其前節(jié)點(diǎn)序號(hào)均為2.對(duì)于每一個(gè)非障礙位置，它的相鄰非障礙節(jié)點(diǎn)均入隊(duì)列，且它們的前節(jié)點(diǎn)序號(hào)均為該位置的序號(hào)，所以如果存在路徑，則從出口處節(jié)點(diǎn)的位置，逆序就可以找到其從出口到入口的通路，搜索路徑如表2.1所示。</p><p>　　表2.1 搜索路徑表</p><p>　　由

21、此可以看出，得到最短路徑(3,4)(3,3)(2,3)(2,2)(1,2)(1,1)(0,1)(0,0)</p><p><b>　　輸出結(jié)果</b></p><p>　　輸出的結(jié)果分為兩種，一種是直觀的用圖給出的通路，其中通路用☆表示，第二種輸出的是尋找完后的路徑，路徑用具體的坐標(biāo)來(lái)表示。</p><p>　　2.2 系統(tǒng)總體設(shè)計(jì) </

22、p><p><b>　　功能結(jié)構(gòu)圖</b></p><p><b>　　圖2.2功能結(jié)構(gòu)圖</b></p><p>　　2.迷宮系統(tǒng)概要設(shè)計(jì)</p><p>　　(1)構(gòu)建一個(gè)二維數(shù)組maze[M+2][N+2]用于存儲(chǔ)迷宮矩陣</p><p>　　(2)自動(dòng)或手動(dòng)生成迷宮，即為

23、二維數(shù)組maze[M+2][N+2]賦值</p><p>　　(3)構(gòu)建一個(gè)隊(duì)列用于存儲(chǔ)迷宮路徑</p><p>　　(4)建立迷宮節(jié)點(diǎn)struct point,用于存儲(chǔ)迷宮中每個(gè)節(jié)點(diǎn)的訪問(wèn)情況</p><p><b>　　(5)實(shí)現(xiàn)搜索算法</b></p><p>　　(6)屏幕上顯示操作菜單</p>&

24、lt;p><b>　　3.程序中的函數(shù)</b></p><p>　　(1)主函數(shù) main()</p><p>　　(2)手動(dòng)生成迷宮函數(shù) shoudong_maze()</p><p>　　(3)自動(dòng)生成迷宮函數(shù) zidong_maze()</p><p>　　(4)將迷宮打印成圖形 print_maze()&l

25、t;/p><p>　　(5)打印迷宮路徑 (若存在路徑) result_maze()</p><p>　　(6)迷宮游戲函數(shù) youxi()</p><p>　　(7)入隊(duì) enqueue()</p><p>　　(8)出隊(duì) dequeue()</p><p>　　(9)判斷隊(duì)列是否為空 is_empty()</p&

26、gt;<p>　　(10)訪問(wèn)節(jié)點(diǎn) visit()</p><p>　　(11)搜索迷宮路徑 mgpath()</p><p><b>　　2.3系統(tǒng)詳細(xì)設(shè)計(jì)</b></p><p>　　實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有數(shù)據(jù)類型及操作的偽代碼算法</p><p>　　1.節(jié)點(diǎn)類型和指針類型</p>&

27、lt;p>　　迷宮矩陣類型：int maze[M+2][N+2];為方便操作使其為全局變量</p><p>　　迷宮中節(jié)點(diǎn)類型及隊(duì)列類型：</p><p>　　struct point{int row,col,predecessor}que[512]</p><p><b>　　2.迷宮的操作</b></p><p&g

28、t;<b>　　(1)手動(dòng)生成迷宮</b></p><p>　　void shoudong_maze(int m,int n)</p><p>　　{定義i,j為循環(huán)變量</p><p><b>　　for(i<=m)</b></p><p><b>　　for(j<=n)&l

29、t;/b></p><p>　　輸入maze[i][j]的值</p><p><b>　　}</b></p><p><b>　　(2)自動(dòng)生成迷宮</b></p><p>　　void zidong_maze(int m,int n)</p><p>　　{定義i,j

30、為循環(huán)變量</p><p><b>　　for(i<=m)</b></p><p><b>　　for(j<=n)</b></p><p>　　maze[i][j]=rand()%2 //由于rand()產(chǎn)生的隨機(jī)數(shù)是從0到 RAND_MAX,RAND_MAX是定義在stdl

31、ib.h中的,其值至少為32767),要產(chǎn)生從X到Y(jié)的數(shù),只需要這樣寫：k=rand()%(Y-X+1)+X;</p><p><b>　　}</b></p><p><b>　　(3)打印迷宮圖形</b></p><p>　　void print_maze(int m,int n)</p><p>

32、;　　{用i,j循環(huán)變量，將maze[i][j]輸出 □、■}</p><p><b>　　(4)打印迷宮路徑</b></p><p>　　void result_maze(int m,int n)</p><p>　　{用i,j循環(huán)變量，將maze[i][j]輸出 □、■、☆}</p><p><b>　　搜

33、索迷宮路徑</b></p><p>　　①迷宮中隊(duì)列入隊(duì)操作</p><p>　　void enqueue(struct point p)</p><p>　　{將p放入隊(duì)尾，tail++}</p><p>　?、诿詫m中隊(duì)列出隊(duì)操作</p><p>　　struct point dequeue(struct

34、 point p)</p><p>　　{head++,返回que[head-1]}</p><p><b>　?、叟袛嚓?duì)列是否為空</b></p><p>　　int is_empty()</p><p>　　{返回head==tail的值，當(dāng)隊(duì)列為空時(shí)，返回0}</p><p>　?、茉L問(wèn)迷宮

35、矩陣中節(jié)點(diǎn)</p><p>　　void visit(int row,int col,int maze[41][41])</p><p>　　{建立新的隊(duì)列節(jié)點(diǎn)visit_point,將其值分別賦為row,col,head-1,maze[row][col]=2,表示該節(jié)點(diǎn)以被訪問(wèn)過(guò);調(diào)用enqueue(visit_point),將該節(jié)點(diǎn)入隊(duì)}</p><p><

36、;b>　?、萋窂角蠼?lt;/b></p><p>　　void mgpath(int maze[41][41],int m,int n)</p><p>　　{先定義入口節(jié)點(diǎn)為struct point p={0,0,-1},從maze[0][0]開(kāi)始訪問(wèn)。如果入口處即為障礙，則此迷宮無(wú)解，返回0 ，程序結(jié)束。否則訪問(wèn)入口節(jié)點(diǎn)，將入口節(jié)點(diǎn)標(biāo)記為訪問(wèn)過(guò)maze[p.row][p.

37、col]=2,調(diào)用函數(shù)enqueue(p)將該節(jié)點(diǎn)入隊(duì)。</p><p>　　判斷隊(duì)列是否為空，當(dāng)隊(duì)列不為空時(shí)，則運(yùn)行以下操作：</p><p>　　{ 調(diào)用dequeue()函數(shù)，將隊(duì)頭元素返回給p，</p><p>　　如果p.row==m-1且p.col==n-1,即到達(dá)出口節(jié)點(diǎn)，即找到了路徑，結(jié)束；</p><p>　　如果p.col

38、+1<n且maze[p.row][p.col+1]==0,說(shuō)明未到迷宮右邊界，且其右方有通路,則visit(p.row,p.col+1,maze),將右邊節(jié)點(diǎn)入隊(duì)標(biāo)記已訪問(wèn)；</p><p>　　如果p.row+1<m且maze[p.row+1][p.col]==0,說(shuō)明未到迷宮下邊界，且其下方有通路,則visit(p.row+1,p.col,maze),將下方節(jié)點(diǎn)入隊(duì)標(biāo)記已訪問(wèn)；</p>

39、<p>　　如果p.col-1>0且maze[p.row][p.col-1]==0,說(shuō)明未到迷宮左邊界，且其左方有通路,則visit(p.row,p.col-1,maze),將左方節(jié)點(diǎn)入隊(duì)標(biāo)記已訪問(wèn)；</p><p>　　如果p.row-1>0且maze[p.row-1][p.col]==0,說(shuō)明未到迷宮上邊界，且其上方有通路,則visit(p.row,p.col+1,maze),將上方

40、節(jié)點(diǎn)入隊(duì)標(biāo)記已訪問(wèn)。</p><p><b>　　}</b></p><p>　　訪問(wèn)到出口(找到路徑)即p.row==m-1且p.col==n-1,則逆序?qū)⒙窂綐?biāo)記為3即：</p><p>　　maze[p.row][p.col]==3;</p><p>　　while(p.predecessor!=-1)</p

41、><p>　　{p=queue[p.predecessor]; </p><p>　　maze[p.row][p.col]==3;}</p><p>　　最后將路徑圖形打印出來(lái)。</p><p>　　搜索算法流程如圖2.3所示：</p><p>　　圖2.3 迷宮路徑搜索流程圖 </p><p>&

42、lt;b>　　菜單選擇</b></p><p>　　while(cycle!=(-1))</p><p>　　☆ 手動(dòng)生成迷宮 請(qǐng)按：1</p><p>　　☆ 自動(dòng)生成迷宮 請(qǐng)按：2</p><p>　　☆ 進(jìn)入迷宮游戲 請(qǐng)按：3</p><p>　　☆ 退出迷宮游戲 請(qǐng)按：4<

43、;/p><p>　　☆ ~~特別鳴謝~~ 請(qǐng)按：0</p><p>　　scanf("%d",&i);</p><p><b>　　switch(i)</b></p><p>　　{ case 1：請(qǐng)輸入行列數(shù)(如果超出預(yù)設(shè)范圍則提示重新輸入) </p><p>　　s

44、houdong_maze(m,n);</p><p>　　print_maze(m,n);</p><p>　　mgpath(maze,m,n);</p><p>　　if(X!=0) result_maze(m,n);</p><p>　　case 2 ：請(qǐng)輸入行列數(shù)(如果超出預(yù)設(shè)范圍則提示重新輸入)</p><p>

45、;　　zidong_maze(m,n);</p><p>　　print_maze(m,n);</p><p>　　mgpath(maze,m,n);</p><p>　　if(X!=0) result_maze(m,n);</p><p>　　case 3: youxi();</p><p>　　case 4：cyc

46、le=(-1);</p><p>　　case 0: 特別鳴謝;break;</p><p><b>　　}</b></p><p>　　注：具體源代碼見(jiàn)附錄</p><p>　　第3章 程序運(yùn)行結(jié)果與分析</p><p><b>　　3.1 調(diào)試分析</b></p&

47、gt;<p>　　在調(diào)試過(guò)程中，首先使用的是棧進(jìn)行存儲(chǔ)，但是產(chǎn)生的路徑是多條或不是最短路徑，所以通過(guò)算法比較，改用隊(duì)列。</p><p><b>　　3.2 測(cè)試結(jié)果</b></p><p><b>　　1.迷宮系統(tǒng)主界面</b></p><p>　　圖3.1 迷宮系統(tǒng)主界面</p><p

48、><b>　　手動(dòng)生成迷宮</b></p><p>　　2.1 手動(dòng)生成迷宮無(wú)解情況</p><p>　　圖3.2 手動(dòng)生成迷宮界面</p><p>　　用戶自定義迷宮的行數(shù)、列數(shù)、迷宮障礙矩陣，由系統(tǒng)生成對(duì)應(yīng)的迷宮并求出無(wú)解。</p><p>　　2.2 手動(dòng)生成迷宮有解情況</p><p&g

49、t;　　圖3.3 手動(dòng)生成迷宮界面</p><p>　　用戶自定義迷宮的行數(shù)、列數(shù)、迷宮障礙矩陣，由系統(tǒng)生成對(duì)應(yīng)的迷宮并求出路徑。上面測(cè)試?yán)又?，路徑為?,0）→(1,0)→(1,1)→(2,1)→(2,2)→(3,2)→(3,3)，在圖中用“☆”表示。</p><p>　　手動(dòng)輸入迷宮代碼如下：</p><p>　　void shoudong_maze(int

50、m,int n)//手動(dòng)輸入迷宮</p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　printf("\n\n");</p><p>　　printf("請(qǐng)按行輸入迷宮，0表示通路，1表示障礙(用空格隔開(kāi)):

51、\n\n");</p><p>　　for(i=0;i<m;i++)</p><p>　　for(j=0;j<n;j++)</p><p>　　scanf("%d",&maze[i][j]);</p><p><b>　　}</b></p><p>

52、;<b>　　自動(dòng)生成迷宮</b></p><p>　　3.1自動(dòng)生成迷宮無(wú)解情況</p><p>　　圖3.4 自動(dòng)生成迷宮界面</p><p>　　用戶自定義迷宮的行數(shù)和列數(shù)，由系統(tǒng)自動(dòng)生成迷宮圖并求出上例迷宮無(wú)解。</p><p>　　3.2 自動(dòng)生成迷宮有解情況</p><p>　　圖3.

53、5 自動(dòng)生成迷宮界面</p><p>　　用戶自定義迷宮的行數(shù)和列數(shù)，由系統(tǒng)自動(dòng)生成迷宮圖并求出路徑。上面測(cè)試?yán)又?，路徑為?,0）→(0,1)→(0,2)→(0,3)→(0,4)→(1,4)→(2,4)→（3,4）→（4,4），在圖中用“☆”表示。</p><p>　　自動(dòng)生成迷宮代碼如下：</p><p>　　void zidong_maze(int m,in

54、t n)//自動(dòng)生成迷宮</p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　printf("\n迷宮生成中……\n\n");</p><p>　　system("pause");</p>

55、;<p>　　for(i=0;i<m;i++)</p><p>　　for(j=0;j<n;j++)</p><p>　　maze[i][j]=rand()%2;</p><p>　　for(i=0;i<3;i++)</p><p>　　for(j=0;j<3;j++)</p><p&

56、gt;<b>　　{</b></p><p>　　maze[i][j]=0;</p><p>　　maze[m-1-i][n-1-j]=0;</p><p><b>　　}</b></p><p>　　//由于rand()產(chǎn)生的隨機(jī)數(shù)是從0到RAND_MAX</p><p>

57、　　//RAND_MAX是定義在stdlib.h中的,其值至少為32767)</p><p>　　//要產(chǎn)生從X到Y(jié)的數(shù),只需要這樣寫：k=rand()%(Y-X+1)+X; </p><p><b>　　}</b></p><p><b>　　迷宮游戲</b></p><p>　　4.1 迷宮游戲

58、主界面</p><p>　　圖3.6 迷宮游戲主界面</p><p>　　4.2 迷宮游戲過(guò)程</p><p>　　圖3.7 迷宮游戲過(guò)程圖</p><p>　　用戶可用上下左右鍵控制迷宮中人物行走方向，控制人物走出迷宮。</p><p>　　迷宮游戲地圖代碼如下：</p><p>　　int

59、iMap[10][20] = </p><p>　　{{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},</p><p>　　{0,0,0,0,0,1,0,0,0,0,1,1,1,1,1,0,0,0,0,1},</p><p>　　{1,0,1,1,0,1,0,1,1,0,0,0,0,0,0,0,1,1,0,1},</p>

60、;<p>　　{1,0,1,1,0,1,0,1,1,1,1,1,1,0,1,1,1,1,0,1},</p><p>　　{1,0,0,0,0,1,0,0,0,0,0,1,1,0,1,0,0,0,0,1},</p><p>　　{1,0,1,1,0,1,0,1,0,1,1,1,1,0,1,0,1,0,1,1},</p><p>　　{1,0,1,1,1,

61、1,0,1,1,1,1,1,1,0,1,1,1,0,1,1},</p><p>　　{1,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,1},</p><p>　　{1,0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,1,0,0,0},</p><p>　　{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1

62、,1,1}};</p><p>　　其人物行走方向以左為例：</p><p>　　if(iMap[iRow][iCol - 1] == 0)//可以行走</p><p><b>　　{</b></p><p>　　MoveCursorTo(iCol * 2,iRow);</p><p>　

63、　printf("←");//當(dāng)前位置移動(dòng)方向 </p><p>　　iCol -= 1;//左移</p><p>　　MoveCursorTo(iCol * 2,iRow);</p><p>　　printf("♀");//在當(dāng)前的位置輸出</p><p><b>　　}</b>

64、</p><p>　　注：其他代碼詳見(jiàn)附錄。</p><p><b>　　5.特別鳴謝界面</b></p><p>　　圖3.8 特別鳴謝界面</p><p><b>　　部分代碼如下：</b></p><p>　　system("cls");<

65、;/p><p>　　printf("制作人：\n\n\t\t劉暢\n\n\t\t周潔\n\n\t\t周胡勇\n\n\n");</p><p>　　system("pause");</p><p>　　system("cls");</p><p><b>　　6.退出迷宮系統(tǒng)&l

66、t;/b></p><p>　　圖3.9 退出迷宮系統(tǒng)界面</p><p><b>　　部分代碼如下：</b></p><p>　　cycle=(-1);</p><p>　　printf("\t正在退出系統(tǒng)。。。\n\t歡迎下次再來(lái)O(∩_∩)O~~\n\n");</p><

67、;p><b>　　break;</b></p><p>　　default:printf("\n");</p><p>　　printf("你的輸入有誤!\n");</p><p>　　printf("\nPress Enter To Contiue!\n");</p>

68、;<p>　　getchar();</p><p>　　while(getchar()!='\n');</p><p><b>　　break;</b></p><p><b>　　第4章 心得總結(jié)</b></p><p>　　這是我們小組成員第一次以團(tuán)隊(duì)合作的形式參

69、與程序設(shè)計(jì)這樣的實(shí)驗(yàn)。由于數(shù)據(jù)結(jié)構(gòu)這門課本身就比較晦澀和難以理解，我們從剛開(kāi)始選題就陷入了僵局。經(jīng)過(guò)我們幾次的討論和商討，最終決定選擇這個(gè)符合我們小組成員實(shí)際能力的選題——迷宮。在確定下選題了之后，我們就著手開(kāi)始準(zhǔn)備實(shí)現(xiàn)程序的各個(gè)步驟。我們依據(jù)實(shí)驗(yàn)報(bào)告的要求和步驟一項(xiàng)項(xiàng)進(jìn)行規(guī)劃，期間在圖書館查閱了很多資料，小組成員之間也相互學(xué)習(xí)，不懂的地方大家一起討論。至于最后代碼的實(shí)現(xiàn)，也是我們小組成員共同努力的結(jié)果。我們不斷改進(jìn)和完善代碼中繁瑣和冗

70、余的部分，力圖寫出一個(gè)最簡(jiǎn)潔明了又不脫離實(shí)際的程序，盡可能做到和現(xiàn)實(shí)相貼近。在上機(jī)實(shí)際操作中，也并不是從一開(kāi)始就順利的，代碼中出現(xiàn)了不少錯(cuò)誤，雖然我們一一調(diào)試改正，但在最后還是遇到了瓶頸，大家也都紛紛絞盡腦汁思考問(wèn)題所在。當(dāng)然，錯(cuò)誤最后被我們查找了出來(lái)。而后便是收尾工作，成員們依舊盡心盡力，最終，經(jīng)過(guò)我們一周多的努力，我們有了實(shí)驗(yàn)成果。 </p><p>　　在這次團(tuán)隊(duì)合作中，我們都深深體會(huì)到學(xué)好專業(yè)知識(shí)的重

71、要性，老師上課所教授的基本知識(shí)是非常必要的，在真正應(yīng)用到實(shí)際選題的時(shí)候就凸顯了出來(lái)，就以我們小組的選題為例，迷宮問(wèn)題的基本思想就是棧的問(wèn)題，如果對(duì)棧的知識(shí)比較了解，在實(shí)現(xiàn)迷宮問(wèn)題時(shí)是不會(huì)太吃力的。其次，通過(guò)團(tuán)隊(duì)合作，我們每個(gè)人都感覺(jué)到了團(tuán)隊(duì)精神的重要性，它不是說(shuō)將每個(gè)人的想法疊加或簡(jiǎn)單拼湊起來(lái)，而是需要我們每個(gè)人協(xié)調(diào)，汲取每個(gè)人的專長(zhǎng)和想法的獨(dú)到之處，進(jìn)而整合起來(lái)，確定一個(gè)完備的方案。其中非常重要的是，在相互討論和商榷中，爭(zhēng)執(zhí)是不可避免

72、的。成員們并沒(méi)有因此動(dòng)怒，而是耐心傾聽(tīng)和思考，說(shuō)出每個(gè)人的意見(jiàn)，做到了讓每個(gè)人都信服。所以說(shuō)，通過(guò)這次實(shí)驗(yàn)，也使我們小組成員之間的關(guān)系更加和諧和親密。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1]文東,華進(jìn).Visual C++程序設(shè)計(jì)基礎(chǔ)與項(xiàng)目實(shí)訓(xùn).第1版.北京:中國(guó)人民大學(xué)出版社,2009</p><p>　　[

73、2]段德亮,余健,張仁才.C#課程設(shè)計(jì)案例精編.第1版.北京:清華大學(xué)出版社,2008</p><p>　　[3]李翠霞.零基礎(chǔ)學(xué)Visual C++.第2版.北京：機(jī)械工業(yè)出版社，2010</p><p>　　[4]李言，李偉明，李賀.Visual C++項(xiàng)目開(kāi)發(fā)全程實(shí)錄.第1版.北京：清華大學(xué)出版社，2008</p><p>　　[5]朱戰(zhàn)立.數(shù)據(jù)結(jié)構(gòu)--使用C

74、語(yǔ)言.第四版.北京：電子工業(yè)出版社，2011</p><p>　　[6]譚浩強(qiáng).C程序設(shè)計(jì).第三版.北京：清華大學(xué)出版社，2005</p><p><b>　　附錄</b></p><p><b>　　程序代碼：</b></p><p>　　#include"stdlib.h"&

75、lt;/p><p>　　#include"stdio.h"</p><p>　　#include <windows.h></p><p>　　#include <conio.h></p><p>　　#include <time.h></p><p>　　#defin

76、e N 39</p><p>　　#define M 39</p><p><b>　　int X;</b></p><p>　　int maze[N+2][M+2];</p><p>　　struct point</p><p><b>　　{</b></p>

77、<p>　　int row,col,predecessor;</p><p><b>　　}</b></p><p>　　queue[512];</p><p>　　int head=0,tail=0;</p><p>　　void shoudong_maze(int m,int n)//手動(dòng)輸入迷宮<

78、/p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　printf("\n\n");</p><p>　　printf("請(qǐng)按行輸入迷宮，0表示通路，1表示障礙(用空格隔開(kāi)):\n\n");</p&g

79、t;<p>　　for(i=0;i<m;i++)</p><p>　　for(j=0;j<n;j++)</p><p>　　scanf("%d",&maze[i][j]);</p><p><b>　　}</b></p><p>　　void zidong_maze(

80、int m,int n)//自動(dòng)生成迷宮</p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　printf("\n迷宮生成中……\n\n");</p><p>　　system("pause");&

81、lt;/p><p>　　for(i=0;i<m;i++)</p><p>　　for(j=0;j<n;j++)</p><p>　　maze[i][j]=rand()%2;</p><p>　　for(i=0;i<3;i++)</p><p>　　for(j=0;j<3;j++)</p>

82、<p><b>　　{</b></p><p>　　maze[i][j]=0;</p><p>　　maze[m-1-i][n-1-j]=0;</p><p><b>　　}</b></p><p>　　//由于rand()產(chǎn)生的隨機(jī)數(shù)是從0到RAND_MAX</p>&

83、lt;p>　　//RAND_MAX是定義在stdlib.h中的,其值至少為32767)</p><p>　　//要產(chǎn)生從X到Y(jié)的數(shù),只需要這樣寫：k=rand()%(Y-X+1)+X; </p><p><b>　　}</b></p><p>　　void print_maze(int m,int n)//輸出迷宮圖</p>

84、<p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　printf("\n迷宮生成結(jié)果如下:\n\n");</p><p>　　printf("迷宮入口\n");</p><p>　　printf

85、("↓");</p><p>　　for(i=0;i<m;i++)</p><p><b>　　{</b></p><p>　　printf("\n");</p><p>　　for(j=0;j<n;j++) </p><p><b>

86、　　{</b></p><p>　　if(maze[i][j]==0) printf("□");//通</p><p>　　if(maze[i][j]==1) printf("■");//堵</p><p><b>　　}</b></p><p><b>　　

87、}</b></p><p>　　printf("→迷宮出口\n");</p><p><b>　　}</b></p><p>　　void result_maze(int m,int n)//輸出探索迷宮結(jié)果</p><p><b>　　{</b></p>

88、<p><b>　　int i,j;</b></p><p>　　printf("迷宮通路(用☆表示)如下所示：\n\t");</p><p>　　for(i=0;i<m;i++)</p><p><b>　　{</b></p><p>　　printf(&q

89、uot;\n");</p><p>　　for(j=0;j<n;j++)</p><p><b>　　{</b></p><p>　　if(maze[i][j]==0||maze[i][j]==2) printf("□");//通</p><p>　　if(maze[i][j]==1)

90、 printf("■");//障礙</p><p>　　if(maze[i][j]==3) printf("☆");//路徑</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b&

91、gt;</p><p>　　void enqueue(struct point p)//增加</p><p><b>　　{</b></p><p>　　queue[tail]=p;</p><p><b>　　tail++;</b></p><p><b>　　}

92、</b></p><p>　　struct point dequeue()//刪除</p><p><b>　　{</b></p><p><b>　　head++;</b></p><p>　　return queue[head-1];</p><p><

93、b>　　}</b></p><p>　　int is_empty()//空對(duì)</p><p><b>　　{</b></p><p>　　return head==tail;</p><p><b>　　}</b></p><p>　　void visit(

94、int row,int col,int maze[41][41])</p><p><b>　　{</b></p><p>　　struct point visit_point={row,col,head-1};</p><p>　　maze[row][col]=2;</p><p>　　enqueue(visit_po

95、int);</p><p><b>　　}</b></p><p>　　int mgpath(int maze[41][41],int m,int n)//路徑探索</p><p><b>　　{</b></p><p><b>　　X=1;</b></p>&l

96、t;p>　　struct point p={0,0,-1};</p><p>　　if(maze[p.row][p.col]==1)</p><p><b>　　{</b></p><p>　　printf("\n===============================================\n");&

97、lt;/p><p>　　printf("此迷宮無(wú)解\n\n");X=0;return 0;}</p><p>　　maze[p.row][p.col]=2;</p><p>　　enqueue(p);</p><p>　　while(!is_empty())</p><p><b>　　{&l

98、t;/b></p><p>　　p=dequeue();</p><p>　　if((p.row==m-1)&&(p.col==n-1)) break;</p><p>　　if((p.col+1<n)&&(maze[p.row][p.col+1]==0))visit(p.row,p.col+1,maze);//右

99、順時(shí)針，依次東南西北探索</p><p>　　if((p.row+1<m)&&(maze[p.row+1][p.col]==0))visit(p.row+1,p.col,maze);//下</p><p>　　if((p.col-1>=0)&&(maze[p.row][p.col-1]==0)) visit(p.row,p.col-1,maze

100、);//左</p><p>　　if((p.row-1>=0)&&(maze[p.row-1][p.col]==0)) visit(p.row-1,p.col,maze);//上</p><p><b>　　}</b></p><p>　　if(p.row==m-1&&p.col==n-1)//到達(dá)終點(diǎn)&l

101、t;/p><p><b>　　{</b></p><p>　　printf("\n==================================================================\n");</p><p>　　printf("迷宮路徑為：\n");</p>&

102、lt;p>　　printf("(%d,%d)\n",p.row,p.col);//輸出當(dāng)前路徑坐標(biāo)</p><p>　　maze[p.row][p.col]=3;//更改通路路徑的值</p><p>　　while(p.predecessor!=-1)//前一點(diǎn)為通路</p><p><b>　　{</b></p

103、><p>　　p=queue[p.predecessor];//循環(huán)尋找前點(diǎn)</p><p>　　printf("(%d,%d)\n",p.row,p.col);</p><p>　　maze[p.row][p.col]=3;</p><p><b>　　}</b></p><p>

104、;<b>　　}</b></p><p>　　else {printf("\n=============================================================\n");</p><p>　　printf("此迷宮無(wú)解！\n\n");X=0;}</p><p>&l

105、t;b>　　return 0;</b></p><p><b>　　}</b></p><p>　　void MoveCursorTo(int iX,int iY)</p><p><b>　　{</b></p><p>　　HANDLE hStd = GetStdHandle(S

106、TD_OUTPUT_HANDLE);</p><p>　　COORD crPlayer = {iX,iY};</p><p>　　SetConsoleCursorPosition(hStd, crPlayer);</p><p><b>　　}</b></p><p>　　void youxi()</p>

107、<p><b>　　{ </b></p><p>　　double t,jl=10;</p><p>　　time_t st,en;</p><p>　　int iMap[10][20] = </p><p>　　{{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},<

108、/p><p>　　{0,0,0,0,0,1,0,0,0,0,1,1,1,1,1,0,0,0,0,1},</p><p>　　{1,0,1,1,0,1,0,1,1,0,0,0,0,0,0,0,1,1,0,1},</p><p>　　{1,0,1,1,0,1,0,1,1,1,1,1,1,0,1,1,1,1,0,1},</p><p>　　{1,0,0

109、,0,0,1,0,0,0,0,0,1,1,0,1,0,0,0,0,1},</p><p>　　{1,0,1,1,0,1,0,1,0,1,1,1,1,0,1,0,1,0,1,1},</p><p>　　{1,0,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,0,1,1},</p><p>　　{1,0,1,1,0,0,0,0,0,1,0,0,0,0,0,

110、0,1,0,1,1},</p><p>　　{1,0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,1,0,0,0},</p><p>　　{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}};</p><p>　　for(int nI = 0; nI < 10; nI++)</p><p>&

111、lt;b>　　{</b></p><p>　　for(int nJ = 0; nJ < 20; nJ++)</p><p><b>　　{</b></p><p>　　if(iMap[nI][nJ] == 1)</p><p><b>　　{</b></p>&

112、lt;p>　　printf("■");</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　printf(" ");</p>

113、<p><b>　　}</b></p><p><b>　　}</b></p><p>　　printf("\n");//打印地圖</p><p><b>　　}</b></p><p>　　printf("\n\n\t按Esc退出到

114、主界面。。。");</p><p>　　printf("\n紀(jì)錄%.5f\n",jl);</p><p>　　int iRow = 1,iCol = 0; //定義人物的坐標(biāo)</p><p>　　int iInput = 0;</p><p>　　MoveCursorTo(iCol * 2,iRow);</

115、p><p>　　time (&st);</p><p>　　printf("♀");//在當(dāng)前的位置輸出</p><p>　　bool bRun = true;//表示程序繼續(xù)運(yùn)行</p><p>　　while(bRun)</p><p><b>　　{</b></

116、p><p>　　iInput = _getch();</p><p>　　if(iInput == 27) //用戶按下了ESC鍵</p><p><b>　　{</b></p><p>　　system("cls");</p><p><b>　　break;</

117、b></p><p><b>　　}</b></p><p>　　if(iInput == 224)//用戶按下了控制鍵</p><p><b>　　{</b></p><p>　　iInput = _getch();</p><p>　　switch(iInput)&

118、lt;/p><p><b>　　{</b></p><p>　　case 75://左</p><p><b>　　{</b></p><p>　　if(iMap[iRow][iCol - 1] == 0)//可以行走</p><p><b>　　{</b

119、></p><p>　　MoveCursorTo(iCol * 2,iRow);</p><p>　　printf("←");//當(dāng)前位置移動(dòng)方向 </p><p>　　iCol -= 1;//左移</p><p>　　MoveCursorTo(iCol * 2,iRow);</p><p>

120、　　printf("♀");//在當(dāng)前的位置輸出</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　break;</b></p><p>　　case 72://上</p><p&

121、gt;<b>　　{</b></p><p>　　if(iMap[iRow - 1][iCol] == 0)//可以行走</p><p><b>　　{ </b></p><p>　　MoveCursorTo(iCol * 2,iRow);</p><p>　　printf("↑&qu

122、ot;);//當(dāng)前位置移動(dòng)方向</p><p>　　iRow -= 1;//上移</p><p>　　MoveCursorTo(iCol * 2,iRow);</p><p>　　printf("♀");//在當(dāng)前的位置輸出</p><p><b>　　}</b></p><p&g

123、t;<b>　　}</b></p><p><b>　　break;</b></p><p>　　case 77://右</p><p><b>　　{</b></p><p>　　if(iCol + 1 >= 20)//到達(dá)終點(diǎn)</p><p>

124、<b>　　{</b></p><p>　　MoveCursorTo(0,16);</p><p>　　printf(" 沖出迷宮！\n");</p><p>　　time (&en);</p><p>　　t=difftime(en,st);</p>

125、;<p>　　printf("游戲用時(shí)%.5f sec \n\n",t);</p><p><b>　　if(t>=jl)</b></p><p>　　printf("o(︶︿︶)o 遺憾，再接再厲。。。\n\n");</p><p>　　else if(t<jl)<

126、;/p><p><b>　　{ </b></p><p>　　printf("~\(≧▽≦)/~ 好棒，紀(jì)錄刷新?。?！\n\n");</p><p><b>　　jl=t;</b></p><p><b>　　}</b></p><

127、p>　　bRun = false; //結(jié)束循環(huán)</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　if(iMap[iRow][iCol + 1] == 0)//可以行走</p><p><b>　　{</b>&

128、lt;/p><p>　　MoveCursorTo(iCol * 2,iRow);</p><p>　　printf("→"); //當(dāng)前位置移動(dòng)方向</p><p>　　iCol += 1;//右移</p><p>　　MoveCursorTo(iCol * 2,iRow);</p><p>　　pri

129、ntf("♀");//在當(dāng)前的位置輸出</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　break;</b></p><p>　　case 80://下</p><p>&l

130、t;b>　　{</b></p><p>　　if(iMap[iRow + 1][iCol] == 0)//可以行走</p><p><b>　　{</b></p><p>　　MoveCursorTo(iCol * 2,iRow);</p><p>　　printf("↓");//

131、當(dāng)前位置移動(dòng)方向 </p><p>　　iRow += 1;//下移</p><p>　　MoveCursorTo(iCol * 2,iRow); </p><p>　　printf("♀");//在當(dāng)前的位置輸出</p><p><b>　　}</b></p><p>

132、<b>　　}</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>

133、　　system("cls");</p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p><b>　　double t;</b></p><p>　　

134、time_t start,end;</p><p>　　int i,m,n,cycle=0;</p><p>　　while(cycle!=(-1))</p><p><b>　　{</b></p><p>　　printf("*****************************-------------

135、--------******************************\n");</p><p>　　printf(" 歡迎進(jìn)入迷宮求解系統(tǒng)\n\n");</p><p>　　printf(" \n");</p><p>　　print

136、f("***************************-------------------------****************************\n");</p><p>　　printf(" ☆ 手動(dòng)生成迷宮 請(qǐng)按：1\n\n");</p><p>　　printf(&q