华东交大理工学院
课程设计(论文)任务书
电信 分 院 2009 电子商务 专 业 （1） 班
一、课程设计(论文)题目 走 迷 宫
二、课程设计(论文)工作自 20## 年6月20日起至 20## 年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、演示走迷宫的过程和结果。
学生签名：
20##年6月30日
课程设计(论文)评审意见
（1）任务难易及完成情况 ：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
（2）调试能力评价 ：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
（3）论文撰写水平评价 ：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
（4）论文格式规范性评价 ：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
（5）考勤 ：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
总评成绩：
评阅人： 李广丽 职称： 讲师
20##年7月2日
目 录[chenhl1]
绪论........................................................................................ 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”
第一章 概要设计
为实现上述程序功能，主要使用的JAVA AWT和JAVA SWING包
import java.awt.*;
import javax.swing.*;
importhartech.ui.*;
3. 本程序包含四个模块：
1） 主程序模块：
import java.awt.*;
import javax.swing.*;
import hartech.ui.*;
/**
* <p>Title: maze Global class</p>
*
* <p>Description: </p>
*
* <p>Date: 20##-08-31 </p>
*/
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 --- www.hartech.cn");//建立一个Swing窗体
jFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);//单击关闭图标后，程序退出并关闭
// add
Main.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++) {
buttons[i][j].setText("");//清除按钮的数字，设置名字为空
buttons[i][j].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++) {
buttons[i][j].setText("");
buttons[i][j].setForeground(null);
buttons[i][j].setSelected(true);
}
}
UI.jLabel_state.setText(" Move now?");
}
// 重画按钮图，根据rows、cols
public static JPanel drawButtons() {
buttons = new JToggleButton[rows][cols];
UI.jPanel_map = new JPanel(new GridLayout(rows, cols));
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
buttons[i][j] = new JToggleButton();
UI.jPanel_map.add(buttons[i][j]);
}
}
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++) {
buttons[i][j].setSelected(brick[i][j]);
}
}
}
// 根据现在按钮情况设置brick[][]数组，用于move()内前面
public static void readBricks() {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
brick[i][j] = buttons[i][j].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 (brick[i][j]) {
out += "true,";
}
else {
out += "false,";
}
}
out += "},\r\n";
}
hartech.JFile.stringToFile(out, "E:/dest.txt");
}
*/
// 复制二维数组
public static boolean[][] copyBoolean(boolean[][] in) {
int row = in.length, col = in[0].length;
boolean[][] out = new boolean[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
out[i][j] = in[i][j];
}
}
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.*;
/**
* <p>Title: maze's MainUI </p>
*
* <p>Description: </p>
*
* <p>Date: 20##-08-31 </p>
*/
publicclass UI extends JPanel {
privatestaticfinallongserialVersionUID = 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());
// add
add(jPanel_control(), BorderLayout.SOUTH);//布局管理器，从左到右设置按钮
}
publicstatic 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() {
publicvoid 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_AXIS
jPanel_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);
returnjPanel_control;
}
//监视器接口
staticclass ActionListener_button implements ActionListener {
publicvoid actionPerformed(ActionEvent e) {
if (e.getActionCommand().equals("move")) {
Main.move();
} elseif (e.getActionCommand().equals("clean")) {
Main.clean();
} elseif (e.getActionCommand().equals("blank")) {
Main.blank();
} elseif (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 --- www.hartech.cn"));
jPanel.setBackground(Color.WHITE);
Main.ui = new UI();
// add
jPanel.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;
/**
* <p>
* Tite: 迷宫问题
* </p>
*
* <p>
* Description: 以一个mxn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。
* 设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
*
* 下面用递归实现，实际上就是用了图深度优先遍历 走过的格子直接标记为障碍 line 76: 入栈、入递归、出栈，为了保持现场，类似于Practice_2_3
publicclass Walking {
privateint rows;
privateint cols;
private Dimension goal;
@SuppressWarnings("unused")
private Dimension begin;
// false 为障碍或已走过
privateboolean map[][];
private Stack stack, stack_hasWalk, stack_route;
privateboolean hasFound = false;
privateint count = 1;
Timer timer = new Timer(Main.speed, new ActionListener_Timer());
// 初始化，输入地图 NxM
public Walking(boolean[][] map) {
this(map, new Dimension(0, 0), new Dimension(map.length - 1,
map[0].length - 1));
}
// 初始化，可自定义 起始位置、终点位置
public Walking(boolean[][] map, Dimension begin, Dimension goal) {
rows = map.length;
cols = map[0].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演示已经的路和正确的路
privatevoid printWalking() {
stack_hasWalk.reverse();
timer.setDelay(Main.speed);
timer.start();
}
// 用于timer中激发的事件，演示慢慢走路
class ActionListener_Timer implements ActionListener {
publicvoid actionPerformed(ActionEvent e) {
Dimension d;
// 走完了
if (stack_hasWalk.isEmpty()) {
// 标记正确路线
while (!stack_route.isEmpty()) {
d = (Dimension) stack_route.pop();
Main.buttons[d.width][d.height].setForeground(new Color(204, 52, 103));
}
if (!hasFound) {
UI.jLabel_state.setText(" is there any way to go ? tell me !");
} else {
Main.buttons[Main.rows - 1][Main.cols - 1].setText("^^");
Main.buttons[0][0].setForeground(new Color(204, 52, 103));
Main.buttons[Main.rows - 1][Main.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.buttons[d.width][d.height]
.setText(String.valueOf(count++));
}
}
}
privatevoid spider(int row, int col) {
// 本蜘蛛停止探测，原因：要探测区域出界 或为障碍 或已探测过 或其它蜘蛛已找到目标
if (row < 0 || row > rows - 1 || col < 0 || col > cols - 1
|| !map[row][col] || hasFound) {
return;
}
// 找到了
elseif (goal.width == row && goal.height == col) {
hasFound = true;
stack_route = (Stack) stack.clone();
}
// 向四个方向探测，顺时钟
else {
// 标记已走过
map[row][col] = false;
stack_hasWalk.push(new Dimension(row, col));
// 右
stack.push(new Dimension(row, col + 1));
spider(row, col + 1);
stack.pop();
// 下
stack.push(new Dimension(row + 1, col));
spider(row + 1, col);
stack.pop();
// 左
stack.push(new Dimension(row, col - 1));
spider(row, col - 1);
stack.pop();
// 上
stack.push(new Dimension(row - 1, col));
spider(row - 1, col);
// ** 递归回来后出栈，可维持栈的原来状态，就像没进入递归一样，然后进行下面方向探测
stack.pop();
}
}
}
第三章 调试分析与截图
1、 调试分析：
在设计走迷宫算法的过程中，我主要是利用递归求解和入栈，出栈来解决的。从起点开始出发，每次都首先使自身节点右边的节点入栈，当遇到障碍物时，使下方节点入栈，又遇到障碍物时使左方节点入栈，再使上方节点入栈，依次类推。走过的节点也算作障碍物，知道找到一条通路。再将通路节点一次出栈，并将字体颜色设置为红色。
经过调试分析，本程序能够完成需求分析的各项需求。
2、 截图：
本程序的运行环境为JAVA
进入演示程序后即显示图形用户界面：
3. 单击“Move！”按钮即可开始走迷宫。迷宫运行后如图
红色数字部分为其中一条通路。
4. 单击“Blank”按钮后可重新设置迷宫如图
5. 点击“Clean”按钮可消除搜寻迷宫通路留下的痕迹，点击“Move”可重新搜寻迷宫通路
6. 点击“Reset”可复位，即显示出原先的迷宫。
7. 进度条可控制搜寻迷宫通路过程的速度。
总结和体会
本次数据结构课程设计，我设计的是迷宫通路求解。主要使用了JAVA AWT包和JAVA SWING包，刚开始学的时候主要接触的都是JAVA AWT,通过这次学习让我能够更加系统的自学了JAVA SWING包中的一些组件及其构造方法。在求解迷宫算法的设计中，我算法的核心思想就是递归和入栈出栈。由于一开始设计的失误导致，迷宫通路的求解一直不能正确的运行，在经过反复调试后，经实践证明其可以实现查找通路的功能
参考文献
[1] 王元珍,韩宗芬.IBM-PC宏汇编语言程序设计（第二版）.华中理工大学出版社.
[2]叶核亚《数据结构（Java版）（第2版）》电子工业出版社
[3] 耿祥义、张跃平 《Java基础教程（第2版）》清华大学出版社
[4]刘小晶 《数据结构（Java语言描述）》 清华大学出版社
各个章节使用标题格式，然后利用菜单插入-〉引用-〉索引和目录 自动生成目录