迷宫数据结构

1、实验报告题目：设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。一、 需求分析1. 以二维数组mazeNN表示迷宫，数组中以元素值0表示通路，1表示障碍，限定迷宫大小N<100。2. 第一行的数据为迷宫的行数m和列数n；从第2行到第m+1为迷宫值，同一行两个数字之间用空格表示。3. 实现一个以链表作存储结构的栈类型。4. 编写一个求解迷宫的非递归程序。5. 迷宫的入口位置和出口位置可由用户自己设定6. 本程序只求出一条成功的通路求得的通路以三元组（i,j,d）的形式输出，其中：(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。7. 测试数据：迷宫的

2、测试数据如下：左上角(1,1)为入口，右下角(9,8)为出口0010001000100010000011010111001000010000010001010111100111000101110000008程序执行的命令为：1）创建迷宫；2）求解迷宫；3）输出迷宫的解。二、概要设计拟采用栈来保存从入口到当前位置的路径，并采用“穷举求解”的方法进行求解。程序中将涉及到以下抽象数据类型：1. 设定栈的抽象数据类型定义：ADT Stack 数据对象：D= 数据关系：R1=基本操作：InitStack (StackSq* S) 操作结果：构造一个空栈S。StackEmpty(StackSq* S) 初

3、始条件：栈S已存在。 操作结果：若S为空栈，则返回TRUE，否则返回FALSE。Push(StackSq* S,SElemType e) 初始条件：栈S已存在。 操作结果：在栈S的栈顶插入新的栈顶元素e。Pop(StackSq* S,SElemType &e) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素，并以e返回其值。ADT Stack2.设定迷宫的抽象数据类型为：ADT maze数据对象：数据关系：基本操作：InitMaze(&Maze,row,col)初始条件：用数组MazeMN表示迷宫，迷宫的数据由用户自己定义，其中自第1行至第M行、每行中自第1列至第1列的元素

4、已有值，并且以值0表示通路，以值1表示障碍。操作结果：构成迷宫的数字型数组，以0表示通路，以1表示障碍。MatePath（&S）初始条件：迷宫S已被赋值。操作结果：若迷宫S中存在一条通路，则按如下规定改变迷宫S的状态：以2表示路径上的位置，以3表示死胡同；否则迷宫的状态不变。PrintMaze(Maze)初始条件：迷宫M已经存在操作结果：以数字形式输出迷宫。ADT maze；3.本程序包括三个模块1) 主程序模块：void main() 初始化； do 接受命令; 处理命令; while(命令!=”退出”)；2) 栈模块-实现栈的抽象数据类型3）迷宫模块-实现迷宫抽象数据类型各个模块之

5、间的调用关系如下： 主程序模块->迷宫模块 ->栈模块三 详细设计1. 坐标位置类型typedef struct PosType /定义坐标int x; /当前横坐标int y; /当前纵坐标PosType;2.迷宫类型int Maze;/迷宫存放在一个数字型数组中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; /设定当前位置为入口位置curpos.y=start.y;int curstep=1; /探索第一步doif(Pass(curpos,maze,n1,n2)=1)/当前位置可通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) /到达出口位置return 1;els

7、eNextPos(curpos,1); /探索下一步curstep+;/ifelse /当前位置不能通过if(!StackEmpty(stack)Pop(stack,e);while(e.di=4&&!StackEmpty(stack)MarkPrint(e.seat,maze);/留下不能通过的标记，并退回一步Pop(stack,e);/whileif(e.di<4) /换下一个方向探索e.di+;Push(stack,e);NextPos(e.seat,e.di); /设当前位置是该新方向上的相邻块，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("请输入迷宫(以0表示可走,1表示有障碍)：n");/按照用户要求输入一二维数组来表示迷宫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) /标记此处不能走 mazecurpos.xcurpos.y+; return 1; 2. 栈类型typedef struct migong int ord; /通道块在路径上的序号PosType seat; /通道块在迷宫中坐标位置 int di; /从此通道块走向下一通道块的方向SElemType; /栈数据元素的类型typedef structSNode SElemType SItem; struct SNode *next;SNode , * LinkStack;栈的基本操作设置如下：int InitStack(LinkStack

10、&S)S=(LinkStack)malloc(sizeof(SNode); /通过malloc函数分配空间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; /如果不能得到数据元素，则返回0(false)int Push(LinkStack &S,SElemType e)LinkStack q=S;LinkStack m=(LinkStack)malloc(sizeof(SNode); /通过malloc函数分配空间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)/依次输出从栈底到栈顶的每个元素if (S!=NULL)LinkStack q=S;if (q->next!=NULL) /若栈不是空的printf("n依次输出从栈底到栈顶的每个元

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; /设定当前位置为入口位置curpos.y=start.y;int curstep=1; /探索第一步if(Pass(curpos,maze,n1,n2)!=1)/判断初始方块是否是障碍物return 0;elsedoif(Pass(curpos,maze,n1,n2)=1)/当前位置可通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) /到达出口位置return 1;elseNextPos(curpos,1); /探索下一步curstep+;/ifelse /当前位置不能通过if(!StackEmpty(stack)Pop(stack,e);while(e.di=4&&!StackEmpty(stack)MarkPrint(e.seat,maze);/留下不能通过的标记，并退回一步Pop(stack,e);/whileif(e.di<4) /换下一个方向探索e.di+;Push(stack,e);NextPos(e.seat,e.di); /设

18、当前位置是该新方向上的相邻块curpos.x=e.seat.x;curpos.y=e.seat.y;while(!StackEmpty(stack);return 0;4. 主函数和其他函数的代码void main()int m,n;int mazeNN=0;LinkStack S;PosType start,end;int cmd;for(int i;i+)printf("n-n");printf(" 1.创建迷宫:n");printf(" 2.退出 n");printf("-n");printf("请

19、输入选择：n");scanf("%d",&cmd);switch(cmd)case 1:printf("请输入迷宫的行数和列数:n");scanf("%d%d",&m,&n);InitMaze(maze,m,n); /迷宫初始化printf("请输入起点坐标:n");scanf("%d%d",&start.x,&start.y);start.x-;start.y-;printf("请输入出口坐标: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("此迷宫无通路！n");printf("此时路径在迷宫中(用2标记表示可通路径，用3表示死胡同)显示为：n");PrintMaze(maze,m,n);/输出改变状态的迷宫b

21、reak;case 2:exit(0);break;default:exit(0);break;DestroyStack(S);int Pass(PosType seat,int mazeNN,int n1,int n2) /检查当前通道块是否可通 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