} }
public boolean equals(Object o){ }
if(o == null){ }
if(!(o instanceof Position)){ }
Position p =(Position) o;
return this.x == p.x && this.y == p.y;
return false; return false;
3.6 Stack.java (数据结构类型)
3.6.1 UML图
Stack类创建的对象是Sprite类的最重要的成员之一。该类负责保存在求解迷宫过程中所走过的路径信息。该类包含一个内部类Node，定义了栈中存储的节点元素的类型。另外还含有一个整型成员变量n和一个Node类型的成员变量top，分别记录栈中元素的个数以及栈顶元素的信息。而Node类定义的是栈中节点的类型，包含当前节点的信息info（Object类型）和以及栈中下一个元素的引用next（相当在C语言中的指针，这儿类似与链式存储的栈）。标明Stack类的主要成员变量、成员方法的UMl图如图8所示。
图8 Stack类的UML图
以下是UML图中有关数据和方法的详细说明。 1） 成员变量
? top是Node类的对象，表示栈定元素。
? n是int类型的变量，表示栈中元素的个数。 2） 成员方法 ? push(Object o)方法，Stack类对象可调用该方法，根据o对象和当前的top对象创建
一个新的top变量，然后n自加。
26
? top()方法，将top对象的info作为返回值返回。
? pop()方法，当栈不为空时，将当前栈顶元素的info返回，并把next赋给top对象，n
自减。
? isEmpty()方法，负责判断栈是否为空。 3）内部类Node
? 内部类Node代表栈中节点元素的类型，包含一个构造方法和两个成员变量info和next。
info是Object类型的变量，可转换为Position类型的变量；next是Node类型的变量，是栈顶元素的下一个元素的引用（相当于指针）。
3.6.2 代码（Stack.java）
package maze; /** * 栈类 * */
public class Stack {
private Node top;//节点为Node类型 private int size;//栈中节点数
public Stack(){//构造方法 top=null; }
public void push(Object o){ }
public Object top(){ }
public void pop(){ }
public boolean isEmpty(){
return size==0;
27
size=0;
top=new Node(o,top); size++;
if(isEmpty())return null; Object o=top.info; return o;
if(isEmpty()) return ; else{ }
top=top.next; size--; return ;
}
}
private class Node{ }
public Object info; public Node next;
public Node(Object o,Node n){//Node类构造方法 info=o; }
next=n;
3.7 Rollback.java（核心算法——回溯法）
3.7.1 效果图
Rollback类绘制人物的效果图如图9所示。
图9 人物图
3.7.2 UML图
Rollback类创建的对象是是MazeGUI类最重要的成员之一。该类负责根据Maze类中的
迷宫数组的信息采用回溯算法，控制并绘制人物在迷宫图形界面窗口中的位置。标明Rollback类的主要成员变量、成员方法的UMl图如图10所示。
28
图10 Rollback类的UML图
以下是UML图中有关数据和方法的详细说明。 1）成员变量
? curPos是Position类型的对象，该对象表示在求解迷宫过程中人物位置的点，同时也
是栈顶元素。
? memory是Stack类型的对象，表示一个栈，而元素采用链式存储的结构。 ? maze是Maze类型的对象，是MazeGUI类中maze对象的一个引用。
? mt是MazeGUI类型的对象，在Rollback类中是通过该变量来控制线程的。 ? person是Image类型的对象，是所要绘制的人物图像。 2）成员方法
? Rollback(Maze m, MazeGUI mt)方法是Rollback类的构造方法。
? forward()方法，该方法根据maze对象的isPass（）方法的返回值来判断curPos周围
是否有通路。若有，将curPos压入栈中，并把下一个通路的坐标赋给curPos的坐标，并标记该通路已走过。
? back（）方法，当curPos周围没有通路时，调用此方法获取栈顶元素中info域，若不
空，则将curPos标记为从栈中弹出的点，并弹出栈顶元素，把info域赋给curPos，实现回溯。若为空，则表示栈中没有元素，此时已经回溯到起点，迷宫不存在可通的路径，使求解迷宫线程等待。
? isOver（）方法,该方法负责判断是否找到了终点。若curPos的坐标和maze.end的坐
标相同则找到了终点，返回true，否则返回false。 ? remember（Position p）方法，该方法调用memory的push（）方法，将引用p压入栈
中。
? draw(Graphics g)方法，该方法负责在curPos点处绘制人物图像。
? setCurPos(int x,int y)方法，该方法根据x，y来设置curPos的坐标。
29
3.7.3 算法伪代码
先将curPos（初始值为begin）压入stack中 do｛
mark()，即标记当前位置已走过，使对应位置的mazeMap[][]值为2； if（curPos周围有通路，即对应位置的mazeMap[][]值为0）｛ 选择一个有通路方向，修改curPos的坐标； 将curPos压入栈中；
If（curPos的坐标和end的坐标相同） 结束； ｝ else｛
stack.pop()，出栈； stack.top()取栈顶元素；
If（该元素不为null）｛
将curPos的坐标修改为该位置的坐标；
｝ else｛
stack已空，为找到end；
｝
｝while（当stack不为null）
3.7.4 代码（Rollback.java）
package maze;
import java.awt.*; import javax.swing.*; /**
* 回溯算法实现 * */
public class Rollback{ Position curPos;//当前位置 Stack memory;//路径堆栈 Maze maze; MazeGUI mt;
Image person=new ImageIcon(\).getImage();
public Rollback(Maze m, MazeGUI mt){ this.maze = m; this.mt = mt;
this.memory = new Stack();
30
rollback对象 forward()方法
rollback对象 back()方法