学号专业计算机科学与技术姓名
实验日期2017.6.20教师签字成绩
实验报告
【实验名称】迷宫问题的求解
【实验目的】
(1)通过本课程的学习,能熟练掌握几种基本数据结构的基本操作。
(2)能针对给定题目,选择相应的数据结构,分析并设计算法,进而给出问题的正确求解过程并编写代码实现。
(3)用递归和非递归两种方式完成迷宫问题的求解。
【实验原理】
迷宫问题通常是用“穷举求解”方法解决,即从入口出发,顺着某一个方向进行探索,若能走通,则继续往前走;否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通路。假如所有可能的通路都探索到而未能到达出口,则所设定的迷宫没
有通路。栈是一个后进先出的结构,可以用来保存从入口到当前位置的路径。
【实验内容】
1 需求分析
1.基本要求:
(1)首先实现一个以链表作存储结构的栈类型,然后编写一
个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)
的形式输出。其中:(i,j)指示迷宫中的一个坐标,d表示
走到下一坐标的方向。如,对于教材第50页图3.4所示的迷
宫,输出一条通路为:(1,1,1),(1,2,2),(2,2,
2),(3,2,3),(3,1,2),…
(2)编写递归形式的算法,求得迷宫中所有可能的通路。
(3)以方阵形式输出迷宫及其通路。
(4)按照题意要求独立进行设计,设计结束后按要求写出设
计报告。
2.输入输出的要求:
(i) 求得的通路以三元组(i,j,d)的形式输出,其中:(i,
j)指示迷宫中的一个坐标,d表示走到下一个坐标的方向。
(ii)输出迷宫示意图
3.程序所能达到的功能:
(i) 实现一个以链表作存储结构的栈类型,以非递归算法求出
通路
(ii)以一个递归算法,对任意输入的迷宫矩阵求出所有通路。
2 概要设计
1.①构建一个二维数组maze[M][N]用于存储迷宫矩阵
②手动生成迷宫,即为二维数组maze[M][N]赋值
③构建一个栈用于存储迷宫路径
④建立迷宫节点用于存储迷宫中每个节点的访问情况;
非递归
本程序包含6个函数:
(1)主函数 main()
(2)生成迷宫 create_maze()
(4)打印迷宫 print_maze()
(5)搜索迷宫路径并用三元组输出路径 mgpath()
(6)用图来输出路径print_tu();
递归
本程序包含3个函数:
(1)主函数main();
(2)打印迷宫printmaze();
(3)搜索迷宫路径pass(int x,int y);
3. 详细设计
1.非递归
起点和终点的结构类型 typedef struct{
int h;
int l;
}T;
栈节点类型 typedef struct cell{
int row;
int col;
int dir;
}TCell;
1.生成迷宫
void creat_maze(int a,int b)
{定义i,j为循环变量