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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計說明書迷宮問題求解學生姓名馬東1021024068 號學 103信班管級成績指導教婧李師數(shù)學與計算機科學學院2012年3月2日數(shù)據(jù)結(jié)構(gòu)課程設(shè)計評閱書 目題迷宮問題求解學生姓名馬東開始學號1021024068指導教師評語及成績成績：教師簽名：年月日 開始輸入迷宮的行數(shù) x和列數(shù)y構(gòu)建一個空棧Initstack( SqStack *S)n判斷棧是否為開始輸入迷宮的內(nèi)墻數(shù)j和具體位置x1 y1輸入迷宮的起點和終點&en d.x，&en d.y設(shè)置迷宮內(nèi)部，將內(nèi)墻設(shè)為mx1y1=0 輸入迷宮的起點和終點坐標& begi n x/y, &end x/y

2、Nif(MazePath(beign,end)求的路徑(判斷)N可以通過Footprint(curpos);/留下足跡，入棧Push( &S,e)，足跡加一 curstep+，繼續(xù)進 行判斷不可通過，換個方向繼續(xù)判斷Y是否到終點j i，輸入 輸岀此通路Print(x,y);輸岀迷宮答辯教師評語及成績成績：函數(shù)輸出已建立好的迷宮供YN找不到路教師簽名：用戶檢查判斷是否有路徑徑年 月日 空可由Print(x,y);找到路徑教研室意見總成績：室主任簽名：年 月曰注：指導教師成績60%，答辯成績40%，總成績合成后按五級制記入。陝筋理工警俛課程設(shè)計任務(wù)書2011 2012學年第二學期專業(yè)： 信

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

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

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

6、存從入口到當前位置的路徑。顯然要用到棧。關(guān)鍵詞： 迷宮；窮舉；棧；目錄1 課題描述12 問題分析和任務(wù)定義23 數(shù)據(jù)結(jié)構(gòu)分析33.1 存儲結(jié)構(gòu)333.2 算法描述4 流程圖 65 程序編碼 106 程序測試與運行過程 196.1 程序調(diào)試 196.2 程序運行過程 197 結(jié)果分析25總結(jié) 26 參考文獻27 1 課題描述 本課程設(shè)計是解決迷宮求解的問題，從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù) 往前走；否則沿原路退回，換一個方向再繼續(xù)探索， 直至所有可能的通路都探索到為止。為了保 證在任何位置上都能沿原路退回， 顯然需要用一個后進先出的結(jié)構(gòu)來保存從入口到當前位置的路 徑。因此，在求迷

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

8、徑上最后一個通道塊” 由此，“納入路徑”的操作即為“當前位置入?！?；“從當前路徑上刪除前一通道塊”的操作即為 “出棧”。1問題分析和任務(wù)定義 2根據(jù)課設(shè)題目要求，擬將整體程序分為四大模塊。以下是四個模塊的大體分析：根據(jù)用戶輸入的迷 1 建立迷宮：要建立迷宮首先就要建立存儲結(jié)構(gòu)，這里我用數(shù)組的方式建立的。25 可以根據(jù)要求調(diào)解） ；宮的大小 （我設(shè)置的最大值為外墻是以設(shè)計好的，是不可以通過路徑，0 這里將設(shè)置圍墻， 1 是可以通過的路徑， -12 設(shè)置迷宮： 內(nèi)墻需要用戶來設(shè)置，障礙的難度可自行定義； ,0 移動方向 ,依次為東南西北，首先3 尋找路徑：尋找路徑我設(shè)置了四個方向向東走，若不成功

9、則轉(zhuǎn)換方向，成功則繼續(xù)前進，將走過的路徑進行標記，然后存入棧中；4 輸出結(jié)果：輸出的結(jié)果分為兩種， 一種是用戶建立的迷宮主要是讓用戶檢查是否符合要求， 第二種輸岀的是尋找完后的路徑，路徑用1 2 3 4 來表示。23 數(shù)據(jù)結(jié)構(gòu)分析3.1 存儲結(jié)構(gòu) 定義一個整型數(shù)組 PosType 用來存儲行列的值。typedef struct / 棧的元素類型int ord; / 通道塊在路徑上的序號PosType seat; / 通道塊在迷宮中的坐標位置int di; /從此通道塊走向下一通道塊的"方向" （03表示東北） SElemType;棧的存儲結(jié)構(gòu)：#define STACK_I

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

11、= (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if( !(*S).base ) exit(0);(*S).top = (*S).base;/ 棧底與棧頂相同表示一個空棧3(*S).stacksize = STACK_INIT_SIZE;return 1;Status StackEmpty(SqStack S)/ 若棧 S 為空棧(棧頂與棧底相同的) ,則返回 1,否則返回 0if(S.top = S.base) return 1;else return 0;Status Push(SqStack *S, SElemType e)

12、/ 插入元素 e 為新的棧頂元素。if(*S).top - (*S).base >= (*S).stacksize) / 棧滿,追加存儲空間(*S).base = (SElemType *)realloc(*S).base , (*S).stacksize + STACKINCREMENT) sizeof(SElemType);exit(0); if( !(*S).base )(*S).top = (*S).base+(*S).stacksize; (*S).stacksize += STACKINCREMENT;*(*S).top)+=e;return 1;Status Pop(SqS

13、tack *S,SElemType *e)ereturn 0;。1返回其值，并返回；否則返回0若棧不空，則刪除 S的棧頂元素，用if(*S).top = (*S).base)*e = * -(*S).top;return 1;查找路徑的算法，簡單算法說明如下：1. Status MazePath(PosType start,PosType end)的通道，則求得一條 end 中存在從入口 / 若迷宮 mazestart 到出口 ；否則返回，并返回從 棧底到棧頂存放在棧中 / ()104InitStack(&S); curpos=start; curstep=1; doif(Pass(c

14、urpos)/ 當前位置可以通過，即是未曾走到過的通道塊 FootPrint(curpos); / 留下足跡e =( curstep, curpos,1);Push(&S,e); / 入棧當前位置及狀態(tài) if(curpos.x=end.x&&curpos.y=end.y) / 到達終點 ( 出口 ) return 1;curpos=NextPos(curpos,e.di);else/ 當前位置不能通過if(!StackEmpty(S)退棧到前一位置Pop(&S,&e); /前一位置處于最后一個方向 ) ( 北 / curstep-; while(e.di

15、=3&&!StackEmpty(S)MarkPrint(e.seat); Pop(&S,&e); / 留下不能通過的標記 (-1) , 退回一步if(e.di<3) / 沒到最后一個方向( 北 )e.di+; Push(&S,e);/ 換下一個方向探索 curpos=NextPos(e.seat,e.di); / 設(shè)定當前位置是該新方向上的相鄰塊while(!StackEmpty(S);return 0;4.流程圖4.1建立迷宮構(gòu)造空棧函數(shù)并判斷，若是則建立迷宮，否則返回并構(gòu)造空棧。y建立迷宮，將所有的周邊值設(shè)置為mx1y1=0結(jié)束3.1圖建立迷宮

16、函數(shù)流程圖60，用printf 函數(shù)輸岀4.2設(shè)置迷宮先設(shè)置迷宮障礙和起點與終點坐標，障礙設(shè)為結(jié)束圖3.2設(shè)置迷宮函數(shù)的流程圖4.3尋找路徑 先輸入起點與終點坐標。判斷，若能通過則留下足跡，入棧，足跡加一并繼續(xù)判斷，若不能，則換方向繼續(xù)判斷。.開始輸岀迷宮結(jié)束3.38尋找路徑函數(shù)流程圖圖4.4輸岀結(jié)果結(jié)束輸出結(jié)果流程圖3.45 程序編碼#include<stdio.h>#include<stdlib.h>#include<string.h>#include<malloc.h>/ 迷宮坐標位置類型typedef structint x; / 行值/

17、 列值 int y;PosType;#define MAXLENGTH 25 / 設(shè)迷宮的最大行列為 25typedef int MazeTypeMAXLENGTHMAXLENGTH; / 迷宮數(shù)組 行列 typedef struct / 棧的元素類型int ord; / 通道塊在路徑上的序號PosType seat; / 通道塊在迷宮中的坐標位置int di; /從此通道塊走向下一通道塊的"方向" （03表示東北）SElemType;/ 全局變量MazeType m; / 迷宮數(shù)組int curstep=1; / 當前足跡 ,初值為 1存儲空間初始分配量10#define

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

19、*sizeof(SElemType);if( !(*S).base )exit(0);/ (*S).top = (*S).base; 棧底與棧頂相同表示一個空棧 (*S).stacksize = STACK_INIT_SIZE;return 1;。 0，否則返回，則返回為空棧(棧頂與棧底相同的)S/ 若棧 1int StackEmpty(SqStack S)if(S.top = S.base)11return 1;elsereturn 0;插入元素 /e 為新的棧頂元素。int Push(SqStack *S, SElemType e)if(*S).top - (*S).base >=

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

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

22、.y=curstep;/ 根據(jù)當前位置及移動方向，返回下一位置PosType NextPos(PosType c,int di),0; / 行增量 ,列增量 / 移動方向 ,依次為東南西北c.x+=direcdi.x;c.y+=direcdi.y;return c;) / -1( 不能通過的路徑點的序號變?yōu)閎 的使迷宮 mvoid MarkPrint(PosType b)mb.xb.y= -1;若迷宮 / end 到出口中存在從入口 mazestart 的通道，則求得一條 13/ 存放在棧中 (從棧底到棧頂 )，并返回 1；否則返回 0int MazePath(PosType start,Po

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

24、)return 1;curpos=NextPos(curpos,e.di); else/ 當前位置不能通過 if(!StackEmpty(S)Pop(&S,&e); / 退棧到前一位置 curstep - ;14(北)while(e.di=3&&!StackEmpty(S) / 前一位置處于最后一個方向 Pop(&S,&e); /退回一步curstep-;()北 if(e.di<3) / e.di+; / 相鄰塊沒到最后一個方向換下一個方向探索Push(&S,e); curstep+;/MarkPrint(e.seat); / 留下

25、不能通過的標記 (-1)curpos=NextPos(e.seat,e.di);設(shè)定當前位置是該新方向上的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(=,mij););15void main()PosType begin,end;int i,j,x,y,x1,y1,n,k; dosystem(cls);printf(<<<<<<<<<<<<&l

26、t;<<<welcome>>>>>>>>>>>>>>>>/清屏函數(shù)nnn);printf(1 請輸入迷宮的行數(shù) ,列數(shù) ( 包括外墻 )n);printf(2 請輸入迷宮內(nèi)墻單元數(shù) n);printf(3 迷宮結(jié)構(gòu)如下 n);printf(4 輸入迷宮的起點和終點 n);printf(5 輸出結(jié)果 n);printf(0 退出 n);n 請選擇 );scanf(%d,&n);switch(n),列數(shù) (包括外墻 )： (空格隔開 );case 1: 牰湩晴尨請輸入迷宮的行數(shù)

27、 scanf(%d%d, &x, &y);for(i=0;i<x;i+) / 定義周邊值為 0(同墻 ) m0i=0;/ 迷宮上面行的周邊即上邊墻mx -1i=0;/ 迷宮下面行的周邊即下邊墻for(j=1;j<y -1;j+)16mj0=0; / 迷宮左邊列的周邊即左邊墻mjy -1=0;/ 迷宮右邊列的周邊即右邊墻 for(i=1;i<x -1;i+)for(j=1;j<y -1;j+)1 mij=1; / 定義通道初值為 break; case 2:灻楲瑮 ?請輸入迷宮內(nèi)墻單元數(shù)： ); scanf(%d,&j);牰湩晴尨請依次輸入迷宮內(nèi)墻

28、每個單元的行數(shù),列數(shù)： (空格隔開 )n);for(i=1;i<=j;i+)scanf(%d%d,&x1,&y1); mx1y1=0;break;0 牐湩 ?瀻楲瑮 ?輸入退出 );scanf(%d,&k);break; case 3: 慣敳 ?箋瀠楲瑮 ?請輸入起點的行數(shù) ,列數(shù)：(空格隔開) ); scanf(%d%d,&begin.x,&begin.y);牰湩晴尨請輸入終點的行數(shù) ,列數(shù)：(空格隔開) ); scanf(%d%d,&end.x,&end.y);break;case 5: if(MazePath(begin,en

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