數(shù)據(jù)結(jié)構(gòu)與算法----迷宮求解課程設(shè)計

1、<p>　　課 程 設(shè) 計</p><p>　　課程設(shè)計名稱： 迷宮求解 </p><p>　　專 業(yè) 班 級 ： </p><p>　　學(xué) 生 姓 名 ： </p><p>　　學(xué) 號 ： </p>&l

2、t;p>　　指 導(dǎo) 教 師 ： </p><p>　　課程設(shè)計時間： 2010-6-20 </p><p><b>　　專業(yè)課程設(shè)計任務(wù)書</b></p><p>　　說明：本表由指導(dǎo)教師填寫，由教研室主任審核后下達給選題學(xué)生，裝訂在設(shè)計（論文）首頁</p><p>

3、<b>　　1 需求分析</b></p><p>　　本課程設(shè)計內(nèi)容是解決迷宮問題。迷宮是一個矩形區(qū)域，有一個入口和出口。在迷宮內(nèi)部不能穿越墻或障礙。輸入一個m*n大小的方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。迷宮問題要求尋找一條從入口到出口的路徑。由于計算解迷宮時，通常用的是“窮舉求解”的方法，即從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前進：否則沿原路退回，換一個方向再繼

4、續(xù)探索；直至所有可能的通路都探索為止。為了保證在任何位置上都能沿遠路退回，顯然需要用一個后進先出的結(jié)構(gòu)來保存從入口到當(dāng)前位置的路徑。因此，在求迷宮通路的算法中要應(yīng)用“棧”的思想。</p><p>　　首先，在計算機中可以用0、1圖表示迷宮。所求路徑必須是簡單路徑，即在求得的路徑上不能重復(fù)出現(xiàn)同一通道。假設(shè)“當(dāng)前位置”指的是“在搜索過程中的某一時刻所在圖中某個位置”，則求迷宮中一條路徑的算法的基本思想是：若當(dāng)前位置

5、“可通”，則納入“當(dāng)前路徑”，并繼續(xù)朝“下一位置”探索，即切換“下一位置”為“當(dāng)前位置”，如此重復(fù)直至到達出口；若當(dāng)前位置“不可通”，則應(yīng)順著“來向”退回到“前一通道”，然后朝著除“來向”之外的其他方向繼續(xù)探索；若該通道塊的四周4個方向均“不可通”，則應(yīng)從“當(dāng)前路徑”上刪除該通道。所謂“下一位置”指的是當(dāng)前位置四周4個方向（東、南、西、北）“1”。假設(shè)以棧S記錄“當(dāng)前路徑”，則棧頂中存放的是“當(dāng)前路徑上最后一個通道”。由此，“納入路徑”

6、的操作即為“當(dāng)前位置入?！?；“從當(dāng)前路徑上刪除前一通道”的操作即為“出?！?。2 概要設(shè)計</p><p>　　1、主要設(shè)計思想若當(dāng)前位置可通，則納入當(dāng)前路徑，并繼續(xù)朝下一個位置探索，即切換下一位置為當(dāng)前位置，如此重復(fù)直至到達出口；若當(dāng)前位置不可通，則應(yīng)順著來向退回到前一通道塊，然后朝著除來向之外的其他方向繼續(xù)探索；若該通道塊的四周4個方塊均不可通，則應(yīng)從當(dāng)前路徑上刪除該通道塊.設(shè)以棧記錄當(dāng)前路徑，則棧頂中存放

7、的是當(dāng)前路徑上最后一個通道塊.由此，納入路徑的操作即為當(dāng)前位置入棧；從當(dāng)前路徑上刪除前一通道塊的才操作即為出棧.設(shè)頂當(dāng)前位置的初值為入口位置；Do{若當(dāng)前位置可通，則{ 將當(dāng)前位置插入棧頂； //納入通路若該位置是出口位置，則結(jié)束； //求得路徑存放在棧中否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；}否則，若棧不空切棧頂位置尚有其他方向未經(jīng)探索，則設(shè)定新的當(dāng)前位置為沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；若棧不空

8、但棧頂位置的四周均不可通；則{ 刪去棧頂位置； //從路徑中刪除該通道塊若棧不空，則重新測試新的棧頂位置，直至找到一個可通的相鄰塊或出棧至棧空</p><p>　　2、數(shù)據(jù)結(jié)構(gòu)設(shè)計考慮</p><p>　　1) 創(chuàng)建一個Int類型的二維數(shù)組Maze(i,j),用來存放0和1 ；創(chuàng)建一個堆棧，用來存儲當(dāng)前路徑2) 創(chuàng)造一個棧包括（*top表示棧頂，*base表示?；?，stackSi

9、ze表示棧容量）堆棧中每個空間包括（ord表示當(dāng)前位置在路徑上的序號，seat表示當(dāng)前坐標(biāo)，di表示往下一坐標(biāo)的方向）當(dāng)前坐標(biāo)包括（r表示行，c表示列）</p><p>　　3、主要采取三大模塊：主程序模塊、棧模塊和迷宮模塊</p><p>　　棧模塊：實現(xiàn)迷宮數(shù)據(jù)的抽象化和對迷宮數(shù)據(jù)的處理；迷宮模塊：實現(xiàn)迷宮數(shù)據(jù)抽象類型；主程序模塊：初始化迷宮模塊。4、邏輯結(jié)構(gòu)存儲結(jié)構(gòu)a. 邏

10、輯結(jié)構(gòu)：創(chuàng)建一個堆棧，含有（頭指針 top,棧深stackSize）堆棧中每個結(jié)點含有（指針next，行r, 列c）b. 存儲結(jié)構(gòu)：</p><p>　　堆棧結(jié)構(gòu)：坐標(biāo)結(jié)構(gòu)：定義：#define MAXNUM 100/* 棧中最大元素個數(shù) */#define N 11 /*地圖的第一維長度*/#include #include typedef struct {int x;/* 行下標(biāo) */

11、int y;/* 列下標(biāo) */int d;/* 運動方向 */} DataType;struct SeqStack { /* 順序棧類型定義 */int top; /* 指示棧頂位置 */DataType s[MAXNUM];}</p><p><b>　　3 運行環(huán)境</b></p><p>　　Microsoft Visual C++6.0：</

12、p><p>　　Visual C++6.0不僅是一個C++編譯器，而且是一個基于Windows操作系統(tǒng)的可視化集成開發(fā)環(huán)境（integrated development environment,IDE）。Visual C++6.0由許多組件組成，包括編輯器、調(diào)試器以及程序向?qū)ppWizard、類向?qū)lass Wizard等開發(fā)工具。 這些組件通過一個名為Developer Studio的組件集成為和諧的開發(fā)環(huán)境。

13、</p><p>　　4 開發(fā)工具和編程語言</p><p><b>　　編程語言為 C語言</b></p><p><b>　　5 詳細設(shè)計</b></p><p>　　#include <stdio.h>#include <malloc.h>#define STACK

14、_INIT_SIZE 1000int n=-1;int sumN=0;</p><p>　　一、棧模塊struct Stack{int TheOriginali[STACK_INIT_SIZE];//保存進棧元素的坐標(biāo)i.int TheOriginalj[STACK_INIT_SIZE];//保存進棧元素的坐標(biāo)j.int top;int base;};void initStack(stru

15、ct Stack *p){p->top=p->base=0;}//初始化.Push(struct Stack *p,int i,int j){sumN=sumN+1;n=n+1;p->top=p->top+1;p->TheOriginali[n]=i;p->TheOriginalj[n]=j;}//進棧.Pop(struct Stack *p,int readij[1])

16、{sumN=sumN+1;n=n-1;p->top=p->top-1;readij[0]=p->TheOriginali[n];readij[1]=p->TheOriginalj[n];}//出棧并讀出前一步的坐標(biāo).</p><p>　　二、迷宮模塊initMaze(int Maze[9][8])//建迷宮.{int i;for (i=0;i<=8;i++) {

17、Maze[0][i]=1;}for (i=0;i<=9;i++) {Maze[i][0]=1;}for (i=0;i<=8;i++) {Maze[9][i]=1;}for (i=0;i<=9;i++) {Maze[i][8]=1;}Maze[1][1]=0;Maze[1][2]=0;Maze[1][3]=1;Maze[1][4]=0;Maze[1][5]=0;Maze[1][6]=0;Maze[1][7]

18、=1;Maze[2][1]=1;Maze[2][2]=0;Maze[2][3]=1;Maze[2][4]=0;Maze[2][5]=0;Maze[2][6]=0;Maze[2][7]=0;Maze[3][1]=0;Maze[3][2]=0;Maze[3][3]=0;Maze[3][4]=0;Maze[3][5]=1;Maze[3][6]=1;Maze[3][7]=1;Maze[4][1]=1;Maze[4][2]=0;Maze[4

19、][</p><p>　　三、主程序模塊main(){struct Stack *p;struct Stack S;int Maze[9][8];int m,n,data1[1],data2[1];int Entrancei,Entrancej;int Exportsi,Exportsj;int sum=0;p=&S;initMaze(Maze);printf("迷宮圖(

20、1代表墻不通的意思,0代表路)\n");printf("************************************************\n"); for(m=0;m<=9;m++){for(n=0;n<=8;n++){printf("%4d",Maze[m][n]);sum++; if(sum%9==0) printf("

21、\n");}}printf("************************************************\n");//打印迷宮圖.printf("請輸入入口坐標(biāo):");scanf("%d",&data1[0]);scanf</p><p>　　在這個問題中主要運用了棧的各種基本操作，例如構(gòu)造空棧，判

22、斷棧是否為空，入棧操作，出棧操作等等。在迷宮中用‘1’表示墻，用‘0’表示通道；探索過的路徑用‘.’表示可通過，用‘#’表示死胡同。定義了一個二維字符數(shù)組來表示迷宮，將迷宮的入口位置的坐標(biāo)，在路徑中的序號及該位置走到下一個位置的方向放入棧中。在設(shè)計程序的過程中由于沒有注意到行列都是從0開始的，導(dǎo)致輸出時少了一行和一列，后來行數(shù)和列數(shù)都加1后就正確了。雖然這個程序運行后可以得到正確的實驗結(jié)果，但是有時還會顯示存在著一個警告（warning

23、 C4715: 'nextDir' : not all control paths return a value）就是說不是所有的控制路徑都能返回一個真值。我上網(wǎng)查了許多的資料還是不能解決這個問題，是做這個程序設(shè)計留下的一個遺憾。通過這次的程序設(shè)計我學(xué)習(xí)到了很多的東西，明白了做一個大的程序題要用到以前學(xué)到過的很多知識，就說我的程序用的是棧的知識，還用了Switch語句和for語句這兩個循環(huán)語句，用了二維字符數(shù)組的知識。迷

24、宮問題還有許多其他的方法來解決，例如順序表，深度優(yōu)先遍歷，廣度優(yōu)先遍歷等。</p><p><b>　　7 測試結(jié)果</b></p><p>　　任意輸入入口坐標(biāo)和出口坐標(biāo)，將會得到一條路徑或者是找不到路徑。</p><p>　　例如輸入入口坐標(biāo)2、3，出口坐標(biāo)4、6，在坐標(biāo)2、3和4、6間便會得到一條路徑。如圖1 </p>&

25、lt;p><b>　　圖1 存在路徑</b></p><p>　　輸入入口坐標(biāo)5、6，出口坐標(biāo)7、8,在這兩點間便沒有路徑。如圖2 </p><p><b>　　圖2 不存在路徑</b></p><p><b>　　參考文獻</b></p><p>　　[1].《數(shù)據(jù)結(jié)

26、構(gòu)》，嚴蔚敏，吳偉民，清華大學(xué)出版社，2002</p><p>　　[2]《C++程序設(shè)計教程（第二版）》，錢能，清華大學(xué)出版社，2005</p><p>　　[3]《C++實用教程（第一版）》，楊明軍、董亞卓、汪黎，人民郵電出版社，2002.</p><p>　　[4]《C程序設(shè)計（第二版）》，譚浩強，北京，清華大學(xué)出版社，1999</p><

27、p>　　[5]《Visual C++實用教程（第一版）》，張榮梅、梁曉林，冶金工業(yè)出版社，2004</p><p><b>　　心得體會</b></p><p>　　通過本次課程設(shè)計，增強了我對棧、數(shù)組等數(shù)據(jù)結(jié)構(gòu)的理解和應(yīng)用，了解了數(shù)學(xué)建模的基本方法。進一步掌握了棧、二維數(shù)組的定義、基本操作和存儲結(jié)構(gòu)，并掌握了棧、二維數(shù)組的C語言的實現(xiàn)。 在數(shù)據(jù)結(jié)構(gòu)的邏輯特性