数据结构实验报告&迷宫求解&（一）
数据结构实验报告
一、需求分析
1以二维数组a[ROW][COL]表示迷宫。数组中以数字1表示障碍，数字0表示通路
2，用预先定好的迷宫作为原始迷宫文件
3设定的迷宫的路口和出口
4若设定的迷宫存在通路，则以‘#’表示障碍，‘*’表示通路打印出来
5.本程序只求出一条成功的通路
二、概要设计
设定栈的抽象数据类型定义：
ADT Stack{
数据对象：D={ai|ai属于CharSet，i=1、2…n，n&=0}
数据关系：R={&ai-1,ai&|ai-1,ai属于D，i=2,3,…n}
基本操作：
InitStack(&S)
&&&&&&&&&&&&&&&&
操作结果：构造一个空栈
Push（&S，e）
&&&&&&&&&&&&&&&&
初始条件：栈已经存在
&&&&&&&&&&&&&&&&
操作结果：将e所指向的数据加入到栈s中
Pop（&S,&e）
&&&&&&&&&&&&&&&&
初始条件：栈已经存在
&&&&&&&&&&&&&&&&
操作结果：若栈不为空，用e返回栈顶元素，并删除栈顶元素
Getpop（&S，&e）
&&&&&&&&&&&&&&&&
初始条件：栈已经存在
&&&&&&&&&&&&&&&&
操作结果：若栈不为空，用e返回栈顶元
StackEmpty(&S)
&&&&&&&&&&&&&&&&
初始条件：栈已经存在
&&&&&&&&&&&&&&&&
操作结果：判断栈是否为空。若栈为空，返回1，否则返回0
Destroy(&S)
&&&&&&&&&&&&&&&&
初始条件：栈已经存在
&&&&&&&&&&&&&&&&
操作结果：销毁栈s
}ADT Stack
设定迷宫的抽象数据类型定义
ADT yanshu{
数据对象：D={ai,j|ai,j属于{‘ ’、‘*’、‘@’、‘#’},0&=i&=M,0&=j&=N}
数据关系：R={ROW,COL}
ROW={&ai-1,j,ai,j&|ai-1,j,ai,j属于D，i=1,2,…M,j=0,1,…N}
COL={&ai,j-1,ai,j&|ai,j-1,ai,j属于D,i=0,1,…M，j=1,2,…N}
基本操作：
InitMaze(MazeType
&maze, int a[][COL], int row, int
初始条件：二维数组int a[][COL],已经存在，其中第1至第m-1行，每行自第1到第n-1列的元素已经值，并以值0表示障碍，值1表示通路。
操作结果：构造迷宫的整形数组，以空白表示通路，字符‘0’表示障碍
&&&&&&&&&&&&&&&
在迷宫四周加上一圈障碍
&&&&&&&&&&&&&
MazePath（&maze）{
&&&&&&&&&&&&&&&
初始条件：迷宫maze已被赋值
&&&&&&&&&&&&&&&
操作结果：若迷宫maze中存在一条通路，则按如下规定改变maze的状态；以字符‘*’表示路径上的位置。字符‘@’表示‘死胡同’；否则迷宫的状态不变
PrintMaze（M）{
初始条件：迷宫M已存在
操作结果：以字符形式输出迷宫
&&&&&&&&&&
本程序包括三个模块
主程序模块
void main()
构造迷宫；
迷宫求解；
迷宫输出；
栈模块——实现栈的抽象数据类型
迷宫模块——实现迷宫的抽象数据类型
求解迷宫一条路径的伪码算法
设定当前位置的初值为入口位置：
若当前位置可通，
则｛将当前位置插入栈顶；
若该位置是出口位置，则结束；
否则切换当前位置的东邻块为新的当前位置；
若栈不空且栈顶位置还有其他方向未被探索，
则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；
若栈不空但栈顶位置的四周均不可通，
则｛删去栈顶位置；
若栈不空，则重新测试新的栈顶位置，
直至找到一个可通的相邻块或出栈至栈空；｝
｝while(栈不空)
｛栈空说明没有路径存在｝
三、详细设计
1坐标位置类型
typedef struct{
//迷宫中的行
//......的列
}PosT//坐标&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
typedef struct{
int arr[RANGE][RANGE];
}MazeT&&&&&&&&&&&
//迷宫类型
InitMaze(MazeType
&maze, int a[][COL], int row, int
//设置迷宫的初值，包括边缘一圈的值
Bool MazePath(MazeType
&maze,PosType start, PosType end)
//求解迷宫maze中，从入口start到出口end的一条路径
//若存在，则返回true，否则返回false
Void PrintMaze（MazeType maze）
//将迷宫打印出来
typedef struct{
int&&&&&&&&&
//当前位置在路径上的"序号"
PosType&&&&&
//当前的坐标位置
DirectiveType&&
//往下一个坐标位置的方向
}SElemT//栈的元素类型
typedef struct{
SElemType *
SElemType *
栈的基本操作设置如下：
InitStack（SqStack & S）
//初始化，设S为空栈（S.top=NUL）
Void DestroyStack(Stack
//销毁栈S，并释放空间
ClearStack（SqStack & S）
//将栈S清空
StackLength（SqStack &S）
//返回栈S的长度
StackEmpty（SqStack &S）
？、若S为空栈（S.top==NULL），则返回TRUE，否则返回FALSE
GetTop（SqStack &S，SElemType e）
//r若栈S不空，则以e待会栈顶元素并返回TRUE，否则返回FALSE
Pop(SqStack&S，SElemType e)
//若分配空间成功，则在S的栈顶插入新的栈顶元素s并返回TRUE
//否则栈不变，并返回FALSE
Push(SqStack&S，SElemType &e)
//若分配空间程控，则删除栈顶并以e带回其值，则返回TRUE
//否则返回FALSE
StackTraverse（SqStack &S，Status）（*Visit）（SElemType e））
//从栈顶依次对S中的每个节点调用函数Visit
4求迷宫路径的伪码算法：
Status MazePath(MazeType
&maze,PosType start, PosType end){
//求解迷宫maze中,从入口start到出口end的一条路径
InitStack(s);
PosType curpos =
int curstep = 1;&&&&&&&&&&&&&&&
//探索第一部
if( Pass(maze,curpos) ){&&&
//如果当前位置可以通过,即是未曾走到的通道块
&&&&&&&&&&&
FootPrint(maze,curpos);&&&&&&&&&&&
//留下足迹
&&&&&&&&&&&
e = CreateSElem(curstep,curpos,1);&&&
//创建元素
&&&&&&&&&&&
Push(s,e);
&&&&&&&&&&&
if( PosEquare(curpos,end) )&&&
return TRUE;
&&&&&&&&&&&
curpos =NextPos(curpos,1);&&&&&&&&&&&
//获得下一节点:当前位置的东邻
&&&&&&&&&&&
curstep++;&&&&&&&&&&&&&&&&&&&&&&&&&&&
//探索下一步
}else{&&&&&&&&&&&&&&&&&&&&&&&
//当前位置不能通过
&&&&&&&&&&&
if(!StackEmpty(s)){
&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&
while(e.di==4 && !StackEmpty(s)
&&&&&&&&&&&&&&&&&&&
MarkPrint(maze,e.seat); Pop(s,e);&&
//留下不能通过的标记,并退回步
&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&
if(e.di&4){
&&&&&&&&&&&&&&&&&&&
e.di++; Push(s,e);&&&&&&&&&&&
//换一个方向探索
&&&&&&&&&&&&&&&&&&&
curpos = NextPos(e.seat,e.di);&&&
//设定当前位置是该方向上的相块
&&&&&&&&&&&&&&&
&&&&&&&&&&&
}while(!StackEmpty(s));
return FALSE;
//MazePath
四、调试分析
首先呢，想自己读入数据的，回来发现那样，很麻烦，所以还是事先定义一个迷宫。
栈的元素类型
一开始有点迷惑，后来就解决了
本题中三个主要算法；InitMaze，MazePath和PrintMaze的时间复杂度均为O（m*n）本题的空间复杂度也是O（m*n）
五、用户手册
1．本程序运行在windows系列的操作系统下，执行文件为：Maze_Test.exe
六、测试结果
Base.h&&&&&&&&&&&&&&
//公用的常量和类型
Stack.h&&&&&&&&&&&&&
Maze.h&&&&&&&&&&&&&
//迷宫类型
Maze_Test.c
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。数据结构实验报告--迷宫求解
1．实验要求
l&实验目的：
（1）进一步掌握指针、异常处理的使用；
（2）掌握栈的操作的实现方法；
（3）培养使用栈解决实际问题的能力
l&实验内容：利用栈实现迷宫求解问题，具体要求如下：
（1）可以使用递归或非递归两种方法实现；
（2）老鼠能够记住自己的路，不会反复走重复的路径；
（3）可以自己任意设置起点；
（4）必须要有异常处理，比如输入参数错误时应抛出异常
2.&程序分析
2.1&存储结构
&&&&&该程序采用栈的顺序存储结构，利用一组地址连续的存储单元依次存放老鼠在迷宫中的每一步路径，由于栈的插入和删除只能在栈顶实现，因此，每前进一步，表示该点的数组元素入栈，栈顶指针top+1；每后退一步，表示原来点的数组元素出栈，top-1。栈的操作示意如图(a)所示：
图(a)&栈的操作示意图
数据结构实验报告--迷宫求解下载
下载资料需要，并消耗一定积分。
下载此资料的人还喜欢：
技术交流、我要发言！ 发表评论可获取积分！ 请遵守相关规定。
本周热点资料
电子资料热门词
上传者其它资料
C语言|源代码下载排行数据结构与算法 - 编程入门网}