前言學習數(shù)據(jù)結構的最終目的是解決實際的應用問題，特別是非數(shù)值計算類型的應用問題，數(shù)據(jù)結構課程設計就是為此目的一次實際訓練。要求我們在對題目進行獨立分析的基礎上，完成設計和開發(fā)，并最終接受嚴格的測試考核。以深化對數(shù)據(jù)結構課程中基本概念、理論和方法的理解，提升綜合運用所學知識處理實際問題的能力，使我們的的程序設計能力與調試水平有一個明顯的提升。課程設計所安排的題目，都有一定的難度和深度，從抽象數(shù)據(jù)類型的提煉、數(shù)據(jù)結構選擇到算法的設計，均由我們每個人自主完成。在一周的時間內(nèi)，歷經(jīng)查找參考資料、使用技術手冊、設計編碼和撰寫文檔的實踐，進一步升華對軟件工程師和程序員人格素質的認識和理解。 本課程設計的主要設計內(nèi)容是： 設計一個馬踏棋盤問題的演示程序。即將馬隨機地放在國際象棋的8*8棋盤的某個方格中，然后令馬按走棋規(guī)則開始進行移動。要求馬將棋盤上的每個方格進入且只進入一次，走遍全部64個方格。要求編制非遞歸程序，求出馬的行走路線，將數(shù)字1，2，64依次填入一個8*8的方陣在屏幕上顯示輸出。針對該問題本課程設計采用的是面向對象的開發(fā)語言Java，在Windows7, myeclipse8.5.0的平臺上開發(fā)出來，并有圖形界面。最終較好的實現(xiàn)了全部要求，達到了預期效果。從中我也學到了很多，不僅僅是課堂外的新知識，還有那種會查資料，會學習新知識的能力。這個課程設計的順利完成，離不開胡老師的指導和幫助，在他的細心指導和幫助下，我對馬踏棋盤程序開發(fā)的整個流程有了深刻地了解和系統(tǒng)地掌握，在這里學生表示真誠地感謝。另外也謝謝這次課程設計提供給我?guī)椭耐瑢W們。此外，本課程設計還參考了一些文獻資料，在此向這些文獻資料的作者深表謝意。本課程設計可作為數(shù)據(jù)結構和Java課程教學的參考案例。由于時間倉促和本人水平所限，設計中難免有不當和欠妥之處，敬請老師不吝批評指正。 筆者 2016.6目錄摘要3第一章 需求分析.4第二章 概要設計.52.1系統(tǒng)描述。.52.2運行環(huán)境.52.3馬踏棋盤流程52.4算法設計第三章 詳細設計3.1 Jisuan類實現(xiàn)3.23.33.4Disizhang 4.14,24.3Diwu 5.15.2Cankaowenxian Fulu 摘要本課程設計中的程序實現(xiàn)了馬踏棋盤問題的求解,并能夠演示起始位置在棋盤上任何位置的問題的實現(xiàn).程序采用圖形演示,使算法的描述更形象,更生動,使教學更能產(chǎn)生良好的效果。對于該程序，我嚴格按照面向對象的思想進行開發(fā),其中有Jisuan類, Shuchu類, Jframe類和Main四個類。其中Jisuan類主要是初始化各點的可走路徑，并且刪除不合法的點；Shuchu類主要最優(yōu)算法的實現(xiàn)；Jframe類為圖形用戶界面的設計,主要完成棋盤的繪制和結果的打??；Main類主要是負責整個程序的控制。最終調試運行通過，實現(xiàn)了全部要求，取得了理想效果。關鍵詞：數(shù)據(jù)結構 馬踏棋盤 Java 圖形界面Abstract This course design of the program realization horses on board the solution, and to demonstrate the starting position on the board of the realization of the problem any position. The program using graphical presentation, the method of more image, the more vivid description, and make the teaching more can produce good effect. For the program, I in strict accordance with the object-oriented ideas of development, including Jisuan class, Shuchu class, Jframe classes and Main four classes. Among them Jisuan kind basically is the initial points of walk path, and remove not legal point; Shuchu main kinds of the realization of the optimal algorithm; Jframe class for the graphical user interface design, the main finish drawing the board and results of the print; Main kinds of major is responsible for the entire process control. Final test and operation, realize the requirements through all, make the ideal effect.Key words: data structure horse on board Java graphical interface第一章 需求分析數(shù)據(jù)結構課程設計是計算機科學與技術專業(yè)學生必做的集中實踐性環(huán)節(jié)之一，是學習完數(shù)據(jù)結構課程后進行的一次全面的綜合練習。其目的在于通過課程設計，使學生能夠得到較系統(tǒng)的技能訓練，從而鞏固和加深對數(shù)據(jù)結構的基礎理論知識的理解，培養(yǎng)學生綜合運用所學理論知識解決實際問題的能力，使學生成為具有扎實的計算機理論基礎和較強的獨立動手能力的復合型、應用型人才。馬踏棋盤問題是一個古老而著名的問題,它最初是由大數(shù)學家Euler提出的.問題是這樣的:國際象棋中的棋子(叫作馬)在一個空棋盤內(nèi)移動,問它能否經(jīng)過64格中的每一格且只經(jīng)過一次?(馬按L行移動,即在某方向前進兩格接著在與原方向垂直的方向上前進一格)本程序實現(xiàn)了馬踏棋盤問題的求解,并能夠演示起始位置在棋盤上任何位置的問題的實現(xiàn).程序采用圖形演示,使算法的描述更形象,更生動,使教學更能產(chǎn)生良好的效果。第二章 概要設計2.1系統(tǒng)描述本程序采用myeclipse8.5.0來編制整個程序,這樣既可以使大家對算法的實現(xiàn)有了一定的了解,也可以熟悉一下Java圖形界面以及Java語言的命名規(guī)范。作為數(shù)據(jù)結構的課程設計,本人希望同時也能讓大家順便熟悉一下Java的基本語言結構和強大的開發(fā)能力。在馬踏棋盤的課程設計中,我們嚴格按照面向對象的思想進行開發(fā),其中有Jisuan類, Shuchu類, Jframe類和Main類。讀者應注意各個類之間的關系,以便也能順道理解Java中類的思想。2.2運行環(huán)境 本程序是在windows7, myeclipse8.5.0的環(huán)境下運行的。2.3馬踏棋盤流程將馬隨機地放在國際象棋的8*8棋盤Board88的某個方格中，然后令馬按走棋規(guī)則開始進行移動。要求馬將棋盤上的每個方格進入且只進入一次，走遍全部64個方格。2.4算法設計2.4.1 設計思想 利用某種算法直接找到最優(yōu)解，算出最優(yōu)路徑，而不是一步步嘗試遇到錯誤回溯。設一數(shù)組與棋盤坐標一一對應（1，1）到（8，8），存放每個棋盤格上應算出的路徑數(shù)字。 路徑從164存放到與棋盤數(shù)組中對應的數(shù)組中，將數(shù)組當形參傳到圖形用戶界面，利用Graphics繪制棋盤并打印數(shù)組。 建立主函數(shù)，調用計算路徑類和繪制棋盤類。2.4.2程序結構說明程序的運行關系如圖2-1. 圖2-1 程序運行關系圖2.4.3算法結構設計最優(yōu)算法設計 準備階段： (a) 按國際象棋馬的走法，最多有8種可能，創(chuàng)建數(shù)組int path=0,0,0,1,1,2,2,1,-2,3,-1,2,4,-1,-2,5,2,1,6,2,-1,7,-2,1,8,-2,-1存放8中可能，為了滿足與棋盤一一對應故用3×8數(shù)組。 (b) 創(chuàng)建數(shù)組int way=new int99存放棋盤每點可走的路徑數(shù)。 (c) 創(chuàng)建數(shù)組int output=new int99存放最終繪制棋盤格中輸出的數(shù)字，即行走路線。 (d) 計算出棋盤上每點的可走路徑數(shù)，存入way數(shù)組，超出棋盤邊界的點被舍棄，讓數(shù)組與棋盤一一對應。 計算階段： (a) 從用戶輸入起始點坐標，存入m，n。 (b) 先假設每個點最小可走路徑數(shù)為min=8。 (c) 根據(jù)way數(shù)組中已經(jīng)存放的值與假設的最小可走路徑數(shù)為8比較，若小于8則存入min，如此循環(huán)最多8次，找出使min值最小的點，設為下次要走的點，依次類推，直至找出64個點，即最優(yōu)路徑。用戶輸入 利用java提供的Scanner函數(shù)從操作臺進行輸入。圖形用戶界面 利用Jframe窗體建立圖形用戶界面，編寫構造函數(shù)，用Graphics()函數(shù)繪制矩形并填充顏色，畫出棋盤表格，并利用drawString()在相應的棋盤坐標中打印出output數(shù)組中數(shù)字。第三章 詳細設計3.1 Jisuan類實現(xiàn) public class jisuan /計算棋盤中各點可走路徑public void init(intway)int i,j,k,x,y;intpath=0,0,0,1,1,2,2,1,-2,3,-1,2,4,-1,-2,5,2,1,6,2,-1,7,-2,1,8,-2,-1; /存放馬的行走規(guī)則，為了使坐標和棋盤一一對應，定義8×3數(shù)組 for(i=1;i<=8;i+) /先初始各點可走路徑為零 for(j=1;j<=8;j+) wayij=0;for(i=1;i<=8;i+) /計算各點可走路徑，如果合法便存儲 for(j=1;j<=8;j+) for(k=1;k<=8;k+) x=i;y=j; x=x+pathk1; y=y+pathk2; /x,y代表走下一步后的坐標，通過k的增長，改變行走的方向 if(x>=1&&x<=8&&y>=1&&y<=8) /判斷是否落在棋盤內(nèi)，否則不存儲 wayij+ ; /init/jisuan注釋： 此類主要初始化各點的可走路徑，并且刪除不合法的點。 首先初始化way數(shù)組為0，然后利用for循環(huán)嵌套實現(xiàn)64次運算，每次再嵌套一個執(zhí)行8次的循環(huán)，利用k+實現(xiàn)改變行走路線，前提是path數(shù)組中已經(jīng)存儲了馬的行走規(guī)則，根據(jù)每次到達的點判斷是否落在棋盤內(nèi)，若合法則相應坐標格的way數(shù)組自加1，以此來計算出棋盤中各點的可走路線數(shù)，完成最優(yōu)算法的準備階段。3.2 Shuchu類算法實現(xiàn)public class shuchu public void calcu(intoutput,intway) int z,x,y,m,n,k,min; int i=0;int j=0; int path=0,0,0,1,1,2,2,1,-2,3,-1,2,4,-1,-2,5,2,1,6,2,-1,7,-2,1,8,-2,-1;System.out.println("請輸入馬的起始位置坐標:x y(其中x,y均為正整數(shù),0<x<9,0<y<9,輸入時兩數(shù)之間以空格隔開)");Scanner scan=new Scanner(System.in); /從鍵盤輸入起始點坐標m=scan.nextInt();n=scan.nextInt();if(m>=1&&m<=8&&n>=1&&n<=8) /判斷輸入位置是否合法 for(z=1;z<=64;z+) /分64次寫入 min = 8; /初始可選路徑最小值為8 outputmn=z; /用output來記錄所走路徑 waymn=0; /走過的點可選路徑設為0，沒走過設為可選路徑數(shù) for(k=1;k<=8;k+) /走最小可選路徑數(shù)的點 x=m+pathk1; y=n+pathk2; /x,y代表走下一步后的坐標，通過k的增長，改變行走的方向 if(x>=1&&x<=8&&y>=1&&y<=8) if(wayxy!=0) /沒走過的點 -wayxy; /可選路徑數(shù)減1，因為本點剛走過 if(wayxy<min) /如果可選路徑數(shù)小于min min=wayxy; /使axy存放最小可選路徑數(shù)的點 i=x; j=y; /form=i;n=j; /下一個點的坐標 /for“64次” /判斷合法 elseSystem.out.println("錯誤：坐標超出棋盤邊界！"); /calu/shuchu注釋： 此類為主要最優(yōu)算法的實現(xiàn)類。 首先依然定義馬的行走路線，和一些循環(huán)中用到的變量。然后利用Scanner函數(shù)進行用戶輸入。橫縱坐標存入m和n。 判斷起始坐標是否合法，合法則用一個64次的循環(huán)分別寫入output數(shù)組中馬的行走路線，假設min的值為8。 用一個8次循環(huán)分別列出馬的可走路徑，若合法且是沒走過的點將對應的way數(shù)組減1，因為下次若走到此點，可選路徑數(shù)必然要減1，不可走已經(jīng)走過的點。如果該點的可走路徑數(shù)<min中的值，則更新為此點的way數(shù)組值。最后將是min保持最小的點的坐標賦值給（m，n），作為馬將走的下一個點將此點的output數(shù)組值更新為2。以此類推馬的整個行走路線就完成了，且已經(jīng)將164分別寫入到output數(shù)組中.3.3Jframe類的實現(xiàn)import java.awt.Color;import javax.swing.*;import java.awt.Graphics;import java.awt.Font;public class Jframe extends JFrameint seed=new int99;public Jframe() /窗體構造函數(shù)this.setSize(500,500);setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);setVisible(true);public void paint(Graphics g) /創(chuàng)建Graphics畫圖super.paint(g);g.setColor(Color.black);g.drawRect(50,50,400,400); /畫棋盤邊界for(int i=1;i<=4;i+)for(int j=1;j<=4;j+)g.fillRect(100*j, 100*i-50, 50, 50); /畫棋盤黑格1for(int i=1;i<=4;i+)for(int j=1;j<=4;j+)g.fillRect(100*j-50, 100*i, 50, 50); /畫棋盤黑格2g.setColor(Color.blue);Font num=new Font("楷體",Font.BOLD,25);g.setFont(num); /設置字體for(int i=1;i<=8;i+)for(int j=1;j<=8;j+)g.drawString(seedij+"", 50*j+15,50*i+35); /打印棋盤格中數(shù)字public void write(int output) /將結果數(shù)組引入Jframe類，并賦給數(shù)組seedfor(int i=1;i<=8;i+)for(int j=1;j<=8;j+)seedij=outputij; /Jframe注釋: 此類為圖形用戶界面,主要完成棋盤的繪制和結果的打印. 創(chuàng)建構造函數(shù),設置窗體大小,使窗體可見. 創(chuàng)建Graphics()畫圖函數(shù),設置背景顏色為黑色,繪制棋盤邊框.因為國際象棋棋盤為黑白交替方格,所以將黑色部分用Rectfill()函數(shù)畫出,就形成了棋盤,利用for循環(huán)將黑色方格分兩次畫完,設計的棋盤坐標如下: (50,50) (400,50)(50,400) (400,400)圖3-1 棋盤的設計每個格子的長寬是50,50。左斜線是第一次畫的黑格,右斜線是第二次畫的黑格.3.4Main類的實現(xiàn)public class Main public static void main(String args) int i,j;int way=new int99; /初始化可算路徑數(shù)數(shù)組int output=new int99; /初始化結果輸出數(shù)組jisuan ad=new jisuan();ad.init(way); /運行計算類shuchu aw=new shuchu();aw.calcu(output, way); /運行輸出類System.out.printf("運行結果如下(稍后會以棋盤界面顯示,為便于看圖,相鄰兩步之間棋盤顏色不同):n");for(i=1;i<=8;i+) /輸出 for(j=1;j<=8;j+)System.out.printf("%6d",outputij);System.out.printf("n");Jframe w=new Jframe(); /圖形用戶輸出w.write(output); /載入結果輸出數(shù)組 /main /Main注釋:創(chuàng)建way和output數(shù)組.調用類并創(chuàng)建對象,對象調用函數(shù).在控制臺同樣輸出一份結果,和圖形用戶界面的相同.創(chuàng)建窗體,并傳入output數(shù)組參數(shù)流程圖如下：圖3-2 Main類流程圖程序的源代碼參見附錄。第四章 調試分析這次課程設計我遇到如下問題，最終通過調試分析都得到了很好的解決。4.1最優(yōu)算法的求解，無從下手，最后借鑒前輩的思路想到了走最小度數(shù)點的算法。4.2 從shuchu類計算的結果無法傳入Jframe函數(shù)，曾試過全局變量，但是分裝性不好，最后把結果數(shù)組當作形式參數(shù)傳入Jframe類的一個write（）函數(shù)。4.3無法在棋盤的格子上打印數(shù)字，因為drawstring（）函數(shù)只能打印字符型變量，而我的output是整形變量，最后利用drawstring（output+“”，50，50）一個小技巧將int型轉化為string型。4.4剛開始棋盤畫得很麻煩，所以后期直接用填充色矩形畫出黑的，其余的就成了白的，并分兩步話出棋盤，感覺比較簡單。4.5開始無法使數(shù)組與棋盤坐標一一對應。程序運行截屏見附錄B。第五章 總結5.1遇到的問題5.11最優(yōu)算法的求解，無從下手，最后借鑒前輩的思路想到了走最小度數(shù)點的算法。5.12 從shuchu類計算的結果無法傳入Jframe函數(shù)，曾試過全局變量，但是分裝性不好，最后把結果數(shù)組當作形式參數(shù)傳入Jframe類的一個write（）函數(shù)。5.13無法在棋盤的格子上打印數(shù)字，因為drawstring（）函數(shù)只能打印字符型變量，而我的output是整形變量，最后利用drawstring（output+“”，50，50）一個小技巧將int型轉化為string型。5.14剛開始棋盤畫得很麻煩，所以后期直接用填充色矩形畫出黑的，其余的就成了白的，并分兩步話出棋盤，感覺比較簡單。5.15開始無法使數(shù)組與棋盤坐標一一對應。5.2收獲與體會總體感覺這個課題還是比較簡單的，不找出問題的根本,就無法理解自己獲得的是什么,在一個星期的課程設計中，我將掌握的專業(yè)理論知識很好地運用到對這個課題的理解中.做到了理論和實踐相結合，在實踐中加深了對專業(yè)理論知識的理解，并提升了對理論知識的運用能力，獲得了許多寶貴的經(jīng)驗。5.21 鞏固和加深了對數(shù)據(jù)結構的理解，提高綜合運用本課程所學知識的能力。5.22 培養(yǎng)了我選用參考書，查閱手冊及文獻資料的能力。培養(yǎng)獨立思考，深入研究，分析問題、解決問題的能力。5.23 過實際編譯系統(tǒng)的分析設計、編程調試，掌握應用軟件的分析方法和工程設計方法。5.24 能夠按要求編寫課程設計報告書，能正確闡述設計和實驗結果，正確繪制系統(tǒng)和程序框圖。5.25 通過這次課程設計，培養(yǎng)了我嚴肅認真的工作作風，逐步建立正確的生產(chǎn)觀念、經(jīng)濟觀念和全局觀念。由于時間緊迫，我做的這個課程設計可能還不十分完善，但重要的是，這次課程設計讓我學到了很多知識。通過這次課程設計，我對數(shù)據(jù)結構課程有了進一步的了解和認識，對數(shù)據(jù)結構的理解上升到一個新的高度，也充分地了解到一個好的算法對于程序的重要性。最后再次感謝這次課程設計提供給我?guī)椭睦蠋煟瑢W們以及參考文獻的作者們，謝謝你們！參考文獻【1】 嚴蔚敏，吳偉民.數(shù)據(jù)結構（c語言版）.北京：清華大學出版社，2007【2】Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,，Clifford Stein.Introduction to Algorithms, Second Edition. 北京: 高等教育出版社, 2002【3】【美】s巴斯.計算機算法：設計與分析引論.朱洪等譯.上海：復旦大學出版社，19854 Ralph Morelli. Java面向對象程序設計（第三版）.北京：清華大學出版社， 2008【5】張亦輝，馮華，胡潔.Java面向對象程序設計.北京：人民郵電出版社，2008附錄A 源代碼-class jisuan-public class jisuan /計算棋盤中各點可走路徑public void init(intway)int i,j,k,x,y;int path=0,0,0,1,1,2,2,1,-2,3,-1,2,4,-1,-2,5,2,1,6,2,-1,7,-2,1,8,-2,-1;/存放馬的行走規(guī)則，為了使坐標和棋盤一一對應定義8*3數(shù)組for(i=1;i<=8;i+) /先初始各點可走路徑為零for(j=1;j<=8;j+)wayij=0;for(i=1;i<=8;i+) /計算各點可走路徑，如果合法便存儲for(j=1;j<=8;j+)for(k=1;k<=8;k+) x=i;y=j;x=x+pathk1;y=y+pathk2; /x,y代表走下一步后的坐標，通過k的增長，改變行走的方向if(x>=1&&x<=8&&y>=1&&y<=8) /判斷是否落在棋盤內(nèi)，否則不存儲wayij+; /init /jisuan-class shuchu-import java.util.Scanner;public class shuchu public void calcu(intoutput,intway)int z,x,y,m,n,k,min;int i=0;int j=0;int path=0,0,0,1,1,2,2,1,-2,3,-1,2,4,-1,-2,5,2,1,6,2,-1,7,-2,1,8,-2,-1;System.out.println("請輸入馬的起始位置坐標:x y(其中x,y均為正整數(shù),0<x<9,0<y<9,輸入時兩數(shù)之間以空格隔開)");Scanner scan=new Scanner(System.in); /從鍵盤輸入起始點坐標m=scan.nextInt();n=scan.nextInt();if(m>=1&&m<=8&&n>=1&&n<=8) /判斷輸入位置是否合法for(z=1;z<=64;z+) /分64次寫入min = 8; /初始可選路徑最小值為8outputmn=z; /用output來記錄所走路徑waymn=0; /走過的點可選路徑設為0，沒走過設為可選路徑數(shù)for(k=1;k<=8;k+) /走最小可選路徑數(shù)的點x=m+pathk1;y=n+pathk2; /x,y代表走下一步后的坐標，通過k的增長，改變行走的方向if(x>=1&&x<=8&&y>=1&&y<=8)if(wayxy!=0) /沒走過的點-wayxy; /可選路徑數(shù)減1，因為本點剛走過if(wayxy<min) /如果可選路徑數(shù)小于 minmin=wayxy; /使axy存放最小可選路徑數(shù)的點i=x;j=y; /form=i;n=j; /下一個點的坐標 /for“64次” /判斷合法elseSystem.out.println("錯誤：坐標超出棋盤邊界！"); /calu /shuchu-class Jframe-import java.awt.Color;import javax.swing.*;import java.awt.Graphics;import java.awt.Font;public class Jframe extends JFrameint seed=new int99;public Jframe() /窗體構造函數(shù)this.setSize(500,500);setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);setVisible(true);public void paint(Graphics g) /創(chuàng)建Graphics畫圖super.paint(g);g.setColor(Color.black);g.drawRect(50,50,400,400); /畫棋盤邊界for(int i=1;i<=4;i+)for(int j=1;j<=4;j+)g.fillRect(100*j, 100*i-50, 50, 50); /畫棋盤黑格1for(int i=1;i<=4;i+)for(int j=1;j<=4;j+)g.fillRect(100*j-50, 100*i, 50, 50); /畫棋盤黑格2g.setColor(Color.blue);Font num=new Font("楷體",Font.BOLD,25);g.setFont(num); /設置字體for(int i=1;i<=8;i+)for(int j=1;j<=8;j+)g.drawString(seedij+"", 50*j+15,50*i+35); /打印棋盤格中數(shù)字public void write(int output) /將結果數(shù)組引入Jframe類，并賦給數(shù)組seedfor(int i=1;i<=8;i+)for(int j=1;j<=8;j+)seedij=outputij; /Jframe-class Main-public class Main public static void main(String args) int i,j;int way=new int99; /初始化可算路徑數(shù)數(shù)組int output=new int99; /初始化結果輸出數(shù)組jisuan ad=new jisuan();ad.init(way); /運行計算類shuchu aw=new shuchu();aw.calcu(output, way); /運行輸出類System.out.printf("運行結果如下(稍后會以棋盤界面顯示,為便于看圖,相鄰兩步之間棋盤顏色不同):n");for(i=1;i<=8;i+) /輸出 for(j=1;j<=8;j+)System.out.printf("%6d",outputij);System.out.printf("n");Jframe w=new Jframe(); /圖形用戶輸出w.write(output); /載入結果輸出數(shù)組 /main /Main附錄B 運行截屏4.1第一次輸入坐標(6,6)圖4-1 第一次輸入截圖圖4-2 第一次運行結果截圖（其中數(shù)字編號即為馬踏棋盤的順序）4.2第二次輸入坐標(8,1)圖4-3 第二次輸入截圖圖4-4 第二次運行結果截圖4.3第三次輸入坐標(5,9)圖4-5 第三次輸入截圖圖4-6 第三次運行結果截圖26