1、 数据结构课程设计报告 题目：迷宫问题 姓名： 学号： 班级： 指导教师： 2012 年 6 月 6 日 1. 问题描述 2 输入任意大小的迷宫数据，用递归和非递归方法求出一条走出迷宫的路径，并将 路径输出。 2. 设计思路 以 0 和 1 分别表示迷宫中的通路和障碍，没有通路则不显示。未显示为得出没有 通路的结论； 走迷宫的方式是一个一个的线路去试 如果是死路的话就退回去，类似数据结 构中栈的先进后出， 所以可以用栈这种结构表示迷宫，通过不断的试验当试出最后 的路线时输出栈即可，由于它是不断循环的实验，所以可以采用链栈实现迷宫的求 解。同时因为迷宫需要不断重复的试验，可以看成反复的调用“迷宫
2、“这个函数， 这是典型的递归问题，所以也可以使用递归解决问题。另外由于数据对象是迷宫所 以可以用 0 和 1 构建不同类型的迷宫更符合实际也更有乐趣。 3. 数据结构设计 前面提到要用到链栈和递归两种方式操作；为了更好的以链表作存储结构的栈， 可以用二维数组存储迷宫信息，同时通路以三元组（i，j，d）的形式输出，其中： （i，j）指示迷宫中的一个坐标，d 表示走到下一个坐标的方向。这样是路径更加 明显，具体的数据结构为： #define maxsize 100 #define NULL 0 typedef struct /定义迷宫定义迷宫 int Mazemaxsizemaxsize; /二维
3、数组存放迷宫信息二维数组存放迷宫信息 int maze_x,maze_y; /迷宫的行数和列数迷宫的行数和列数 maze; typedef struct point /链栈的每个结点链栈的每个结点定义定义 int vex_x,vex_y; /结点的横纵坐标结点的横纵坐标 int direction; /下一个结点的方向下一个结点的方向 struct point *next; /指向下一个结点指向下一个结点 Point; 3 递归法像一位手握大权的领导。当他站在迷宫入口处时，他才懒得亲自去走，这 时这位领导会吩咐他的手下，让他们分别向着迷宫的各个方向去探索；当遇到岔 路口时留一个人守在这里，再分
4、出几股人，朝着每个方向继续探索；最后总会有 一个人发现出口。发现出口的这个人将出口的位置报告给离他最近的路口处留守 的人，再由这个人报告给上一个路口的人，依次层层上报，最后消息传到了领导 那里，于是这位领导就顺着这条画好的通路大摇大摆地通过了迷宫。所以具体的 数据结构为： #include #include #define maxsize 100 #define NULL 0 typedef struct /定义迷宫定义迷宫 int Mazemaxsizemaxsize; /二维数组存放迷宫信息二维数组存放迷宫信息 int maze_x,maze_y; /迷宫的行数和列数迷宫的行数和列数 maze; maze a; typedef struct point /链栈的每个结点定义链栈的每个结点定义 int vex_x,vex_y; /结点的横纵坐标结点的横纵坐标 int direction; /下一个结点的方向下一个结点的方向 struct point *next; /指向下一个
