數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
上學(xué)時(shí)沒學(xué)過數(shù)據(jù)結(jié)構(gòu)和算法，于是現(xiàn)在有機(jī)會(huì)就自學(xué)。下面是我最近在等待進(jìn)入項(xiàng)目組期間，花了1小時(shí)學(xué)習(xí)了一下迷宮問題。
一．需求設(shè)計(jì)：以一個(gè)m*m 的方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口的通道，或得出沒有通路的結(jié)論。
二．概要設(shè)計(jì)：
存儲(chǔ)結(jié)構(gòu)：
采用了數(shù)組以及結(jié)構(gòu)體來存儲(chǔ)數(shù)據(jù)，在探索迷宮的過程中用到的棧，屬于順序存儲(chǔ)結(jié)構(gòu)。
/*八個(gè)方向的數(shù)組表示形式*/
int move[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1, 0},{-1, 1}};
/*用結(jié)構(gòu)體表示位置*/
struct position
{int x,y;};
position stack[m*m+1];
基本算法：
走迷宮的過程可以模擬為一個(gè)搜索的過程：每到一處，總讓它按東、東南、南、西南、西、西北、北、東北8個(gè)方向順序試探下一個(gè)位置；如果某方向可以通過，并且不曾到達(dá)，則前進(jìn)一步，在新位置上繼續(xù)進(jìn)行搜索；如果8個(gè)方向都走不通或曾經(jīng)到達(dá)過，則退回一步，在原來的位置上繼續(xù)試探下一位置。
每前進(jìn)或后退一步，都要進(jìn)行判斷：若前進(jìn)到了出口處，則說明找到了一條通路；若退回到了入口處，則說明不存在通路。
用一個(gè)字符類型的二維數(shù)組表示迷宮，數(shù)組中每個(gè)元素取值“0”（表示通路）或“1”（表示墻壁）。迷宮的入口點(diǎn)在位置（1，1）處，出口點(diǎn)在位置（m,m）處。設(shè)計(jì)一個(gè)模擬走迷宮的算法，為其尋找一條從入口點(diǎn)到出口點(diǎn)的通路。
二維數(shù)組的第0行、第m+1行、第0列、第m+1列元素全置成“1”，表示迷宮的邊界；第1行第1列元素和第m行第m列元素置成“0”，表示迷宮的入口和出口；其余元素值用隨機(jī)函數(shù)產(chǎn)生。
假設(shè)當(dāng)前所在位置是（x,y）。沿某個(gè)方向前進(jìn)一步，它可能到達(dá)的位置最多有8個(gè)。
如果用二維數(shù)組move記錄8個(gè)方向上行下標(biāo)增量和列下標(biāo)增量，則沿第i個(gè)方向前進(jìn)一步，可能到達(dá)的新位置坐標(biāo)可利用move數(shù)組確定：
x=x+move[i][0]
y=y+move[i][1]
從迷宮的入口位置開始，沿圖示方向順序依次進(jìn)行搜索。在搜索過程中，每前進(jìn)一步，在所到位置處做標(biāo)記“”（表示這個(gè)位置在通路上），并將該位置的坐標(biāo)壓入棧中。每次后退的時(shí)候，先將當(dāng)前所在位置處的通路標(biāo)記“”改成死路標(biāo)記“×”（表示這個(gè)位置曾到達(dá)過但走不通，以后不要重復(fù)進(jìn)入），然后將該位置的坐標(biāo)從棧頂彈出。搜索到出口位置時(shí)，數(shù)組中那些值為“”的元素形成一條通路。
【數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)】相關(guān)文章：
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)心得體會(huì)08-23
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)心得體會(huì)09-05
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)心得體會(huì)10篇03-11
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)心得體會(huì)(10篇)03-11
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)心得體會(huì)（精選6篇）07-10
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)心得體會(huì)7篇03-20
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)心得體會(huì) 13篇02-22
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)心得體會(huì)11篇02-22