c语言迷宫问题的求解(栈和递归) 下载本文

实验报告

【实验名称】 【实验目的】

1. 了解栈的基本操作以及充分理解栈的特点。熟悉掌握栈的基本操作和结构体的运用。

2. 学会用栈或者递归方法解决迷宫问题。

项目一 迷宫问题的求解

【实验原理】

1.本次实验中,以二维数组maze[row][col]表示迷宫,0表示通路,1表示墙,在构建迷宫时,为了清晰显示,在最外层添加一圈墙。

2.算法的核心思想是利用栈后进先出的特点,对迷宫进行探索,如果此路可行,则将此坐标的信息入栈,如果此路不通,则将此坐标的信息出栈。

3.输入形式:根据控制台的提示,依次输入迷宫的行数、列数,然后输入迷宫,再输入入口和出口坐标。

4.输出形式:由用户选择,由递归、非递归两种求解方式输出一条迷宫通路。以非递归方式会显示一种求解方案,并给出相应的三元组序列和迷宫方阵;以递归方式则会显示出所有的路线。

【实验内容】

1. 需求分析 (1) 问题描述

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

要求以递归和非递归两种方式分别输出一条迷宫的通路,以带方向坐标和迷宫图像表示。

(2) 基本要求

(1)首先实现一个以链表作存储结构的栈类型,然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出。其中:(i,j)指示迷宫中的一个坐标,d表示走到下一坐标的方向。如,对于下列数据的迷宫,输出一条通路为:(1,1,1),(1,2,2),(2,2,2),(3,2,3),(3,1,2),…。

(2)编写递归形式的算法,求得迷宫中所有可能的通路。 (3)以方阵形式输出迷宫及其通路。

2. 概要设计

(1) 栈的抽象数据类型 ADT Stack{

数据对象:D={ai|ai∈ElemSet, i=1,2, …,n, n≥0} 数据关系:R1={|ai-1,ai∈D, i=1,2, …,n } 约定an端为栈顶,a1端为栈底。 基本操作:

InitStack( &S )

操作结果:构造一个空栈S。 DestroyStack ( &S )

初始条件:栈S已存在。 操作结果:销毁栈S。 ClearStack( &S )

初始条件:栈S已存在。 操作结果:将S清为空栈。 StackEmpty( S )

初始条件:栈S已存在。

操作结果:若S为空栈,则返回TRUE,否则返回FALSE。 StackLength( S )

初始条件:栈S已存在。

操作结果:返回S的数据元素个数,即栈的长度。 GetTop( S, &e )

初始条件:栈S已存在且非空。 操作结果:用e返回S的栈顶元素。 Push( &S, e )

初始条件:栈S已存在。

操作结果:插入元素e为新的栈顶元素。 Pop( &S, &e )

初始条件:栈S已存在且非空。

操作结果:删除S的栈顶元素,并用e返回其值。 }ADT Stack

(2) 程序模块

A. 主程序模块: int main() { }

B. 栈模块:

实现栈抽象数据类型 C. 迷宫模块:

实现迷宫抽象数据类型

3. 详细设计 (1) 类型定义

typedef struct {

int x; int y;

}coordinate; //迷宫中坐标类型

typedef struct {

int x; //x行 int y; //y列

int d; //下一步的位置 }SElemType;//数据类型

typedef struct Stack {

SElemType elem; struct Stack *next;

}Stack,*LinkStack; //链栈定义 (2) 递归求解算法

void MazePath2(int maze[M][N],int a,int b,coordinate end,int m,int n) //采用递归的方式进行四个方向的探索 {

maze[a][b]=-1; //起点标记为-1,即一定正确的通路,每次递归便将递归的坐标标记为正确的通路

if(a==end.x&&b==end.y) {

printf(\

PrintMaze2(maze,m,n); //找到了路径,绘制地图 }

if(maze[a][b+1]==0)

MazePath2(maze,a,b+1,end,m,n); //向右探索