算法与数据结构 课程设计
课题：求解迷宫通路的图形界面演示程序
作者：吴昊 QQ：328035823
1
目录
1.题目及需求分析········································4 2.概要设计··············································4 3.详细设计·············································10 4.调试分析·············································39 5.课程设计总结·········································42
2
1．题目及需求分析
1.1题目
编制一个求解迷宫通路的图形界面演示程序。
1.2需求分析
1. 输入一个任意大小的迷宫，任设起点、终点、障碍，用栈求出一条走出迷宫的路径，并
显示在屏幕上；
2. 根据用户界面提示，用键盘输入，Home键设置迷宫起点，End键设终点，上下左右箭头
键移动，Enter键添加墙，Del键删除墙，完成后按F9键演示，演示完毕后可F5刷新题图，重新对地图的起点、终点、障碍进行设置，Esc键退出；
3. 本程序要求至少得出一条成功的通路，也可求得全部路径。此外，也可尝试保存或载入
测试文件（此功能不做强行要求）。
4. 当未输入起点时，消息显示“Error： You must set the START.”；未输入终点时，显
示“Error： You must set the END.”；找到路径时，屏幕显示足迹，并在消息框出现Path found，否则消去足迹，显示Path not found。
5. 用户可以通过界面上提供的菜单选项，选择“帮助”查看操作说明。
6. （算法选优）用户可以通过界面上提供的菜单选项，选择“A*算法求最短路径”演示求
解迷宫最短路径。
2.概要设计
根据需求分析的用户界面的设计要求，考虑到我们在Java课程中学习过GUI设计，对Java的GUI的比较熟悉，所以我们用Java语言来开发本项目。
在设计求解迷宫的程序时，要求编写8个Java源文件：Dialog.java、Maze.java、MazeGUI.java、Position.java、Rollback.java、stack.java、Astar.java和Aposition.java。
该程序除了上述6个Java源文件所给出的类以外，还需呀Java系统提供的一些重要的类，如java.awt包中的容器类、画图类、事件类及监听器接口、javax.swing包中的各种轻量组件类和java.lang包中线程类等。
3
2.1 UML类图
程序的所用到的一些重要的类以及之间的关联关系如图2-1所示。
图2-1 UML类图
2.2 Dialog.java(主类)
Dialog.java(主类)是JDialog类的一个子类。该类负责创建提示用户输入迷宫大小的对话框，通过用户输入的参数来确定所要创建的迷宫图形界面的窗口的大小。该类含有main方法，程序从该类开始执行。Begin类的成员变量有JTextField、JButton、JFrame。Begin类的主要成员和成员方法的作用将在后面的详细设计中阐述。
2.3 Maze.java
Maze类创建的对象是MazeGUI类和Rollback类最重要的成员之一，代表迷宫。该类负责接收在迷宫窗口所设置起点、终点、障碍的位置参数来绘制迷宫图像并存储迷宫结构的信息。该类的主要成员变量有3种类型的对象：Position、Image以及存放整型数的二维数组。Maze类的主要成员和成员方法的作用将在后面的详细设计中阐述。
2.4 MazeGUI.java
MazeGUI类是Frame类的一个子类，创建的对象是Rollback类最重要的成员之一。该类负责创建迷宫图形窗口界面，方便用户在界面上设置起点、终点、障碍等并展现求解迷宫的过程。该类的主要成员变量有4种类型的对象：Maze、Rollback、Position和Thread。该类还包含一个内部类SolveThread，该内部类实现了runnable接口。MazeGUI类的主要成员和成员方法的作用将在后面的详细设计中阐述。
4
2.5 Position.java（图形界面坐标的存储结构）
Position类创建的对象是Maze类、MazeGUI类和Rollback类最重要的成员之一。该类负责在Maze类、MazeGUI类和Rollback类之间传递消息，其对象存有当前位置的坐标信息。该类包含两个整型的成员变量x和y，记录当前位置在迷宫图形界面的横、纵坐标。Position类的主要成员和成员方法的作用将在后面的详细设计中阐述。
2.6 Stack.java（数据类型结构）
为了体现算法与数据结构的课程特点，我们并没有用Java系统类库中java.Util.Stack类，而是编写了一个通用的Stack存储结构。
Stack类创建的对象是Rollback类的最重要的成员之一。该类负责保存在求解迷宫过程中所走过的路径信息。该类包含一个内部类Node，定义了栈中存储的节点元素的类型。另外还含有一个整型成员变量n和一个Node类型的成员变量top，分别记录栈中元素的个数以及栈顶元素的信息。而Node类定义的是栈中节点的类型，包含当前节点的信息info（Object类型）和以及栈中下一个元素的引用next（相当在C语言中的指针）。Stack类的主要成员和成员方法的作用将在后面的详细设计中阐述。
2.7 Rollback.java（核心算法—回溯算法）
Rollback类创建的对象是是MazeGUI类最重要的成员之一。该类负责根据Maze类中的迷宫数组的信息采用回溯算法，控制并绘制人物在迷宫图形界面窗口中的位置。该类的主要成员变量有4种类型的对象：Maze、MazeGUI、Position和Stack。Rollback类的主要成员和成员方法的作用将在后面的详细设计中阐述。
2.8 Astar.java（核心算法—A*算法）
Astar类创建的对象是是MazeGUI类最重要的成员之一。该类负责根据Maze类中的迷宫数组的信息采用A*算法，找到起点到终点的最短路径并打印出来。该类的主要成员变量有4种类型的对象：Maze、APosition、Stack和LinkedList。Astar类的主要成员和成员方法的作用将在后面的详细设计中阐述。
2.9 Aposition（A*算法的存储结构）
Aposition类是Position类的派生类，APosition类创建的对象是Astar类、MazeGUI类和Rollback类最重要的成员之一。该类负责在Astar类、MazeGUI类和Rollback类之间传递消息，其对象存有当前位置的坐标信息、A*算法的评估函数值、开关标记和父节点等。APosition类的主要成员和成员方法的作用将在后面的详细设计中阐述。
5