四川大学锦江学院
数据结构课程设计报告
题目：迷宫求解问题
系 别： 计算机科学与工程系
专 业 ： 软件工程班
小组成员： 郭萌博 吴燕 蒋丽
指导教师： 李炳法
起止时间：2009-8
至
2009-12
迷宫求解问题
1、设计目的
仅认识到栈是一种特殊的线性表是远远不够的，本次实习的目的在于使读者深入了解栈的特
征，以便在实际问题背景下灵活运用它，同时还将巩固这种结构的构造方法。
2、问题描述
取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒子
中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置以块奶酪，
吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口
走到出口，而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。设计一个计算机程序
对任意设定的矩形迷宫如下图 A 所示，求出一条从入口到出口的通路，或得出没有通路的结论。
入口
出口
图解
3、设计要求
要求设计程序输出如下：
(1) 建立一个大小为 width * height 的任意迷宫 (迷宫数据可由用户输入或由程序自动生成)，
并在屏幕上显示出来；
(2) 找出一条通路；
(3) 用一种标志在迷宫中标出标出该条通路；
(4) 在屏幕上输出迷宫和通路；
(5) 上述功能可用菜单选择。
4、课程设计详细内容
① 需求分析：
迷宫程序设计的主要目地是完成实现自动寻找迷宫路径的算法，其次是完成用户接
口部分。
② 概要设计：
迷宫程序主要分为两大模块：用户界面接口模块、迷宫内部运行核心模块。用户界
面接口模块主要包块手动定义宽和高生成一个迷宫、随机生成迷宫、以及错误判断和退出程序。
迷宫内部运行的核心模块包括迷宫的生成，求解和打印。
③ 详细设计：
首先声明一下由于程序中用到了一些中文字符，所以必须在具有中文支持的
Windows 操作系统中才能正常运行，如果是 Linux 系统，还需要有相关的支持。
1. 迷宫内部运行核心模块：
A-迷宫生成：程序首先用一个二维数组代表一个 width × height 的矩阵，然后迷宫就
建立在这个矩阵上，用每个“细胞 (cell)”代表矩阵的交叉点，一个细胞有 6 个属性：up, right,
down, le!, visited, path。从迷宫第一个细胞起， 随机打开或者关闭一个或者几个方向，然后做
下访问过的标记直到最后一个细胞。这样就创建出了每个被访问过细胞的指针情况。
流程图：
定义 mp, visits,
path[direc&ons]
visits
开始
N
B-解迷宫：创建一个栈，从第一个细胞开始，顺时针判断每个细胞是否在创建时被访
问 (即是否在创建时留下指针信息) ，然后把没有被访问的依次入栈，同时每个细胞留下被访问
了的标记，如果遇到“死路” (即其余三个方向每个方向都被先前访问过) ，则依次出栈到岔路为
止然后继续寻找，最后访问到出口。
流程图：
direc&on=0
判断每个“细胞”位置，
得到相应的
path[direc&ons]
细胞是
否被访
问过
direc&o
ns
是否指
到最后
一个细
胞
visits--
随机生成 direc&ons
及 path[direc&ons],
然后把相应的指针附
给每个细胞。
指针指向第一个细胞
Y
Y
N
Y
N
Y
N
开始
定义一个栈并申请空间，
初始化指针位置
判断申请
是否失败
Y
