数据结构迷宫问题实验报告

竭诚为您提供优质文档/双击可除数据结构迷宫问题实验报告

篇一：数据结构-迷宫-实验报告与代码

一．需求分析

本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。程序执行的命令：1创建迷宫；2求解迷宫；3输出迷宫求解；

二．算法设计

本程序中采用的数据模型，用到的抽象数据类型的定义，程序的主要算法流程及各模块之间的层次调用关系

程序基本结构：

设定栈的抽象数据类型定义：

ADTstack{

数据对象：D={ai|ai∈charset，i=1,2,3,?..,n,n>=0;}

数据关系：R={|ai?1，ai∈D,i=2,?,n}

设置迷宫的抽象类型

ADTmaze{

数据对象：D={ai|ai∈‘’，‘@’，‘#’，‘1’,i=1,2,?,n,n>=0}数据关系：R={r,c}

r={|ai-1,ai∈D,i=1,2,?,n,}

c=|ai-1,ai∈D,i=1,2,?,n,}

结构体定义：

typedefstruct//迷宫中x行y列的位置

{intx;

inty;

}posType;

typedefstruct//栈类型

{intord;//通道块在路径上的“序号”

posTypeseat;//通道块在迷宫中的“坐标位置”

intdi;//从此通道块走向下一通道块的“方向”

}mazeType;

typedefstruct

{mazeType*base;

mazeType*top;

intstacksize;

}mazestack;

基本函数：

statusInitstack(mazestack

if(!s.base)

exit(oVeRFLow);

s.top=s.base+s.stacksize;

s.stacksize+=sTAcKIncRemenT;

}

*s.top++=e;

returnoK;

}

2）出栈操作

statuspop(mazestack

e=*--s.top;

returnoK;

}

3）判断栈是否为空

statusstackempty(mazestack

returneRRoR;

}

4）迷宫路径求解

statusmazepath(posTypestart,posTypeend)//迷宫路径求解{

posTypecurpos;

mazestacks;

mazeTypee;

intcurstep;

Initstack(s);

curpos=start;//设定当前位置为入口位置curstep=1;//探索第一步

cout{

if(pass(curpos))//当前位置可以通过，即是未曾走到的通道块{

Footprint(curpos);//留下足迹

e.ord=curstep;

e.seat=curpos;

e.di=1;

push(s,e);//加入路径

if(curpos.x==end.x

returnTRue;//到达终点（出口）

}

curpos=nextpos(curpos,e.di);//下一位置是当前位置的东邻

++curstep;//探索下一步

}

else//当前位置不能通过

{

if(!stackempty(s))

{

pop(s,e);

while(e.di==4//留下不能通过的标记pop(s,e);

cout}

if(e.di{

++e.di;//换下一个方向探索

篇二：数据结构试验报告-迷宫问题

实验报告：迷宫问题

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

一、需求分析：

1)采用二维数组maze[m][n]来表示迷宫，其中：maze[0][j]和maze[m-1][j](0≤j≤n-1)及maze[i][0]和maze[i][n-1](0≤i≤m-1)为添加在迷宫外围的一圈障碍。数据元素值0表示通路，1表示障碍。限定迷宫的大小m≤8，n≤10.

2)本次实验直接在主程序中输入表示迷宫的二维数组。另外，迷宫的入口和出口位置都将在主程序中直接设置。

3)实验中求出的迷宫通路用“-”表示，迷宫的障碍用“#”表示，已走过但未能求出通路的路径用“@”表示。

4)本程序只求出一条成功的通路。

5)本次实验将直接输出构建迷宫的二维数组、初始化的二维数组和求解后的迷宫数组。

二、概要设计：

数据结构及其抽象数据类型的定义。

（1）栈的抽象数据类型

ADTstack{

数据对象：D={ai|ai∈charset,i=1,2?n,n>=0}

数据关系：R1={|ai-1,ai∈D,i=2,?n}

基本操作：

Initstack(,#,@,*},0基本操作：

Initmaze(

#defineRAnge20//RAnge为实际分配的空间行列数

#definem8//maze数组的行数

#definen11//maze数组的列数

typedefstruct//表达迷宫元素位置信息的坐标

{

intr,c;

}posType;

typedefstruct//m，n为待处理的迷宫的行列数，RAnge为实际分配的空间行列数{

intm,n;

chararr[RAnge][RAnge];

}mazeType;

typedefintdirectiveType;//东西南北方向用1，2，3，4整数对应

typedefstruct//路径拟用栈来存储，此处定义栈元素中数据域的信息{

intstep;//存储到达该点时经历的步数

posTypeseat;//该点位置

directiveTypedi;//从该点位置走向下一位置的方向

}elemType;

typedefstructnodeType//路径拟用链栈来存储

{

elemTypedata;

structnodeType*next;

}nodeType,*LinkType;

typedefstruct//对链栈的头指针和元素个数进行封装

{

LinkTypetop;

intsize;

}stack;

//以上是对存储结构逐层进行定义

voidInitstack(stack

s.size=0;

}

statusmakenode(LinkType

if(!p)

returnFALse;

p->data=e;

p->next=nuLL;

returnTRue;

}

statuspush(stack

if(makenode(p,e))

{

p->next=s.top;

s.top=p;

s.size++;

returnTRue;

}

returnFALse;

}

statusstackempty(stacks)

{//判断是否为空栈，这里是通过top指针为nuLL来判断的，本质上也可以通过size是否为0来判断

if(s.top==nuLL)

returnTRue;

returnFALse;

}

statuspop(stack

if(stackempty(s))

returnFALse;

else

{

p=s.top;

s.top=s.top->next;

e=p->data;

s.size--;

free(p);

returnTRue;

}

}

statuspass(mazeTypemaze,posTypecurpos)

{//判断迷宫maze中，当前位置curpos是否是一个可达位置

intm,n;//注意这里的m，n只是表达下标的临时变量，与前面出现的m，n是不一样的

m=curpos.r;

n=curpos.c;

if(maze.arr[m][n]==)

returnTRue;

returnFALse;

}

statussame(posTypecurpos,posTypeend)

{//判断当前位置curpos是否已达出口

if(curpos.r==end.r

returnFALse;

}

voidFootprint(mazeType

m=curpos.r;

n=curpos.c;

maze.arr[m][n]=-;

}

posTypenextpos(posTypecurpos,intdi)

{//通过di的值，确定下一步的位置，下一步位置实际是当前位置的四个邻居中的一个

switch(di)

{

case1:

curpos.c++;//向东走

break;

case2:

curpos.r++;//向南走

break;

case3:

curpos.c--;//向西走

break;

篇三：数据结构迷宫问题实验报告

《数据结构与算法设计》

迷宫问题实验报告

——实验二

专业：物联网工程

班级：物联网1班

学号：15180118

姓名：刘沛航

一、实验目的

本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。

二、实验内容

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

三、程序设计

1、概要设计

（1）设定栈的抽象数据类型定义ADTstack{

数据对象：D={ai|ai属于charset，i=1、2…n，n>=0}

数据关系：R={|ai-1,ai属于D，i=2,3,…n}

基本操作：

Initstack(//迷宫中的行

intcol;//......的列

}posType;//坐标

（2）迷宫类型：

typedefstruct{

intm,n;

intarr[RAnge][RAnge];

}mazeType;//迷宫类型

voidInitmaze(mazeType//当前位置在路径上的"序号"

posTypeseat;//当前的坐标位置

DirectiveTypedi;//往下一个坐标位置的方向

}selemType;//栈的元素类型

typedefstruct{

selemType*base;

selemType*top;

intstacksize;

}sqstack;

栈的基本操作设置如下：

VoidInitstack（sqstack

posTypecurpos=start;

intcurstep=1;//探索第一部

do{

if(pass(maze,curpos)){//如果当前位置可以通过,即是未曾走到的通道块

Footprint(maze,curpos);//留下足迹

e=creat