騎士游歷java課程設(shè)計

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告目 錄1 設(shè)計目的與意義32 系統(tǒng)描述33 運行環(huán)境44 系統(tǒng)的分析與設(shè)計44.1 程序結(jié)構(gòu)說明44.2 accessiblesquare算法實現(xiàn)44.3 畫圖類算法實現(xiàn)64.4 主調(diào)用程序的設(shè)計和開發(fā)75 系統(tǒng)測試85.1 游戲初始界面85.2 游戲以（1，1）為起點運行界面95.3 游戲以（6，3）為起點界面105.4 游戲以（6，3）為起點運行界面106 總結(jié)11源程序121 設(shè)計目的與意義 java課程設(shè)計是計算機科學(xué)與技術(shù)專業(yè)學(xué)生必做的集中實踐性環(huán)節(jié)之一，是學(xué)習(xí)完java程序設(shè)計課程后進行的一次全面的綜合練習(xí)。其目的在于通過課程設(shè)計，使學(xué)生能夠得到較系統(tǒng)的技能訓(xùn)練

2、，從而鞏固和加深對java 編程的基礎(chǔ)理論知識的理解，培養(yǎng)學(xué)生綜合運用所學(xué)理論解決實際問題的能力，使學(xué)生成為具有扎實的計算機理論基礎(chǔ)和較強的獨立動手能力的復(fù)合型、應(yīng)用型人才。2 系統(tǒng)描述騎士游歷問題是一個古老而著名的問題，它最初是由大數(shù)學(xué)家euler提出的。問題是這樣的：國際象棋中的棋子(叫作騎士)在一個空棋盤內(nèi)移動，問它能否經(jīng)過64格中的每一格且只經(jīng)過一次？(騎士按l行移動,即在某方向前進兩格接著在與原方向垂直的方向上前進一格)該課程設(shè)計要求實現(xiàn)騎士游歷問題的求解，并能夠演示起始位置在棋盤上任何位置的游歷問題的實現(xiàn)。程序?qū)⒉捎脛討B(tài)的圖形演示，使算法的描述更形象、更生動。本程序采用applet

3、來編制整個程序，這樣既可以加深對算法的實現(xiàn)的了解，也可以進一步熟悉java圖形界面、applet以及java語言的命名規(guī)范。騎士游歷的課程設(shè)計是按照面向?qū)ο蟮乃枷脒M行開發(fā)，其中主要的類包括accessiblesquare 類、mypanel類和knightstour類。其中accessiblesquare 類主要是算法實現(xiàn)，采用啟發(fā)式算法；knightstour類是主類，或者說是控制類，它完成對算法類和圖畫類的調(diào)用；mypanel類是畫圖類用來實現(xiàn)圖形化顯示結(jié)果。3 運行環(huán)境本程序是在windows xp的環(huán)境下運行的。4 系統(tǒng)的分析與設(shè)計4.1 程序結(jié)構(gòu)說明本程序由三個類組成一個工程文件。其

4、中knightstour是主類，或者說是控制類， accessiblesquare類主要是算法實現(xiàn)，mypanel實現(xiàn)圖形化顯示結(jié)果。程序的運行關(guān)系如圖4-1。accessiblesquare類mypanel類knightstour類圖4-1 程序運行關(guān)系圖4.2 accessiblesquare算法實現(xiàn)1) accessiblesquare類主要是算法實現(xiàn)，采用啟發(fā)式算法。先把八個可能走的方向用兩個數(shù)組(horizontal 和vertical )表示，選擇走哪個方向就在原坐標上進行相應(yīng)的加法，表示騎士到了一個新的位置。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) 由于程序采用啟發(fā)式算法，應(yīng)考察每一方格的可到達性。使用數(shù)組accessibility 表示可達到數(shù),并當騎士游歷時，程序動態(tài)修正剩余格子的可達到數(shù)。accessibility arraypos = 0 表明格子已經(jīng)被占據(jù)。3) 使用冒泡法來查詢最小數(shù)。冒泡排序的基本概念是：依次比較相鄰的兩個數(shù)，將大數(shù)放在前面，小數(shù)放在后面。即首先比較第1個和第2個數(shù)，將大數(shù)放前，小數(shù)放后。然后比

6、較第2個數(shù)和第3個數(shù)，將大數(shù)放前，小數(shù)放后，如此繼續(xù)，直至比較最后兩個數(shù)，將大數(shù)放前，小數(shù)放后，此時第一趟結(jié)束，在最后的數(shù)必是所有數(shù)中的最小數(shù)。重復(fù)以上過程，直至最終完成排序。/冒泡排序法private void sortall () for ( int begin = 0 ; begin < countaccessibility - 1 ; begin + ) for ( int i = begin + 1; i < countaccessibility ; i + ) if ( accessibility begin > accessibility i ) swapall

7、( begin, i ); /end of if / end of inner for / end of outer for / end of sortall /進行移動操作 public void domoving() for ( int i = 0 ; i < countaccessibility ; i + ) knightstour.access xpos i yposi - ; /直到?jīng)]有路徑了 knightstour.access ownxpos ownypos = 0 ; /交換兩個數(shù) private void swapall ( int i , int j ) int t

8、emp ; 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 畫圖類算法實現(xiàn)由于目前用戶對界面的要求逐步提高，因此，現(xiàn)在的可視化編程已經(jīng)取代了傳統(tǒng)的用戶界面的設(shè)計方法。而在可視化編程中，人機之間的直接聯(lián)系主要是通過一些窗口和對話框來實現(xiàn)。jbuilder9也不例外，它也是通過

9、這些窗口和對話框來實現(xiàn)窗體。用戶需要的控件則可以直接放置在窗體上，利用這些控件來實現(xiàn)復(fù)雜的功能。 用戶界面設(shè)計器是用戶在編寫程序過程中最常用到的工具。用戶在進行界面設(shè)計時，只需單擊文件視圖標簽中的design頁，就會出現(xiàn)該用戶界面設(shè)計器。用戶可以利用jbuilder提供的各種控件來搭建自己的程序界面。而且同時，jbuilder9還為這些界面自動生成了相應(yīng)的代碼，為用戶提供了程序的環(huán)境。接下來，就要由用戶設(shè)置屬性，來編寫一些實現(xiàn)用戶特定功能的代碼。這在很大程度上減少了用戶界面設(shè)計的復(fù)雜度，使用戶的主要精力投入到如何實現(xiàn)和加強功能上來。本程序是applet的圖形界面以及如何利用圖形用戶界面的控件接

10、受用戶信息，并用圖形或圖像顯示結(jié)果。1) mypanel函數(shù)實現(xiàn)圖形化顯示結(jié)果， mypanel類就是畫圖類。首先用兩種不同顏色的方塊(white和biack)顯示出棋盤，還有其他兩種方塊(wknight和bknight),這兩種方塊上都有騎士，但顏色不一樣。在騎士游歷過程中不斷用后來兩種有騎士的方塊代替前兩種方塊，其中需要注意的是保持棋盤的顏色一致性。如5-3圖所示，將其設(shè)置為靜態(tài)變量，方便使用，防止修改時出錯。 圖4-3 騎士游歷游戲中的棋盤用圖2) 顯示騎士起始位置，剛走過的步的位置和現(xiàn)在的位置，用邊框的不同來加以區(qū)別，采用函數(shù)g.setcolor(color.green)(剛走過的步顯

11、示為綠色)和g.setcolor(color.biue)(當步顯示為藍色)實現(xiàn)。這個類的對象在主類knightstour中被實例化。采用public viod paintcomponent(graphics g)函數(shù)畫出圖形。/mypanel函數(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 = 2 ;/用于顯示騎士 public static f

12、inal 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 newxrecord ,int newy

13、record ) /重載構(gòu)造函數(shù) initvariance(); initboard( newxrecord , newyrecord ); 4.4 主調(diào)用程序的設(shè)計和開發(fā) knightstour類是控制類，它完成對算法類和畫圖類的調(diào)用。由于java的gui編程是事件驅(qū)動的，因此在knightstour類中，通過監(jiān)聽前面介紹的幾個button的事件相應(yīng)，完成程序的調(diào)用過程。采用二維數(shù)組表示初始位置位于某個位置的可達到數(shù)，即以棋盤任意一點為初試位置，騎士游歷完整個棋盤的路徑數(shù)。利用access數(shù)組來表示這個二維數(shù)組。public static int access= 2, 3, 4, 4, 4,

14、 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類中添加了兩個按鈕，。按鈕一：jbutton nextmoving = new jbutton( "下一步" )；按鈕二：jbutton nexttour = new jbutt

15、on( "新起點重新開始" )，用于用戶對游戲進行操作，這兩個按鈕分別有事件響應(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

16、 actionperformed ( actionevent e ) mypanel.shownext() ; ); 5 系統(tǒng)測試 這段時間做騎士游歷程序，雖然在編程的過程中遇到了許多的困難，最終通過請教老師，或到圖書館查閱相關(guān)書籍或上網(wǎng)查找資料等途徑將它們一一解決了。經(jīng)過不斷修改程序終于編譯通過可以正常運行，其運行結(jié)果如下所示：5.1 游戲初始界面5.2 游戲以（1，1）為起點運行界面5.3 游戲以（6，3）為起點界面5.4 游戲以（6，3）為起點運行界面6 總結(jié)通過這個星期的課程設(shè)計，我也深刻體會到了多問幾個為什么的重要性。真正理解了作為一個計算機專業(yè)的學(xué)生不僅僅要學(xué)好計算機理論知識，同時

17、也要有較強的動手能力。源程序package cao;import java.awt.*;import java.awt.event.*;import javax.swing.*;import java.awt.image.*;public class knightstour extends japplet / 初始位置位于某個位置的可達到數(shù)采用二維數(shù)組表示 /即以棋盤任意一點為初試位置，騎士游歷完整個棋盤的路徑數(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

18、,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 accessbak = 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 ;

19、 private int startx ; private int starty ; private boolean success = false; mypanel mypanel ;/聲明 mypanel的一個對象 public void tour ( int xpos ,int ypos )/成員函數(shù)/ int x,y; countmoving + ; /如果64個格子都被走過，則返回 if (countmoving = 63 ) tourxpos countmoving = xpos ; tourypos countmoving = ypos ; success = true ; co

20、untmoving - ; return ; accessiblesquares nextsquare = new accessiblesquares( xpos, ypos ); /初試化 accessiblesquares對象，給nextsquare分配內(nèi)存 while (nextsquare.hasmoreaccessible() /利用accessiblesquares()對象調(diào)用hasmoreaccessible()成員函數(shù) / 開始移動 nextsquare.domoving();/調(diào)用 nextsquare.domoving()函數(shù) /把這一步記錄下來 tourxpos coun

21、tmoving = xpos ; tourypos countmoving = ypos ; / 嘗試下一步的移動 nextsquare.nextaccessible(); tour ( nextsquare.getxpos() , nextsquare.getypos() ); /如果64個格子都被走過，則返回 if ( success ) countmoving - ; return ; /如果失敗，則從起始位置從新開始 nextsquare.undomoving(); countmoving - ; /游歷方法結(jié)束 /定義棋盤行和列 /先定義一行棋盤 public static int

22、arraycopy ( int array1 )/定義一個整形數(shù)組arraycopy intarray2 = new int array1.length; for ( int row = 0 ; row < 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 ;

23、 row < array1.length ; row + ) for ( int column = 0 ; column < array10.length ; column + ) array2 row 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 +

24、) chessboard row column = 0 ; ; ; public static void main( string args ) knightstour application = new knightstour(); 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

25、 ; column < 8 ; column + ) success = false ; countmoving = -1; startx = row ; starty = column ; access = arraycopy ( accessbak ); tour ( row ,column ); recordcount + ; recordxpos recordcount = arraycopy ( tourxpos ) ; recordypos recordcount = arraycopy ( tourypos ) ; recordcount = 0 ; mypanel = n

26、ew mypanel( recordxpos 0 ,recordypos 0 ) ; jpanel buttonpanel = new jpanel(); jbutton nextmoving = new jbutton( "下一步" ); jbutton nexttour = new jbutton( "新起點重新開始" ); buttonpanel.add( nexttour ); buttonpanel.add( nextmoving ); getcontentpane().add( buttonpanel, borderlayout.south

27、); getcontentpane().add( mypanel ); nextmoving.addactionlistener(/匿名內(nèi)部類,定義了actionperformed函數(shù),調(diào)用shownext函數(shù)響應(yīng)next moving button事件 new actionlistener() public void actionperformed ( actionevent e ) mypanel.shownext() ; );/end call to addactionlistener nexttour.addactionlistener(/內(nèi)部類定義了actionperformed函數(shù)

28、,響應(yīng)next tour button事件 new actionlistener() public void actionperformed ( actionevent e ) if ( recordcount < recordxpos.length - 1 ) recordcount + ; else recordcount = 0 ; mypanel.initboard ( recordxpos recordcount , recordypos recordcount ); mypanel.repaint(); );/end call to addactionlistener pub

29、lic void paint (graphics g ) super.paint( g ); /end of class knightstourclass accessiblesquares /騎士8個方向走l形狀所需的x坐標和y坐標的變化量 private static 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軸的坐標 private int ypos ;/騎士所處y軸的坐標 private int acce

30、ssibility ;/表示可達到數(shù) private int ownxpos ,ownypos ; private int ownaccessibility ; private int arraypos ; private int countaccessibility; public accessiblesquares(int x , int y )/構(gòu)造函數(shù) int testxpos; int testypos; xpos = new int 8 ;/騎士所處x軸的坐標 ypos = new int 8 ; accessibility = new int 8 ; arraypos = 0 ;

31、 ownxpos = x ; ownypos = y ; ownaccessibility = knightstour.access x y ; for (int i = 0 ; i < horizontal.length ; i+ )/有八種到達的情況 testxpos = x + horizontal i ;/得出x,y坐標的測試位置 testypos = y + vertical i ; if ( (testxpos >= 0 ) & ( testxpos < 8 ) & (testypos >= 0 ) & ( testypos <

32、 8 ) ) /判斷測試位置是否在棋盤內(nèi) xpos arraypos = testxpos ;/由測試位置給出正確x,y坐標 ypos arraypos = testypos ; accessibility arraypos = knightstour.access testxpostestypos; /利用對應(yīng)的x,y坐標得出相應(yīng)的可到達的路徑總數(shù) / accessibility arraypos = 0 表明格子已經(jīng)被占據(jù) if (accessibility arraypos > 0 ) arraypos + ; /尋找空格子結(jié)束 / 結(jié)束for循環(huán),尋找結(jié)束 countaccess

33、ibility = arraypos ;/統(tǒng)計可達到數(shù) if (countaccessibility > 0 ) sortall(); arraypos = -1 ; public boolean hasmoreaccessible() / arraypos + 1 指向下一個可行的 if ( (arraypos + 1 ) < countaccessibility ) return true; else return false; / hasmoreaccessible()方法結(jié)束 public accessiblesquares nextaccessible() arraypo

34、s + ; return this; public accessiblesquares accessibleat( int pos) if (pos >= 0) & (pos < countaccessibility ) arraypos = pos ; return this; public int getxpos() return xpos arraypos ; public int getypos() return ypos arraypos ; public int getaccessibility() return accessibility arraypos ;

35、 public int gettotalaccessible() return countaccessibility; /冒泡排序法.冒泡排序的基本概念是：依次比較相鄰的兩個數(shù)，將大數(shù)放在前面，小數(shù)放在后面。 private void sortall () for ( int begin = 0 ; begin < countaccessibility - 1 ; begin + ) for ( int i = begin + 1; i < countaccessibility ; i + ) if ( accessibility begin > accessibility

36、i ) swapall( begin, i ); /end of if / end of inner for / end of outer for / end of sortall /交換兩個數(shù) 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 ; accessibility i = accessibili

37、ty j ; accessibility j = temp; /進行移動操作 public void domoving() for ( int i = 0 ; i < countaccessibility ; i + ) knightstour.access xpos i yposi - ; /直到?jīng)]有路徑了 knightstour.access ownxpos ownypos = 0 ; /撤消移動操作 public void undomoving() for ( int i = 0 ; i < countaccessibility ; i + ) knightstour.acc

38、ess xpos i yposi + ; knightstour.access ownxpos ownypos = ownaccessibility ; /mypanel函數(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 = 2 ;/用于顯示騎士 public static final int bknight = 3 ; private int c

39、hessboard; 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 newxrecord ,int newyrecord ) /重載構(gòu)造函數(shù) initvariance(); ini

40、tboard( 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( "white.jpg"); images 1 = new imageicon( "black.jpg"); images 2 = new imageicon( "wknig

41、ht.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 for for ( int row = 0 ;