数据结构(java)走迷宫.doc

华东交大理工学院 课程设计(论文)任务书 电信 分院 2009 电子商务 专业（1） 班 一、课程设计(论文)题目 走 迷 宫 二、课程设计(论文)工作自 2011 年 6月 20 日起至 2011 年 6月 30 日止。三、课程设计(论文) 地点: 机房 四、课程设计(论文)内容要求：1本课程设计的目的（1）熟练掌握数据结构的基本算法，提高算法设计与分析能力 （2）基本掌握面向对象设计基本思路和方法；（3）利用所学的基本知识和技能，解决简单的程序设计问题；（4）提高学生的科技论文写作能力。 2课程设计的任务及要求1）基本要求：（1）课程设计前必须根据课程设计题目认真准备实验源程序及调试时所需的数据； （2）要求采用简明、严格的问题描述，设计求解算法；（3）数据结构选用得当，程序结构合理；（4）程序简明易懂，多运用输出提示，程序运行正确； （5）对设计进行总结和讨论。2）课程设计论文编写要求（1）要按照书稿的规格打印撰写课设论文（2）论文包括目录、正文、总结和体会、参考文献、附录等（3）正文中要有问题描述、设计求解算法、算法的实现、调试分析（调试时出现的主要问题：编译语法错误及修改，重点是运行逻辑问题修改和调整）（4）课设论文装订按学校的统一要求完成3）课设考核： 从以下几方面来考查：（1）出勤情况； （2）设计任务的难易程度及饱满程度；（3）课设任务完成情况； （4）动手调试能力；（5）论文撰写的原理分析、设计思路以及论述的层次性、条理性、格式的规范性。 4）参考文献：1 王元珍,韩宗芬.IBM-PC宏汇编语言程序设计（第二版）.华中理工大学出版社.2 叶核亚数据结构（Java版）（第2版） 电子工业出版社3 耿祥义、张跃平 Java基础教程（第2版） 清华大学出版社4 刘小晶 数据结构（Java语言描述） 清华大学出版社5）课程设计进度安排内容 天数地点构思及收集资料 3图书馆程序设计与调试 4计算机房撰写论文 3图书馆6）选择课程设计题目具体要求：走迷宫：1、用递归算法实现，以栈和队列作为辅助结构，2、并设计图形用户界面提供迷宫大小、入口及出口位置和初始状态等，3、演示走迷宫的过程和结果。学生签名： 2011年6月30日课程设计(论文)评审意见（1）任务难易及完成情况 ：优（）、良（）、中（）、一般（）、差（）； （2）调试能力评价 ：优（）、良（）、中（）、一般（）、差（）； （3）论文撰写水平评价：优（）、良（）、中（）、一般（）、差（）；（4）论文格式规范性评价 ：优（）、良（）、中（）、一般（）、差（）；（5）考勤 ：优（）、良（）、中（）、一般（）、差（）；总评成绩：评阅人： 李广丽 职称： 讲师 2011年7月2日华东交大理工学院课程设计报告目录各个章节使用标题格式，然后利用菜单插入-引用-索引和目录 自动生成目录绪论1第一章 概要设计2第二章 详细设计3第三章 调试分析与截图4总结和体会5参考文献6绪 论1.编制一个求解迷宫通路的图形界面演示程序2.设置一个可以任意设置障碍，删除障碍的迷宫。并求出迷宫的一条通路3.根据用户界面提示，可以使用事先设定的迷宫也可以使用自定义的迷宫。在着迷宫同路的过程中，需将查找的过程演示出来，并且在最后时，需要标记出查找成功的一条路径。4.本程序只求出一条成功的通路，因受图形界面限制，不能保存或载入测试文件（此功能可在Maze_text中实现）。5）当路径掩盖起点或终点时，消息显示“Is there any way to go ?tell me”；找到路径时，屏幕显示足迹，并在消息框出现，“bingo find it，so easy”5第一章 概要设计为实现上述程序功能，主要使用的JAVA AWT和JAVA SWING包import java.awt.*;import javax.swing.*;import hartech.ui.*;3. 本程序包含四个模块：1） 主程序模块：import java.awt.*;import javax.swing.*;import hartech.ui.*;/* * Title: maze Global class * * Description: * * Date: 2006-08-31 */public class Main / _reset 变量用于reset时用static int rows = 12, cols = 14;static int speed_reset = 50, speed = speed_reset;static JToggleButton buttons;static Walking walking;static boolean brick, brick_reset = true, true, true, true, true, false, true, true, true, true,true, true, true, true, , true, false, false, false, true, false, true, true, true, true,false, false, false, true, , true, false, true, false, true, false, false, false, false, true,true, false, true, true, , true, false, true, false, true, false, true, true, true, false,true, false, true, false, , true, true, true, false, false, false, true, false, true, false,true, false, true, true, , true, false, true, true, true, true, true, false, true, false,true, false, false, true, , true, false, true, true, true, true, true, false, true, false,true, false, true, true, , true, false, false, false, false, false, true, true, true, false,true, false, true, false, , true, false, true, true, true, false, false, false, false, false,true, false, true, true, , true, false, true, false, true, false, true, true, true, true,true, false, false, true, , true, false, true, false, true, false, true, false, false, false,false, false, true, true, , true, true, true, false, true, true, true, true, true, true,true, false, true, true, ;static JFrame jFrame;static UI ui;public static void main(String args) /启动新线程，创建一个窗口javax.swing.SwingUtilities.invokeLater(new Runnable() public void run() J.setLookAndFeel(Metal);jFrame = new JFrame(is there any way to go? Maze - );/建立一个Swing窗体jFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);/单击关闭图标后，程序退出并关闭/ addMain.ui = new UI();jFrame.add(ui, BorderLayout.CENTER);jFrame.setSize(700, 400);J.goCenter(jFrame);Main.drawButtons();Main.reset();jFrame.setVisible(true););/ 用于重置到软件开始public static void reset() if (walking != null) walking.timer.stop();clean();brick = copyBoolean(brick_reset);speed = speed_reset;UI.jSlider.setValue(speed);setBricks();/ 用于清楚已标记上的数字public static void clean() if (walking != null) walking.timer.stop();for (int i = 0; i rows; i+) for (int j = 0; j cols; j+) buttonsij.setText();/清除按钮的数字，设置名字为空buttonsij.setForeground(null);UI.jLabel_state.setText( Move now?);/ 去掉全部砖public static void blank() if (walking != null) walking.timer.stop();for (int i = 0; i rows; i+) for (int j = 0; j cols; j+) buttonsij.setText();buttonsij.setForeground(null);buttonsij.setSelected(true);UI.jLabel_state.setText( Move now?);/ 重画按钮图，根据rows、colspublic static JPanel drawButtons() buttons = new JToggleButtonrowscols;UI.jPanel_map = new JPanel(new GridLayout(rows, cols);for (int i = 0; i rows; i+) for (int j = 0; j cols; j+) buttonsij = new JToggleButton();UI.jPanel_map.add(buttonsij);Main.ui.add(UI.jPanel_map, BorderLayout.CENTER);Main.ui.setVisible(true);return UI.jPanel_map;/ 根据brick设置按钮障碍public static void setBricks() for (int i = 0; i rows; i+) for (int j = 0; j cols; j+) buttonsij.setSelected(brickij);/ 根据现在按钮情况设置brick数组，用于move()内前面public static void readBricks() for (int i = 0; i rows; i+) for (int j = 0; j cols; j+) brickij = buttonsij.isSelected();/ 开始走public static void move() if (walking != null) walking.timer.stop();clean();readBricks();/readToFile();walking = new Walking(brick);/* / 用于把绘制好地图数据写入文件 public static void readToFile() String out = ; for (int i = 0; i rows; i+) out += ; for (int j = 0; j cols; j+) if (brickij) out += true,; else out += false,; out += ,rn; hartech.JFile.stringToFile(out, E:/dest.txt); */ 复制二维数组public static boolean copyBoolean(boolean in) int row = in.length, col = in0.length;boolean out = new booleanrowcol;for (int i = 0; i row; i+) for (int j = 0; j col; j+) outij = inij;return out;2) UI模块实现整个控制面板内组件的布局管理；3）Walking模块实现走迷宫的算法；4）Applete模块设置控制面板。第二章 详细设计package hartech.kids.maze;import java.awt.*;import java.awt.event.*;import javax.swing.*;import javax.swing.event.*;/* * Title: mazes MainUI * * Description: * * Date: 2006-08-31 */public class UI extends JPanel private static final long serialVersionUID = 5924032800440919028L;static JPanel jPanel_state, jPanel_map, jPanel_control;static JLabel jLabel_state;static JButton jButton_move, jButton_clean, jButton_blank, jButton_reset;static JSlider jSlider;/添加面板，向面板里添加各个组件public UI() super(new BorderLayout();/ addadd(jPanel_control(), BorderLayout.SOUTH);/布局管理器，从左到右设置按钮public static JPanel jPanel_control() jLabel_state = new JLabel( Move now?);jLabel_state.setHorizontalTextPosition(JLabel.LEFT);/将Move now标签添加/在面板的左下角jSlider = new JSlider(JSlider.HORIZONTAL, 5, 400, Main.speed);/建立一个水平方向的滑竿jSlider.setPreferredSize(new Dimension(5, 5);/滑杆的大小jSlider.setBackground(new Color(208, 220, 255);jSlider.addChangeListener(new ChangeListener() public void stateChanged(ChangeEvent e) Main.speed = (JSlider) e.getSource().getValue();/处理changeEvent时间，当用户滑动杆时速度会改变);/为各个按钮添加监视器jButton_move = new JButton(Move!);jButton_move.addActionListener(new ActionListener_button();jButton_move.setActionCommand(move);jButton_clean = new JButton(Clean);jButton_clean.addActionListener(new ActionListener_button();jButton_clean.setActionCommand(clean);jButton_blank = new JButton(Blank);jButton_blank.addActionListener(new ActionListener_button();jButton_blank.setActionCommand(blank);jButton_reset = new JButton(Reset);jButton_reset.addActionListener(new ActionListener_button();jButton_reset.setActionCommand(reset);jPanel_control = new JPanel();/ Option: X_AXIS Y_AXIS LINE_AXIS PAGE_AXISjPanel_control.setLayout(new BoxLayout(jPanel_control, BoxLayout.X_AXIS);/jPanel_control = new JPanel(new FlowLayout(FlowLayout.RIGHT);jPanel_control.setBackground(new Color(208, 220, 255);jPanel_control.add(jLabel_state);jPanel_control.add(Box.createHorizontalGlue();/从左到右设置按钮jPanel_control.add(jSlider);jPanel_control.add(jButton_move);jPanel_control.add(jButton_clean);jPanel_control.add(jButton_blank);jPanel_control.add(jButton_reset);return jPanel_control;/监视器接口static class ActionListener_button implements ActionListener public void actionPerformed(ActionEvent e) if (e.getActionCommand().equals(move) Main.move(); else if (e.getActionCommand().equals(clean) Main.clean(); else if (e.getActionCommand().equals(blank) Main.blank(); else if (e.getActionCommand().equals(reset) Main.reset();2Applete模块package hartech.kids.maze;import java.awt.BorderLayout;import java.awt.Color;import javax.swing.*;public class Applet extends JApplet private static final long serialVersionUID = -5507838717556718924L;public void init() JPanel jPanel = new JPanel(new BorderLayout();jPanel.setBorder(BorderFactory.createTitledBorder(is there any way to go? Maze - );jPanel.setBackground(Color.WHITE);Main.ui = new UI();/ addjPanel.add(Main.ui);add(jPanel, BorderLayout.CENTER);setSize(700, 400);Main.drawButtons();Main.reset();setVisible(true);3. Walking模块package hartech.kids.maze;import hartech.ds.Stack;import java.awt.*;import java.awt.event.ActionListener;import java.awt.event.ActionEvent;import javax.swing.Timer;/* * * Tite: 迷宫问题 * * * * Description: 以一个mxn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。 * 设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 * * 下面用递归实现，实际上就是用了图深度优先遍历 走过的格子直接标记为障碍 line 76: 入栈、入递归、出栈，为了保持现场，类似于Practice_2_3public class Walking private int rows;private int cols;private Dimension goal;SuppressWarnings(unused)private Dimension begin;/ false 为障碍或已走过private boolean map;private Stack stack, stack_hasWalk, stack_route;private boolean hasFound = false;private int count = 1;Timer timer = new Timer(Main.speed, new ActionListener_Timer();/ 初始化，输入地图 NxMpublic Walking(boolean map) this(map, new Dimension(0, 0), new Dimension(map.length - 1,map0.length - 1);/ 初始化，可自定义 起始位置、终点位置public Walking(boolean map, Dimension begin, Dimension goal) rows = map.length;cols = map0.length;this.map = Main.copyBoolean(map);this.goal = goal;this.begin = begin;stack = new Stack();stack_hasWalk = new Stack();stack_route = new Stack();spider(begin.width, begin.height);printWalking();/ 根据stack_hasWalk、stack_route演示已经的路和正确的路private void printWalking() stack_hasWalk.reverse();timer.setDelay(Main.speed);timer.start();/ 用于timer中激发的事件，演示慢慢走路class ActionListener_Timer implements ActionListener public void actionPerformed(ActionEvent e) Dimension d;/ 走完了if (stack_hasWalk.isEmpty() / 标记正确路线while (!stack_route.isEmpty() d = (Dimension) stack_route.pop();Main.buttonsd.widthd.height.setForeground(new Color(204, 52, 103);if (!hasFound) UI.jLabel_state.setText( is there any way to go ? tell me !); else Main.buttonsMain.rows - 1Main.cols - 1.setText();Main.buttons00.setForeground(new Color(204, 52, 103);Main.buttonsMain.rows - 1Main.cols - 1.setForeground(new Color(204, 52, 103);UI.jLabel_state.setText( Bingo ! i find it ! so easy.);/ 停止该定时器timer.stop();/ 慢慢走中。else d = (Dimension) stack_hasWalk.pop();Main.buttonsd.widthd.height.setText(String.valueOf(count+);private void spider(int row, int col) / 本蜘蛛停止探测，原因：要探测区域出界 或为障碍 或已探测过 或其它蜘蛛已找到目标if (row rows - 1 | col cols - 1| !maprowcol | hasFound) return;/ 找到了else if (goal.width = row & goal.height = col) hasFound = true;s