C++迷宫问题实验报告

数据结构集中上机

试验报告

学院： 计算机科学与技术 专业：计算机科学与技术学号：00000000 班级：（6） 姓名：

20010.10.27

题目：编制一个求解迷宫通路的程序

以一个M*N的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

实验要求： 实现一个以链表作存储结构的栈类型。然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i , j , d）的形式输出，其中（i , j ）指示迷宫中的一个坐标，d表示走到下一坐标的方向。

实验过程：

1.基本算法以及分析：

本程序主要是以链表构造栈的形式，寻找迷宫路径，根据创立的结点，输入结点里的一些数据，如下

struct Stack //构造栈

{

int Maze_x,Maze_y; //定义迷宫X，Y坐标

Stack * next; //定义栈指针

};

程序由主函数开始，首先，定义一个二维数组迷宫。选择开始坐标点，然后，开始入栈，利用各个位置的判断循环建立结点，记录各个位置的数据，若走进死胡同则退栈，并且判断是否栈空，找到路径并到达出口后将栈倒置，使其按从入口到出口的顺序输出，之后调用迷宫图案输出

函数，使其按要求输出。

2.程序源代码：

迷宫问题

#include

#include

using namespace std;

struct Stack //构造栈

{

int Maze_x,Maze_y,Maze_z; //定义迷宫X，Y坐标,z方向 Stack * next; //定义栈指针

};

Stack *ps; //链头指针

void Pop() //出栈函数

{

Stack *p;

p = ps;

ps=ps->next;

delete p;

}

void push(int x,int y,int z) //进栈 函数

{

Stack *t;

t = new Stack;

t->Maze_x = x;

t->Maze_y = y;

t->Maze_z = z;

t->next = ps;

ps = t;

}

void Mazepath(int a[][10],int i,int j) //迷宫路线寻找 函数

{

a[i][j]=2;

int c,d,m=1; //定义变量c,d为出口坐标,变量m作为走过的步数

coutc>>d;

while(i!=c || j!=d) //判断是否到达出口 {

if(a[i][j+1]==0) //判断右边是否可行 {

push(i,j,1);

j++;

a[i][j] = 2; //标记走过的位置

}

else if(a[i+1][j]==0)

{

push(i,j,2);

i++;

a[i][j] = 2;

}

else if(a[i][j-1]==0)

{

push(i,j,3);

j--;

a[i][j] = 2;

}

else if(a[i-1][j]==0)

{

push(i,j,4);

i--;

a[i][j] = 2;

}

else

{

int e1,e2;

Stack *p;

p = ps;

ps=ps->next;

e1=p->Maze_x;

e2=p->Maze_y;

a[e1][e2]=3;

delete p;

i = ps->Maze_x;

j = ps->Maze_y;

if(ps==NULL) //判断下边是否可行 //标记走过的位置 //判断左边是否可行 //标记走过的位置 //判断上边是否可行 //标记走过的位置 //四个方向都不可行，退栈 //标记走过的死胡同坐标 //删除栈顶元素 //判断栈空否

出 } { coutnext;

pk->next = t;

}

Stack *k=pk;

pk = pk->next;

delete(k); //释放PK空间

while(pk!=NULL) //输出走过的坐标

{

cout