数据结构课程设计报告
         
    题目：迷宫问题非递归求解
       
 
                 
2010年  6月    4日
                       
一. 实验内容………………………….3
二. 需求分析……………………………3
三．总体设计……………………………4
四．详细设计……………………………6
五．代    码……………………………10
六. 测    试…………………………….15
七. 总    结…………………………….17
一.实验内容
任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；
要求：
二.需求分析
1.可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径
输出；
要求：使用非递归算法。
2.用户可以根据自己的需求进行输入所需的迷宫，其中1表示迷宫的墙壁，0表示迷宫的通路，从而建立自己的迷宫；
3.用户还可以自己设计迷宫的入口坐标，当然也可以设计出口了；
4.程序执行的命令包括：
    （1）构造栈Stack, T 描述迷宫中当前位置的结构类型, LinkNode链表结点三个类,其中Stack是Linknode的友元类.
（2）构造存取迷宫的二维指针GetMaze(int &m,int &n)
（3）恢复迷宫Restore(int **maze,int m,int n)  （
4）在迷宫中寻一条通路Mazepath(int **maze,int m,int n)    c语言while语句流程图
（5）输出所到的通路PrintPath()
(6) 定义当前位置移动的4个方向move数组.
三．总体设计
存储结构：
首先用二维指针存储迷宫数据，迷宫数据由用户输入。
一个以链表作存储结构的栈类型，然后编写一个求解迷宫的递归或非递归程序。求得的通路以三元组（i，j，d）形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向（东、南、西、北四个方向所用代表数字，自行定义）。
1．从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。
迷宫的入口点的下标为（1，1），出口点的下标为（m，n）。为处理方便起见，可在迷宫
的四周加一圈障碍。对于迷宫的任一位置，均可约定有东、南、西、北四个方向可通。经过的位置把0变为-1，带输出迷宫路径后在恢复迷宫院士为止
2. 本程序有三个模块：
⑴ 主程序模块
⑵ 三个类模块即其对象：实现栈链表抽象数据类型；
⑶ 迷宫二维指针单元模块：存储迷宫,,寻路径,输出迷宫,恢复迷宫。
(二)流程图
四．详细设计
(一).基本算法：
首先用二维指针存储迷宫数据，迷宫数据由用户输入。
一个以链表作存储结构的栈类型，然后编写一个求解迷宫的递归或非递归程序。求得的通路以三元组（i，j，d）形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向（东、南、西、北四个方向所用代表数字，自行定义）。
迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按东、南、西、北4个方向顺序试探下一个位置；如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索；如果4方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。
每前进或后退一步，都要进行判断：若前进到了出口处，则说明到了一条通路；若退回到了入口处，则说明不存在通路。
用一个二维指针数组迷宫表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。迷宫的入口点在位置（1，1）处，出口点在位置（m,n）处。设计一个模拟走迷宫的算法，为其寻一条从入口点到出口点的通路。
二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”， 表示迷宫的外墙；第1行第1列元素和第m行第m列元素置成“0”， 表示迷宫的入口和出口；其余元素值用GetMaze函数获取.
假设当前所在位置是（x,y）。沿某个方向前进一步，它可能到达的位置最多有4。
如果用二维数组move记录4方向上行下标增量和列下标增量，则沿第i个方向前进一步，可能到达的新位置坐标可利用move数组确定：
        x=x+move[loop][0]
        y=y+move[loop][1]
从迷宫的入口位置开始，沿图示方向顺序依次进行搜索。定义一个栈，按从入口到出口存取路径.
在搜索过程中，每前进一步，如果有新位置入栈，则把上一个探索的位置存入栈中,当前位置”-1”（表示这个位置在通路上），并将该位置的坐标压入栈中。
如果没有新位置入栈，则返回到上一个位置.
到达出口后,最后一个位置入栈,输出路径,并回复路径.把-1变为0.
总之,入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。
迷宫的入口点的下标为（1，1），出口点的下标为（m，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫的任一位置，均可约定有东、南、西、北四个方向可通。
(二). 为实现算法，需要类的象数据类型：
类及其对象:
类 Stack             对象成员如下:
Stack();            构造函数，置空栈操作结果：构造一个空的栈S。
Stack();            析构函数
void Push(T e);    把元素data压入栈中
T Pop();          使栈顶元素出栈
T GetPop();      取出栈顶元素
void Clear();    把栈清空
bool empty();    判断栈是否为空，如果为空则返回1，否则返回0
T类              迷宫中当前位置的结构类型:
T对象成员如下:

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。