迷宮問題的求解數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)說(shuō)明書 迷宮問題求解學(xué)生姓名馬東學(xué)號(hào)1021024068班級(jí)信管103成績(jī)指導(dǎo)教師李婧數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院2012年3月2日數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)評(píng)閱書題 目迷宮問題求解學(xué)生姓名馬東學(xué)號(hào)1021024068指導(dǎo)教師評(píng)語(yǔ)及成績(jī)成績(jī)： 教師簽名： 年 月 日答辯教師評(píng)語(yǔ)及成績(jī)成績(jī)： 教師簽名： 年 月 日教研室意見總成績(jī)： 室主任簽名： 年 月 日注：指導(dǎo)教師成績(jī)60%，答辯成績(jī)40%，總成績(jī)合成后按五級(jí)制記入。課程設(shè)計(jì)任務(wù)書20112012學(xué)年第二學(xué)期專業(yè)： 信息管理與信息系統(tǒng) 學(xué)號(hào)： 1021024068 姓名： 馬東 課程設(shè)計(jì)名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 設(shè) 計(jì) 題 目： 迷宮問題

2、求解 完 成 期 限：自 2012 年 2 月 20 日至 2012 年 3 月 2 日共 2 周 設(shè)計(jì)依據(jù)、要求及主要內(nèi)容（可另加附頁(yè)）：設(shè)計(jì)要求:設(shè)計(jì)內(nèi)容：輸入一個(gè)任意大小的迷宮數(shù)據(jù)，設(shè)置入口、出口及障礙，借助棧結(jié)構(gòu)求解走出迷宮的路徑并輸出。邏輯設(shè)計(jì)：對(duì)問題描述中涉及的操作對(duì)象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設(shè)計(jì)的結(jié)果應(yīng)寫出每個(gè)抽象數(shù)據(jù)類型的定義（包括數(shù)據(jù)結(jié)構(gòu)的描述和每個(gè)基本操作的功能說(shuō)明），各個(gè)主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖；詳細(xì)設(shè)計(jì)：定義相應(yīng)的存儲(chǔ)結(jié)構(gòu)并寫出各函數(shù)的偽碼算法。在這個(gè)過程中，要綜合考慮系統(tǒng)功能，使得

3、系統(tǒng)結(jié)構(gòu)清晰、合理、簡(jiǎn)單和易于調(diào)試，抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說(shuō)明盡可能明確具體。詳細(xì)設(shè)計(jì)的結(jié)果是對(duì)數(shù)據(jù)結(jié)構(gòu)和基本操作做出進(jìn)一步的求精，寫出數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的類型定義，寫出函數(shù)形式的算法框架；程序編碼：把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語(yǔ)言程序。同時(shí)加入一些注解和斷言，使程序中邏輯概念清楚；程序調(diào)試與測(cè)試：采用自底向上，分模塊進(jìn)行，即先調(diào)試低層函數(shù)。能夠熟練掌握調(diào)試工具的各種功能，設(shè)計(jì)測(cè)試數(shù)據(jù)確定疑點(diǎn)，通過修改程序來(lái)證實(shí)它或繞過它。調(diào)試正確后，認(rèn)真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果；結(jié)果分析：程序運(yùn)行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及

4、其輸出結(jié)果。算法的時(shí)間、空間復(fù)雜性分析；編寫課程設(shè)計(jì)報(bào)告；以上要求中前三個(gè)階段的任務(wù)完成后，先將設(shè)計(jì)說(shuō)明數(shù)的草稿交指導(dǎo)老師面審，審查合格后方可進(jìn)入后續(xù)階段的工作。設(shè)計(jì)工作結(jié)束后，經(jīng)指導(dǎo)老師驗(yàn)收合格后將設(shè)計(jì)說(shuō)明書打印裝訂，并進(jìn)行答辯。指導(dǎo)教師（簽字）： 教研室主任（簽字）： 批準(zhǔn)日期： 年 月 日摘 要由計(jì)算機(jī)解迷宮時(shí)，通常用的是窮舉求解的方法，即從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路反回，換一個(gè)方向繼續(xù)探索，直至所有可行的通路都探索到為止。為了保證在任何位置上都能沿原路返回，顯然需要用一個(gè)后進(jìn)先出的結(jié)構(gòu)來(lái)保存從入口到當(dāng)前位置的路徑。顯然要用到棧。關(guān)鍵詞：迷宮；窮舉；

5、棧； 目 錄1 課題描述················································

6、··························12 問題分析和任務(wù)定義······················

7、········································23 數(shù)據(jù)結(jié)構(gòu)分析········

8、83;·················································

9、83;········· 33.1存儲(chǔ)結(jié)構(gòu)·······································

10、·································33.2算法描述···············

11、3;·················································

12、3;······34 流程圖 ··········································

13、83;······················65 程序編碼··························&#

14、183;··············································106 程序測(cè)試與運(yùn)行過程·&

15、#183;·················································&

16、#183;·········19 6.1程序調(diào)試······································

17、83;·······························19 6.2程序運(yùn)行過程················

18、83;·················································197

19、 結(jié)果分析·················································&

20、#183;·······················25 總結(jié)·························&#

21、183;·················································&#

22、183;·26 參考文獻(xiàn)···············································&

23、#183;·························271 課題描述 本課程設(shè)計(jì)是解決迷宮求解的問題，從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個(gè)方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，顯然需要用一個(gè)后進(jìn)先出的結(jié)構(gòu)來(lái)保存從入口到當(dāng)前位置的路徑。因此，在求迷宮通路的

24、算法中要應(yīng)用“?！钡乃枷爰僭O(shè)“當(dāng)前位置”指的是“在搜索過程中的某一時(shí)刻所在圖中某個(gè)方塊位置”，則求迷宮中一條路徑的算法的基本思想是：若當(dāng)前位置“可通”，則納入“當(dāng)前路徑”，并繼續(xù)朝“下一位置”探索，即切換“下一位置”為“當(dāng)前位置”，如此重復(fù)直至到達(dá)出口；若當(dāng)前位置“不可通”，則應(yīng)順著“來(lái)向”退回到“前一通道塊”，然后朝著除“來(lái)向”之外的其他方向繼續(xù)探索；若該通道塊的四周4個(gè)方塊均“不可通”，則應(yīng)從“當(dāng)前路徑”上刪除該通道塊。所謂“下一位置”指的是當(dāng)前位置四周4個(gè)方向（東、南、西、北）上相鄰的方塊。假設(shè)以棧S記錄“當(dāng)前路徑”，則棧頂中存放的是“當(dāng)前路徑上最后一個(gè)通道塊”。由此，“納入路徑”的操作

25、即為“當(dāng)前位置入棧”；“從當(dāng)前路徑上刪除前一通道塊”的操作即為“出?！?。2 問題分析和任務(wù)定義根據(jù)課設(shè)題目要求，擬將整體程序分為四大模塊。以下是四個(gè)模塊的大體分析： 1 建立迷宮：要建立迷宮首先就要建立存儲(chǔ)結(jié)構(gòu)，這里我用數(shù)組的方式建立的。根據(jù)用戶輸入的迷宮的大?。ㄎ以O(shè)置的最大值為25可以根據(jù)要求調(diào)解）； 2 設(shè)置迷宮：這里將0設(shè)置圍墻，1是可以通過的路徑，-1是不可以通過路徑，外墻是以設(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)，將走過的路徑

26、進(jìn)行標(biāo)記，然后存入棧中； 4 輸出結(jié)果：輸出的結(jié)果分為兩種，一種是用戶建立的迷宮主要是讓用戶檢查是否符合要求，第二種輸出的是尋找完后的路徑，路徑用1 2 3 4···來(lái)表示。3 數(shù)據(jù)結(jié)構(gòu)分析3.1存儲(chǔ)結(jié)構(gòu)定義一個(gè)整型數(shù)組PosType用來(lái)存儲(chǔ)行列的值。typedef struct / 棧的元素類型 int ord; / 通道塊在路徑上的序號(hào) PosType seat; / 通道塊在迷宮中的坐標(biāo)位置 int di; / 從此通道塊走向下一通道塊的方向(03表示東北) SElemType; 棧的存儲(chǔ)結(jié)構(gòu)：#define STACK_INIT_SIZE 10/ 存儲(chǔ)空間

27、初始分配量 #define STACKINCREMENT 2/ 存儲(chǔ)空間分配增量 / 棧的順序存儲(chǔ)表示 typedef struct SqStackSElemType *base;/ 在棧構(gòu)造之前和銷毀之后，base的值為NULL SElemType *top;/ 棧頂指針 int stacksize;/ 當(dāng)前已分配的存儲(chǔ)空間，以元素為單位 SqStack;/ 順序棧 3.2算法描述 1.棧的基本操作的算法，簡(jiǎn)單算法說(shuō)明如下：Status InitStack(SqStack *S)/構(gòu)造一個(gè)空棧S，為棧底分配一個(gè)指定大小的存儲(chǔ)空間(*S).base = (SElemType *)malloc(

28、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) / 若棧S為空棧（棧頂與棧底相同的），則返回1，否則返回0。if(S.top = S.base) return 1;else return 0;Status Push(SqStack *S, SElemType e)/插入元素e為新的棧頂元素。if(*S).top -

29、 (*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 += STACKINCREMENT;*(*S).top)+=e;return 1;Status Pop(SqStack *S,SElemType *e)/若棧不空，

30、則刪除S的棧頂元素，用e返回其值，并返回1；否則返回0。if(*S).top = (*S).base) return 0;*e = *-(*S).top;return 1;1. 查找路徑的算法，簡(jiǎn)單算法說(shuō)明如下：Status MazePath(PosType start,PosType end) / 若迷宮maze中存在從入口start到出口end的通道，則求得一條 / 存放在棧中(從棧底到棧頂)，并返回1；否則返回0 InitStack(&S); curpos=start; curstep=1;doif(Pass(curpos)/ 當(dāng)前位置可以通過，即是未曾走到過的通道塊 FootP

31、rint(curpos); / 留下足跡 e =( curstep, curpos,1);Push(&S,e); / 入棧當(dāng)前位置及狀態(tài) if(curpos.x=end.x&&curpos.y=end.y) / 到達(dá)終點(diǎn)(出口) return 1;curpos=NextPos(curpos,e.di);else/ 當(dāng)前位置不能通過 if(!StackEmpty(S)Pop(&S,&e); / 退棧到前一位置 curstep-; / 前一位置處于最后一個(gè)方向(北) while(e.di=3&&!StackEmpty(S)MarkPrint(

32、e.seat); Pop(&S,&e); /留下不能通過的標(biāo)記(-1) , 退回一步if(e.di<3) / 沒到最后一個(gè)方向(北) e.di+; Push(&S,e);/ 換下一個(gè)方向探索curpos=NextPos(e.seat,e.di); / 設(shè)定當(dāng)前位置是該新方向上的相鄰塊while(!StackEmpty(S);return 0; 4. 流程圖 4.1建立迷宮 構(gòu)造空棧函數(shù)并判斷，若是則建立迷宮，否則返回并構(gòu)造空棧。開始 輸入迷宮的行數(shù)x和列數(shù)y 構(gòu)建一個(gè)空棧InitStack（SqStack *S） n判斷棧是否為空 建立迷宮，將所有的周邊值設(shè)置為

33、mx1y1=0 y 結(jié)束 圖3.1建立迷宮函數(shù)流程圖 4.2設(shè)置迷宮 先設(shè)置迷宮障礙和起點(diǎn)與終點(diǎn)坐標(biāo)，障礙設(shè)為0，用printf函數(shù)輸出開始輸入迷宮的內(nèi)墻數(shù)j和具體位置x1 y1輸入迷宮的起點(diǎn)和終點(diǎn)&end.x,&end.y 設(shè)置迷宮內(nèi)部，將內(nèi)墻設(shè)為mx1y1=0可由Print（x,y）;函數(shù)輸出已建立好的迷宮供用戶檢查結(jié)束 圖3.2設(shè)置迷宮函數(shù)的流程圖4.3尋找路徑 先輸入起點(diǎn)與終點(diǎn)坐標(biāo)。判斷，若能通過則留下足跡，入棧，足跡加一并繼續(xù)判斷，若不能，則換方向繼續(xù)判斷。開始輸入迷宮的起點(diǎn)和終點(diǎn)坐標(biāo)&begin x/y,&end x/yif(MazePath(bei

34、gn,end)求的路徑（判斷） N可以通過Footprint(curpos);/留下足跡，入棧Push（&S,e），足跡加一curstep+，繼續(xù)進(jìn)行判斷N不可通過，換個(gè)方向繼續(xù)判斷是否到終點(diǎn) Y判斷是否有路徑 Y找到路徑輸出迷宮找不到路徑 N 結(jié)束 圖3.3尋找路徑函數(shù)流程圖4.4輸出結(jié)果 開始 輸入i，j Print(x,y);輸出此通路 輸出迷宮 結(jié)束 圖3.4輸出結(jié)果流程圖5 程序編碼#include<stdio.h>#include<stdlib.h>#include<string.h>#include<malloc.h>/ 迷

35、宮坐標(biāo)位置類型typedef struct int x;/ 行值 int y;/ 列值 PosType;#define MAXLENGTH 25 / 設(shè)迷宮的最大行列為25 typedef int MazeTypeMAXLENGTHMAXLENGTH; / 迷宮數(shù)組行列 typedef struct / 棧的元素類型 int ord; / 通道塊在路徑上的序號(hào) PosType seat; / 通道塊在迷宮中的坐標(biāo)位置 int di; / 從此通道塊走向下一通道塊的方向(03表示東北) SElemType;/ 全局變量 MazeType m; / 迷宮數(shù)組 int curstep=1; / 當(dāng)前

36、足跡,初值為1 #define STACK_INIT_SIZE 10/ 存儲(chǔ)空間初始分配量 #define STACKINCREMENT 2/ 存儲(chǔ)空間分配增量 / 棧的順序存儲(chǔ)表示 typedef struct SqStackSElemType *base;/ 在棧構(gòu)造之前和銷毀之后，base的值為NULL SElemType *top;/ 棧頂指針 int stacksize;/ 當(dāng)前已分配的存儲(chǔ)空間，以元素為單位 SqStack;/ 順序棧/構(gòu)造一個(gè)空棧Sint InitStack(SqStack *S)/ 為棧底分配一個(gè)指定大小的存儲(chǔ)空間(*S).base = (SElemType *

37、)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 1;elsereturn 0;/插入元素e為新的棧頂元素。int Push(SqStack *S, SElemType e)if(*S).top - (

38、*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 += STACKINCREMENT;*(*S).top)+=e;return 1;/若棧不空，則刪除S的棧頂元素，用e返回其值，并返回1；否則返回0。int Pop(SqSt

39、ack *S,SElemType *e)if(*S).top = (*S).base)return 0;*e = *-(*S).top; / 這個(gè)等式的+ * 優(yōu)先級(jí)相同，但是它們的運(yùn)算方式，是自右向左return 1;/ 定義墻元素值為0,可通過路徑為1,不能通過路徑為-1,通過路徑為足跡/ 當(dāng)迷宮m的b點(diǎn)的序號(hào)為1(可通過路徑)，return 1; 否則，return 0。int Pass(PosType b) if(mb.xb.y=1)return 1;elsereturn 0;void FootPrint(PosType a) / 使迷宮m的a點(diǎn)的序號(hào)變?yōu)樽阚E(curstep)，表示經(jīng)

40、過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的b點(diǎn)的序號(hào)變?yōu)?1(不能通過的路徑)void MarkPrint(PosType b) mb.xb.y=-1;/ 若迷宮maze中存在從入口start到出口end的通道，則求得一條 / 存放在棧中(從棧底到棧頂)，并返回1；否則返回0 int Ma

41、zePath(PosType start,PosType end) SqStack S;PosType curpos;SElemType e;InitStack(&S);curpos=start;doif(Pass(curpos)/ 當(dāng)前位置可以通過，即是未曾走到過的通道塊 FootPrint(curpos); / 留下足跡 e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=0;Push(&S,e); / 入棧當(dāng)前位置及狀態(tài) curstep+; / 足跡加1 if(curpos.x=end.x&&cur

42、pos.y=end.y) / 到達(dá)終點(diǎn)(出口) return 1;curpos=NextPos(curpos,e.di);else/ 當(dāng)前位置不能通過 if(!StackEmpty(S)Pop(&S,&e); / 退棧到前一位置 curstep-;while(e.di=3&&!StackEmpty(S) / 前一位置處于最后一個(gè)方向(北)MarkPrint(e.seat); / 留下不能通過的標(biāo)記(-1) Pop(&S,&e); / 退回一步 curstep-;if(e.di<3) / 沒到最后一個(gè)方向(北) e.di+; / 換下一個(gè)方向

43、探索Push(&S,e); 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;i<x;i+)for(j=0;j<y;j+)printf("%3d",mij);printf("n"); void main()PosType begin,end;int i,j,x,y,x1,y1,n,k;dosystem("cl

44、s"); /清屏函數(shù)printf(" <<<<<<<<<<<<<<<<welcome>>>>>>>>>>>>>>>> nnn");printf(" 1請(qǐng)輸入迷宮的行數(shù),列數(shù)(包括外墻)n");printf(" 2請(qǐng)輸入迷宮內(nèi)墻單元數(shù)n");printf(" 3迷宮結(jié)構(gòu)如下n");printf(" 4輸入迷宮

45、的起點(diǎn)和終點(diǎn)n");printf(" 5輸出結(jié)果n");printf(" 0退出n");printf("nn請(qǐng)選擇 "); scanf("%d",&n);switch(n)case 1: printf("請(qǐng)輸入迷宮的行數(shù),列數(shù)(包括外墻)：(空格隔開)"); scanf("%d%d", &x, &y); for(i=0;i<x;i+) / 定義周邊值為0(同墻) m0i=0;/ 迷宮上面行的周邊即上邊墻 mx-1i=0;/ 迷宮下面行的

46、周邊即下邊墻 for(j=1;j<y-1;j+) mj0=0;/ 迷宮左邊列的周邊即左邊墻 mjy-1=0;/ 迷宮右邊列的周邊即右邊墻 for(i=1;i<x-1;i+)for(j=1;j<y-1;j+)mij=1; / 定義通道初值為1 break; case 2: printf("請(qǐng)輸入迷宮內(nèi)墻單元數(shù)："); scanf("%d",&j); printf("請(qǐng)依次輸入迷宮內(nèi)墻每個(gè)單元的行數(shù),列數(shù)：(空格隔開)n"); for(i=1;i<=j;i+) scanf("%d%d",

47、&x1,&y1);mx1y1=0; break; case 3:Print(x,y);printf("輸入0退出");scanf("%d",&k);break; case 4: printf("請(qǐng)輸入起點(diǎn)的行數(shù),列數(shù)：（空格隔開）"); scanf("%d%d",&begin.x,&begin.y); printf("請(qǐng)輸入終點(diǎn)的行數(shù),列數(shù)：（空格隔開）"); scanf("%d%d",&end.x,&end.y);break; case 5: if(MazePath(begin,end) / 求得一條通路 pr