《实验二 迷宫实验》由会员分享，可在线阅读，更多相关《实验二 迷宫实验（5页珍藏版）》请在金锄头文库上搜索。
1、实验二 迷宫实验一、 实验目的1、掌握栈的定义、操作及应用。2、掌握数组的定义、操作及应用。3、了解建立迷宫问题数学模型的方法。4、了解解决迷宫问题的算法。二、 实验仪器和设备1、微机2、MICROSOFT VC+6.0三、 实验原理及内容迷宫是一个矩形区域，只有两个门，一个叫做入口，另一个叫做出口。在出口处放上一块奶酪，将一只老鼠放在迷宫的入口处，随后官迷入口处。老鼠必须在规定的时间内找到出口，否则会在迷宫中饿死。在迷宫的内部包含不能穿越的墙或障碍。障碍物沿着行和列放置，它们与迷宫的矩形边界平行。如下图所示。图 21 迷宫示意图用一个取值为0，1，-1的二维数组 MAZEMN表示迷宫，如果用
2、IJ来表示老鼠处在迷宫中的第 I 行，第 J 列的位置，该位置值为 1 表示有障碍，值为 0 表示有通路，值为-1 表示老鼠已经路过该位置，不能再次回到该位置，如下图所示。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
3、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-2 迷宫数组 MAZE老鼠在IJ上的可能移动方向有 8 个，分别表示 N（北） 、NE （东北） 、E（东） 、SE（东南） 、S（南） 、SW（西南） 、W（西
4、）和 NW（东北） ，如图 23 所示。图 43 移动方向示意图图 2-3老鼠没到一个位置，就从北方向开始，按顺时针方向向查找其余各个方向，以决定走某一个方向。如果某个方向上的相邻位置为 0，老鼠就可以沿着这个方向走；如果某个方向上的相邻位置为 1 或-1，表示有障碍或已经路过，老鼠就不能沿着这个方向走。将老鼠从入口到出口所经过的各个位置ij，以及从该位置出发能到达下一个位置的方向direction 组合起来，构成一个三元组（i,j,direction ） 。然后将三元组存放在栈中，从而构成一个从入口处到出口处的通路栈。在行进过程中，若取了一个错误的方向则返回，并继续试探下一个方向。如果八个方
5、向都有障碍，则应回到上一个位置继续探试。由于边界上的位置没有八个方向，为了避免检验每个位置是否在边界上，给迷宫加一个值为 1 的外边。由于老鼠不可能处在边界上的位置，因此老鼠可能路过的任何位置都有八个移动方向。四、 实验步骤1、 析迷宫问题，建立数学模型，确定求解方法，画出流程图。2、 写解决迷宫问题的程序。如下代码是使用栈解决迷宫问题的完整程序。#include #include #include #define ROW 11/定义入口#define COLUMN 15typedef struct /*栈中的数据元素的类型定义*/int row; /*行下标*/int col; /*列下标*
6、/int direction; /*下一步移动方向*/ DATA;typedef struct node /* 栈类定义*/DATA data;struct node *next;LinkStack;typedef struct/*移动方向的坐标偏移值*/int x_offset;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,
7、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,
8、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;int IsEmpty(LinkStack *top) /*判断栈是否为空，如果栈空，返回 true(1),否则返回 false(0)*/if(top-next=NULL
9、)return 1;else return 0;void Push(LinkStack *top,DATA x) /*将元素 x 压入到栈 S 中，先申请结点再将其入栈*/LinkStack *S;S=(LinkStack *)malloc(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-n
10、ext;data=S-data; free(S);return data;void main()LinkStack *S;DATA d,temp;int i;InitLinkStack( /*初始化栈*/d.col=d.row=1; d.direction=0;Push(S,d); /*将迷宫入口处入栈*/while(!IsEmpty(S)/*老鼠的当前位置保存在 temp 中*/temp=Pop(S);i=temp.direction;while(i8)/*生成下一个老鼠位置 */d.row=temp.row+diri.x_offset;d.col=temp.col+diri.y_offse
11、t;d.direction=0;if(d.row=11)&(d.col=15) /*已找到出口*/printf(%d,%d ,d.row,d.col);while(!IsEmpty(S)d=Pop(S);printf(%d,%d ,d.row,d.col);free(S);exit(0);else if(mazed.rowd.col=0) /*得到下一个可移动位置*/mazed.rowd.col=-1;Push(S,d);i=d.direction; temp=d;else i+;3、上机调试、运行程序。五、 实验结果解释：得到的数据i,j既为老鼠在预先设定的二维数组的迷宫里的位置，依次通过这些位置，老鼠即可到达出口六、 实验心得通过有趣的迷宫实验我掌握了栈的定义、操作及应用。并且掌握了数组的定义、操作及应用。了解建立迷宫问题数学模型的方法，了解解决迷宫问题的算法。更为重要的是了解了通过数组和结构体结合来生成的数据结构的特点及应用，这是在这之前未接触过的。通过 C 语言的实现，我加强了对 C 语言的应用于理解，学会了软件编程中基础的数据结构的搭建与使用。通过两次的实验，我对计算机软件基础有了更加深刻的认识，能够将所学的计算机编程语言应用到实际问题的解决中，学会了基本的编程方法，使我受益匪浅。
