数据结构课程设计java求解迷宫回溯法A算法精品资料.docx

算法与数据结构 课程设计课题：求解迷宫通路的图形界面演示程序作者：吴昊 QQ：328035823目录1.题目及需求分析········································42.概要设计··············································43.详细设计·············································104.调试分析·············································395.课程设计总结·········································421题目及需求分析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包中线程类等。2.1 UML类图程序的所用到的一些重要的类以及之间的关联关系如图2-1所示。图2-1 UML类图2.2 Dialog.java(主类)Dialog.java(主类)是JDialog类的一个子类。该类负责创建提示用户输入迷宫大小的对话框，通过用户输入的参数来确定所要创建的迷宫图形界面的窗口的大小。该类含有main方法，程序从该类开始执行。Begin类的成员变量有JTextField、JButton、JFrame。Begin类的主要成员和成员方法的作用将在后面的详细设计中阐述。2.3 Maze.javaMaze类创建的对象是MazeGUI类和Rollback类最重要的成员之一，代表迷宫。该类负责接收在迷宫窗口所设置起点、终点、障碍的位置参数来绘制迷宫图像并存储迷宫结构的信息。该类的主要成员变量有3种类型的对象：Position、Image以及存放整型数的二维数组。Maze类的主要成员和成员方法的作用将在后面的详细设计中阐述。2.4 MazeGUI.javaMazeGUI类是Frame类的一个子类，创建的对象是Rollback类最重要的成员之一。该类负责创建迷宫图形窗口界面，方便用户在界面上设置起点、终点、障碍等并展现求解迷宫的过程。该类的主要成员变量有4种类型的对象：Maze、Rollback、Position和Thread。该类还包含一个内部类SolveThread，该内部类实现了runnable接口。MazeGUI类的主要成员和成员方法的作用将在后面的详细设计中阐述。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类的主要成员和成员方法的作用将在后面的详细设计中阐述。2.9事件跟踪图2.9.1用户启动迷宫图形界面图2-2 用户启动迷宫图形界面2.9.2用户设置迷宫参数图2-3 用户设置迷宫参数2.9.3回溯法求解迷宫图2-4 回溯法求解迷宫3.详细设计3.1 工程文件视图3.2 Dialog.java(主类)3.2.1 效果图Dialog创建的对话框效果如图1所示。图1 Dialog创建的对话框对象3.2.2 UML图Dialog类是javax.swing包中JDialog的一个子类，标明该类的主要成员变量和方法的UML图如图2所示。图2 Dialog类的UMl图以下是UML图中有关数据和方法的详细说明。1） 成员变量l tf1、tf2是JTextField类创建的文本框。用来接收用户输入的设置迷宫的大小参数，即行和列的数目。当用户没有输入时，tf1、tf2的默认文本内容为10。l b是JButton类创建的按钮，名字为“生成迷宫”。b被放置在对话框的右下角。b还为自己注册了ActionEvent的事件监听器。当点击按钮时，根据tf1、tf2的文本内容创建一个MazeGUI的对象，生成迷宫图形界面窗口。2）成员方法l Dialog()是构造方法，负责完成对话框的初始化操作。初始化操作包括：将内容为" 列数： "的JLabel对象、内容为" 列数： "的JLabel对象、tf1、tf2、b添加到对话框中，并设置对话框的布局，设置背景颜色，设置对话框的标题为“课程设计-求解迷宫”。另外还为对话框注册了WindowEvent的事件监听器。l main(String srgd)方法是程序运行的入口方法。3.2.3 代码（Dialog.java）package maze;import java.awt.*;import java.awt.event.*;import javax.swing.*;/* * 启动窗口 * */SuppressWarnings("serial")public class Dialog extends JDialog private JTextField tf1=new JTextField("10",10);private JTextField tf2=new JTextField("10",10);private JButton b=new JButton("生成迷宫");public static void main(String srgd)tryThread.sleep(300);catch(Exception e)e.printStackTrace();new Dialog();public Dialog()setTitle("课程设计-求解迷宫");setLayout(new BorderLayout();JPanel p=new JPanel(new GridLayout(4,1);FlowLayout flowLayout=new FlowLayout();flowLayout.setAlignment(FlowLayout.LEFT);flowLayout.setHgap(10);FlowLayout flowLayout1=new FlowLayout();flowLayout1.setAlignment(FlowLayout.RIGHT);JPanel p1=new JPanel(flowLayout);JPanel p2=new JPanel(flowLayout);JPanel p3=new JPanel();JPanel p4=new JPanel();JPanel p5=new JPanel(flowLayout1);p1.add(new JLabel(" 行数： ");p1.add(tf1);p2.add(new JLabel(" 列数： ");p2.add(tf2);p1.setBackground(new Color(226,244,255);p2.setBackground(new Color(226,244,255);p3.setBackground(new Color(226,244,255);p4.setBackground(new Color(226,244,255);p.add(p3);p.add(p1);p.add(p2);p.add(p4);p5.add(b);p5.setBackground(new Color(196,227,248);add(new JLabel(new ImageIcon("maze.jpg"),BorderLayout.NORTH);add(p,BorderLayout.CENTER);add(p5,BorderLayout.SOUTH);setSize(345, 250);setLocation(400, 100);setVisible(true);b.addActionListener(new ActionListener()public void actionPerformed(ActionEvent e)new MazeGUI(Integer.parseInt(tf1.getText(), Integer.parseInt(tf2.getText();setVisible(false););addWindowListener(new WindowAdapter()public void windowClosing(WindowEvent e)System.exit(0););3.3 Maze.java3.3.1 效果图Maze类绘制的墙、通路、路径、起点和终点的效果图如图3所示。图3 墙、通路、路径、起点和终点3.3.2 UML图Maze类创建的对象是MazeGUI类和Rollback类最重要的成员之一，代表迷宫。标明Maze类的主要成员变量、成员方法的UMl图如图4所示。图4 Maze类的UML图以下是UML图中有关数据和方法的详细说明。1） 成员变量l mazeMap是int类型的二维数组，数组的元素的值表示迷宫对应位置的内容。若元素的值为0表示迷宫对应位置可通过，即为通路；若元素的值为1表示迷宫对应位置为墙；若元素的值为2表示迷宫对应位置为已经走过的足迹；若元素的值为3，表示迷宫对应位置是从栈中弹出的点，并且不能再次通过；若元素的值为4，表示迷宫对应位置为起点，保证起点不可通过。l begin和end是Position类创建的对象，其存储了起点和终点在迷宫图形界面上的坐标信息。l drawPos是Position类创建的对象，在迷宫图形界面上表现为一个方框，起到定位的作用，其存储了在设置起点、终点、障碍在迷宫图形界面的位置时当前的坐标信息。l wallPic、roadPic、goPic、beginPic和endPic是Image类创建的对象，其内容分别为墙、通路、路径、起点和终点的图片。l row和col是int类型的变量，其值分别表示迷宫数组的行数和列数。2） 成员方法l Maze(int row,int col)是Maze类的构造方法，通过调用setMaze方法来创建maze对象，其参数row，col是从MazeGUI类中传来的参数。l setMaze(int row,int col)方法，maze对象可调用该方法完成迷宫数组的初始化操作：创建指定行数和列数的迷宫数组，将迷宫图形界面外围位置对应迷宫数组的元素的值设为1，将其余元素的值设为0。l isPass(Position p)方法，maze对象可调用该方法判断传入的参数p点周围的四个方向是否能通过，并返回一个整型数。根据p点坐标，确定该点在迷宫数组中的元素位置，然后再根据该位置四个方向上相邻位置元素的值判断该p点周围的四个方向是否能通过。若元素的值为0表示可以通过。对于返回值，若返回-1，表示p点四周没有通路（包括从栈中弹出的点）；若返回0，表示p点东方向有通路；若返回1，表示p点南方向有通路；若返回2，表示p点西方向有通路；若返回3，表示p点北方向有通路。l mark(Position p,int m)方法，maze对象可调用该方法将传入的参数p点在迷宫数组的对应位置的元素设为m。l draw(Graphics g)方法，maze对象可调用该方法根据迷宫数组元素的值来绘制墙、通路、路径图像和用于在迷宫图形界面定位的方框，此外该方法还根据begin和end中存储的坐标信息来绘制对应位置的起点和终点图像。l setBegin(int x,int y)和setEnd(int x,int y)方法，maze对象可调用该方法根据传入的参数x，y来创建Position类的对象begin和end。3.3.3 代码（Maze.java）package maze;import java.awt.*;import javax.swing.*;/* * 迷宫参数 * */public class Maze int mazeMap;/地图数据Position begin;/起始坐标Position end;/结束坐标Position drawPos=new Position(1,1);Image wallPic=new ImageIcon("wall.jpg").getImage();Image roadPic=new ImageIcon("road.jpg").getImage();Image a=new ImageIcon("a.jpg").getImage();Image goPic=new ImageIcon("go.jpg").getImage();Image endPic=new ImageIcon("end.jpg").getImage();Image beginPic=new ImageIcon("begin.jpg").getImage();int row=0,col=0;public Maze(int row,int col)this.row=row;this.col=col;mazeMap=new introwcol;for(int i=0;i<row;i+)for(int j=0;j<col;j+)if(i=0|j=0|j=col-1|i=row-1)/迷宫最外层设为墙this.mazeMapij=1;else this.mazeMapij=0;public Maze()public void mark(Position p,int m)/标记位置已走过this.mazeMapp.yp.x=m;public void draw(Graphics g)/绘制地图图片for(int i=0;i<row;i+)for(int j=0;j<col;j+)if(begin!=null&&i=begin.y&&j=begin.x)/起点g.drawImage(beginPic,j*50, 24+i*50, 50, 50,null);else if(end!=null&&i=end.y&&j=end.x)/终点g.drawImage(endPic,j*50, 24+i*50, 50, 50,null);else if(this.mazeMapij = 1)/墙壁g.drawImage(wallPic,j*50, 24+i*50, 50, 50,null);else if(this.mazeMapij = 2)/已走过的路径g.drawImage(goPic,j*50, 24+i*50, 50, 50,null);else if(this.mazeMapij = 3)/已走过的路径，消除脚印g.drawImage(roadPic,j*50, 24+i*50, 50, 50,null);else if(this.mazeMapij = 5)/A*方法路径g.drawImage(a,j*50, 24+i*50, 50, 50,null);else/通道g.drawImage(roadPic,j*50, 24+i*50, 50, 50,null);g.drawRect(drawPos.x*50, 24+drawPos.y*50, 50, 50);public void resume()/恢复迷宫for(int i=0;i<row;i+)for(int j=0;j<col;j+)if(this.mazeMapij=2|this.mazeMapij=3)this.mazeMapij=0;public void setEnd(int x,int y)end=new Position(x,y);public void setBegin(int x,int y)begin=new Position(x,y);34 MazeGUI.java3.4.1 效果图MazeGUI类创建的迷宫图形界面窗口的效果图如图5所示。图5 MazeGUI类创建的迷宫图形界面窗口的效果图3.4.2 UML图MazeGUI类是Frame类的一个子类，创建的对象是Rollback类最重要的成员之一。该类负责创建迷宫图形窗口界面，方便用户在界面上设置起点、终点、障碍等并展现求解迷宫的过程。该类还包含两个内部类SolveThead、AThread，该内部类实现了runnable接口。标明Maze类的主要成员变量、成员方法的UMl图如图6所示。图6 MazeGUI类的UML图以下是UML图中有关数据和方法的详细说明。1） 成员变量l obj是Object类型的对象，该对象用于充当线程问题中的同步锁。l row、col是int类型的变量，用来设置值迷宫图形界面的大小（不是指长度和宽度）。l offScreen是Image类的对象，用于双缓冲技术防止屏幕闪烁。l maze是Maze类的对象。该对象是在MazeGUI类的构造方法中根据row和col的值来创建的。l rollback是Rollback类的对象，该对象负责求解迷宫，并绘制人物在迷宫图形界面中的位置。l t1、t2是Thread线程类的对象，该对象负责控制求解迷宫的线程，便于展现求解迷宫的过程。2） 成员方法l paint(Graphics g)方法，该方法调用了maze对象的draw（Graphics g）和rollback对象的draw（Graphics g），分别绘制迷宫内容图像和人物图像。l update(Graphics g)l MazeGUI(int row,int col)是MazeGUI类的构造方法，负责完成创建迷宫图形界面窗口的初始化操作。初始化操作包括：根据row和col创建maze对象，并根据创建的maze对象和MazeGUI自身的一个引用来创建rollback对象；为迷宫图形窗口注册KeyEvent的事件监听器；设置窗口的大小，以及窗口在屏幕上显示的位置，设置菜单栏和菜单选项的内容，放入窗口中，并为菜单选项注册ActionEvent的事件监听器。l threadSleep（）方法，在求解迷宫的过程结束时，MazeGUI类的对象可调用该方法暂停求解迷宫线程，使求解迷宫线程等待。具体来说是，求解迷宫线程拥有MazeGUI类的对象的监视器，当对象调用该方法时，放弃对此监视器的所有权并等待，直到其他线程通过调用 notify 方法，或 notifyAll 方法通知在此对象的监视器上等待的线程醒来。然后该线程将等到重新获得对监视器的所有权后才能继续执行。l keyTyped(KeyEvent e)方法为KeyListener接口中的抽象方法，必须要实现，但在本程序中没有实际用处，故在MazeGUI类中该方法为空方法；l keyReleased(KeyEvent e)方法为KeyListener接口中的抽象方法，必须要实现，但在本程序中没有实际用处，故在MazeGUI类中该方法为空方法；l keyPressed（KeyEvent e）方法为KeyListener接口中的抽象方法，必须要实现。该方法的操作如下：当按下键盘上的按键时，将会调用repaint（）方法。根据所按下键的键值分成一下几种情况：若按下键盘的Enter键，将会把迷宫图形界面中定位方框位置对应的迷宫数组的元素值改为1，maze对象将在该位置绘制墙的图像；若按下键盘的Delete键，将会把迷宫图形界面中定位方框位置对应的迷宫数组的元素值改为0，maze对象将在该位置绘制通路的图像；若按下键盘方向键的上键，将会把迷宫图形界面中定位方框上移一个单位；若按下键盘方向键的下键，将会把迷宫图形界面中定位方框下移一个单位；若按下键盘方向键的左键，将会把迷宫图形界面中定位方框左移一个单位；若按下键盘方向键的右键，将会把迷宫图形界面中定位方框右移一个单位；若按下键盘的Home键，将会调用maze对象的setBegin(int x,int y)方法，把当前定位方框所在位置的坐标传给setBegin(int x,int y)方法，创建Maze类中的begin对象，并且maze对象将在该位置绘制起点图像；若按下键盘的End键，将会调用maze对象的setEnd(int x,int y)方法，把当前定位方框所在位置的坐标传给setEnd(int x,int y)方法，创建Maze类中的end对象，并且maze对象将在该位置绘制终点图像；若按下键盘的F9键，如果迷宫图形界面没有设置起点或终点，将会提示设置起点或终点，否则不能演示求解迷宫，如果迷宫设置完毕，将启动求解迷宫线程，演示求解迷宫的过程；l actionPerformed(ActionEvent e)方法，当鼠标点击菜单选项时将把产生的事件传给该方法，鼠标点击菜单选项“退出”时，将会关闭窗口并退出程序；鼠标点击刷新地图时，将会清空迷宫里内容，让用户重新设置。3）内部类SolveThreadl 内部类SolveThread实现了runnable接口，是在MazeGUI内部定义的一个线程类。该线程根据rollback.isOver()返回的值判断求解迷宫过程是否结束，若没有结束，则不断在求解过程中不断地使线程睡眠200毫秒，可使求解迷宫的过程能清楚地展现给用户，此外还调用rollback.forward()、rollback.back()等求解迷宫的核心算法，并调用repaint（）重绘。3.4.3 代码（MazeGUI.java）package maze;import java.awt.*;import java.awt.event.*;import javax.swing.*;/* * 迷宫图形界面 * */SuppressWarnings("serial")public class MazeGUI extends Frame implements KeyListener,ActionListener/迷宫GUIfinal Object obj=new Object();/锁对象int row=0,col=0;Image offScreen = null;Maze maze;/构建迷宫参数Rollback rollback;Astar astar;Thread t1 = new Thread(new SolveThread(),"SolveThread");/寻路进程，在初始化Thread类时，把目标对象传递给这个线程实例Thread t2 = new Thread(new AThread(),"AThread");public void paint(Graphics g)/调用绘制地图的draw()方法和绘制人物位置的draw()方法maze.draw(g);rollback.draw(g);public void update(Graphics g)/双缓冲防止屏幕闪烁if(offScreen = null)offScreen = this.createImage(col*50, row*50);Graphics offg = offScreen.getGraphics();Color c = offg.getColor();offg.setColor(Color.BLUE);offg.fillRect(0, 0, col*50, row*50);offg.setColor(c);paint(offg);g.drawImage(offScreen, 0, 0, null);public MazeGUI()public MazeGUI(int row,int col)/初始化窗体this.setTitle("算法课程设计-求解迷宫问题");this.setSize(col*50, row*50);this.setLocation(200, 80);this.setResizable(false);this.addWindowListener(new WindowAdapter()public void windowClosing(WindowEvent e)System.exit(0););this.row=row;this.col=col;maze = new Maze(row,col);/构建迷宫参数 rollback = new Rollback(maze, this);this.setVisible(true);MenuBar menuBar=new MenuBar();Menu fileMenu=new Menu("文件");Menu settingMenu=new Menu("操作");MenuItem exitItem=new MenuItem("退出");MenuItem mapItem=new MenuItem("刷新地图");MenuItem aItem=new MenuItem("A*算法寻找最短路径");MenuItem helpItem=new MenuItem("帮助");fileMenu.add(exitItem);settingMenu.add(mapItem);settingMenu.add(aItem);settingMenu.add(helpItem);menuBar.add(fileMenu);menuBar.add(settingMenu);setMenuBar(menuBar);addKeyListener(this);exitItem.addActionListener(this);mapItem.addActionListener(this);aItem.addActionListener(this);helpItem.addActionListener(this);private class SolveThread implements Runnable/提供一个实现借口Runnable接口的类的实例，作为一个线程的目标对象public void run()while(!rollback.isOver()/寻路结束后，线程结束synchronized (obj) tryThread.sleep(200); catch(InterruptedException e)e.printStackTrace();if(!rollback.forward()rollback.back();repaint();private class AThread implements Runnable/展示用A*算法求解迷宫过程的线程public void run()while(!astar.as.isEmpty()synchronized (obj) tryThread.sleep(200); catch(InterruptedException e)e.printStackTrace();Aposition temp=(Aposition)astar.as.top();astar.as.pop();maze.mazeMaptemp.ytemp.x=5;rollback.curPos.x=temp.x;rollback.curPos.y=temp.y;repaint();if(astar.as.isEmpty() JOptionPane.showMessageDialog(null, "找到最短路径最短路径！");public void keyTyped(KeyEvent e)public void keyReleased(KeyEvent e)public void keyPressed(KeyEvent e)if(e.getKeyCode()=KeyEvent.VK_DELETE)maze.mark(maze.drawPos,0);else if(e.getKeyCode()=Key