迷宫问题——数据结构课程设计迷宫问题.doc

*******************
实践教学
*******************
兰州理工大学
计算机与通信学院
2012年春季学期
算法与数据结构课程设计
题目: 迷宫问题

专业班级:计算机科学与技术一班
姓名: 程文鑫
学号:
指导教师: 张永
成绩:
目录
摘要 3
前言 4
正文 5
一、采用c++语言定义相关的数据类型 5
二、各模块的伪码算法 6
三、函数的调用关系图 10
四、调试分析 11
五、测试结果 11
1、开始界面 12
2、自动生成迷宫运行情况 12
3、键盘输入迷宫运行情况 14
总结 16
致谢 17
参考文献 18
附录 19
源程序(带注释) 19
摘要
本程序主要是对任意给定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。使我们基本掌握线性表及栈上基本运算的实现,进一步理解和熟练掌握课本中所学的各种数据结构,学会如何把学到的知识用于解决实际问题,培养我们的动手能力。
1、生成迷宫:根据提示输入数据,然后生成一个8行8列的迷宫。
2、探索迷宫路径:由输入的入口位置开始,对相邻的(上,下,左,右)四个方向的方块进行探索,若可通则“纳入路径”,否则顺着“来向”退到“前一通道块”,朝着“来向”之外的其它方向继续探索。
3、保存迷宫路径:若探索到出口则把探索到的路径压入另一个栈中,并最后弹出路径坐标,输出在屏幕上。

关键字:栈,栈的存储结构,出栈与入栈
前言
求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前探索,若能走通,则继续往前走;否则沿原路退回,换一个方向再继续探索,直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回,显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此,在求迷宫通路的算法中应用“栈”也就是自然而然的事。迷宫问题要求,所求路径必须是简单路径,即在求得路径上不能同时重复出现同一通道。在迷宫中用1和0分别表示迷宫中的通路和障碍。
首先,输入迷宫数据,在计算机的屏幕上显示一个8行8列的矩阵表示迷宫。矩阵中的每个数据或为通路(以0表示),或为墙(以1表示),所求路径必须是简单路径,即在求得的路径上不能重复出现同一道块。
其次,假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”,则求迷宫中一条路径的算法的基本思想是:若当前位置“可通”,则“纳入当前路径”,并继续朝“下一个位置”探索,即切换“下一位置”为“当前位置”,如此重复直到到达出口;若当前位置“不可通”,则应顺着“来向”退回到“前一通道块”,然后朝着除“来向”,之外的其它方向继续探索,若该通道块的四周四个方块均“不可通”,则应该从“当前路径”上删除该通道块,所谓“下一个位置”指的是“当前位置”四周四个方向(上,下,左,右)上相邻的方块。假设以栈S记录“当前路径”,则栈顶中存放的是“当前路径上最后一个通道块”。由此,“纳入路径”的操作为“当前位置入栈”;从当前路径删除前一通道块的操作为“出栈”。
最后,若找到出口,则从栈中弹出数据,在屏幕上显示从入口到出口的路径坐标。最后希望通过对该课题的设计,理解和掌握所学到的各种数据结构,学会把学到的知识应用于解决实际的问题当中,培养自己的动手能力。
正文
一、采用c++语言定义相关的数据类型
1、定义坐标(X,Y):
#include<iostream>
#include<fstream>
using namespace std;
struct Coor
{
int row;
int column;
int direction;
};
2、定义方向:
struct Move
{
int row;
int column;
};
3、定义/链表结点:
struct LinkNode
{
Coor data;
LinkNode *next;
};
4、定义栈:
class stack
{
private:
LinkNode *top;
public:
stack();
~stack();
void Push(Coor data);
Coor Pop();
Coor GetPop();
void Clear();
bool IsEmpty();
};
5、定义迷宫定义移动的4个方向:
Move move[4]={{0,1},{1,0},{0,-1},{-1,0}};
6、几个函数功能的描述:
stack();