迷宮問題的求解數(shù)據(jù)結構課程設計

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

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

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

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

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

6、··························12 問題分析和任務定義······················

7、········································23 數(shù)據(jù)結構分析········

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

9、83;········· 33.1存儲結構·······································

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

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

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

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

14、183;··············································106 程序測試與運行過程·&

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

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

17、83;·······························19 6.2程序運行過程················

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

19、 結果分析·················································&

20、#183;·······················25 總結·························&#

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

22、183;·26 參考文獻···············································&

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

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

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

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

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

28、STACK_INIT_SIZE*sizeof(SElemType);if( !(*S).base ) exit(0);(*S).top = (*S).base;/ 棧底與棧頂相同表示一個空棧(*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) / 棧滿，追加存儲空間 (*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. 查找路徑的算法，簡單算法說明如下：Status MazePath(PosType start,PosType end) / 若迷宮maze中存在從入口start到出口end的通道，則求得一條 / 存放在棧中(從棧底到棧頂)，并返回1；否則返回0 InitStack(&S); curpos=start; curstep=1;doif(Pass(curpos)/ 當前位置可以通過，即是未曾走到過的通道塊 FootP

31、rint(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=3&&!StackEmpty(S)MarkPrint(

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

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

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

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

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

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

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

40、過ma.xa.y=curstep;/ 根據(jù)當前位置及移動方向，返回下一位置 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點的序號變?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)/ 當前位置可以通過，即是未曾走到過的通道塊 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&&cur

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

43、探索Push(&S,e); curstep+;/ 設定當前位置是該新方向上的相鄰塊curpos=NextPos(e.seat,e.di);while(!StackEmpty(S);return 0;/ 輸出迷宮的結構 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請輸入迷宮的行數(shù),列數(shù)(包括外墻)n");printf(" 2請輸入迷宮內(nèi)墻單元數(shù)n");printf(" 3迷宮結構如下n");printf(" 4輸入迷宮

45、的起點和終點n");printf(" 5輸出結果n");printf(" 0退出n");printf("nn請選擇 "); scanf("%d",&n);switch(n)case 1: printf("請輸入迷宮的行數(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("請輸入迷宮內(nèi)墻單元數(shù)："); scanf("%d",&j); printf("請依次輸入迷宮內(nèi)墻每個單元的行數(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("請輸入起點的行數(shù),列數(shù)：（空格隔開）"); scanf("%d%d",&begin.x,&begin.y); printf("請輸入終點的行數(shù),列數(shù)：（空格隔開）"); scanf("%d%d",&end.x,&end.y);break; case 5: if(MazePath(begin,end) / 求得一條通路 pr