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

《数据结构课程设计java求解迷宫-回溯法-A算法.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计java求解迷宫-回溯法-A算法.docx（41页珍藏版）》请在第一文库网上搜索。

1、算法与数据结构课程设计课题：求解迷宫通路的图形界面演示程序作者：吴昊QQ：328035823目录1 .题目及需求分析42 .概要设计43 .详细设计104 .调试分析395 .课程设计总结421 .题目及需求分析1.1 题目编制个求解迷宫通路的图形界面演示程序。12需求分析1 .输入一个任意大小的迷宫，任设起点、终点、障碍，用栈求出一条走出迷宫的路径，并显示在屏幕上；2 .根据用户界面提示，用键盘输入，HomC键设置迷宫起点，End键设终点，上下左右箭头键移动，Enter键添加墙，De1键删除墙，完成后按F9键演示，演示完毕后可F5刷新题图，重新对地图的起点、终点、障碍进行设置，ESC键退出；

2、3 .本程序要求至少得出一条成功的通路，也可求得全部路径。此外，也可尝试保存或载入测试文件（此功能不做强行要求）。4 .当未输入起点时，消息显示“Error：YoumustsettheSTART.,;未输入终点时，显示“Error：YoumustsettheEND.找到路径时，屏幕显示足迹，并在消息框出现Pathfound,否则消去足迹，显示Pathnotfoundo5 .用户可以通过界面上提供的菜单选项，选择“帮助”查看操作说明。6 .（算法选优）用户可以通过界面上提供的菜单选项，选择“A*算法求最短路径”演示求解迷宫最短路径。2.概要设计根据需求分析的用户界面的设计要求，考虑到我们在JaV

3、a课程中学习过GUI设计，对JaVa的GU1的比较熟悉，所以我们用JaVa语言来开发本项目。在设计求解迷宫的程序时，要求编写8个Java源文件：Dia1og.java、MaZe.java、MazeGUI.java、PoSition.javaRo11back.javastack.javastar.java和Aposition.java。该程序除了上述6个Java源文件所给出的类以外,还需呀Java系统提供的一些重要的类，如java.awt包中的容器类、画图类、事件类及监听器接口、javax.swing包中的各种轻量组件类和java.Iang包中线程类等。2.1UM1类图程序的所用到的一些重要的类

4、以及之间的关联关系如图2-1所示。CkBSSMaZeCa58/图2-1UM1类图2.2Dia1Og.java（主类）Dia1og.java（主类）是JDia1og类的一个子类。该类负责创建提示用户输入迷宫大小的对话框，通过用户输入的参数来确定所要创建的迷宫图形界面的窗口的大小。该类含有main方法，程序从该类开始执行。BCgin类的成员变量有JTeXtFieId、JButtonJFrameBegin类的主要成员和成员方法的作用将在后面的详细设计中阐述。2.3Maze,javaMaZe类创建的对象是MaZeGU1类和RonbaCk类最重要的成员之一，代表迷宫。该类负责接收在迷宫窗口所设置起点、终

5、点、障碍的位置参数来绘制迷宫图像并存储迷宫结构的信息。该类的主要成员变量有3种类型的对象:Position.Image以及存放整型数的二维数组。MaZe类的主要成员和成员方法的作用将在后面的详细设计中阐述。2.4MazeGU1javaMazeGUI类是Frame类的个子类，创建的对象是RoI1baCk类最重要的成员之一。该类负责创建迷宫图形窗口界面，方便用户在界面上设置起点、终点、障碍等并展现求解迷宫的过程。该类的主要成员变量有4种类型的对象：Maze、Ro11back、Position和Threado该类还包含一个内部类SO1VeThread,该内部类实现了nmnab1e接口。MaZeGUI

6、类的主要成员和成员方法的作用将在后面的详细设计中阐述。2.5Position,java（图形界面坐标的存储结构）Position类创建的对象是MaZe类、MazeGUI类和Ro11back类最重要的成员之一。该类负责在Maze类、MaZeGU1类和RonbaCk类之间传递消息，其对象存有当前位置的坐标信息。该类包含两个整型的成员变量X和y,记录当前位置在迷宫图形界面的横、纵坐标。POSition类的主要成员和成员方法的作用将在后面的详细设计中阐述。2. 6Stack.java（数据类型结构）为了体现算法与数据结构的课程特点,我们并没有用Java系统类库中java.Uti1.Stack类，而是编

7、写了一个通用的StaCk存储结构。Stack类创建的对象是Ro11back类的最重要的成员之一。该类负责保存在求解迷宫过程中所走过的路径信息。该类包含一个内部类Node,定义了栈中存储的节点元素的类型。另外还含有一个整型成员变量n和一个Node类型的成员变量top,分别记录栈中元素的个数以及栈顶元素的信息。而Node类定义的是栈中节点的类型，包含当前节点的信息info（Object类型）和以及栈中下一个元素的引用next（相当在C语言中的指针）。StaCk类的主要成员和成员方法的作用将在后面的详细设计中阐述。2.7RoIIbackjava（核心算法一回溯算法）Ro11back类创建的对象是是M

8、aZeGU1类最重要的成员之一。该类负责根据Maze类中的迷宫数组的信息采用回溯算法，控制并绘制人物在迷宫图形界面窗口中的位置。该类的主要成员变量有4种类型的对象：Maze、MazeGUIPoSition和StaCk。RoI1baCk类的主要成员和成员方法的作用将在后面的详细设计中阐述。2. 8Astar.java（核心算法一A*算法）AStar类创建的对象是是MaZeGU1类最重要的成员之一。该类负责根据MaZe类中的迷宫数组的信息采用A*算法，找到起点到终点的最短路径并打印出来。该类的主要成员变量有4种类型的对象：Maze、APositionStaCk和1inked1ist。AStar类的

9、主要成员和成员方法的作用将在后面的详细设计中阐述。3. 9Aposition（A*算法的存储结构）APOSition类是POSitiOn类的派生类，APOSition类创建的对象是AStar类、MazeGUI类和Ro11back类最重要的成员之一。该类负责在Astar类、MazeGUI类和Ro11back类之间传递消息，其对象存有当前位置的坐标信息、A*算法的评估函数值、开关标记和父节点等。APoSition类的主要成员和成员方法的作用将在后面的详细设计中阐述。2.9事件跟踪图2.9.1用户启动迷宫图形界面sdMazeCase图2-2用户启动迷宫图形界面5dMaZeCaSe/弓户崇作MazeG

10、U1actionPerfofmedO坏乱drawPos生悻draw()绘制aCtionPerfofmedO!draw()Enter.De1draw()图2-3用户设置迷宫参数setBegiO设置会点、终点2.9.3回溯法求解迷宫5dMaZeCaSe/图2-4回溯法求解迷宫3.详细设计3.1工程文件视图,冷MazeCase/0src，由maze团Apositionjavat团AstarJavatJDia1ogjavat团MazejavaD团MazeGU1java0团PositionJavaQ1Ro11backjava团Stackjava国JRESystem1ibrary（jre6.1gifEjS

11、ajpg晅begin.jpgend.jpg0gojpgB0a,maze.jpgCjHroad.jpg国Thumbs.db0wa11.jpg4. 2Dia1og,java（主类）3.2.1效果图Dia1og创建的对话框效果如图1所示。3. 图1Dia1og创建的对话框对象4. 2.2UM1图Dia1og类是javax.SWing包中JDia1og的一个子类,标明该类的主要成员变量和方法的UM1图如图2所示。图2Dia1og类的UMI图以下是UM1图中有关数据和方法的详细说明。1)成员变量 tf1、tf2是JTextFie1d类创建的文本框。用来接收用户输入的设置迷宫的大小参数,即行和列的数目。当

12、用户没有输入时，tf1、tf2的默认文本内容为10。 b是JBUttOn类创建的按钮，名字为“生成迷宫”。b被放置在对话框的右下角。b还为自己注册了ACtionEVent的事件监听器。当点击按钮时，根据tf1、tf2的文本内容创建一个MaZeGU1的对象，生成迷宫图形界面窗口。2)成员方法 Dia1og()是构造方法，负责完成对话框的初始化操作。初始化操作包括：将内容为“列数：的J1abe1对象、内容为列数：的J1abe1对象、b添加到对话框中，并设置对话框的布局，设置背景颜色，设置对话框的标题为“课程设计一求解迷宫”。另外还为对话框注册了WindoWEVent的事件监听器。main(Stri

13、ngSrgd口)方法是程序运行的入口方法。3.2.3代码(Dia1og,java)packagemaze;importjava.awt.*;importjava.awt.event.*;importjavax.swing.*;/*启动窗口SuppresSWarnings(,seria1u)pub1icc1assDia1ogextendsJDia1ogprivateJTextFie1dtf1=newJTextFie1d(10,10);privateJTextFie1dtf2=newJTextFie1d(,10,10);privateJButtonb=newJBUttQn(生成迷宫；pub1ics

14、taticvoidmain(Stringsrgd)try(Thread.s1eep(300);catch(Exceptione)e.PrintStackTrace();)newDia1og();)pub1icDia1og()SetTit1e(”课程设计一求解迷宫”)；Set1ayout(newBorder1ayout();JPane1p=newJPane1(newGrid1ayout(4z1);F1ow1ayoutf1ow1ayout=newF1ow1ayout();f1ow1ayout.SetA1ignment(F1ow1ayout.1EFT);fIow1ayout.setHgap(10);

15、F1ow1ayoutf1ow1ayout1=newF1ow1ayout();f1ow1ayout1.SetA1ignment(F1ow1ayout.RIGHT);JPane1p1=newJPane1(f1ow1ayout);JPane1p2=newJPane1(f1ow1ayout);JPane1p3=newJPane1();JPane1p5=newJPane1(f1ow1ayout1);p1.add(newJ1abe1(p1.add(tf1);p2.add(newJ1abe1(行数：)；列数：)；P.add(p3);P.add(p1);P.add(p2);P.add(p4);p5.add(b);Co1or(196,227,248);p5.SetBackground(newadd(newJ1abe1(newImageicon(maze.jpgn),Border1ayout.NOR