实验二 迷宫实验.doc

实验七 排序实验实验四 迷宫实验一、 实验目的1、掌握栈的定义、操作及应用。2、掌握数组的定义、操作及应用。3、了解建立迷宫问题数学模型的方法。4、了解解决迷宫问题的算法。二、 实验原理编写程序，利用栈、数组解决迷宫问题。本实验综合了栈、数组及数学建模等知识点，考察了学生对栈、数组等数据结构的理解和应用，使学生了解数学建模的基本方法。迷宫是一个矩形区域，只有两个门，一个叫做入口，另一个叫做出口。在出口处放上一块奶酪，将一只老鼠放在迷宫的入口处，随后关闭迷宫入口处。老鼠必须在规定的时间内找到出口，否则会在迷宫中饿死。在迷宫的内部包含不能穿越的墙或障碍。障碍物沿着行和列放置，它们与迷宫的矩形边界平行。如图41所示。图41 迷宫示意图用一个取值为0，1，-1的二维数组mazemn表示迷宫，如果用ij来表示老鼠处在迷宫中的第i行，第j列的位置，该位置值为1表示有障碍，值为0表示有通路，值为-1表示老鼠已经路过该位置，不能再次回到该位置，如图42所示。1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 0 1 0 0 0 1 1 0 0 0 1 1 1 1 1 11 1 0 0 0 1 1 0 1 1 1 0 0 1 1 1 11 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 11 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 11 1 1 0 1 0 0 1 0 1 1 1 1 1 1 1 11 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 11 1 1 0 1 1 0 0 1 1 1 1 1 1 1 1 11 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 11 1 1 0 0 0 1 1 0 1 1 0 0 0 0 0 11 0 0 1 1 1 1 1 0 0 0 1 1 1 1 0 11 0 1 0 0 1 1 1 1 1 0 1 1 1 1 0 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1图2 迷宫数组maze老鼠在ij上的可能移动方向有8个，分别表示N（北）、NE（东北）、E（东）、SE（东南）、S（南）、SW（西南）、W（西）和NW（东北），如图43所示。Wij-1ijE ij+1NEi-1j+1SEi+1j+1S i+1jSWi+1j-1Ni-1jNWi-1j-1图43 移动方向示意图老鼠每到一个位置，就从北方向开始，按顺时针方向向查找其余各个方向，以决定走某一个方向。如果某个方向上的相邻位置为0，老鼠就可以沿着这个方向走；如果某个方向上的相邻位置为1或-1，表示有障碍或已经路过，老鼠就不能沿着这个方向走。将老鼠从入口到出口所经过的各个位置ij，以及从该位置出发能到达下一个位置的方向direction组合起来，构成一个三元组（i,j,direction）。然后将三元组存放在栈中，从而构成一个从入口处到出口处的通路栈。在行进过程中，若取了一个错误的方向则返回，并继续试探下一个方向。如果八个方向都有障碍，则应回到上一个位置继续探试。由于边界上的位置没有八个方向，为了避免检验每个位置是否在边界上，给迷宫加一个值为1的外边。由于老鼠不可能处在边界上的位置，因此老鼠可能路过的任何位置都有八个移动方向。三、 实验仪器和设备1、微机2、Microsoft VC+6.0四、 预习要求1、 复习栈、二维数组的定义、基本操作和存储结构。2、 掌握栈、二维数组的C语言的实现。3、 理解解决迷宫问题的算法原理。4、 了解建立迷宫问题数学模型的基本方法。五、 实验内容及步骤1、 析迷宫问题，建立数学模型，确定求解方法，画出流程图。2、 写解决迷宫问题的程序。如下代码是使用栈解决迷宫问题的完整程序。#include #include #define ROW 11#define COLUMN 15typedef struct /*栈中的数据元素的类型定义*/int row; /*行下标*/int col; /*列下标*/int direction; /*下一步移动方向*/ DATA;Typedif struct node /* 栈类定义*/DATA data;Struct node *next;LinkStack;Typedef struct/*移动方向的坐标偏移值*/int x_offset;int y_offset;DIRECTIONS;DIRECTIONS dir8=-1,0,-1,1,0,1,1,1,(1,0),1,-1,0,-1,-1,-1;Int mazeROW+2COLUMN+2=1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1,1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1,1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1,1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1,1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1,1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1,1,1,1,0,1,1,0,0,1,1,1,1,1,1,1,1,1,1,0,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,0,1，1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1,1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,; /*迷宫数组*/Void InitLinkStack(LinkStack *top) /* 初始化栈，将栈置空*/ *top=(LinkStack *)malloc(sizeof(LinkStack); (*top)-next=NULL;Bool IsEmpty(LinkStack *top) /*判断栈 是否为空，如果栈空，返回true,否则返回false*/ If(top-next=NULL) return true; Else return false;Void Push(LinkStack *top,DATA x) /*将元素x压入到栈S中，先申请结点再将其入栈*/ LinkStack*S；S=（LinkStack *）nalloc(sizeof(Linkstack);S-data=x; S-next=top-next;top-next=S;DATA Pop(LinkStack *top) /* 将栈S中的栈顶元素出栈*/ LinkStack *S; DATA data; If(!IsEmpty(top) /* 如果栈非空，则返回栈顶元素*/ S=top-next; top-next=S-next; data=S-data; free(S);return data;viod main()LinkStack *S;DATA d,temp;int i;InitLinkStack(&S); /*初始化栈*/d.col=d.row=1; d direction=0;Push(S,d); /*将迷宫入口处入栈*/while(!EsEmpty(S)/*老鼠的当前位置保存在temp中 */temp=Plp(S);i=temp.direction;while(i8)/*生成下一个老鼠位置*/d.row=temp.row+diri.x_offset;d.col=temp.col+diri.y_offset;d.direction=0;if(d.row=11&d.col=15) /*已找到出口*/ print(“%d,%d”,d.row,d.col); while(!IsEmpty(S)d=Pop(S);p