数据结构实验报告--链栈编写迷宫

数 据 结 构

课程设计报告

题目: 用栈解决迷宫问题

院 系： 二系 专业班级： 10信息 * 名： *** 学 号： *********** 指导教师： * *

2012年6月

一需求分析

1.1问题描述：以一个m×n的长方形表示迷宫，0和1分别表示迷宫中的通路和障碍。设

计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论

1.2基本要求：

(1)输入形式和输入值的范围：

50行50列。

(2)输出形式：

求得的通路以三元组（x,y,j）的形式输出，其中：（i,j）指示迷宫中的一个坐标，j表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1,1,1）, （1,2,2）,（2,2,2），（3,2,3）, （3,1,2）,…。

(3)程序所能达到的功能：

求出一条从入口到出口的通路及路径长度或得出没有通路的结论。 二、概要设计 1、数据结构

以结构体储存迷宫信息，链栈储存结点及坐标。

2、程序模块

(1)迷宫生产模块：手动生成迷宫。

(2)判断结点存在：防止结点的重复访问。

(3)路径查找模块：实现通路的查找，返回一条通路。 (4)路径输出模块：实现路径以题意要求输出。 3、各模块之间的调用关系及算法设计 主函数 创建迷宫 初始化 迷宫求解函数 找到出口？ 改变条件 否 符和条件？ 否 是 是 进栈 输出路径

- 1 -

三、详细分析

1.结构体：

int arry[M][N]； int max_x,max_y;

2.链栈的设计：

int vex_x,vex_y; struct point *next; int direction;

3.创建迷宫：

cout<<\"请输入迷宫的列和列: \"; cin>>a.max_x>>a.max_y; for(i=1;i<=a.max_x;i++) { 输入各数组元素 } return a;

4.查找栈中结点判断是否与当前结点相等：

Point *p=head; While(p非空)

{ if(但前坐标与栈中某坐标相等) return 1 p=p->next; }

Return 0；

5.迷宫函数，返回一条通道或者NULL： Point *top,*p; int j,find,x,y;

do

{ while(方向j<4) { find=0；

switch(j)//1234分别表示东南西北 { case 1:

if(纵坐标加1后在迷宫内，且当前结点为0，且当前结点没有在栈中出现) { 当前结点进栈；

把方向j赋予当前结点方向； find=1; }break;

case 2:

if(纵横标加1后在迷宫内，且当前结点为0，且当前结点没有在栈中出现) { 当前结点进栈；

把方向j赋予当前结点方向； find=1; }break；

- 2 -

case 3:

if(纵做标减1后在迷宫内，且当前结点为0，且当前结点没有在栈中出现) { 当前结点进栈；

把方向j赋予当前结点方向； find=1; }break； case 4:

if(纵横标减1后在迷宫内，且当前结点为0，且当前结点没有在栈中出现) { 当前结点进栈；

把方向j赋予当前结点方向； find=1; }break; }

if(find==1)

{ j++;break;} else j++;

}

if(j>4)

{ if(栈顶前一个结点不为空) {当前结点出栈且方向加1} else return NULL; }

}while(当前结点不是出口) return top; 6.输出函数：

int i=0,top=0; Point *stack[M]; if(栈顶为空)

cout<<”没通路”<{ while(栈顶不为空)

{通过一个顺序栈将链栈逆序;top++;} While(top>0) {输出结果}

} 7.主函数：

void main（） { sd road; Point *po; road=creat(); po=secret(road); disp(po);

}

- 3 -

四、测试与分析

1.测试数据：

程序运行结果截图：

(1).4行4列迷宫矩阵：

(2).6行6列迷宫矩阵：

(3).没路的情况：

2.分析：

(1).输入所要建立的迷宫的行列数；

- 4 -

(2).输入矩阵，0表通道，1表示墙；

(3).从入口(1,1)进入先判断东面是否为通道，若通则进入，否则在判断下一个方向(1,2,3,4表是东南西北，起始为东按顺时针转动)。如4行4列矩阵，入口(1,1)东面为通道进入(1,2)；东面仍为通道进入(1,3)；东面不通，往南，南通进入(2, 3),东面为通进入(2,4)；4个方向都不通返回(2,3)；且往南不通，在往西，通进入(2,3)…… 五、总结：

1．收获：通过本试验我对链栈有了更深入的了解，对链栈的使用更加熟练。让我深知要想熟练掌握一门算法大量的编程训练是必不可少的，在编写的过程中我们更容易发现问题所在，对算法有更深会的理解。

2．遇到问题：在将算法应用到迷宫问题过程中，遇到了不少问题，反复琢磨和查找相关书籍才将其解决。首先，是如何用链栈储存调用迷宫矩阵中的相关坐标；再次，是判断方向的转变使其不会重复走过的路经；最后，当所行路经不通时如何退出返回到迁移结点。

3．从一个小的迷宫问题，引出了许多知识，这种探索式的学习是很有重要意义的。从迷宫基本的操作到链栈的运用和理解，提高了我程序的调试能力和对算法的深入思考，加深了对数据结构的的认识。 六、附录：

源程序清单:

# include using namespace std; # define maxsize 20

typedef struct//定义迷宫 {

int arry[maxsize][maxsize];//二维数组存放迷宫信息 int max_x,max_y;//迷宫的行数和和列数 }sd;

typedef struct point {

int vex_x,vex_y;//结点的横纵坐标 struct point *next;//指向下一个结点 int direction;//下一个结点的方向 }Point;

sd creat()//创建迷宫 {

int i,j; sd a;

cout<<\"请输入迷宫的行数: \"; cin>>a.max_x;

cout<<\"请输入迷宫的列数: \"; cin>>a.max_y;

for(i=1;i<=a.max_x;i++) { cout<<\"输出第\"<- 5 -

for(j=1;j<=a.max_y;j++) cin>>a.arry[i][j]; }

cout<int found(int x,int y,Point *head) {

Point *p=head; while(p!=NULL) { if(x==p->vex_x&&y==p->vex_y) return 1; p=p->next; }

return 0; }

Point * secret(sd a)//迷宫函数，返回一条通路或者NULL {

Point * top,*p;//top为栈的栈顶指针 int j,find,x,y;

p=(Point *)malloc(sizeof(Point)); p->next=NULL;

p->vex_x=1;p->vex_y=1;//p->next=NULL; top=p;

j=1;//j为方向，1,2,3,4分别为东，南，西，北 do { while(j<=4) { find=0;

//find判断是否有符合条件的结点，若有为1，没有为0.

x=p->vex_x; y=p->vex_y; switch(j) { case 1: if(y+1<=a.max_x&&!a.arry[x][y+1]&&!found(x,y+1,top))

//若纵坐标加1后，在迷宫范围内，当前结点为0，当店结点没有在链栈中出现，则当前结点加入链栈 {

p=(Point *)malloc(sizeof(Point));

p->vex_x=x;p->vex_y=y+1; p->next=top;

- 6 -

top->direction=j;//当前结点在上一个结点的方向 top=p;find=1; }break; case 2:

if(x+1<=a.max_x&&!a.arry[x+1][y]&&!found(x+1,y,top)) {

p=(Point *)malloc(sizeof(Point)); p->vex_x=x+1;p->vex_y=y; p->next=top; top->direction=j; top=p; find=1; }break; case 3:

if(y-1>=1&&!a.arry[x][y-1]&&!found(x,y-1,top)) {

p=(Point *)malloc(sizeof(Point)); p->vex_x=x;p->vex_y=y-1;p->next=top; top->direction=j; top=p;find=1; }break; case 4:

if(x-1<=1&&!a.arry[x-1][y]&&!found(x-1,y,top)) { p=(Point *)malloc(sizeof(Point));

p->vex_x=x-1;p->vex_y=y;p->next=top;

top->direction=j; top=p; find=1; }break; }

if(find==1)

//若找到符合条件的结点，则j赋1，然后退出while循环 { j=1;break; }

else j++;//若没有，j加1 }

if(j>4)//4个方向都找不到符合条件的结点时. {

if(top->next!=NULL)//若top不空，则出栈，方向j加1 { p=p->next;top=p;

//使栈顶结点指向前一个节点，原节点删除 j=top->direction+1; top->direction=j;

- 7 -

} else return NULL;//若top空，则返回NULL }

}while(top->vex_x!=a.max_x || top->vex_y!=a.max_y);//若果当前结点不是出口，则继续进行do循环 return top; }

void disp(Point *po)//输出结果 {

int i=0,top=0;

Point *stack[maxsize];

if(po==NULL)cout<<\"没路\"<next; } cout<<\"迷宫通道如下：\"<1) { top--; cout<<\"(\"<vex_x<<\ack[top]->direction<<\")\";

i++; if(i%4==0) cout<top--;

cout<<\"(\"<vex_x<<\cout<void main() {

sd road; Point *po; road=creat(); po=secret(road); disp(po); }

- 8 -