迷宮問題的求解數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)北華大學(xué)呂磊

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

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

3、格說明盡可能明確具體。詳細(xì)設(shè)計(jì)的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)和基本操作做出進(jìn)一步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定義，寫出函數(shù)形式的算法框架；程序編碼：把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語言程序。同時加入一些注解和斷言，使程序中邏輯概念清楚；程序調(diào)試與測試：采用自底向上，分模塊進(jìn)行，即先調(diào)試低層函數(shù)。能夠熟練掌握調(diào)試工具的各種功能，設(shè)計(jì)測試數(shù)據(jù)確定疑點(diǎn)，通過修改程序來證實(shí)它或繞過它。調(diào)試正確后，認(rèn)真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果；結(jié)果分析：程序運(yùn)行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。算法的時間、空間復(fù)雜性分析；編寫課程設(shè)計(jì)報(bào)告；以上要求中前三個階段的任務(wù)完

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

5、3.2算法描述34 流程圖 65 程序編碼106 程序測試與運(yùn)行過程19 6.1程序調(diào)試19 6.2程序運(yùn)行過程197 結(jié)果分析25 總結(jié)26 參考文獻(xiàn)271 課題描述 本課程設(shè)計(jì)是解決迷宮求解的問題，從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，顯然需要用一個后進(jìn)先出的結(jié)構(gòu)來保存從入口到當(dāng)前位置的路徑。因此，在求迷宮通路的算法中要應(yīng)用“?！钡乃枷爰僭O(shè)“當(dāng)前位置”指的是“在搜索過程中的某一時刻所在圖中某個方塊位置”，則求迷宮中一條路徑的算法的基本思想是：若當(dāng)前位置“可通”，則納入

6、“當(dāng)前路徑”，并繼續(xù)朝“下一位置”探索，即切換“下一位置”為“當(dāng)前位置”，如此重復(fù)直至到達(dá)出口；若當(dāng)前位置“不可通”，則應(yīng)順著“來向”退回到“前一通道塊”，然后朝著除“來向”之外的其他方向繼續(xù)探索；若該通道塊的四周4個方塊均“不可通”，則應(yīng)從“當(dāng)前路徑”上刪除該通道塊。所謂“下一位置”指的是當(dāng)前位置四周4個方向（東、南、西、北）上相鄰的方塊。假設(shè)以棧S記錄“當(dāng)前路徑”，則棧頂中存放的是“當(dāng)前路徑上最后一個通道塊”。由此，“納入路徑”的操作即為“當(dāng)前位置入?！?；“從當(dāng)前路徑上刪除前一通道塊”的操作即為“出棧”。2 問題分析和任務(wù)定義根據(jù)課設(shè)題目要求，擬將整體程序分為四大模塊。以下是四個模塊的大體

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

8、4來表示。3 數(shù)據(jù)結(jié)構(gòu)分析3.1存儲結(jié)構(gòu)定義一個整型數(shù)組PosType用來存儲行列的值。typedef struct / 棧的元素類型 int ord; / 通道塊在路徑上的序號 PosType seat; / 通道塊在迷宮中的坐標(biāo)位置 int di; / 從此通道塊走向下一通道塊的方向(03表示東北) SElemType; 棧的存儲結(jié)構(gòu)：#define STACK_INIT_SIZE 10/ 存儲空間初始分配量 #define STACKINCREMENT 2/ 存儲空間分配增量 / 棧的順序存儲表示 typedef struct SqStackSElemType *base;/ 在棧構(gòu)造之

9、前和銷毀之后，base的值為NULL SElemType *top;/ 棧頂指針 int stacksize;/ 當(dāng)前已分配的存儲空間，以元素為單位 SqStack;/ 順序棧 3.2算法描述 1.棧的基本操作的算法，簡單算法說明如下：Status InitStack(SqStack *S)/構(gòu)造一個空棧S，為棧底分配一個指定大小的存儲空間(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if( !(*S).base ) exit(0);(*S).top = (*S).base;/ 棧底與棧頂相同表示一個空棧(*

10、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 - (*S).base = (*S).stacksize) / 棧滿，追加存儲空間 (*S).base = (SElemType *)realloc(*S).base , (*S).stacksi

11、ze + 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)/若棧不空，則刪除S的棧頂元素，用e返回其值，并返回1；否則返回0。if(*S).top = (*S).base) return 0;*e = *-(*S).top;return 1;1. 查找路徑的算法，簡單算法

12、說明如下：Status MazePath(PosType start,PosType end) / 若迷宮maze中存在從入口start到出口end的通道，則求得一條 / 存放在棧中(從棧底到棧頂)，并返回1；否則返回0 InitStack(&S); curpos=start; curstep=1;doif(Pass(curpos)/ 當(dāng)前位置可以通過，即是未曾走到過的通道塊 FootPrint(curpos); / 留下足跡 e =( curstep, curpos,1);Push(&S,e); / 入棧當(dāng)前位置及狀態(tài) if(curpos.x=end.x&curpos.y=end.y) /

13、到達(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)MarkPrint(e.seat); Pop(&S,&e); /留下不能通過的標(biāo)記(-1) , 退回一步if(e.di3) / 沒到最后一個方向(北) e.di+; Push(&S,e);/ 換下一個方向探索curpos=NextPos(e.seat,e.di); / 設(shè)定當(dāng)前位置是該新方

14、向上的相鄰塊while(!StackEmpty(S);return 0; 4. 流程圖 4.1建立迷宮 構(gòu)造空棧函數(shù)并判斷，若是則建立迷宮，否則返回并構(gòu)造空棧。開始 輸入迷宮的行數(shù)x和列數(shù)y 構(gòu)建一個空棧InitStack（SqStack *S） n判斷棧是否為空 建立迷宮，將所有的周邊值設(shè)置為 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ù)輸出已建

15、立好的迷宮供用戶檢查結(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(beign,end)求的路徑（判斷） N可以通過Footprint(curpos);/留下足跡，入棧Push（&S,e），足跡加一curstep+，繼續(xù)進(jìn)行判斷N不可通過，換個方向繼續(xù)判斷是否到終點(diǎn) Y判斷是否有路徑 Y找到路徑輸出迷宮找不到路徑 N 結(jié)束 圖3.3尋找路徑函數(shù)流程圖4.4輸出結(jié)果 開始 輸入i，j Print(x,y);

16、輸出此通路 輸出迷宮 結(jié)束 圖3.4輸出結(jié)果流程圖5 程序編碼#include#include#include#include/ 迷宮坐標(biāo)位置類型typedef struct int x;/ 行值 int y;/ 列值 PosType;#define MAXLENGTH 25 / 設(shè)迷宮的最大行列為25 typedef int MazeTypeMAXLENGTHMAXLENGTH; / 迷宮數(shù)組行列 typedef struct / 棧的元素類型 int ord; / 通道塊在路徑上的序號 PosType seat; / 通道塊在迷宮中的坐標(biāo)位置 int di; / 從此通道塊走向下一通道塊的

17、方向(03表示東北) SElemType;/ 全局變量 MazeType m; / 迷宮數(shù)組 int curstep=1; / 當(dāng)前足跡,初值為1 #define STACK_INIT_SIZE 10/ 存儲空間初始分配量 #define STACKINCREMENT 2/ 存儲空間分配增量 / 棧的順序存儲表示 typedef struct SqStackSElemType *base;/ 在棧構(gòu)造之前和銷毀之后，base的值為NULL SElemType *top;/ 棧頂指針 int stacksize;/ 當(dāng)前已分配的存儲空間，以元素為單位 SqStack;/ 順序棧/構(gòu)造一個空棧Si

18、nt InitStack(SqStack *S)/ 為棧底分配一個指定大小的存儲空間(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if( !(*S).base )exit(0);(*S).top = (*S).base;/ 棧底與棧頂相同表示一個空棧(*S).stacksize = STACK_INIT_SIZE;return 1;/ 若棧S為空棧（棧頂與棧底相同的），則返回1，否則返回0。int StackEmpty(SqStack S)if(S.top = S.base)return 1;elseretu

19、rn 0;/插入元素e為新的棧頂元素。int Push(SqStack *S, SElemType e)if(*S).top - (*S).base = (*S).stacksize)/ 棧滿，追加存儲空間(*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).t

20、op)+=e;return 1;/若棧不空，則刪除S的棧頂元素，用e返回其值，并返回1；否則返回0。int Pop(SqStack *S,SElemType *e)if(*S).top = (*S).base)return 0;*e = *-(*S).top; / 這個等式的+ * 優(yōu)先級相同，但是它們的運(yùn)算方式，是自右向左return 1;/ 定義墻元素值為0,可通過路徑為1,不能通過路徑為-1,通過路徑為足跡/ 當(dāng)迷宮m的b點(diǎn)的序號為1(可通過路徑)，return 1; 否則，return 0。int Pass(PosType b) if(mb.xb.y=1)return 1;elsere

21、turn 0;void FootPrint(PosType a) / 使迷宮m的a點(diǎn)的序號變?yōu)樽阚E(curstep)，表示經(jīng)過ma.xa.y=curstep;/ 根據(jù)當(dāng)前位置及移動方向，返回下一位置 PosType NextPos(PosType c,int di)PosType direc4=0,1,1,0,0,-1,-1,0; / 行增量,列增量 / 移動方向,依次為東南西北 c.x+=direcdi.x;c.y+=direcdi.y;return c;/ 使迷宮m的b點(diǎn)的序號變?yōu)?1(不能通過的路徑)void MarkPrint(PosType b) mb.xb.y=-1;/ 若迷宮ma

22、ze中存在從入口start到出口end的通道，則求得一條 / 存放在棧中(從棧底到棧頂)，并返回1；否則返回0 int MazePath(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)

23、前位置及狀態(tài) curstep+; / 足跡加1 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-;while(e.di=3&!StackEmpty(S) / 前一位置處于最后一個方向(北)MarkPrint(e.seat); / 留下不能通過的標(biāo)記(-1) Pop(&S,&e); / 退回一步 curstep-;if(e.di3) / 沒到最后一個方向(北)

24、 e.di+; / 換下一個方向探索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;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;dosystem(cls); /清屏函數(shù)printf( nnn);prin

25、tf( 1請輸入迷宮的行數(shù),列數(shù)(包括外墻)n);printf( 2請輸入迷宮內(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請選擇 ); scanf(%d,&n);switch(n)case 1: printf(請輸入迷宮的行數(shù),列數(shù)(包括外墻)：(空格隔開); scanf(%d%d, &x, &y); for(i=0;ix;i+) / 定義周邊值為0(同墻) m0i=0;/ 迷宮上面行的周邊即上邊墻 mx-1i=0;/ 迷宮下面行的周邊即下邊墻 for(j=1;jy

26、-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(請輸入迷宮內(nèi)墻單元數(shù)：); scanf(%d,&j); printf(請依次輸入迷宮內(nèi)墻每個單元的行數(shù),列數(shù)：(空格隔開)n); for(i=1;i=j;i+) scanf(%d%d,&x1,&y1);mx1y1=0; break; case 3:Print(x,y);printf(輸入0退出);scanf(%d,&k);break; case 4:

27、printf(請輸入起點(diǎn)的行數(shù),列數(shù)：（空格隔開）); scanf(%d%d,&begin.x,&begin.y); printf(請輸入終點(diǎn)的行數(shù),列數(shù)：（空格隔開）); scanf(%d%d,&end.x,&end.y);break; case 5: if(MazePath(begin,end) / 求得一條通路 printf(此迷宮從入口到出口的一條路徑如下:n);Print(x,y); / 輸出此通路 elseprintf(此迷宮沒有從入口到出口的路徑n);printf(輸入0退出);scanf(%d,&k);break;while(n!=0);6 程序測試與運(yùn)行 6.1 程序調(diào)試 在

28、調(diào)試程序是主要遇到一下幾類問題： 1.選擇存儲結(jié)構(gòu)的問題：剛接到課設(shè)題目的時候，我就在想用什么來實(shí)現(xiàn)迷宮的存儲。用線性表還是數(shù)組，最后綜合考慮決定用棧和數(shù)組結(jié)合的方式來實(shí)現(xiàn)，用數(shù)組來建立迷宮和輸出迷宮，用棧來查找路徑并將生成的路徑壓入到棧中，因?yàn)闂Ｓ邢热牒蟪龅膬?yōu)點(diǎn)，所以比較容易實(shí)現(xiàn)。2.如何建立迷宮和怎么設(shè)置迷宮的問題：首先迷宮要有一定的范圍怎么才能讓迷宮有序的進(jìn)行，于是我將迷宮的外圍和障礙設(shè)置為0，所有的可走路徑設(shè)置為1，這樣迷宮就清晰可見。3.如何去尋找路徑問題 ：這是整個程序的核心。通過查找書籍得到了一個算法：若當(dāng)前位置“可通”，則納入當(dāng)前路徑，并繼續(xù)朝下一位置搜索，即切換下一位置為當(dāng)前位置，如此重復(fù)到達(dá)出口；若不可通，就退回到前一通道，然后繼續(xù)尋找其他方向；若均不可通，則刪除此路徑。4界面問題：這里就是運(yùn)用了switch(n)語句來實(shí)現(xiàn)的，這樣增加了程序的實(shí)用性。6.2程序運(yùn)行過程出現(xiàn)界面后選擇1，：進(jìn)行迷宮大小的設(shè)計(jì)如圖5.1所示