數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告迷宮算法

1、 課課 程程 設(shè)設(shè) 計(jì)計(jì) 報(bào)報(bào) 告告 課程設(shè)計(jì)名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 課程設(shè)計(jì)題目：迷宮算法 院（系）：計(jì)算機(jī)學(xué)院 專(zhuān) 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 班 級(jí)：04010103 學(xué) 號(hào)：2010040101107 目目 錄錄 1 1 課程設(shè)計(jì)介紹課程設(shè)計(jì)介紹.1 1.1 課程設(shè)計(jì)內(nèi)容.1 1.2 課程設(shè)計(jì)要求.1 2 2 課程設(shè)計(jì)原理課程設(shè)計(jì)原理.2 2.1 課設(shè)題目粗略分析.2 2.2 原理圖介紹.3 2.2.1 功能模塊圖.3 2.2.2 流程圖分析.3 3 數(shù)據(jù)結(jié)構(gòu)分析數(shù)據(jù)結(jié)構(gòu)分析.9 3.1 存儲(chǔ)結(jié)構(gòu).9 3.2 算法描述.9 4 4 調(diào)試與分析調(diào)試與分析.11 4.1 調(diào)試過(guò)程

2、.11 4.2 程序執(zhí)行過(guò)程.11 參考文獻(xiàn)參考文獻(xiàn).13 附附 錄（關(guān)鍵部分程序清單）錄（關(guān)鍵部分程序清單）.14 1 1 課程設(shè)計(jì)介紹課程設(shè)計(jì)介紹 1.11.1 課程設(shè)計(jì)內(nèi)容課程設(shè)計(jì)內(nèi)容 編寫(xiě)算法能夠生成迷宮，并且求解迷宮路徑（求解出任意一條到出口的路徑 即可）： 1. 迷宮用上下左右四種走法； 2. 迷宮的大小和復(fù)雜程度可以由用戶定義； 3. 入口出口也由用戶自己選擇。 1.21.2 課程設(shè)計(jì)要求課程設(shè)計(jì)要求 1.不必演示求解過(guò)程，只需要輸出迷宮求解的路徑； 2.參考相應(yīng)資料完成課設(shè)。 2 2 課程設(shè)計(jì)原理課程設(shè)計(jì)原理 2.12.1 課設(shè)題目粗略分析課設(shè)題目粗略分析 根據(jù)課設(shè)題目要求，擬

3、將整體程序分為四大模塊。以下是四個(gè)模塊的大體分 析： 1 建立迷宮：要建立迷宮首先就要建立存儲(chǔ)結(jié)構(gòu)，這里我用棧的方式建立的。 根據(jù)用戶輸入的迷宮的大小（我設(shè)置的最大值為 25 可以根據(jù)要求調(diào)解） ； 2 設(shè)置迷宮：這里將 0 設(shè)置圍墻，1 是可以通過(guò)的路徑，-1 是不可以通過(guò)路 徑，外墻是以設(shè)計(jì)好的，內(nèi)墻需要用戶來(lái)設(shè)置，障礙的難度可由用戶自行定 義； 3 尋找路徑：尋找路徑我設(shè)置了四個(gè)方向0,1,1,0,0,-1,-1,0移動(dòng)方向,依 次為東南西北，首先向東走，若不成功則轉(zhuǎn)換方向，成功則繼續(xù)前進(jìn)，將走 過(guò)的路徑進(jìn)行標(biāo)記，然后存入棧中； 4 輸出結(jié)果：輸出的結(jié)果分為兩種，一種是用戶建立的迷宮主要

4、是讓用戶檢 查是否符合要求，第二種輸出的是尋找完后的路徑，路徑用 1 2 3 4來(lái) 表示。 2.22.2 原理圖介紹原理圖介紹 2.2.12.2.1 功能模塊圖功能模塊圖 迷宮求解 建 立 迷 宮 設(shè) 置 迷 宮 尋 找 路 徑 輸 出 結(jié) 果 圖 2.1 功能模塊圖 如圖 2.1 所示 2.2.2 流程圖分析流程圖分析 1.建立迷宮 開(kāi)始 構(gòu)建一個(gè)空棧initstack(sqstack *s) 判斷棧是否為空 n 建立迷宮,將所有的周邊值設(shè)為 mx1y1=0; 結(jié)束 輸入迷宮的行數(shù)x和列數(shù) y y 圖 2.2 建立迷宮函數(shù)流程圖 2. 設(shè)置迷宮 圖 2.3 設(shè)置迷宮函數(shù)流程圖 設(shè)置迷宮內(nèi)部，

5、將內(nèi)墻設(shè)為mx1y1=0， 開(kāi)始 結(jié)束 輸入迷宮的內(nèi)墻數(shù)j,和具體位置x1 y1 輸入迷宮的指點(diǎn)和終點(diǎn) 函數(shù)輸出已建 立好的迷宮供用戶檢查 3. 尋找路徑 可以通過(guò)footprint(curpos); / 留下足跡，入棧push(足跡 加一curstep+; 繼續(xù)進(jìn)行判斷 輸入迷宮的起點(diǎn)和終點(diǎn)的坐標(biāo) 輸出此通路 輸入i,j 結(jié)束 開(kāi)始 輸出迷宮 圖 2.5 輸出結(jié)果函數(shù)流程圖 3 數(shù)據(jù)結(jié)構(gòu)分析數(shù)據(jù)結(jié)構(gòu)分析 3.13.1 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) 定義一個(gè)整型數(shù)組 postype 用來(lái)存儲(chǔ)行列的值。 typedef struct / 棧的元素類(lèi)型 int ord; / 通道塊在路徑上的序號(hào) postyp

6、e seat; / 通道塊在迷宮中的坐標(biāo)位置 int di; / 從此通道塊走向下一通道塊的方向(03 表示東北) selemtype; 棧的存儲(chǔ)結(jié)構(gòu)： #define stack_init_size 10/ 存儲(chǔ)空間初始分配量 #define stackincrement 2/ 存儲(chǔ)空間分配增量 / 棧的順序存儲(chǔ)表示 typedef struct sqstack selemtype *base;/ 在棧構(gòu)造之前和銷(xiāo)毀之后，base 的值為 null selemtype *top;/ 棧頂指針 int stacksize;/ 當(dāng)前已分配的存儲(chǔ)空間，以元素為單位 sqstack;/ 順序棧 3.

7、23.2 算法描述算法描述 1.棧的基本操作的算法，簡(jiǎn)單算法說(shuō)明如下： status initstack(sqstack *s) / 構(gòu)造一個(gè)空棧 s，為棧底分配一個(gè)指定大小的存儲(chǔ)空間 (*s).base = (selemtype *)malloc(stack_init_size*sizeof(selemtype); if( !(*s).base ) exit(0); (*s).top = (*s).base; / 棧底與棧頂相同表示一個(gè)空棧 (*s).stacksize = stack_init_size; return 1; status stackempty(sqstack s) / 若

8、棧 s 為空棧（棧頂與棧底相同的） ，則返回 1，否則返回 0。 if(s.top = s.base) return 1; else return 0; status push(sqstack *s, selemtype e) / 插入元素 e 為新的棧頂元素。 if(*s).top - (*s).base = (*s).stacksize) / 棧滿，追加存儲(chǔ)空間 (*s).base = (selemtype *)realloc(*s).base , (*s).stacksize + stackincrement) * sizeof(selemtype); if( !(*s).base )

9、exit(0); (*s).top = (*s).base+(*s).stacksize; (*s).stacksize += stackincrement; *(*s).top)+=e; return 1; status pop(sqstack *s,selemtype *e) / 若棧不空，則刪除 s 的棧頂元素，用 e 返回其值，并返回 1；否則返回 0。 if(*s).top = (*s).base) return 0; *e = *-(*s).top; return 1; 2.查找路徑的算法，簡(jiǎn)單算法說(shuō)明如下： status mazepath(postype start,postyp

10、e end) / 若迷宮 maze 中存在從入口 start 到出口 end 的通道，則求得一條 / 存放在棧中(從棧底到棧頂)，并返回 1；否則返回 0 initstack( curpos=start; curstep=1; do if(pass(curpos)/ 當(dāng)前位置可以通過(guò)，即是未曾走到過(guò)的通道塊 footprint(curpos); / 留下足跡 e =( curstep, curpos,1); push( / 入棧當(dāng)前位置及狀態(tài) if(curpos.x=end.x curpos=nextpos(curpos,e.di); else/ 當(dāng)前位置不能通過(guò) if(!stackempty

11、(s) pop( / 退棧到前一位置 curstep-; / 前一位置處于最后一個(gè)方向(北) while(e.di=3 pop( /留下不能通過(guò)的標(biāo)記(-1) , 退 回一步 if(e.di3) / 沒(méi)到最后一個(gè)方向(北) e.di+; push(/ 換下一個(gè)方向探索 curpos=nextpos(e.seat,e.di); / 設(shè)定當(dāng)前位置是該新方向 上的相鄰塊 while(!stackempty(s); return 0; 4 4 調(diào)試與分析調(diào)試與分析 4.14.1 調(diào)試過(guò)程調(diào)試過(guò)程 在調(diào)試程序是主要遇到一下幾類(lèi)問(wèn)題： 1. 選擇存儲(chǔ)結(jié)構(gòu)的問(wèn)題：剛接到課設(shè)題目的時(shí)候，我就在想用什么來(lái)實(shí)現(xiàn)

12、迷宮的存儲(chǔ)。用線性表還是數(shù)組，最后綜合考慮決定用棧和數(shù)組結(jié)合的方式來(lái)實(shí) 現(xiàn)，用數(shù)組來(lái)建立迷宮和輸出迷宮，用棧來(lái)查找路徑并將生成的路徑壓入到棧中， 因?yàn)闂Ｓ邢热牒蟪龅膬?yōu)點(diǎn)，所以比較容易實(shí)現(xiàn)。 2. 如何建立迷宮和怎么設(shè)置迷宮的問(wèn)題：首先迷宮要有一定的范圍怎么才 能讓迷宮有序的進(jìn)行，于是我將迷宮的外圍和障礙設(shè)置為 0，所有的可走路徑設(shè) 置為 1，這樣迷宮就清晰可見(jiàn)。 3. 如何去尋找路徑問(wèn)題 ：這是整個(gè)程序的核心。通過(guò)查找書(shū)籍得到了一個(gè) 算法：若當(dāng)前位置“可通” ，則納入當(dāng)前路徑，并繼續(xù)朝下一位置搜索，即切換 下一位置為當(dāng)前位置，如此重復(fù)到達(dá)出口；若不可通，就退回到前一通道，然后 繼續(xù)尋找其他方向

13、；若均不可通，則刪除此路徑。 4. 界面問(wèn)題：這里就是運(yùn)用了 switch(n)語(yǔ)句來(lái)實(shí)現(xiàn)的，這樣增加了程序的 實(shí)用性。 4.2 程序執(zhí)行過(guò)程程序執(zhí)行過(guò)程 系統(tǒng)使用說(shuō)明： 1出現(xiàn)界面后選擇 1，進(jìn)行迷宮大小的設(shè)計(jì)（這里設(shè)計(jì) 3*3 大小的）：如圖 4.1 所示 圖 4.1 2. 然后選擇 2，開(kāi)始設(shè)計(jì)迷宮的內(nèi)部：如圖 4.2 所示 圖 4.2 3.選擇 3，觀察設(shè)計(jì)的是否滿足你的要求：如圖 4.3 所示 圖 4.3 4.選擇 4，輸入迷宮的起點(diǎn)和終點(diǎn)：如圖 4.4 所示 圖 4.4 5.選擇 5，查看結(jié)果（路徑由 1.2.3.4.5 表示出來(lái)）：如圖 4.5 所示 圖 4.5 6選擇 0，退出

14、程序。 參考文獻(xiàn)參考文獻(xiàn) 1 嚴(yán)蔚敏，吳偉民. .數(shù)據(jù)結(jié)構(gòu)m.北京：清華大學(xué)出版社，2007. 2 胡圣榮, 周靄如, 羅穗萍.數(shù)據(jù)結(jié)構(gòu)教程與題解m.北京：清華大學(xué)出版社， 2011. 3 譚浩強(qiáng). .c 程序設(shè)計(jì)m.北京：清華大學(xué)出版社，2005. 4 袁平波.數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)m.合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社.2010. 5 殷人昆.數(shù)據(jù)結(jié)構(gòu)m.北京：清華大學(xué)出版社.2011. 6 寧正元.算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題精解和實(shí)驗(yàn)指導(dǎo)m.北京. 清華大學(xué)出版社. 2007. 7 陳媛.算法與數(shù)據(jù)結(jié)構(gòu).第 2 版m.北京. 清華大學(xué)出版社.2011. 附附 錄（關(guān)鍵部分程序清單）錄（關(guān)鍵部分程序清單） 程

15、序代碼程序代碼 #include #include #include #include / 迷宮坐標(biāo)位置類(lèi)型 typedef struct int x;/ 行值 int y;/ 列值 postype; #define maxlength 25 / 設(shè)迷宮的最大行列為 25 typedef int mazetypemaxlengthmaxlength; / 迷宮數(shù)組行列 typedef struct / 棧的元素類(lèi)型 int ord; / 通道塊在路徑上的序號(hào) postype seat; / 通道塊在迷宮中的坐標(biāo)位置 int di; / 從此通道塊走向下一通道塊的方向(03 表示東北) sele

16、mtype; / 全局變量 mazetype m; / 迷宮數(shù)組 int curstep=1; / 當(dāng)前足跡,初值為 1 #define stack_init_size 10/ 存儲(chǔ)空間初始分配量 #define stackincrement 2/ 存儲(chǔ)空間分配增量 / 棧的順序存儲(chǔ)表示 typedef struct sqstack selemtype *base;/ 在棧構(gòu)造之前和銷(xiāo)毀之后，base 的值為 null selemtype *top;/ 棧頂指針 int stacksize;/ 當(dāng)前已分配的存儲(chǔ)空間，以元素為單位 sqstack; / 順序棧 /構(gòu)造一個(gè)空棧 s int ini

17、tstack(sqstack *s) / 為棧底分配一個(gè)指定大小的存儲(chǔ)空間 (*s).base = (selemtype *)malloc(stack_init_size*sizeof(selemtype); if( !(*s).base ) exit(0); (*s).top = (*s).base;/ 棧底與棧頂相同表示一個(gè)空棧 (*s).stacksize = stack_init_size; return 1; / 若棧 s 為空棧（棧頂與棧底相同的） ，則返回 1，否則返回 0。 int stackempty(sqstack s) if(s.top = s.base) return

18、1; else return 0; /插入元素 e 為新的棧頂元素。 int push(sqstack *s, selemtype e) if(*s).top - (*s).base = (*s).stacksize) / 棧滿，追加存儲(chǔ)空間 (*s).base = (selemtype *)realloc(*s).base , (*s).stacksize + stackincrement) * sizeof(selemtype); if( !(*s).base ) exit(0); (*s).top = (*s).base+(*s).stacksize; (*s).stacksize +=

19、 stackincrement; *(*s).top)+=e; return 1; /若棧不空，則刪除 s 的棧頂元素，用 e 返回其值，并返回 1；否則返回 0。 int pop(sqstack *s,selemtype *e) if(*s).top = (*s).base) return 0; *e = *-(*s).top; / 這個(gè)等式的+ * 優(yōu)先級(jí)相同，但是它們的運(yùn)算方式，是自右向左 return 1; / 定義墻元素值為 0,可通過(guò)路徑為 1,不能通過(guò)路徑為-1,通過(guò)路徑為足跡 / 當(dāng)迷宮 m 的 b 點(diǎn)的序號(hào)為 1(可通過(guò)路徑)，return 1; 否則，return 0。 i

20、nt pass(postype b) if(mb.xb.y=1) return 1; else return 0; void footprint(postype a) / 使迷宮 m 的 a 點(diǎn)的序號(hào)變?yōu)樽阚E(curstep)，表示經(jīng)過(guò) ma.xa.y=curstep; / 根據(jù)當(dāng)前位置及移動(dòng)方向，返回下一位置 postype nextpos(postype c,int di) postype direc4=0,1,1,0,0,-1,-1,0; / 行增量,列增量 / 移動(dòng)方向,依次為東南西北 c.x+=direcdi.x; c.y+=direcdi.y; return c; / 使迷宮 m

21、的 b 點(diǎn)的序號(hào)變?yōu)?1(不能通過(guò)的路徑) void markprint(postype b) mb.xb.y=-1; / 若迷宮 maze 中存在從入口 start 到出口 end 的通道，則求得一條 / 存放在棧中(從棧底到棧頂)，并返回 1；否則返回 0 int mazepath(postype start,postype end) sqstack s; postype curpos; selemtype e; initstack( curpos=start; do if(pass(curpos) / 當(dāng)前位置可以通過(guò)，即是未曾走到過(guò)的通道塊 footprint(curpos); / 留

22、下足跡 e.ord=curstep; e.seat.x=curpos.x; e.seat.y=curpos.y; e.di=0; push( / 入棧當(dāng)前位置及狀態(tài) curstep+; / 足跡加 1 if(curpos.x=end.x curpos=nextpos(curpos,e.di); else / 當(dāng)前位置不能通過(guò) if(!stackempty(s) pop( / 退棧到前一位置 curstep-; while(e.di=3 / 留下不能通過(guò)的標(biāo)記(-1) pop( / 退回一步 curstep-; if(e.di3) / 沒(méi)到最后一個(gè)方向(北) e.di+; / 換下一個(gè)方向探索

23、push( curstep+;/ 設(shè)定當(dāng)前位置是該新方向上的相鄰塊 curpos=nextpos(e.seat,e.di); while(!stackempty(s); return 0; / 輸出迷宮的結(jié)構(gòu) void print(int x,int y) int i,j; for(i=0;ix;i+) for(j=0;jy;j+) printf(%3d,mij); printf(n); void main() postype begin,end; int i,j,x,y,x1,y1,n,k; do system(cls); /清屏函數(shù) printf( nnn); printf( 1 請(qǐng)輸入迷

24、宮的行數(shù),列數(shù)(包括外墻)n); printf( 2 請(qǐng)輸入迷宮內(nèi)墻單元數(shù)n); printf( 3 迷宮結(jié)構(gòu)如下n); printf( 4 輸入迷宮的起點(diǎn)和終點(diǎn)n); printf( 5 輸出結(jié)果n); printf( 0 退出n); printf(nn 請(qǐng)選擇 ); scanf(%d, switch(n) case 1: printf(請(qǐng)輸入迷宮的行數(shù),列數(shù)(包括外墻)：(空格隔開(kāi)); scanf(%d%d, for(i=0;ix;i+) / 定義周邊值為 0(同墻) m0i=0; / 迷宮上面行的周邊即上邊墻 mx-1i=0;/ 迷宮下面行的周邊即下邊墻 for(j=1;jy-1;j+) mj0=0; / 迷宮左邊列的周邊即左邊墻 mjy-1=0;/ 迷宮右邊列的周邊即右邊墻 for(i=1;ix-1;i+) for(j=1;jy-1;j+) mij=1; / 定義通道初值為 1 break; case 2: printf(請(qǐng)輸入迷宮內(nèi)墻單元數(shù)：); scanf(%d, printf(請(qǐng)依次輸入迷宮內(nèi)墻每個(gè)單元的行數(shù),列數(shù)：(空格隔開(kāi))n); for(i=1;i=j;i+) scanf(%d%d,