迷宮數(shù)據(jù)結(jié)構(gòu)

1、實(shí)驗(yàn)報(bào)告題目：設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒(méi)有通路的結(jié)論。一、 需求分析1. 以二維數(shù)組mazeNN表示迷宮，數(shù)組中以元素值0表示通路，1表示障礙，限定迷宮大小N<100。2. 第一行的數(shù)據(jù)為迷宮的行數(shù)m和列數(shù)n；從第2行到第m+1為迷宮值，同一行兩個(gè)數(shù)字之間用空格表示。3. 實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類(lèi)型。4. 編寫(xiě)一個(gè)求解迷宮的非遞歸程序。5. 迷宮的入口位置和出口位置可由用戶(hù)自己設(shè)定6. 本程序只求出一條成功的通路求得的通路以三元組（i,j,d）的形式輸出，其中：(i,j)指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向。7. 測(cè)試數(shù)據(jù)：迷宮的

2、測(cè)試數(shù)據(jù)如下：左上角(1,1)為入口，右下角(9,8)為出口0010001000100010000011010111001000010000010001010111100111000101110000008程序執(zhí)行的命令為：1）創(chuàng)建迷宮；2）求解迷宮；3）輸出迷宮的解。二、概要設(shè)計(jì)擬采用棧來(lái)保存從入口到當(dāng)前位置的路徑，并采用“窮舉求解”的方法進(jìn)行求解。程序中將涉及到以下抽象數(shù)據(jù)類(lèi)型：1. 設(shè)定棧的抽象數(shù)據(jù)類(lèi)型定義：ADT Stack 數(shù)據(jù)對(duì)象：D= 數(shù)據(jù)關(guān)系：R1=基本操作：InitStack (StackSq* S) 操作結(jié)果：構(gòu)造一個(gè)空棧S。StackEmpty(StackSq* S) 初

3、始條件：棧S已存在。 操作結(jié)果：若S為空棧，則返回TRUE，否則返回FALSE。Push(StackSq* S,SElemType e) 初始條件：棧S已存在。 操作結(jié)果：在棧S的棧頂插入新的棧頂元素e。Pop(StackSq* S,SElemType &e) 初始條件：棧S已存在。 操作結(jié)果：刪除S的棧頂元素，并以e返回其值。ADT Stack2.設(shè)定迷宮的抽象數(shù)據(jù)類(lèi)型為：ADT maze數(shù)據(jù)對(duì)象：數(shù)據(jù)關(guān)系：基本操作：InitMaze(&Maze,row,col)初始條件：用數(shù)組MazeMN表示迷宮，迷宮的數(shù)據(jù)由用戶(hù)自己定義，其中自第1行至第M行、每行中自第1列至第1列的元素

4、已有值，并且以值0表示通路，以值1表示障礙。操作結(jié)果：構(gòu)成迷宮的數(shù)字型數(shù)組，以0表示通路，以1表示障礙。MatePath（&S）初始條件：迷宮S已被賦值。操作結(jié)果：若迷宮S中存在一條通路，則按如下規(guī)定改變迷宮S的狀態(tài)：以2表示路徑上的位置，以3表示死胡同；否則迷宮的狀態(tài)不變。PrintMaze(Maze)初始條件：迷宮M已經(jīng)存在操作結(jié)果：以數(shù)字形式輸出迷宮。ADT maze；3.本程序包括三個(gè)模塊1) 主程序模塊：void main() 初始化； do 接受命令; 處理命令; while(命令!=”退出”)；2) 棧模塊-實(shí)現(xiàn)棧的抽象數(shù)據(jù)類(lèi)型3）迷宮模塊-實(shí)現(xiàn)迷宮抽象數(shù)據(jù)類(lèi)型各個(gè)模塊之

5、間的調(diào)用關(guān)系如下： 主程序模塊->迷宮模塊 ->棧模塊三 詳細(xì)設(shè)計(jì)1. 坐標(biāo)位置類(lèi)型typedef struct PosType /定義坐標(biāo)int x; /當(dāng)前橫坐標(biāo)int y; /當(dāng)前縱坐標(biāo)PosType;2.迷宮類(lèi)型int Maze;/迷宮存放在一個(gè)數(shù)字型數(shù)組中int MazePath(int mazeNN,PosType start,PosType end,LinkStack &stack,int n1,int n2)/求解迷宮maze中，從入口Start到出口end的一條路徑stack=NULL;SElemType e;PosType curpos;Ini

6、tStack(stack);/初始化stackcurpos.x=start.x; /設(shè)定當(dāng)前位置為入口位置curpos.y=start.y;int curstep=1; /探索第一步doif(Pass(curpos,maze,n1,n2)=1)/當(dāng)前位置可通FootPrint(curpos,maze); /留下足跡e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=1;Push(stack,e); /加入路徑，入棧if(curpos.x=end.x&&curpos.y=end.y) /到達(dá)出口位置return 1;els

7、eNextPos(curpos,1); /探索下一步curstep+;/ifelse /當(dāng)前位置不能通過(guò)if(!StackEmpty(stack)Pop(stack,e);while(e.di=4&&!StackEmpty(stack)MarkPrint(e.seat,maze);/留下不能通過(guò)的標(biāo)記，并退回一步Pop(stack,e);/whileif(e.di<4) /換下一個(gè)方向探索e.di+;Push(stack,e);NextPos(e.seat,e.di); /設(shè)當(dāng)前位置是該新方向上的相鄰塊，1代表向右，2代表向下，3代表向左，4代表向上。 curpos.x=

8、e.seat.x;curpos.y=e.seat.y;while(!StackEmpty(stack);return 0;void InitMaze(int MazeNN,int r,int c) /初始化迷宮 printf("請(qǐng)輸入迷宮(以0表示可走,1表示有障礙)：n");/按照用戶(hù)要求輸入一二維數(shù)組來(lái)表示迷宮for(int i=0;i<r;i+)for(int j=0;j<c;j+) scanf("%d",&Mazeij);if(Mazeij!=0&&Mazeij!=1)exit(0);int MarkPrint

9、(PosType curpos,int mazeNN) /標(biāo)記此處不能走 mazecurpos.xcurpos.y+; return 1; 2. 棧類(lèi)型typedef struct migong int ord; /通道塊在路徑上的序號(hào)PosType seat; /通道塊在迷宮中坐標(biāo)位置 int di; /從此通道塊走向下一通道塊的方向SElemType; /棧數(shù)據(jù)元素的類(lèi)型typedef structSNode SElemType SItem; struct SNode *next;SNode , * LinkStack;棧的基本操作設(shè)置如下：int InitStack(LinkStack

10、&S)S=(LinkStack)malloc(sizeof(SNode); /通過(guò)malloc函數(shù)分配空間if (!S)return 0; /如果分配失敗，則返回0S->next=NULL;return 1;void DestroyStack(LinkStack &S)LinkStack q;if(S!=NULL)while(S->next!=NULL) /如果棧非空，則釋放空間q=S->next;if (S->next->next!=NULL)S->next=S->next->next;elseS->next=NULL;f

11、ree(q);free(S);S=NULL;void ClearStack(LinkStack &S)LinkStack q;if(S!=NULL)while(S->next!=NULL) /如果棧非空，則釋放空間q=S->next;if (S->next->next!=NULL)S->next=S->next->next;elseS->next=NULL;free(q);int StackEmpty(LinkStack S)if (S!=NULL) /判斷棧是否存在if (S->next=NULL)return 1;return

12、0;int StackLength(LinkStack S)int m=0;LinkStack q=S;if (S!=NULL) /判斷棧是否存在if (q->next!=NULL)/判斷棧是否為空while (q->next!=NULL)+m;q=q->next;return m;return 0; int GetTop(LinkStack S,SElemType &e)LinkStack q=S;if (S!=NULL) /判斷棧是否存在if (q->next!=NULL)/判斷棧是否為空while (q->next!=NULL)q=q->nex

13、t;e=q->SItem;return 1;return 0; /如果不能得到數(shù)據(jù)元素，則返回0(false)int Push(LinkStack &S,SElemType e)LinkStack q=S;LinkStack m=(LinkStack)malloc(sizeof(SNode); /通過(guò)malloc函數(shù)分配空間if (S!=NULL)while (q->next!=NULL)q=q->next;m->SItem=e;m->next=NULL;q->next=m;return 0;int Pop(LinkStack &S,SEle

14、mType &e)LinkStack q=S;if (S!=NULL)if (q->next!=NULL) /若棧不是空的while (q->next->next!=NULL)q=q->next;e=q->next->SItem;q->next=NULL;return 1;return 0;int StackTraverse(LinkStack S)/依次輸出從棧底到棧頂?shù)拿總€(gè)元素if (S!=NULL)LinkStack q=S;if (q->next!=NULL) /若棧不是空的printf("n依次輸出從棧底到棧頂?shù)拿總€(gè)元

15、素為：n");while (q->next!=NULL)q=q->next;printf("%d ",q->SItem);printf("n");return 1;return 0;3. 求解迷宮路徑的代碼int MazePath(int mazeNN,PosType start,PosType end,LinkStack &stack,int n1,int n2)/求解迷宮maze中，從入口Start到出口end的一條路徑stack=NULL;SElemType e;PosType curpos;InitStack(

16、stack);/初始化stackcurpos.x=start.x; /設(shè)定當(dāng)前位置為入口位置curpos.y=start.y;int curstep=1; /探索第一步if(Pass(curpos,maze,n1,n2)!=1)/判斷初始方塊是否是障礙物return 0;elsedoif(Pass(curpos,maze,n1,n2)=1)/當(dāng)前位置可通FootPrint(curpos,maze); /留下足跡e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=1;Push(stack,e); /加入路徑，入棧if(curpos.x=e

17、nd.x&&curpos.y=end.y) /到達(dá)出口位置return 1;elseNextPos(curpos,1); /探索下一步curstep+;/ifelse /當(dāng)前位置不能通過(guò)if(!StackEmpty(stack)Pop(stack,e);while(e.di=4&&!StackEmpty(stack)MarkPrint(e.seat,maze);/留下不能通過(guò)的標(biāo)記，并退回一步Pop(stack,e);/whileif(e.di<4) /換下一個(gè)方向探索e.di+;Push(stack,e);NextPos(e.seat,e.di); /設(shè)

18、當(dāng)前位置是該新方向上的相鄰塊curpos.x=e.seat.x;curpos.y=e.seat.y;while(!StackEmpty(stack);return 0;4. 主函數(shù)和其他函數(shù)的代碼void main()int m,n;int mazeNN=0;LinkStack S;PosType start,end;int cmd;for(int i;i+)printf("n-n");printf(" 1.創(chuàng)建迷宮:n");printf(" 2.退出 n");printf("-n");printf("請(qǐng)

19、輸入選擇：n");scanf("%d",&cmd);switch(cmd)case 1:printf("請(qǐng)輸入迷宮的行數(shù)和列數(shù):n");scanf("%d%d",&m,&n);InitMaze(maze,m,n); /迷宮初始化printf("請(qǐng)輸入起點(diǎn)坐標(biāo):n");scanf("%d%d",&start.x,&start.y);start.x-;start.y-;printf("請(qǐng)輸入出口坐標(biāo):n");scanf("

20、;%d%d",&end.x,&end.y);end.x-;end.y-;printf("迷宮為n");PrintMaze(maze,m,n);/輸出初始迷宮if(MazePath(maze,start,end,S,m,n)printf("走出迷宮的路徑為:n");StackTraverse(S);elseprintf("此迷宮無(wú)通路！n");printf("此時(shí)路徑在迷宮中(用2標(biāo)記表示可通路徑，用3表示死胡同)顯示為：n");PrintMaze(maze,m,n);/輸出改變狀態(tài)的迷宮b

21、reak;case 2:exit(0);break;default:exit(0);break;DestroyStack(S);int Pass(PosType seat,int mazeNN,int n1,int n2) /檢查當(dāng)前通道塊是否可通 if(mazeseat.xseat.y=0&&seat.x<n1&&seat.x>=0&&seat.y<n2&&seat.y>=0)return 1;else return 0; int FootPrint(PosType curpos,int mazeNN) mazecurpos.xcurpos.y=2; return 1;void NextPos(Pos