《骑士游历java课程设计.doc》由会员分享，可在线阅读，更多相关《骑士游历java课程设计.doc（17页珍藏版）》请在三一办公上搜索。
1、数据结构课程设计报告目 录1 设计目的与意义32 系统描述33 运行环境44 系统的分析与设计44.1 程序结构说明44.2 AccessibleSquare算法实现44.3 画图类算法实现64.4 主调用程序的设计和开发75 系统测试85.1 游戏初始界面85.2 游戏以（1，1）为起点运行界面95.3 游戏以（6，3）为起点界面105.4 游戏以（6，3）为起点运行界面106 总结11源程序121 设计目的与意义 Java课程设计是计算机科学与技术专业学生必做的集中实践性环节之一，是学习完Java程序设计课程后进行的一次全面的综合练习。其目的在于通过课程设计，使学生能够得到较系统的技能训练
2、，从而巩固和加深对Java 编程的基础理论知识的理解，培养学生综合运用所学理论解决实际问题的能力，使学生成为具有扎实的计算机理论基础和较强的独立动手能力的复合型、应用型人才。2 系统描述骑士游历问题是一个古老而著名的问题，它最初是由大数学家Euler提出的。问题是这样的：国际象棋中的棋子(叫作骑士)在一个空棋盘内移动，问它能否经过64格中的每一格且只经过一次？(骑士按L行移动,即在某方向前进两格接着在与原方向垂直的方向上前进一格)该课程设计要求实现骑士游历问题的求解，并能够演示起始位置在棋盘上任何位置的游历问题的实现。程序将采用动态的图形演示，使算法的描述更形象、更生动。本程序采用Applet
3、来编制整个程序，这样既可以加深对算法的实现的了解，也可以进一步熟悉Java图形界面、Applet以及Java语言的命名规范。骑士游历的课程设计是按照面向对象的思想进行开发，其中主要的类包括AccessibleSquare 类、MyPanel类和KnightsTour类。其中AccessibleSquare 类主要是算法实现，采用启发式算法；KnightsTour类是主类，或者说是控制类，它完成对算法类和图画类的调用；MyPanel类是画图类用来实现图形化显示结果。3 运行环境本程序是在windows xp的环境下运行的。4 系统的分析与设计4.1 程序结构说明本程序由三个类组成一个工程文件。其
4、中KnightsTour是主类，或者说是控制类， AccessibleSquare类主要是算法实现，MyPanel实现图形化显示结果。程序的运行关系如图4-1。AccessibleSquare类MyPanel类KnightsTour类图4-1 程序运行关系图4.2 AccessibleSquare算法实现1) AccessibleSquare类主要是算法实现，采用启发式算法。先把八个可能走的方向用两个数组(horizontal 和vertical )表示，选择走哪个方向就在原坐标上进行相应的加法，表示骑士到了一个新的位置。horizontal 和vertical 表示骑士8个方向走L形状所需的
5、X坐标和Y坐标的变化量： horizontal = 2,1,-1,-2,-2,-1,1,2，vertical = -1,-2,-2,-1,1,2,2,1。 坐标图如下：65432187图4-2 骑士游历走向坐标图2) 由于程序采用启发式算法，应考察每一方格的可到达性。使用数组accessibility 表示可达到数,并当骑士游历时，程序动态修正剩余格子的可达到数。accessibility arrayPos = 0 表明格子已经被占据。3) 使用冒泡法来查询最小数。冒泡排序的基本概念是：依次比较相邻的两个数，将大数放在前面，小数放在后面。即首先比较第1个和第2个数，将大数放前，小数放后。然后比
6、较第2个数和第3个数，将大数放前，小数放后，如此继续，直至比较最后两个数，将大数放前，小数放后，此时第一趟结束，在最后的数必是所有数中的最小数。重复以上过程，直至最终完成排序。/冒泡排序法private void sortAll () for ( int begin = 0 ; begin countAccessibility - 1 ; begin + ) for ( int i = begin + 1; i accessibility i ) swapAll( begin, i ); /end of if / end of inner for / end of outer for / en
7、d of sortAll /进行移动操作 public void domoving() for ( int i = 0 ; i countAccessibility ; i + ) KnightsTour.access xpos i yposi - ; /直到没有路径了 KnightsTour.access ownxpos ownypos = 0 ; /交换两个数 private void swapAll ( int i , int j ) int temp ; temp = xpos i ; xpos i = xpos j ; xpos j = temp; temp = ypos i ; y
8、pos i = ypos j ; ypos j = temp; temp = accessibility i ; accessibility i = accessibility j ; accessibility j = temp; 4.3 画图类算法实现由于目前用户对界面的要求逐步提高，因此，现在的可视化编程已经取代了传统的用户界面的设计方法。而在可视化编程中，人机之间的直接联系主要是通过一些窗口和对话框来实现。JBuilder9也不例外，它也是通过这些窗口和对话框来实现窗体。用户需要的控件则可以直接放置在窗体上，利用这些控件来实现复杂的功能。 用户界面设计器是用户在编写程序过程中最常用到的
9、工具。用户在进行界面设计时，只需单击文件视图标签中的Design页，就会出现该用户界面设计器。用户可以利用JBuilder提供的各种控件来搭建自己的程序界面。而且同时，JBuilder9还为这些界面自动生成了相应的代码，为用户提供了程序的环境。接下来，就要由用户设置属性，来编写一些实现用户特定功能的代码。这在很大程度上减少了用户界面设计的复杂度，使用户的主要精力投入到如何实现和加强功能上来。本程序是Applet的图形界面以及如何利用图形用户界面的控件接受用户信息，并用图形或图像显示结果。1) MyPanel函数实现图形化显示结果， MyPanel类就是画图类。首先用两种不同颜色的方块(WHIT
10、E和BIACK)显示出棋盘，还有其他两种方块(WKNIGHT和BKNIGHT),这两种方块上都有骑士，但颜色不一样。在骑士游历过程中不断用后来两种有骑士的方块代替前两种方块，其中需要注意的是保持棋盘的颜色一致性。如5-3图所示，将其设置为静态变量，方便使用，防止修改时出错。 图4-3 骑士游历游戏中的棋盘用图2) 显示骑士起始位置，刚走过的步的位置和现在的位置，用边框的不同来加以区别，采用函数g.setColor(Color.green)(刚走过的步显示为绿色)和g.setColor(Color.biue)(当步显示为蓝色)实现。这个类的对象在主类KnightsTour中被实例化。采用publ
11、ic viod paintComponent(Graphics g)函数画出图形。/MyPanel函数实现图形化显示结果class MyPanel extends JPanel public static final int WHITE = 0 ;/用于显示棋盘 public static final int BLACK = 1 ; public static final int WKNIGHT = 2 ;/用于显示骑士 public static final int BKNIGHT = 3 ; private int chessboard; private int xrecord ; pri
12、vate int yrecord ; private int displayCount ; private int lastxpos ,lastypos ,nextxpos ,nextypos ; ImageIcon images ; private boolean start ; public MyPanel() /MyPanel构造函数 initvariance(); public MyPanel( int newxrecord ,int newyrecord ) /重载构造函数 initvariance(); initboard( newxrecord , newyrecord ); 4
13、.4 主调用程序的设计和开发 KnightsTour类是控制类，它完成对算法类和画图类的调用。由于JAVA的GUI编程是事件驱动的，因此在KnightsTour类中，通过监听前面介绍的几个Button的事件相应，完成程序的调用过程。采用二维数组表示初始位置位于某个位置的可达到数，即以棋盘任意一点为初试位置，骑士游历完整个棋盘的路径数。利用access数组来表示这个二维数组。Public static int access= 2, 3, 4, 4, 4, 4, 3, 2 ， 3, 4, 6, 6, 6, 6, 4, 3 ， 4, 6, 8, 8, 8, 8, 6, 4 ， 4, 6, 8, 8,
14、 8, 8, 6, 4 ， 4, 6, 8, 8, 8, 8, 6, 4 ， 4, 6, 8, 8, 8, 8, 6, 4 ， 3, 4, 6, 6, 6, 6, 4, 3 ， 2, 3, 4, 4, 4, 4, 3, 2 ；本程序中在KnightsTour类中添加了两个按钮，。按钮一：JButton nextMoving = new JButton( 下一步 )；按钮二：JButton nextTour = new JButton( 新起点重新开始 )，用于用户对游戏进行操作，这两个按钮分别有事件响应。 /匿名内部类,定义了actionPerformed函数,调用showNext函数响应Ne
15、xt Moving Button事件 new ActionListener() public void actionPerformed ( ActionEvent e ) myPanel.showNext() ; ; /匿名内部类,定义了actionPerformed函数,调用showNext函数响应Next Moving Button事件 new ActionListener() public void actionPerformed ( ActionEvent e ) myPanel.showNext() ; ); 5 系统测试 这段时间做骑士游历程序，虽然在编程的过程中遇到了许多的困难，
16、最终通过请教老师，或到图书馆查阅相关书籍或上网查找资料等途径将它们一一解决了。经过不断修改程序终于编译通过可以正常运行，其运行结果如下所示：5.1 游戏初始界面5.2 游戏以（1，1）为起点运行界面5.3 游戏以（6，3）为起点界面5.4 游戏以（6，3）为起点运行界面6 总结通过这个星期的课程设计，我也深刻体会到了多问几个为什么的重要性。真正理解了作为一个计算机专业的学生不仅仅要学好计算机理论知识，同时也要有较强的动手能力。源程序package cao;import java.awt.*;import java.awt.event.*;import javax.swing.*;import
17、java.awt.image.*;public class KnightsTour extends JApplet / 初始位置位于某个位置的可达到数采用二维数组表示 /即以棋盘任意一点为初试位置，骑士游历完整个棋盘的路径数 public static int access = 2,3,4,4,4,4,3,2, 3,4,6,6,6,6,4,3, 4,6,8,8,8,8,6,4, 4,6,8,8,8,8,6,4, 4,6,8,8,8,8,6,4, 4,6,8,8,8,8,6,4, 3,4,6,6,6,6,4,3, 2,3,4,4,4,4,3,2; public static int access
18、bak = arrayCopy ( access ) ; int countMoving = -1 ; int tourXpos = new int 64 ;/游历中，X，Y都有64个位置 int tourYpos = new int 64 ; private int recordXpos ; private int recordYpos ; private int recordCount = - 1 ; private int startx ; private int starty ; private boolean success = false; MyPanel myPanel ;/声明
19、 MyPanel的一个对象 public void tour ( int xpos ,int ypos )/成员函数/ int x,y; countMoving + ; /如果64个格子都被走过，则返回 if (countMoving = 63 ) tourXpos countMoving = xpos ; tourYpos countMoving = ypos ; success = true ; countMoving - ; return ; AccessibleSquares nextSquare = new AccessibleSquares( xpos, ypos ); /初试化
20、AccessibleSquares对象，给nextSquare分配内存 while (nextSquare.hasMoreAccessible() /利用AccessibleSquares()对象调用hasMoreAccessible()成员函数 / 开始移动 nextSquare.domoving();/调用 nextSquare.domoving()函数 /把这一步记录下来 tourXpos countMoving = xpos ; tourYpos countMoving = ypos ; / 尝试下一步的移动 nextSquare.nextAccessible(); tour ( ne
21、xtSquare.getXpos() , nextSquare.getYpos() ); /如果64个格子都被走过，则返回 if ( success ) countMoving - ; return ; /如果失败，则从起始位置从新开始 nextSquare.undomoving(); countMoving - ; /游历方法结束 /定义棋盘行和列 /先定义一行棋盘 public static int arrayCopy ( int array1 )/定义一个整形数组arrayCopy intarray2 = new int array1.length; for ( int row = 0
22、; row array1.length ; row + ) array2 row = array1 row ; ; return array2; /复制数组，即定义出棋盘列 public static int arrayCopy ( int array1 ) int array2 = new int array1.lengtharray10.length; for ( int row = 0 ; row array1.length ; row + ) for ( int column = 0 ; column array10.length ; column + ) array2 row col
23、umn = array1 row column ; ; ; return array2; /棋盘数组函数初始化 public void initialArray ( int chessBoard ) for ( int row = 0 ; row 8 ; row + ) for ( int column = 0 ; column 8 ; column + ) chessBoard row column = 0 ; ; ; public static void main( String args ) KnightsTour application = new KnightsTour(); app
24、lication.tour( 0 , 0 ); public void init () recordCount = -1 ; recordXpos = new int 64 64 ; recordYpos = new int 64 64 ; for (int row = 0 ; row 8 ;row +) for ( int column = 0 ; column 8 ; column + ) success = false ; countMoving = -1; startx = row ; starty = column ; access = arrayCopy ( accessbak )
25、; tour ( row ,column ); recordCount + ; recordXpos recordCount = arrayCopy ( tourXpos ) ; recordYpos recordCount = arrayCopy ( tourYpos ) ; recordCount = 0 ; myPanel = new MyPanel( recordXpos 0 ,recordYpos 0 ) ; JPanel buttonPanel = new JPanel(); JButton nextMoving = new JButton( 下一步 ); JButton next
26、Tour = new JButton( 新起点重新开始 ); buttonPanel.add( nextTour ); buttonPanel.add( nextMoving ); getContentPane().add( buttonPanel, BorderLayout.SOUTH ); getContentPane().add( myPanel ); nextMoving.addActionListener(/匿名内部类,定义了actionPerformed函数,调用showNext函数响应Next Moving Button事件 new ActionListener() public
27、 void actionPerformed ( ActionEvent e ) myPanel.showNext() ; );/end call to addActionListener nextTour.addActionListener(/内部类定义了actionPerformed函数,响应Next Tour Button事件 new ActionListener() public void actionPerformed ( ActionEvent e ) if ( recordCount recordXpos.length - 1 ) recordCount + ; else reco
28、rdCount = 0 ; myPanel.initboard ( recordXpos recordCount , recordYpos recordCount ); myPanel.repaint(); );/end call to addActionListener public void paint (Graphics g ) super.paint( g ); /end of class KnightsTourclass AccessibleSquares /骑士8个方向走L形状所需的X坐标和Y坐标的变化量 private static int horizontal = 2,1,-1
29、,-2,-2,-1,1,2; private static int vertical = -1,-2,-2,-1,1,2,2,1; private int xpos ;/骑士所处X轴的坐标 private int ypos ;/骑士所处y轴的坐标 private int accessibility ;/表示可达到数 private int ownxpos ,ownypos ; private int ownAccessibility ; private int arrayPos ; private int countAccessibility; public AccessibleSquares
30、(int x , int y )/构造函数 int testXPos; int testYPos; xpos = new int 8 ;/骑士所处X轴的坐标 ypos = new int 8 ; accessibility = new int 8 ; arrayPos = 0 ; ownxpos = x ; ownypos = y ; ownAccessibility = KnightsTour.access x y ; for (int i = 0 ; i = 0 ) & ( testXPos = 0 ) & ( testYPos 0 ) arrayPos + ; /寻找空格子结束 / 结束
31、for循环,寻找结束 countAccessibility = arrayPos ;/统计可达到数 if (countAccessibility 0 ) sortAll(); arrayPos = -1 ; public boolean hasMoreAccessible() / arrayPos + 1 指向下一个可行的 if ( (arrayPos + 1 ) = 0) & (pos countAccessibility ) arrayPos = pos ; return this; public int getXpos() return xpos arrayPos ; public in
32、t getYpos() return ypos arrayPos ; public int getAccessibility() return accessibility arrayPos ; public int getTotalAccessible() return countAccessibility; /冒泡排序法.冒泡排序的基本概念是：依次比较相邻的两个数，将大数放在前面，小数放在后面。 private void sortAll () for ( int begin = 0 ; begin countAccessibility - 1 ; begin + ) for ( int i
33、= begin + 1; i accessibility i ) swapAll( begin, i ); /end of if / end of inner for / end of outer for / end of sortAll /交换两个数 private void swapAll ( int i , int j ) int temp ; temp = xpos i ; xpos i = xpos j ; xpos j = temp; temp = ypos i ; ypos i = ypos j ; ypos j = temp; temp = accessibility i ;
34、accessibility i = accessibility j ; accessibility j = temp; /进行移动操作 public void domoving() for ( int i = 0 ; i countAccessibility ; i + ) KnightsTour.access xpos i yposi - ; /直到没有路径了 KnightsTour.access ownxpos ownypos = 0 ; /撤消移动操作 public void undomoving() for ( int i = 0 ; i countAccessibility ; i
35、+ ) KnightsTour.access xpos i yposi + ; KnightsTour.access ownxpos ownypos = ownAccessibility ; /MyPanel函数实现图形化显示结果class MyPanel extends JPanel public static final int WHITE = 0 ;/用于显示棋盘 public static final int BLACK = 1 ; public static final int WKNIGHT = 2 ;/用于显示骑士 public static final int BKNIGHT = 3 ; private int chessboard; private int xrecord ; private int yrecord ; private int displayCount ; private int lastxpos ,lastypos ,nextxpos ,nextypos ; ImageIcon images ; private boolean start ; publ
