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

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

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

3、t;<p>　　_________________________________________ </p><p>　　_________________________________________ </p><p>　　_________________________________________ </p><p>　　評閱教師: _

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

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

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

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

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

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

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

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

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

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

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

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

16、迷宮，這樣迷宮的每一個位置都可以用其行列號來唯一指定，但是二維數(shù)組不能動態(tài)定義其大小，我們可以考慮先定義一個較大的二維數(shù)組maze[M+2][N+2],然后用它的前m行n列來存放元素，即可得到一個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>　　首先從迷宮的入口開始，如果該位置就是迷宮出口，則已經(jīng)找到了一條路徑，搜索工作結(jié)束。否則搜索其上、下、左、右位置是否是障礙，若不是障礙，就移動到該位置，然后再從該位置開始搜索通往出口的路徑；若是障礙就選擇另一個相鄰的位置，并從它開始搜索路徑。為防止搜索重復(fù)出現(xiàn)，則將已搜索過的位置標記為

18、2，同時保留搜索痕跡，在考慮進入下一個位置搜索之前，將當(dāng)前位置保存在一個隊列中，如果所有相鄰的非障礙位置均被搜索過，且未找到通往出口的路徑，則表明不存在從入口到出口的路徑。這實現(xiàn)的是廣度優(yōu)先遍歷的算法，如果找到路徑，則為最短路徑。</p><p>　　以矩陣 0 0 1 0 1 為例，來示范一下</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)(序號0)放入隊列中，其前節(jié)點為空，從它開始搜索，其標記變?yōu)?，由于其只有一個非障礙位置，所以接下來移動到(0,1)(序號1)，其前節(jié)點序號為0，標記變?yōu)?，然后從(0,1)移動到(1

20、,1)(序號2)，放入隊列中，其前節(jié)點序號為1，(1,1)存在(1，2)(序號3)、(2，1)(序號4)兩個可移動位置，其前節(jié)點序號均為2.對于每一個非障礙位置，它的相鄰非障礙節(jié)點均入隊列，且它們的前節(jié)點序號均為該位置的序號，所以如果存在路徑，則從出口處節(jié)點的位置，逆序就可以找到其從出口到入口的通路，搜索路徑如表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é)果分為兩種，一種是直觀的用圖給出的通路，其中通路用☆表示，第二種輸出的是尋找完后的路徑，路徑用具體的坐標來表示。</p><p>　　2.2 系統(tǒng)總體設(shè)計 </

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

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

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

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

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

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

28、t;<b>　　(1)手動生成迷宮</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)自動生成迷宮</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)生的隨機數(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>　?、倜詫m中隊列入隊操作</p><p>　　void enqueue(struct point p)</p><p>　　{將p放入隊尾，tail++}</p><p>　?、诿詫m中隊列出隊操作</p><p>　　struct point dequeue(struct

34、 point p)</p><p>　　{head++,返回que[head-1]}</p><p><b>　?、叟袛嚓犃惺欠駷榭?lt;/b></p><p>　　int is_empty()</p><p>　　{返回head==tail的值，當(dāng)隊列為空時，返回0}</p><p>　　④訪問迷宮

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

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

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

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

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

40、節(jié)點入隊標記已訪問。</p><p><b>　　}</b></p><p>　　訪問到出口(找到路徑)即p.row==m-1且p.col==n-1,則逆序?qū)⒙窂綐擞洖?即：</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>　　最后將路徑圖形打印出來。</p><p>　　搜索算法流程如圖2.3所示：</p><p>　　圖2.3 迷宮路徑搜索流程圖 </p><p>&

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

43、;/p><p>　　☆ ~~特別鳴謝~~ 請按：0</p><p>　　scanf("%d",&i);</p><p><b>　　switch(i)</b></p><p>　　{ case 1：請輸入行列數(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 ：請輸入行列數(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>　　注：具體源代碼見附錄</p><p>　　第3章 程序運行結(jié)果與分析</p><p><b>　　3.1 調(diào)試分析</b></p&

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

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

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

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

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>　　自動生成迷宮</b></p><p>　　3.1自動生成迷宮無解情況</p><p>　　圖3.4 自動生成迷宮界面</p><p>　　用戶自定義迷宮的行數(shù)和列數(shù)，由系統(tǒng)自動生成迷宮圖并求出上例迷宮無解。</p><p>　　3.2 自動生成迷宮有解情況</p><p>　　圖3.

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

54、t n)//自動生成迷宮</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)生的隨機數(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 迷宮游戲過程</p><p>　　圖3.7 迷宮游戲過程圖</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)前位置移動方向 </p><p>　　iCol -= 1;//左移</p><p>　　MoveCursorTo(iCol * 2,iRow);</p><p>　　printf("♀");//在當(dāng)前的位置輸出</p><p><b>　　}</b>

64、</p><p>　　注：其他代碼詳見附錄。</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歡迎下次再來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>　　這是我們小組成員第一次以團隊合作的形式參

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

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

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

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

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

74、語言.第四版.北京：電子工業(yè)出版社，2011</p><p>　　[6]譚浩強.C程序設(shè)計.第三版.北京：清華大學(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)//手動輸入迷宮<

78、/p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　printf("\n\n");</p><p>　　printf("請按行輸入迷宮，0表示通路，1表示障礙(用空格隔開):\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)//自動生成迷宮</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)生的隨機數(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()//空對</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("此迷宮無解\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、順時針，依次東南西北探索</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)//到達終點&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)前路徑坐標</p><p>　　maze[p.row][p.col]=3;//更改通路路徑的值</p><p>　　while(p.predecessor!=-1)//前一點為通路</p><p><b>　　{</b></p

103、><p>　　p=queue[p.predecessor];//循環(huá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("此迷宮無解！\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紀錄%.5f\n",jl);</p><p>　　int iRow = 1,iCol = 0; //定義人物的坐標</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ù)運行</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)前位置移動方向 </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)前位置移動方向</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)//到達終點</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("游戲用時%.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("~\(≧▽≦)/~ 好棒，紀錄刷新?。?！\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)前位置移動方向</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)前位置移動方向 </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(" 歡迎進入迷宮求解系統(tǒng)\n\n");</p><p>　　printf(" \n");</p><p>　　print

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