1、基于c語言的迷宮問題專業(yè)課程設(shè)計*實踐教學(xué)* 蘭州理工大學(xué)軟件學(xué)院2012年春季學(xué)期 算法與數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計題 目： 迷宮問題 專業(yè)班級： 姓 名： 學(xué) 號： 指導(dǎo)教師： 成 績：_摘要在現(xiàn)實生活中，會遇到很多很多關(guān)于迷宮這樣很復(fù)雜、很難解決的問題的問題。如果人工去解決這些問題，會很麻煩，花很長的時間，甚至無法解決。假如用計算機去解決，可以通過手動生成迷宮，也可以通過計算機隨機的產(chǎn)生迷宮，最終退出。而且可以很快的求解迷宮，找到從入口到出口的通路，或者當(dāng)沒有通路時，得出沒有通路的結(jié)論。找出通路之后，會顯示出通路路經(jīng)，而且以圖示的方式顯示出通路，這樣會使人一目了然的看清此迷宮的通路。迷宮是一個矩

2、形區(qū)域，可以使用二維數(shù)組表示迷宮，這樣迷宮的每一個位置都可以用其行列號來唯一指定，但是二維數(shù)組不能動態(tài)定義其大小，我們可以考慮先定義一個較大的二維數(shù)組mazeM+2N+2,然后用它的前m行n列來存放元素，即可得到一個m×n的二維數(shù)組，這樣(0,0)表示迷宮入口位置，(m-1,n-1)表示迷宮出口位置。 關(guān)鍵詞： 迷宮；通路；二維數(shù)組；路徑序言 隨著社會經(jīng)濟的發(fā)展，信息化程度的不斷深入，傳統(tǒng)的人工求解迷宮問題已不能滿足生活的需要。近幾年，隨著迷宮問題越來越復(fù)雜、科技也越來越發(fā)達，人們逐漸的開始用計算機求解迷宮問題。迷宮問題很復(fù)雜，但是人們又不得不去研究這個問題，因為人們的生活中需要它，

3、離不開它。在迷宮路徑的搜索過程中，首先從迷宮的入口開始，如果該位置就是迷宮出口，則已經(jīng)找到了一條路徑，搜索工作結(jié)束。否則搜索其上、下、左、右位置是否是障礙，若不是障礙，就移動到該位置，然后再從該位置開始搜索通往出口的路徑；若是障礙就選擇另一個相鄰的位置，并從它開始搜索路徑。為防止搜索重復(fù)出現(xiàn)，則將已搜索過的位置標(biāo)記為2，同時保留搜索痕跡，在考慮進入下一個位置搜索之前，將當(dāng)前位置保存在一個隊列中，如果所有相鄰的非障礙位置均被搜索過，且未找到通往出口的路徑，則表明不存在從入口到出口的路徑。這實現(xiàn)的是廣度優(yōu)先遍歷的算法，如果找到路徑，則為最短路徑。目錄一、需求分析51.1 功能與數(shù)據(jù)需求5 1.1.

4、1 題目要求的功能5 1.1.2 擴展功能51.2 界面需求61.3 開發(fā)環(huán)境與運行需求6二、概要設(shè)計72.1主要數(shù)據(jù)結(jié)構(gòu)72.2各模塊函數(shù)說明8三、詳細(xì)設(shè)計9四、測試10五、使用說明135.1應(yīng)用程序功能的詳細(xì)說明135.2應(yīng)用程序運行環(huán)境要求135.3輸入數(shù)據(jù)類型、格式和內(nèi)容限制13六、總結(jié)提高146.1課程設(shè)計總結(jié)146.2開發(fā)中遇到的問題和解決方法146.3 對自己完成課設(shè)完成情況的評價14參考文獻15致 謝1623一、需求分析1.1 功能與數(shù)據(jù)需求 問題描述：以一個m×n的長方形表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口

5、的通路，或得出沒有通路的結(jié)論。1.1.1 題目要求的功能 基本要求：首先實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個坐標(biāo)，d表示走到下一坐標(biāo)的方向。如：對于下列數(shù)據(jù)的迷宮，輸出的一條通路為：（1,1,1）, （1,2,2）, （2,2,2）（3,2,3）, （3,1,2）,。測試數(shù)據(jù)：迷宮的測試數(shù)據(jù)如下：左上角（1,1）為入口，右下角（9,8）為出口。001000100010001000001101011100100001000001000101011110011100010111000000

6、1 2 3 4 5 6 7 81.1.2 擴展功能（1）編寫遞歸形式的算法，求得迷宮中所有可能的通路；（2）以方陣形式輸出迷宮及其通路1.2 界面需求請求輸入進入程序請求輸入起始位置請求輸入終點位置輸出方陣迷宮輸出路徑輸出方陣路徑1.3 開發(fā)環(huán)境與運行需求Visual C+6.0二、概要設(shè)計2.1主要數(shù)據(jù)結(jié)構(gòu) 輸入起始位置，終點位置 判斷首節(jié)點是否為通路判斷路徑能否走通對坐標(biāo)標(biāo)記 是否到達迷宮出口處左邊是否存在通路下邊是否存在通路右邊是否存在通路上邊是否存在通路存儲路徑，將路徑入棧 有解迷宮 無解迷宮 YNYNY輸出迷宮 選擇路徑 圖一.主流程圖2.2各模塊函數(shù)說明typedef struct

7、 int pos_xlength;/進棧坐標(biāo)int pos_ylength;int top; int base; Stack; /新建結(jié)構(gòu)體void initStack(Stack *p) /初始化棧Push(Stack *p,int x,int y,int d) /入棧具體操作 Pop(Stack *p,int read2,int d) /出棧并讀出前一步的坐標(biāo) initMaze(int Maze109)/建立迷宮Ways(Stack *p,int Maze109,int rukou_x,int rukou_y,int chukou_x,int chukou_y,int d) /具體路徑的求

8、解 menu();/調(diào)用菜單函數(shù) main();/實現(xiàn)迷宮求解的主函數(shù)三、詳細(xì)設(shè)計 迷宮的過程可以模擬為一個搜索的過程：每到一處，總讓它按左、右、上、下4個方向順序試探下一個位置；如果某方向可以通過，并且不曾到達，則前進一步，在新位置上繼續(xù)進行搜索；如果4方向都走不通或曾經(jīng)到達過，則退回一步，在原來的位置上繼續(xù)試探下一位置。每前進或后退一步，都要進行判斷：若前進到了出口處，則說明找到了一條合適的通路；若退回到了入口處，則說明不存在合法的通路到達出口。用一個二維指針數(shù)組迷宮表示迷宮，數(shù)組中每個元素取值“0”（表示通路）或“1”（表示墻壁）。迷宮的入口點在位置（1，1）處，出口點在位置（m,n）處

9、。設(shè)計一個模擬走迷宮的算法，為其尋找一條從入口點到出口點的通路。二維數(shù)組的第0行、第m+1行、第0列、第m+1列元素全置成“1”， 表示迷宮的外墻；第1行第1列元素和第m行第m列元素置成“0”， 表示迷宮的入口和出口；假設(shè)當(dāng)前所在位置是（x,y）。沿某個方向前進一步，它可能到達的位置最多有4。四、測試圖二.進入迷宮圖三.查找路徑圖四.退出迷宮五、使用說明5.1應(yīng)用程序功能的詳細(xì)說明按提示輸入數(shù)字1進入迷宮，輸入迷宮入口，迷宮出口5.2應(yīng)用程序運行環(huán)境要求Microsoft Visual C+6.05.3輸入數(shù)據(jù)類型、格式和內(nèi)容限制輸入的數(shù)據(jù)都是整型（int），輸入迷宮的數(shù)據(jù)間要用空格或回車隔開

10、六、總結(jié)提高6.1課程設(shè)計總結(jié)要能很好的掌握編程,僅僅通過簡單的程序的編寫是無法達成的,需要大量積累和深入研究才有可能。就從這個迷宮問題求解來說,在迷宮求路徑就需要使用鏈表的棧,靠出棧和進棧來存取路徑數(shù)據(jù).在程序的編寫中也不能一味的向已有的程序進行模仿,而要自己摸索,去尋找最好的解決方法,只有帶著問題去反復(fù)進行實踐,才能更熟練的掌握和運用,當(dāng)然,對現(xiàn)有的程序也要多去接觸,因為有些程序是我們無法在短時間內(nèi)想出來的.最重要的一點是持之以恒,要經(jīng)常性的復(fù)習(xí)原來接觸的程序,這樣才能保證我們有足夠的經(jīng)驗去面對程序問題.6.2開發(fā)中遇到的問題和解決方法 問題： 在開始時迷宮求解的 路徑無法顯示尋找路徑所走

11、的方向等問題。 解決方法：在棧中增加一個變量d來表示方向，在尋找路徑的時候判斷下一個坐標(biāo)點和本坐標(biāo)點的關(guān)系。在（x）行不變的情況下：（y+1）列加一則表示坐標(biāo)往右走了一步記為1、（y-1）列減一則表示坐標(biāo)往左走了一步記為3；在（y）不變的情況下：（x+1）行加一則表示坐標(biāo)往下走了一步記為2、（x-1）行減一則表示坐標(biāo)往上走了一步記為4；6.3 對自己完成課設(shè)完成情況的評價經(jīng)過本次課程設(shè)計，我深刻地明白了理論與實踐應(yīng)用相結(jié)合的重要性，并努力克服自己在分析復(fù)雜問題的弱點。這次課程設(shè)計同時也考驗我的綜合運用所學(xué)知識的能力和操作能力。參考文獻1 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)出版社.2

12、 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)題集（C語言版）.清華大學(xué)出版社.3 DATA STRUCTURE WITH C+. William Ford,William Topp .清華大學(xué)出版社（影印版）. 4 譚浩強.c語言程序設(shè)計. 清華大學(xué)出版社. 5數(shù)據(jù)結(jié)構(gòu)與算法分析（Java版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A. Shaffer , 張銘,劉曉丹譯 電子工業(yè)出版社 2001 年1月致 謝 在這樣的一個程序設(shè)計中，靠一個人的單打獨斗是不可

13、能完成的。在這次設(shè)計過程中，在開始的構(gòu)思、設(shè)想，源代碼編寫時的提示，上機時精心的指點，有了老師和舍友以及身邊同學(xué)的指導(dǎo)、意見和幫助，最終才完成了這個迷宮求解問題系統(tǒng)的設(shè)計與實現(xiàn)。所以在這里要對以上老師及同學(xué)表示感謝，非常感謝他們的幫助。而且在這次課程設(shè)計中我學(xué)習(xí)到了很多很多。附錄：程序源代碼#include <stdio.h> #include <malloc.h> #include<stdlib.h>#include<conio.h>#define length 50#define d direction /用d代表所走路徑的方向int n=-

14、1;int step=0; /記錄步驟數(shù) typedef struct int pos_xlength;/進棧坐標(biāo)int pos_ylength;int top; int base; Stack; /新建結(jié)構(gòu)體void initStack(Stack *p) p->top=p->base=0; /初始化棧. Push(Stack *p,int x,int y,int d) /入棧具體操作 step+;d=0;n=n+1; p->top=p->top+1; p->pos_xn=x; p->pos_yn=y;Pop(Stack *p,int read2,int

15、d) /出棧并讀出前一步的坐標(biāo) step+;d=0;n=n-1; p->top=p->top-1; read0=p->pos_xn; read1=p->pos_yn;initMaze(int Maze109)/建立迷宮函數(shù). int i; for (i=0;i<=9;i+) Maze0i=1; for (i=0;i<=10;i+) Mazei0=1; for (i=0;i<=9;i+) Maze10i=1; for (i=0;i<=10;i+) Mazei9=1; Maze11=0;Maze12=0;Maze13=1;Maze14=0;Maze1

16、5=0;Maze16=0;Maze17=1;Maze18=0; Maze21=0;Maze22=0;Maze23=1;Maze24=0;Maze25=0;Maze26=0;Maze27=1;Maze28=0; Maze31=0;Maze32=0;Maze33=0;Maze34=0;Maze35=1;Maze36=1;Maze37=0;Maze38=1; Maze41=0;Maze42=1;Maze43=1;Maze44=1;Maze45=0;Maze46=0;Maze47=1;Maze48=0; Maze51=0;Maze52=0;Maze53=0;Maze54=1;Maze55=0;Maze

17、56=0;Maze57=0;Maze58=0;Maze61=0;Maze62=1;Maze63=0;Maze64=0;Maze65=0;Maze66=1;Maze67=0;Maze68=1;Maze71=0;Maze72=1;Maze73=1;Maze74=1;Maze75=1;Maze76=0;Maze77=0;Maze78=1;Maze81=1;Maze82=1;Maze83=0;Maze84=0;Maze85=0;Maze86=1;Maze87=0;Maze88=1;Maze91=1;Maze92=1;Maze93=0;Maze94=0;Maze95=0;Maze96=0;Maze97=

18、0;Maze98=0; Print( )/打印出迷宮界面 int m,n,j,sum; int Maze109;printf("迷宮(1代表墻即不通,0代表可通過)n"); printf(" ");for(j=1;j<=8;j+) printf("%4d",j);printf("n");for(m=0;m<=10;m+) for(n=0;n<=9;n+) printf("%4d",Mazemn);sum+; if(sum%10=0) printf("n");

19、 Ways(Stack *p,int Maze109,int rukou_x,int rukou_y,int chukou_x,int chukou_y,int d) /具體路徑的求解函數(shù) int x,y; int read2; x=rukou_x; y=rukou_y; printf("第%d步:",step);printf("(%d,%d,%d)n",x,y,d);if(x=chukou_x&&y=chukou_y)printf("到達出口坐標(biāo)共走了%d步n",step);return 0;else if(Maze

20、xy+1=0) y=y+1;d=1;Push(p,x,y,d);Mazexy-1=1;Mazexy=1; else if(Mazex+1y=0) x=x+1;d=2;Push(p,x,y,d);Mazex-1y=1;Mazexy=1; else if(Mazexy-1=0) y=y-1;d=3;Push(p,x,y,d);Mazexy+1=1;Mazexy=1; else if(Mazex-1y=0) x=x-1;d=4;Push(p,x,y,d);Mazex+1y=1;Mazexy=1; else Pop(p,read,d); x=read0; y=read1;if(p->top=p-

21、>base) printf("找不到出口n");return 0; Ways(p,Maze,x,y,chukou_x,chukou_y,d);return 1; menu()printf("tt*n"); printf("tt* 歡迎進入課程設(shè)計 *n"); printf("tt* 迷宮求解程序 *n"); printf("tt* 菜單: *n");printf("tt*進入迷宮*請輸入1 *n");printf("tt*退出迷宮*請輸入2 *n")

22、;printf("tt*n");int main() Stack *p; Stack S; int Maze109; /定義迷宮int elem_11,elem_21,a,j; int rukou_x,rukou_y,d=0;int chukou_x,chukou_y; int sum=0; p=&S; initMaze(Maze); system("color 5f");/dos窗口背景顏色函數(shù) menu();/調(diào)用菜單函數(shù)printf("請輸入您的選擇:");scanf("%d",&a);if(a=1) Print( ); /打印迷宮圖printf("請輸入入口坐標(biāo):");scanf("%d",&elem_10); scanf("%d"