迷宮問題說明書

1、目目 錄錄摘摘 要要.1前前 言言.2正正 文文.31.采用類C語言定義相關(guān)的數(shù)據(jù)類型.32.各模塊的偽碼算法.33.函數(shù)的調(diào)用關(guān)系圖.54.調(diào)試分析.55.測試結(jié)果.66.源程序（帶注釋）.9總總 結(jié)結(jié).16參考文獻(xiàn)參考文獻(xiàn).17致致 謝謝.18附件附件 部分部分源源程序代碼程序代碼.191摘摘 要要迷宮問題的求解是一個很好的在?；蛘哧犃械确矫娴膽?yīng)用問題，本次設(shè)計是以棧去實(shí)現(xiàn)的。問題的求解主要是給定一個入口坐標(biāo)和出口坐標(biāo)時求出一條從入口到出口的路徑，如果不存在或存在要做出相應(yīng)的判斷，存在時打印其路徑，并做動態(tài)演示。 關(guān)鍵字：棧，棧的存儲結(jié)構(gòu)，出棧與入棧2前前 言言由于計算機(jī)解迷宮時，通常用的

2、是群舉的方法，即從入口出發(fā)，順某一方向搜索。若能走通，則繼續(xù)往前走；否則沿原路退回，換一個方向再繼續(xù)搜直至所有可能的通路都搜索完為止。為了保證在任何位置上都能沿原路返回，這就需要一個后進(jìn)先出的結(jié)構(gòu)來存儲起位置，所以用到了棧的概念。在問題的求解過程中，用到了對棧的定義、棧的初始化、棧的空間的申情、棧的銷毀等有關(guān)棧的知識。 通過這次課程設(shè)計可讓我們更深一步的了解棧的概念。在解決問題的過程中初步懂的如何去選擇合適的方法去處理問題，提高解決問題的效率。3正正 文文1.1. 采用類采用類 c c 語言定義相關(guān)的數(shù)據(jù)類型語言定義相關(guān)的數(shù)據(jù)類型(1) void enqueue(struct point p)

3、 queuetail=p; tail+; (2) struct point dequeue(void) head+; return queuehead-1; 2.2. 各模塊的偽碼算法各模塊的偽碼算法(1)void zidong_maze(int m,int n) /自動生成迷宮問題 system(cls); int i,j;4 printf(自動生成迷宮n); printf(loadingn); system (pause); /暫停 for(i=0;im;i+) for(j=0;jn;j+) mazeij=rand()%2; (2)void print_maze(int m,int n)

4、int i,j; for(i=0;in;i+) /*迷宮外圍設(shè)置封閉*/ mazei0=1; mazein-1=1; maze0i=1; mazen-1i=1; for(i=0;im;i+) printf(n); for(j=0;j50|n50) 6 printf(n); printf(:n); scanf(%d,&m); printf(:n); scanf(%d,&n);b、算法的時間復(fù)雜度和空間復(fù)雜度空間復(fù)雜度：4.27kb；時間復(fù)雜度：O(n)；5.5. 測試結(jié)果測試結(jié)果a歡迎界面：輸入行，列：7選擇界面：8運(yùn)行結(jié)果：96.6. 源程序（帶注釋）源程序（帶注釋）#incl

5、udeiostream#includestdlib.husing namespace std;#define N 50#define M 50int mazeN+2M+2;struct point int row, col, predecessor; queue512;int head=0, tail=0;void zidong_maze(int m,int n) /自動生成迷宮問題 system(cls); int i,j; printf(自動生成迷宮n); printf(loadingn); system (pause); /暫停 for(i=0;im;i+) for(j=0;jn;j+)

6、 mazeij=rand()%2; /0、1 隨機(jī)數(shù)產(chǎn)生，生成迷宮 void print_maze(int m,int n) int i,j; for(i=0;in;i+) /*迷宮外圍設(shè)置封閉*/ mazei0=1; mazein-1=1; maze0i=1;10 mazen-1i=1; for(i=0;im;i+) printf(n); for(j=0;jn;j+) printf(%d,mazeij);void build_maze(int m,int n) system(cls); printf(生成結(jié)果n); printf(迷宮入口n); printf(); print_maze(m,

7、n); printf(迷宮出口n);void result_maze(int m,int n) /迷宮生成圖形 int i,j; printf(迷宮生成圖形如下所示: n); for(i=0;im;i+) printf(n); for(j=0;jn;j+) if(mazeij=0) printf( ); if(mazeij=1) printf(); 11void enqueue(struct point p) queuetail=p; tail+;struct point dequeue(void) head+; return queuehead-1; int is_empty(void) r

8、eturn head=tail; void visit(int row,int col,int maze5252) struct point visit_point=row,col,head-1; mazerowcol=2; enqueue(visit_point); int mgpath(int maze5252,int m,int n) struct point p=0,0,-1; if(mazep.rowp.col=1) printf(此迷宮無解nn);return 0;mazep.rowp.col=2;enqueue(p);while (!is_empty() p=dequeue();

9、 if (p.row=m-1&p.col=n-1) /goal break;12 if(p.col+1n&mazep.rowp.col+1=0) /right visit(p.row,p.col+1,maze); if(p.row+1=0&mazep.rowp.col-1=0) /left visit(p.row,p.col-1,maze); if(p.row-1=0&mazep.row-1p.col=0) /up visit(p.row-1,p.col,maze); print_maze(m,n); printf(n-n);if(p.row=m-1&p

10、.col=n-1) printf(迷宮路徑為:n); printf(%d,%d)n,p.row, p.col); mazep.rowp.col=3; while(p.predecessor !=-1) p=queuep.predecessor; printf(%d,%d)n,p.row,p.col); mazep.rowp.col=3; else printf(此迷宮無解!n); return 0;void menu() int m,n; /控制迷宮的行數(shù)和列數(shù) int cycle; /循環(huán)控制 int choice; /選擇13 printf(n);printf(*歡迎進(jìn)入用戶界面*n);

11、printf(n); while(cycle!=-1) printf(請輸入行數(shù)：n); scanf(%d,&m); printf(請輸入列數(shù):n); scanf(%d,&n); while(m50|n50) printf(n); printf(:n); scanf(%d,&m); printf(:n); scanf(%d,&n); if(m=50&n50|n50) printf(行列數(shù)超出預(yù)設(shè)范圍，請重新輸入n); printf(請輸入行數(shù)n); scanf(%d,&m); printf(請輸入列數(shù)n); scanf(%d,&n); m

12、gpath(maze,m,n); /尋找迷宮路由 result_maze(m,n); /打印出迷宮圖形及路徑 printf(n 是否重新輸入迷宮，如果不繼續(xù)，按-1 退出n); scanf(%d,&cycle);void main()15 system(color f5); /系統(tǒng)函數(shù) menu();16總總 結(jié)結(jié)在這三周的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計中,我的題目是:迷宮問題,這三周課程設(shè)計中,通過該題目的設(shè)計過程,我加深了對棧的邏輯結(jié)構(gòu),存儲結(jié)構(gòu)及入棧出棧過程的理解,對棧的基本運(yùn)算的實(shí)現(xiàn)有所掌握,對課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)進(jìn)一步理解和掌握,學(xué)會了如何把學(xué)到的知識用于解決實(shí)際問題,鍛煉了自己動手的

13、能力。一個人要完成所有的工作是非常困難和耗時的。在以后的學(xué)習(xí)中我會更加注意各個方面的能力的協(xié)調(diào)發(fā)展。在課程設(shè)計時遇到了很多的問題，在老師的幫助，和對各種資料的查閱中，將問題解決，培養(yǎng)了我自主動手，獨(dú)立研究的能力，為今后在學(xué)習(xí)工作中能更好的發(fā)展打下了堅實(shí)的基礎(chǔ)。三周的課程設(shè)計很短暫，但其間的內(nèi)容是很充實(shí)的，在其中我學(xué)習(xí)到了很多平時書本中無法學(xué)到的東西，積累了經(jīng)驗，鍛煉了自己分析問題，解決問題的能力，并學(xué)會了如何將所學(xué)的各課知識融會，組織，來配合學(xué)習(xí)，三周中我收益很大，學(xué)到很多。17參考文獻(xiàn)參考文獻(xiàn)1 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C 語言版） .清華大學(xué)出版社.2 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)題集（C

14、 語言版） .清華大學(xué)出版社.3 DATA STRUCTURE WITH C+.William Ford，William Tcpp.清華大學(xué)出版社（影印版）.4 譚浩強(qiáng).C 語言程序設(shè)計.清華大學(xué)出版社.18致致 謝謝首先感謝我的指導(dǎo)老師王旭陽老師，她在我的課程設(shè)計過程中提出了指導(dǎo)性的方案和架構(gòu)，并指引我閱讀相關(guān)的資料和書籍，使我在不熟悉的領(lǐng)域中仍能迅速掌握新的技術(shù)。感謝我的數(shù)據(jù)結(jié)構(gòu)老師王旭陽老師和張永老師以及 C 語言老師王連相老師在以往的基礎(chǔ)課學(xué)習(xí)中為我打下良好的基礎(chǔ)，這是我這次課程設(shè)計能夠順利完成的前提。我的同學(xué)在設(shè)計完成后對程序的測試，沒有他們，也許就難以發(fā)現(xiàn)一些潛在的錯誤，在此一并表

15、示感謝。19附件附件 部分源程序代碼部分源程序代碼#includeiostream#includestdlib.husing namespace std;#define N 50#define M 50int mazeN+2M+2;struct point int row, col, predecessor; queue512;int head=0, tail=0;void zidong_maze(int m,int n) /自動生成迷宮問題 system(cls); int i,j; printf(自動生成迷宮n); printf(loadingn); system (pause); /暫停

16、 for(i=0;im;i+) for(j=0;jn;j+) mazeij=rand()%2; /0、1 隨機(jī)數(shù)產(chǎn)生，生成迷宮 void print_maze(int m,int n) int i,j; for(i=0;in;i+) /*迷宮外圍設(shè)置封閉*/ mazei0=1; mazein-1=1; maze0i=1;20 mazen-1i=1; for(i=0;im;i+) printf(n); for(j=0;jn;j+) printf(%d,mazeij);void result_maze(int m,int n) /迷宮生成圖形 int i,j; printf(迷宮生成圖形如下所示:

17、 n);void enqueue(struct point p) queuetail=p; tail+;struct point dequeue(void) head+; return queuehead-1; int is_empty(void) return head=tail; void visit(int row,int col,int maze5252) struct point visit_point=row,col,head-1; mazerowcol=2; enqueue(visit_point); int mgpath(int maze5252,int m,int n) st

18、ruct point p=0,0,-1;21 if(mazep.rowp.col=1) printf(此迷宮無解nn);return 0;mazep.rowp.col=2;enqueue(p);while (!is_empty() p=dequeue(); if (p.row=m-1&p.col=n-1) /goal break; if(p.col+1n&mazep.rowp.col+1=0) /right visit(p.row,p.col+1,maze); if(p.row+1=0&mazep.rowp.col-1=0) /left visit(p.row,p.col-1,maze); if(p.row-1=0&mazep.row-1p.col=0) /up visit(p.row-1,p.col,maze); print