迷宮問(wèn)題課程設(shè)計(jì)報(bào)告

1、<p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告</p><p>　　題 目： 迷宮問(wèn)題</p><p><b>　　一. 設(shè)計(jì)目的</b></p><p>　?。?）熟練掌握鏈棧的基本操作及應(yīng)用。</p><p>　?。?）利用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)實(shí)現(xiàn)一個(gè)求解迷宮的非遞歸程序。</p>&l

2、t;p><b>　　二. 設(shè)計(jì)內(nèi)容</b></p><p>　　計(jì)算機(jī)解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某一個(gè)方向進(jìn)行探索，若能走通，則繼續(xù)往前進(jìn)；否則沿著原路退回，換一個(gè)方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到則未能到達(dá)出口，則所設(shè)定的迷宮沒(méi)有通解。</p><p>　　可以二維數(shù)組存儲(chǔ)迷宮數(shù)據(jù)，通常設(shè)定入口點(diǎn)的

3、下標(biāo)為（1，1），出口點(diǎn)的下標(biāo)為（n,n）。為處理方便起見(jiàn)，可以迷宮的四周加一圈障礙。對(duì)于迷宮任一位置，均可約定有東、南、西、北四個(gè)方向可通。</p><p><b>　　三．概要設(shè)計(jì)</b></p><p>　　以一個(gè)m×n的長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對(duì)信任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒(méi)有通路的結(jié)論

4、。</p><p>　　首先實(shí)現(xiàn)一個(gè)鏈表作存儲(chǔ)結(jié)構(gòu)的棧類(lèi)型，然后編寫(xiě)一個(gè)求解迷宮的非遞歸程序。求得的通路以二元組（i,j）的形式輸出，其中：（i,j）指示迷宮中的一個(gè)坐標(biāo)。如：對(duì)于下列數(shù)據(jù)的迷宮，輸出的一條通路為：（1，1），（1，2），（2，2），（3，2），（3，1），……</p><p><b>　　1．功能模塊圖；</b></p><p&g

5、t;<b>　　數(shù)據(jù)結(jié)構(gòu)</b></p><p>　　int mark[N][M] = {0};/*初始化標(biāo)志位,0代表沒(méi)走過(guò),1代表走過(guò)*/ </p><p><b>　　/*方向*/ </b></p><p>　　typedef struct{ </p><p>　　short int vert

6、; </p><p>　　short int horiz; </p><p>　　}offsets; </p><p>　　offsets move[4] = {{0,1},{1,0},{0,-1},{-1,0}};/*北,東,南,西*/ </p><p><b>　　/*迷宮類(lèi)型*/ </b></p>&

7、lt;p>　　typedef struct { </p><p>　　short int row; </p><p>　　short int col; </p><p>　　short int dir; </p><p>　　}element; </p><p>　　element stack[MAX];<

8、/p><p><b>　　各個(gè)函數(shù)</b></p><p>　　element del(int* top)//出棧,top指向棧頂元素</p><p>　　void add(int* top,element item)/*入棧*/</p><p>　　void path(void)/*迷宮函數(shù)*/</p>&l

9、t;p>　　2．各個(gè)模塊詳細(xì)的功能描述。</p><p>　　出棧函數(shù)，top指向棧頂元素</p><p>　　入棧函數(shù)，將可走的路徑入棧</p><p><b>　　迷宮函數(shù)，進(jìn)行尋路</b></p><p><b>　　模塊層次調(diào)用關(guān)系圖</b></p><p>&

10、lt;b>　　四．詳細(xì)設(shè)計(jì)</b></p><p>　　while(top > -1 && !found) </p><p><b>　　{ </b></p><p>　　position= del(&top); /*將棧頂元素取出,*/ </p><p>　　row =

11、 position.row; /*利用中間變量row,col,dir等候判斷*/ </p><p>　　col = position.col; </p><p>　　dir = position.dir; </p><p>　　while(dir < 4 && !found) </p><p>&l

12、t;b>　　{ </b></p><p>　　next_row = row + move[dir].vert; </p><p>　　next_col = col + move[dir].horiz; </p><p>　　if(row == 9&& col == 8) //判斷是否找到終點(diǎn)</p><p>

13、　　found = 1; </p><p>　　else if(!maze[next_row][next_col] && !mark[next_row][next_col])/*判斷下一步可走并且沒(méi)走過(guò),則入棧*/ </p><p><b>　　{ </b></p><p>　　mark[next_row][next_col]

14、= 1; </p><p>　　position.row = row; </p><p>　　position.col = col; </p><p>　　position.dir = ++dir; </p><p>　　add(&top,position);/*合理則入棧*/ </p><p>　　row =

15、 next_row;/*繼續(xù)向下走*/ </p><p>　　col = next_col;</p><p><b>　　dir = 0; </b></p><p><b>　　} </b></p><p><b>　　else </b></p><p>

16、;　　dir++;/*dir<4時(shí),改變方向*/</p><p>　　起點(diǎn)路徑入棧，判斷棧是否滿了，并且是否找到出口，將棧頂元素去除，利用中間變量row,col,dir等候判斷，首先判斷是否找到終點(diǎn)，選擇北,東,南,西四個(gè)方向，offsets move[4] = {{0,1},{1,0},{0,-1},{-1,0}};，運(yùn)用這個(gè)轉(zhuǎn)換方向，判斷下一步可走并且沒(méi)走過(guò),則入棧，可走的話，標(biāo)志數(shù)組標(biāo)志為1，合理可走

17、則入棧，繼續(xù)往下走，不合理則dir++，進(jìn)行下次判斷。四個(gè)方向都走不通的話，棧頂元素出棧，繼續(xù)進(jìn)行下面的判斷，直到找到終點(diǎn)或者走不通。</p><p>　　找到終點(diǎn)后，倒序打印棧里的元素，就是路徑，并保存。</p><p>　　五．測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果</p><p>　　1．正常測(cè)試數(shù)據(jù)和運(yùn)行結(jié)果</p><p>　　int maze[N][

18、M] =</p><p>　　{ {1,1,1,1,1,1,1,1,1,1},</p><p>　　{1,0,0,1,0,0,0,1,0,1},</p><p>　　{1,0,0,1,0,0,0,1,0,1},</p><p>　　{1,0,0,0,0,1,1,0,1,1},</p><p>　　{1,0,1,1,1

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

20、1,0,0,0,0,0,0,1},</p><p>　　{1,1,1,1,1,1,1,1,1,1},</p><p>　　};/*初始化迷宮*/</p><p>　　2．異常測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果</p><p>　　int maze[N][M] =</p><p>　　{ {1,1,1,1,1,1,1,1,1,1},&

21、lt;/p><p>　　{1,0,0,1,0,0,0,1,0,1},</p><p>　　{1,0,0,1,0,0,0,1,0,1},</p><p>　　{1,0,0,0,0,1,1,0,1,1},</p><p>　　{1,0,1,1,1,0,0,1,0,1},</p><p>　　{1,0,0,0,1,0,0,0,0

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

23、1,1,1,1},</p><p>　　};/*初始化迷宮*/</p><p>　　六．調(diào)試情況，設(shè)計(jì)技巧及體會(huì)</p><p>　　調(diào)試比較順利，幾乎沒(méi)有出現(xiàn)什么重大問(wèn)題，在和同學(xué)的討論之后，改進(jìn)了算法。</p><p><b>　　1．改進(jìn)方案</b></p><p>　　在對(duì)文件的存儲(chǔ)方面，

24、有一些不足，存儲(chǔ)出來(lái)的東西，也只是一些數(shù)字，不能很好地讀取。</p><p>　　在對(duì)迷宮的生成方面，也有一些不足，只是能簡(jiǎn)單地初始化迷宮。</p><p><b>　　2．體會(huì)</b></p><p>　　剛開(kāi)始主要是在尋找路徑那里遇到了很多問(wèn)題，起初我用一個(gè)棧來(lái)比較符合通路的坐標(biāo)，實(shí)現(xiàn)起來(lái)很費(fèi)力。在返回值進(jìn)出棧時(shí)又碰到麻煩，就是top=to

25、p->next和return top->data這兩個(gè)地方，有時(shí)沒(méi)出錯(cuò)了但就是不能運(yùn)行出結(jié)果。改了很久也糾正不過(guò)來(lái)，在同學(xué)給的建議下，position.dir = ++dir;，實(shí)現(xiàn)了。。</p><p>　　在輸出路徑時(shí)，怎么標(biāo)記當(dāng)前位置的四個(gè)方向也是一個(gè)難題。我就在考慮怎么指向才是正確的，通過(guò)不斷實(shí)踐，認(rèn)為用路徑出棧時(shí)已出棧的坐標(biāo)和棧頂值的差值可以正確的確定路徑的方向，把它倒退回去看就可以了。&l

26、t;/p><p>　　對(duì)棧的理解，也有了一定的加深，遺憾的是，沒(méi)有寫(xiě)其他兩個(gè)程序，有空一定把它們完成要能很好的掌握編程僅僅通過(guò)幾個(gè)簡(jiǎn)單的程序的編寫(xiě)是無(wú)法達(dá)成的更需要大量積和深入有可能就從這個(gè)迷宮的問(wèn)題來(lái)說(shuō)在搜索的算法來(lái)解決兩點(diǎn)間最短路徑問(wèn)題在程序的編寫(xiě)中也不能一味得向已有的程序進(jìn)行模仿而要自己去摸索去尋求最好的解決方式只有帶著問(wèn)題去反復(fù)進(jìn)行實(shí)踐才能更熟練的掌握和運(yùn)用當(dāng)對(duì)現(xiàn)有的程序也要多去接觸因?yàn)橛行┏绦蚴俏覀儫o(wú)法在短