骑士巡游word文档

数据结构课程设计报告

目 录

1 设计目的与意义.......................................................3

2 系统描述...............................................................3

3 运行环境...............................................................3

4 系统的分析与设计....................................................3

4.1 程序结构说明.......................................................................................................................3

4.2 AccessibleSquare 算法实现..................................................................................................4

5.4 游戏以（6，3）为起点运行界面.......................................................................................9

6 总结..................................................................10

源程序..................................................................10

1 设计目的与意义

Java 课程设计是计算机科学与技术专业学生必做的集中实践性环节之一，是

学习完《Java 程序设计》课程后进行的一次全面的综合练习。其目的在于通过

课程设计，使学生能够得到较系统的技能训练，从而巩固和加深对 Java 编程的

基础理论知识的理解，培养学生综合运用所学理论解决实际问题的能力，使学

生成为具有扎实的计算机理论基础和较强的独立动手能力的复合型、应用型人

才。

任何位置的游历问题的实现。程序将采用动态的图形演示，使算法的描述更形

象、更生动。本程序采用 Applet 来编制整个程序，这样既可以加深对算法的实

现的了解，也可以进一步熟悉 Java 图形界面、Applet 以及 Java 语言的命名规范。

骑士游历的课程设计是按照面向对象的思想进行开发，其中主要的类包括

AccessibleSquare 类、MyPanel 类和 KnightsTour 类。其中 AccessibleSquare 类主

要是算法实现，采用启发式算法；KnightsTour 类是主类，或者说是控制类，它

完成对算法类和图画类的调用；MyPanel 类是画图类用来实现图形化显示结果。

3 运行环境

本程序是在 windows xp 的环境下运行的。

4 系统的分析与设计

1) AccessibleSquare 类主要是算法实现，采用启发式算法。

先把八个可能走的方向用两个数组(horizontal[ ]和 vertical[ ])表示，选择走哪

个方向就在原坐标上进行相应的加法，表示骑士到了一个新的位置。horizontal[

]和 vertical[ ]表示骑士 8 个方向走 L 形状所需的 X 坐标和 Y 坐标的变化量：

horizontal[] = {2,1,-1,-2,-2,-1,1,2}，vertical [] = {-1,-2,-2,-1,1,2,2,1}。 坐标图如下：

图 4-2 骑士游历走向坐标图

2) 由 于 程 序采用启 发 式 算 法 ， 应 考 察 每 一 方 格 的 可 到 达 性 。 使用 数 组

accessibility []表示可达到数,并当骑士游历时，程序动态修正剩余格子的可

达到数。accessibility [ arrayPos ] = 0 表明格子已经被占据。

3) 使用冒泡法来查询最小数。冒泡排序的基本概念是：依次比较相邻的两个

2

1

8