一.需求分析
本程序是利用非递归的方法求出一条走出迷宫的路径,并将路径输出。首先由用户输入一组二维数组来组成迷宫,确认后程序自动运行,当迷宫有完整路径可以通过时,以0和1所组成的迷宫形式输出,标记所走过的路径结束程序;当迷宫无路径时,提示输入错误结束程序。程序执行的命令:1创建迷宫 ;2求解迷宫;3输出迷宫求解;
二.算法设计
本程序中采用的数据模型,用到的抽象数据类型的定义,程序的主要算法流程及各模块之间的层次调用关系
程序基本结构:
设定栈的抽象数据类型定义:
ADT Stack {
数据对象:D={ai|ai∈CharSet,i=1,2,3,?..,n,n>=0;} 数据关系:R={<ai?1,ai >|ai?1,ai∈D,i=2,?,n}
设置迷宫的抽象类型
ADT maze{
数据对象:D={ai|ai∈‘ ’,‘@’,‘#’,‘1’,i=1,2,?,n,n>=0} 数据关系:R={r,c}
r={<ai-1,ai>|ai-1,ai∈D, i=1,2,?,n,}
c=<ai-1,ai>|ai-1,ai∈D, i=1,2,?,n,}
…… …… 余下全文
数据结构实验报告
实验三 迷宫
姓名:xxx
学号:xxx
专业:信息安全
实验日期:第十二.三周周日
实验三 迷宫
一、实验目的
1、了解回溯法在求解迷宫问题中的应用
2、进一步掌握栈的使用
二、实验内容
用回溯法求解迷宫问题,可以用一个栈保存探索的序列。并且在该迷宫的行走中,站在一点可以有八个方向选择。
比如如下的迷宫
Enter-> 0 1 1 1 0 0 0 0 0 0
0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 0 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 1 1 0 1 1 0 1 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 --> EXIT
…… …… 余下全文
数 据 结 构
实验报告书
广东机电职业技术学院
20##年5月
目录
一、实验要求(需求分析)... 3
a. 实验目的... 3
b. 实验内容... 3
c.程序功能... 3
二、程序分析... 4
2.1 存储结构... 4
2.2 关键算法分析... 4
三、程序运行分析... 8
1.程序运行流程图:... 8
2.程序运行结果截图:... 9
四.总结... 11
五、附录... 12
20##级数据结构实验报告
实验名称:迷宫求解问题
学生姓名:黄若海
班 级:软件1004班
学 号: 07100415
日 期: 2011年6月2日
通过实验,掌握如下内容:
Ø 进一步掌握指针、模板类、异常处理的使用
Ø 掌握队列的操作的实现方法
…… …… 余下全文
//////////By Lea//////////////
////////2010210501////////////
#include<stdio.h>
#include<stdlib.h>
/*数据定义*/
typedef enum { ERROR, OK } Status;
typedef struct
{
int row; //row表示"行"号
int line; //line表示"列"号
…… …… 余下全文
数据结构实验报告——
迷宫求解问题实验
上机环境: DevC++
二、程序设计相关信息
(1)实验题目:迷宫求解问题
问题描述:
实验题3.5 改进3.1.4节中的求解迷宫问题程序,要求输出如图3.14所示的迷宫的所有路径,并求最短路径长度及最短路径。
(2)实验项目组成:
本项目由一个原程序mg.cpp及mg.exe文件组成。
(3)实验项目的程序结构:
函数调用关系图:
(4)实验项目包含的函数的功能描述:
mg[M+1][N+1] //构造迷宫二维数组,1表示墙不可走方块,0表示通道
mgpath(int xi,int yi,int xe,int ye)
//求解路径为:(xi,yi)->(xe,ye)
//采用顺序栈存储,进栈,回溯,退栈等
(5)算法描述:
求解迷宫从入口到出口的所有路径,从入口出发,顺某一个方向向前试探,对于可走的方块都进栈,并将这个可走发方位保存,且top+1,然后试探下一个方块,若下一个方块能走通则继续,否则则回溯到前一个方块,且top-1。为记录所有的路径调用Path[k]=Stack[k]记录,从次方块向不同方向去试探,已经走过的方块则为不可走方块。最后比较top值找到一条最短路径并输出。
…… …… 余下全文
数据结构课程设计
课程设计日期:
实验题目
一、问题描述
输入一个任意大小的迷宫数据,用递归和非递归两种方法求出一条走出迷宫的路径,并将路径输出。
二、实现目标
综合运用递归、栈等数据结构知识,掌握、提高分析、设计、实现及测试程序的综合能力
三、主要功能模块及实现功能
(创建一顺序栈:
PSeqStack Init_SeqStack(void)
判断栈是否为空:
int Empty_SeqStack(PSeqStack S)
在栈顶插入一新元素x:
int Push_SeqStack (PSeqStack S, DataType x)
删除栈顶元素并保存在*x :
int Pop_SeqStack(PSeqStack S ,DataType *x)
销毁栈 :
void Destroy_SeqStack(PSeqStack *S)
利用栈的非递归算法求迷宫路径:
int mazepath(int maze [ ][n+2] ,item move[ ],int x0,int y0)
…… …… 余下全文
评分依据及结果
一、 需求分析
1.问题描述:
以一个m*n的长方阵表示迷宫,空格和感叹号分别表示迷宫中的通路和障碍。设计一个程序,对随机产生的迷宫,求一条从入口到出口的通路,或得出没有通路的结论。
2.基本要求
首先实现一个以链表为存储结构的栈类型,然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出。
其中(i,j)表示迷宫的一个坐标,d表示走到下一座标的方向。
3.程序的执行命令有:
1)输入迷宫的列数 2)输入迷宫的行数
二、 概要设计
为实现上述功能,需要以一个链表为存储结构的栈类型
1. 栈的顺序存储表示
typedef struct
{
int x; /*列*/
…… …… 余下全文
实验报告:迷宫问题
题目:编写一个求解迷宫通路的程序
一、 需求分析:
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) 实验中求出的迷宫通路用“-”表示,迷宫的障碍用“#”表示,已走过但未能求出通路的路径用“@”表示。
…… …… 余下全文