完整版騎士游歷java課程設(shè)計(jì)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告1 設(shè)計(jì)目的與意義 32 系統(tǒng)描述 33運(yùn)行環(huán)境 34 系統(tǒng)的分析與設(shè)計(jì) 34.1 程序結(jié)構(gòu)說(shuō)明 34.2 AccessibleSquare 算法實(shí)現(xiàn) 44.3 畫圖類算法實(shí)現(xiàn) 54.4 主調(diào)用程序的設(shè)計(jì)和開發(fā) 75 系統(tǒng)測(cè)試 75.1 游戲初始界面 85.2 游戲以1,1為起點(diǎn)運(yùn)行界面 85.3 游戲以6, 3為起點(diǎn)界面 95.4 游戲以6,3為起點(diǎn)運(yùn)行界面 96 總結(jié) 10源程序 101設(shè)計(jì)目的與意義Java課程設(shè)計(jì)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)學(xué)生必做的集中實(shí)踐性環(huán)節(jié)之一, 是 學(xué)習(xí)完«Java程序設(shè)計(jì)?課程后進(jìn)行的一次全面的綜合練習(xí). 其目的在于通過(guò)課 程設(shè)計(jì),使

2、學(xué)生能夠得到較系統(tǒng)的技能練習(xí),從而穩(wěn)固和加深對(duì) Java編程的基 礎(chǔ)理論知識(shí)的理解,培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)理論解決實(shí)際問(wèn)題的水平,使學(xué)生成 為具有扎實(shí)的計(jì)算機(jī)理論根底和較強(qiáng)的獨(dú)立動(dòng)手水平的復(fù)合型、應(yīng)用型人才.2系統(tǒng)描述騎士游歷問(wèn)題是一個(gè)古老而著名的問(wèn)題,它最初是由大數(shù)學(xué)家 Euler提出 的.問(wèn)題是這樣的：國(guó)際象棋中的棋子叫作騎士在一個(gè)空棋盤內(nèi)移動(dòng),問(wèn)它能 否經(jīng)過(guò)64格中的每一格且只經(jīng)過(guò)一次騎士按L行移動(dòng),即在某方向前進(jìn)兩格 接著在與原方向垂直的方向上前進(jìn)一格該課程設(shè)計(jì)要求實(shí)現(xiàn)騎士游歷問(wèn)題的求解,并能夠演示起始位置在棋盤上 任何位置的游歷問(wèn)題的實(shí)現(xiàn).程序?qū)⒉捎脛?dòng)態(tài)的圖形演示,使算法的描述更形象、

3、 更生動(dòng).本程序采用Applet來(lái)編制整個(gè)程序,這樣既可以加深對(duì)算法的實(shí)現(xiàn)的 了解,也可以進(jìn)一步熟悉Java圖形界面、Applet以及Java語(yǔ)言的命名標(biāo)準(zhǔn).騎士游歷的課程設(shè)計(jì)是根據(jù)面向?qū)ο蟮乃枷脒M(jìn)行開發(fā),其中主要的類包括 AccessibleSquare類、MyPanel 類和 KnightsTour 類.其中 AccessibleSquare類主 要是算法實(shí)現(xiàn),采用啟發(fā)式算法；KnightsTour類是主類,或者說(shuō)是限制類,它 完成對(duì)算法類和圖畫類的調(diào)用;MyPanel類是畫圖類用來(lái)實(shí)現(xiàn)圖形化顯示結(jié)果.3運(yùn)行環(huán)境本程序是在windows xp的環(huán)境下運(yùn)行的.4系統(tǒng)的分析與設(shè)計(jì)4.1 程序結(jié)

4、構(gòu)說(shuō)明本程序由三個(gè)類組成一個(gè)工程文件.其中KnightsTour是主類,或者說(shuō)是控制類,AccessibleSquare主要是算法實(shí)現(xiàn),MyPanel實(shí)現(xiàn)圖形化顯示結(jié)果.程序的運(yùn)行關(guān)系如圖4-1.AccessibleSquareKnightsTour 類MyPane l 類圖4-1程序運(yùn)行關(guān)系圖4.2 AccessibleSquare 算法實(shí)現(xiàn)1) AccessibleSquare主要是算法實(shí)現(xiàn),采用啟發(fā)式算法.先把八個(gè)可能走的方向用兩個(gè)數(shù)組(horizontal和vertical)表示,選擇走哪 個(gè)方向就在原坐標(biāo)上進(jìn)行相應(yīng)的加法,表示騎士到了一個(gè)新的位置.horizontal 和vertic

5、al表示騎士 8個(gè)方向走L形狀所需的X坐標(biāo)和Y坐標(biāo)的變化量： horizontal = 2,1,-1,-2,-2,-1,1,2 , vertical = -1,-2,-2,-1,1,2,2,1.坐標(biāo)圖如下：G-QQ"011dQ-0QQ圖4-2 騎士游歷走向坐標(biāo)圖2) 由丁程序采用啟發(fā)式算法,應(yīng)考察每一方格的可到達(dá)性.使用數(shù)組 accessibility 表示可到達(dá)數(shù),并當(dāng)騎士游歷時(shí),程序動(dòng)態(tài)修正剩余格子的可達(dá) 到數(shù).accessibility arrayPos = 0說(shuō)明格子已經(jīng)被占據(jù).3) 使用冒泡法來(lái)查詢最小數(shù).冒泡排序的根本概念是：依次比較相鄰的兩個(gè)數(shù),將大數(shù)放在前面,小數(shù)放在

6、后面.即首先比較第1個(gè)和第2個(gè)數(shù),將大數(shù)放前,小數(shù)放后.然后比較第2個(gè)數(shù)和第3個(gè)數(shù),將大數(shù)放前,小數(shù)放后,如此繼續(xù),直至比較最后兩個(gè)數(shù),將大數(shù)放前,小數(shù)放后,此時(shí)第一趟結(jié)束,在最后的數(shù)必是所有數(shù)中的最小數(shù).重復(fù)以上過(guò)程,直至最終完成排序.冒泡排序法private void sortAll ()(for ( int begin = 0 ; begin < countAccessibility - 1 ; begin + )(for ( int i = begin + 1; i < countAccessibility ; i + )(if ( accessibility begin

7、> accessibility i )(swapAll( begin, i ); /end of if/ end of inner for/ end of outer for/ end of sortAll進(jìn)行移動(dòng)操作public void domoving()(for ( int i = 0 ; i < countAccessibility ; i + )(KnightsTour.access xpos i yposi - ;直到?jīng)]有路徑了KnightsTour.access ownxpos ownypos = 0 ;交換兩個(gè)數(shù)private void swapAll ( int

8、 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 ;accessibility i = accessibility j ; accessibility j = temp;4.3畫圖類算法實(shí)現(xiàn)由于目前用戶對(duì)界面的要求逐步提升,因此,現(xiàn)在的可視化編程已經(jīng)取 代了傳統(tǒng)的用戶界面的設(shè)計(jì)方法.而在可視化編程中,人機(jī)之間的直接聯(lián)系 主要是通過(guò)一些窗口和對(duì)話框來(lái)實(shí)現(xiàn).JBuilder

9、9也不例外,它也是通過(guò)這些窗口和對(duì)話框來(lái)實(shí)現(xiàn)窗體.用戶需要的控件那么可以直接放置在窗體上,利 用這些控件來(lái)實(shí)現(xiàn)復(fù)雜的功能.用戶界面設(shè)計(jì)器是用戶在編寫程序過(guò)程中最常用到的工具. 用戶在進(jìn)行界 面設(shè)計(jì)時(shí),只需單擊文件視圖標(biāo)簽中的 Design貞,就會(huì)出現(xiàn)該用戶界面設(shè)計(jì) 器.用戶可以利用JBuilder提供的各種控件來(lái)搭建自己的程序界面. 而且同時(shí), JBuilder9還為這些界面自動(dòng)生成了相應(yīng)的代碼,為用戶提供了程序的環(huán)境.接下來(lái),就要由用戶設(shè)置屆性,來(lái)編寫一些實(shí)現(xiàn)用戶特定功能的代碼.這在很大程度上減少了用戶界面設(shè)計(jì)的復(fù)雜度, 使用戶的主要精力投入到如何實(shí)現(xiàn)和增強(qiáng)功能上來(lái).本程序是Applet的圖

10、形界面以及如何利用圖形用戶界面的控件接受用戶 信息,并用圖形或圖像顯示結(jié)果.1) MyPanel函數(shù)實(shí)現(xiàn)圖形化顯示結(jié)果,MyPanel類就是畫圖類.首先用兩種不同顏色的方塊(WHITE和BIACK)顯示出棋盤,還有其他兩種方塊(WKNIGHT 和BKNIGHT),這兩種方塊上都有騎士,但顏色不一樣.在騎士游歷過(guò)程中不 斷用后來(lái)兩種有騎士的方塊代替前兩種方塊,其中需要注意的是保持棋盤的 顏色一致性.如5-3圖所示,將其設(shè)置為靜態(tài)變量,方便使用,預(yù)防修改時(shí) 出錯(cuò).圖4-3 騎士游歷游戲中的棋盤用圖2)顯示騎士起始位置,岡Q走過(guò)的步的位置和現(xiàn)在的位置,用邊框的不同來(lái)加以區(qū)別,采用函數(shù)g.setCol

11、or(Color.green)(剛走過(guò)的步顯示為綠色)和 g.setColor(Color.biue)(當(dāng)步顯示為藍(lán)色)實(shí)現(xiàn).這個(gè)類的對(duì)象在主類 KnightsTour 中被實(shí)例化.采用 public viod paintComponent(Graphics g)函數(shù)畫 出圖形./MyPanel函數(shù)實(shí)現(xiàn)圖形化顯示結(jié)果class MyPanel extends JPanel (public static final int WHITE = 0 ;/ 用丁顯示棋盤public static final int BLACK = 1 ;public static final int WKNIGHT =

12、 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 ;public MyPanel() (/MyPanel 構(gòu)造函數(shù)initvariance();public MyPanel( int ne

13、wxrecord ,int newyrecord ) (/ 重載構(gòu)造函數(shù) initvariance();initboard( newxrecord , newyrecord );4.4 主調(diào)用程序的設(shè)計(jì)和開發(fā)KnightsTour類是限制類,它完成對(duì)算法類和畫圖類的調(diào)用.由于JAVA的GUI編程是事件驅(qū)動(dòng)的,因此在 KnightsTour類中,通過(guò)監(jiān)聽前面介紹的幾個(gè) Button的事件相應(yīng),完成程序的調(diào)用過(guò)程.采用二維數(shù)組表示初始位置位于某個(gè)位置的可到達(dá)數(shù),即以棋盤任意一點(diǎn)為 初試位置,騎士游歷完整個(gè)棋盤的路徑數(shù).利用access數(shù)組來(lái)表示這個(gè)二維 數(shù)組.Public static int a

14、ccess=(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；本程序中在KnightsTour類中添加了兩個(gè)按鈕,.按鈕一：JButton nextMoving =new JButton("下一步")；按鈕二：JButton nextTour = new JButton('新起點(diǎn)重新 開始"),用于用戶對(duì)游戲進(jìn)行操作,這兩個(gè)按鈕分別有事件

15、響應(yīng).匿名內(nèi)部類,定義了 actionPerformed函數(shù),調(diào)用showNext函數(shù)響應(yīng)Next Moving Button事件new ActionListener() (public void actionPerformed ( ActionEvent e ) ( myPanel.showNext() ;匿名內(nèi)部類,定義了 actionPerformed函數(shù),調(diào)用showNext函數(shù)響應(yīng)Next Moving Button事件new ActionListener() (public void actionPerformed ( ActionEvent e ) ( myPanel.showN

16、ext() ;);5系統(tǒng)測(cè)試這段時(shí)間做騎士游歷程序,雖然在編程的過(guò)程中遇到了許多的困難,最終 通過(guò)請(qǐng)教老師,或到圖書館查閱相關(guān)書籍或上網(wǎng)查找資料等途徑將它們一一解決 了.經(jīng)過(guò)不斷修改程序終丁編譯通過(guò)可以正常運(yùn)行,其運(yùn)行結(jié)果如下所示：5.1 游戲初始界面5.2 游戲以1, 1為起點(diǎn)運(yùn)行界面5.3 游戲以6, 3為起點(diǎn)界面5.4 游戲以6, 3為起點(diǎn)運(yùn)行界面6總結(jié)通過(guò)這個(gè)星期的課程設(shè)計(jì),我也深刻體會(huì)到了多問(wèn)幾個(gè)為什么的重要性.真正理解了作為一個(gè)計(jì)算機(jī)專業(yè)的學(xué)生不僅僅要學(xué)好計(jì)算機(jī)理論知識(shí),同時(shí)也要有較強(qiáng)的動(dòng)手水平.源程序package cao;import java.awt.*;import jav

17、a.awt.event.*;import javax.swing.*;import java.awt.image.*;public class KnightsTour extends JApplet (/初始位置位于某個(gè)位置的可到達(dá)數(shù)采用二維數(shù)組表示/即以棋盤任意一點(diǎn)為初試位置,騎士游歷完整個(gè)棋盤的路徑數(shù)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,

18、4,4,3,2;public static int accessbak = arrayCopy ( access );int countMoving = -1 ;int tourXpos = new int 64 ;/ 游歷中,X, 丫都有 64 個(gè)位置int tourYpos = new int 64 ;private int recordXpos ;private int recordYpos ;private int recordCount = - 1 ;private int startx ;private int starty ;private boolean success = f

19、alse;MyPanel myPanel ;/ 聲明 MyPanel 的一個(gè)對(duì)象public void tour ( int xpos ,int ypos )/ 成員函數(shù)/ int x,y;countMoving + ;如果64個(gè)格子都被走過(guò),那么返回if (countMoving = 63 ) tourXpos countMoving = xpos ;tourYpos countMoving = ypos ;success = true ;countMoving - ;return ;AccessibleSquares nextSquare = new AccessibleSquares(

20、xpos, ypos );初試化AccessibleSquares對(duì)象,給nextSquare分配內(nèi)存while (nextSquare.hasMoreAccessible()利用 AccessibleSquares()對(duì)象調(diào)用 hasMoreAccessible()成員函數(shù) /開始移動(dòng)nextSquare.domoving();/ 調(diào)用 nextSquare.domoving()函數(shù)把這一步記錄下來(lái)tourXpos countMoving = xpos ;tourYpos countMoving = ypos ;/嘗試下一步的移動(dòng)nextSquare.nextAccessible();tou

21、r ( nextSquare.getXpos() , nextSquare.getYpos();/如果64個(gè)格子都被走過(guò),那么返回if ( success ) countMoving -;return ; 如果失敗,那么從起始位置從新開始nextSquare.undomoving();countMoving - ;/游歷方法結(jié)束定義棋盤行和列先定義一行棋盤public static int arrayCopy ( int array1 )/ 定義一個(gè)整形數(shù)組arrayCopy( intarray2 = new int arrayl.length;for ( int row = 0 ; row

22、< array1.length ; row + )( array2 row = array1 row ;return array2;復(fù)制數(shù)組,即定義出棋盤列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 ro

23、w column = array1 row column ; ;return array2;棋盤數(shù)組函數(shù)初始化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 KnightsT

24、our();application.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 (

25、 accessbak );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("下一步");JB

26、utton nextTour = new JButton("新起點(diǎn)重新開始");buttonPanel.add( nextTour );buttonPanel.add( nextMoving );getContentPane().add( buttonPanel, BorderLayout.SOUTH );getContentPane().add( myPanel );nextMoving.addActionListener(匿名內(nèi)部類,定義了 actionPerformed函數(shù),調(diào)用showNext函數(shù)響應(yīng) Next Moving Button 事件 new Action

27、Listener() public void actionPerformed ( ActionEvent e ) ( myPanel.showNext() ;);/end call to addActionListenernextTour.addActionListener(內(nèi)部類定義了 actionPerformed函數(shù),響應(yīng)Next Tour Button事件 new ActionListener() (public void actionPerformed ( ActionEvent e ) ( if ( recordCount < recordXpos.length - 1 )

28、( recordCount + ; else ( recordCount = 0 ; myPanel.initboard ( recordXpos recordCount , recordYpos recordCount );myPanel.repaint(););/end call to addActionListenerpublic void paint (Graphics g )( super.paint( g );/end of class KnightsTourclass AccessibleSquares (/騎士 8個(gè)方向走L形狀所需的X坐標(biāo)和Y坐標(biāo)的變化量private sta

29、tic int horizontal = (2,1,-1,-2,-2,-1,1,2;private static int vertical = (-1,-2,-2,-1,1,2,2,1;private int xpos ;/騎士所處 X軸的坐標(biāo)private int ypos ;/騎士所處y軸的坐標(biāo)private int accessibility ;/ 表示可到達(dá)數(shù) private int ownxpos ,ownypos ;private int ownAccessibility ;private int arrayPos ;private int countAccessibility;p

30、ublic AccessibleSquares(int x , int y )(/ 構(gòu)造函數(shù) int testXPos; int testYPos;xpos = new int 8 ;/騎士所處 X軸的坐標(biāo)ypos = new int 8 ;accessibility = new int 8 ;arrayPos = 0 ;ownxpos = x ; ownypos = y ;ownAccessibility = KnightsTour.access x y ;for (int i = 0 ; i < horizontal.length ; i+ )(/有八種到達(dá)的情況testXPos =

31、 x + horizontal i ;/ 得出 X,Y 坐標(biāo)的測(cè)試位置 testYPos = y + vertical i ;if ( (testXPos >= 0 ) & ( testXPos < 8 ) &(testYPos >= 0 ) & ( testYPos < 8 ) ) (/判斷測(cè)試位置是否在棋盤內(nèi)xpos arrayPos = testXPos ;/由測(cè)試位置給出正確X,Y坐標(biāo)ypos arrayPos = testYPos ;accessibility arrayPos = KnightsTour.access testXPos

32、testYPos;/利用對(duì)應(yīng)的X,Y坐標(biāo)得出相應(yīng)的可到達(dá)的路徑總數(shù)/ accessibility arrayPos = 0 說(shuō)明格子已經(jīng)被占據(jù) if (accessibility arrayPos > 0 ) arrayPos + ;/尋找空格子結(jié)束/結(jié)束for循環(huán),尋找結(jié)束countAccessibility = arrayPos ;/ 統(tǒng)計(jì)可到達(dá)數(shù)if (countAccessibility > 0 ) (sortAll(); arrayPos = -1 ;public boolean hasMoreAccessible()(/ arrayPos + 1指向下一個(gè)可行的if (

33、 (arrayPos + 1 ) < countAccessibility )(return true; else ( return false; / hasMoreAccessible()方法結(jié)束public AccessibleSquares nextAccessible()(arrayPos + ;return this;public AccessibleSquares accessibleAt( int pos)(if (pos >= 0) & (pos < countAccessibility )arrayPos = pos ;return this;pub

34、lic int getXpos()(return xpos arrayPos ;public int getYpos()(return ypos arrayPos ;public int getAccessibility()(return accessibility arrayPos ;public int getTotalAccessible()(return countAccessibility;冒泡排序法.冒泡排序的根本概念是：依次比較相鄰的兩個(gè)數(shù),將大數(shù)放在前面,小數(shù) 放在后面.private void sortAll ()(for ( int begin = 0 ; begin &l

35、t; countAccessibility - 1 ; begin + )(for ( int i = begin + 1; i < countAccessibility ; i + )(if ( accessibility begin > accessibility i )(swapAll( begin, i ); /end of if/ end of inner for/ end of outer for/ end of sortAll交換兩個(gè)數(shù)private void swapAll ( int i , int j )(int temp ;temp = xpos i ; xp

36、os i = xpos j ; xpos j = temp;temp = ypos i ; ypos i = ypos j ; ypos j = temp;temp = accessibility i ;accessibility i = accessibility j ; accessibility j = temp;/進(jìn)行移動(dòng)操作public void domoving()(for ( int i = 0 ; i < countAccessibility ; i + )(KnightsTour.access xpos i yposi - ;直到?jīng)]有路徑了KnightsTour.acc

37、ess ownxpos ownypos = 0 ;/撤消移動(dòng)操作public void undomoving()(for ( int i = 0 ; i < countAccessibility ; i + )(KnightsTour.access xpos i yposi + ;KnightsTour.access ownxpos ownypos = ownAccessibility ;/MyPanel函數(shù)實(shí)現(xiàn)圖形化顯示結(jié)果class MyPanel extends JPanel (public static final int WHITE = 0 ;/ 用于顯示棋盤public st

38、atic 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 ;public MyP

39、anel() (/MyPanel 構(gòu)造函數(shù) initvariance();public MyPanel( int newxrecord ,int newyrecord ) (/ 重載構(gòu)造函數(shù) initvariance();initboard( newxrecord , newyrecord );public void initvariance () (chessboard = new int 8 8 ;xrecord = new int 64 ; yrecord = new int 64 ;images = new Imageicon 4 ;images 0 = new Imageicon(

40、"white.jpg");images 1 = new imageicon( "black.jpg");images 2 = new imageicon( "wknight.jpg");images 3 = new imageicon( "bknight.jpg");/畫棋盤,給棋盤上色public void initboard ( int newxrecord ,int newyrecord )(start = true ;displayCount = -1 ;for (int row = 0 ; row < 8 ;row +)(for ( int column = 0 ; column < 8 ; column + )(/0表示白的,1表示黑的chessboard row column = ( row + column ) % 2 ;/end of outer forfor ( int row