..前言學習數據結構的最終目的是解決實際的應用問題,特別是非數值計算類型的應用問題,數據結構課程設計就是為此目的一次實際訓練。要求我們在對題目進行獨立分析的基礎上,完成設計和開發,并最終接受嚴格的測試考核。以深化對數據結構課程中基本概念、理論和方法的理解,提升綜合運用所學知識處理實際問題的能力,使我們的的程序設計能力與調試水平有一個明顯的提升。課程設計所安排的題目,都有一定的難度和深度,從抽象數據類型的提煉、數據結構選擇到算法的設計,均由我們每個人自主完成。在一周的時間內,歷經查找參考資料、使用技術手冊、設計編碼和撰寫文檔的實踐,進一步升華對軟件工程師和程序員人格素質的認識和理解。本課程設計的主要設計內容是：設計一個馬踏棋盤問題的演示程序。即將馬隨機地放在國際象棋的8*8棋盤的某個方格中,然后令馬按走棋規則開始進行移動。要求馬將棋盤上的每個方格進入且只進入一次,走遍全部64個方格。要求編制非遞歸程序,求出馬的行走路線,將數字1,2,…,64依次填入一個8*8的方陣在屏幕上顯示輸出。針對該問題本課程設計采用的是面向對象的開發語言Java,在Windows7,myeclipse8.5.0的平臺上開發出來,并有圖形界面。最終較好的實現了全部要求,達到了預期效果。從中我也學到了很多,不僅僅是課堂外的新知識,還有那種會查資料,會學習新知識的能力。這個課程設計的順利完成,離不開胡老師的指導和幫助,在他的細心指導和幫助下,我對馬踏棋盤程序開發的整個流程有了深刻地了解和系統地掌握,在這里學生表示真誠地感謝。另外也謝謝這次課程設計提供給我幫助的同學們。此外,本課程設計還參考了一些文獻資料,在此向這些文獻資料的作者深表謝意。本課程設計可作為數據結構和Java課程教學的參考案例。由于時間倉促和本人水平所限,設計中難免有不當和欠妥之處,敬請老師不吝批評指正。筆者2016.6目錄摘要………………………3需求分析………………….4第二章概要設計………………….52.1系統描述。。。?！?52.2運行環境…………..52.3馬踏棋盤流程…………………52.4算法設計第三章詳細設計3.1Jisuan類實現Disizhang4.14,24.3Diwu5.15.2CankaowenxianFulu摘要本課程設計中的程序實現了馬踏棋盤問題的求解,并能夠演示起始位置在棋盤上任何位置的問題的實現.程序采用圖形演示,使算法的描述更形象,更生動,使教學更能產生良好的效果。對于該程序,我嚴格按照面向對象的思想進行開發,其中有Jisuan類,Shuchu類,Jframe類和Main四個類。其中Jisuan類主要是初始化各點的可走路徑,并且刪除不合法的點；Shuchu類主要最優算法的實現；Jframe類為圖形用戶界面的設計,主要完成棋盤的繪制和結果的打?。籑ain類主要是負責整個程序的控制。最終調試運行通過,實現了全部要求,取得了理想效果。關鍵詞：數據結構馬踏棋盤Java圖形界面AbstractThiscoursedesignoftheprogramrealizationhorsesonboardthesolution,andtodemonstratethestartingpositionontheboardoftherealizationoftheproblemanyposition.Theprogramusinggraphicalpresentation,themethodofmoreimage,themorevividdescription,andmaketheteachingmorecanproducegoodeffect.Fortheprogram,Iinstrictaccordancewiththeobject-orientedideasofdevelopment,includingJisuanclass,Shuchuclass,JframeclassesandMainfourclasses.AmongthemJisuankindbasicallyistheinitialpointsofwalkpath,andremovenotlegalpoint;Shuchumainkindsoftherealizationoftheoptimalalgorithm;Jframeclassforthegraphicaluserinterfacedesign,themainfinishdrawingtheboardandresultsoftheprint;Mainkindsofmajorisresponsiblefortheentireprocesscontrol.Finaltestandoperation,realizetherequirementsthroughall,maketheidealeffect.Keywords:datastructurehorseonboardJavagraphicalinterface第一章需求分析數據結構課程設計是計算機科學與技術專業學生必做的集中實踐性環節之一,是學習完《數據結構》課程后進行的一次全面的綜合練習。其目的在于通過課程設計,使學生能夠得到較系統的技能訓練,從而鞏固和加深對數據結構的基礎理論知識的理解,培養學生綜合運用所學理論知識解決實際問題的能力,使學生成為具有扎實的計算機理論基礎和較強的獨立動手能力的復合型、應用型人才。馬踏棋盤問題是一個古老而著名的問題,它最初是由大數學家Euler提出的.問題是這樣的:國際象棋中的棋子<叫作馬>在一個空棋盤內移動,問它能否經過64格中的每一格且只經過一次?<馬按L行移動,即在某方向前進兩格接著在與原方向垂直的方向上前進一格>本程序實現了馬踏棋盤問題的求解,并能夠演示起始位置在棋盤上任何位置的問題的實現.程序采用圖形演示,使算法的描述更形象,更生動,使教學更能產生良好的效果。第二章概要設計2.1系統描述本程序采用來編制整個程序,這樣既可以使大家對算法的實現有了一定的了解,也可以熟悉一下Java圖形界面以及Java語言的命名規范。作為數據結構的課程設計,本人希望同時也能讓大家順便熟悉一下Java的基本語言結構和強大的開發能力。在馬踏棋盤的課程設計中,我們嚴格按照面向對象的思想進行開發,其中有Jisuan類,Shuchu類,Jframe類和Main類。讀者應注意各個類之間的關系,以便也能順道理解Java中類的思想。2.2運行環境本程序是在windows7,的環境下運行的。2.3馬踏棋盤流程將馬隨機地放在國際象棋的8*8棋盤Board[8][8]的某個方格中,然后令馬按走棋規則開始進行移動。要求馬將棋盤上的每個方格進入且只進入一次,走遍全部64個方格。2.4算法設計設計思想=1\*GB3①利用某種算法直接找到最優解,算出最優路徑,而不是一步步嘗試遇到錯誤回溯。=2\*GB3②設一數組與棋盤坐標一一對應〔1,1到〔8,8,存放每個棋盤格上應算出的路徑數字。=3\*GB3③路徑從1～64存放到與棋盤數組中對應的數組中,將數組當形參傳到圖形用戶界面,利用Graphics繪制棋盤并打印數組。=4\*GB3④建立主函數,調用計算路徑類和繪制棋盤類。程序結構說明程序的運行關系如圖2-1.圖2-1程序運行關系圖2.4.3算法結構設計=1\*GB3①最優算法設計準備階段：<a>按國際象棋馬的走法,最多有8種可能,創建數組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}}存放8中可能,為了滿足與棋盤一一對應故用3×8數組。<b>創建數組int[][]way=newint[9][9]存放棋盤每點可走的路徑數。<c>創建數組int[][]output=newint[9][9]存放最終繪制棋盤格中輸出的數字,即行走路線。<d>計算出棋盤上每點的可走路徑數,存入way數組,超出棋盤邊界的點被舍棄,讓數組與棋盤一一對應。計算階段：<a>從用戶輸入起始點坐標,存入m,n。<b>先假設每個點最小可走路徑數為min=8。<c>根據way數組中已經存放的值與假設的最小可走路徑數為8比較,若小于8則存入min,如此循環最多8次,找出使min值最小的點,設為下次要走的點,依次類推,直至找出64個點,即最優路徑。=2\*GB3②用戶輸入利用java提供的Scanner函數從操作臺進行輸入。=3\*GB3③圖形用戶界面利用Jframe窗體建立圖形用戶界面,編寫構造函數,用Graphics<>函數繪制矩形并填充顏色,畫出棋盤表格,并利用drawString<>在相應的棋盤坐標中打印出output數組中數字。第三章詳細設計3.1Jisuan類實現publicclassjisuan{//計算棋盤中各點可走路徑publicvoidinit<int[][]way>{inti,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}};//存放馬的行走規則,為了使坐標和棋盤一一對應,定義8×3數組for<i=1;i<=8;i++>//先初始各點可走路徑為零for<j=1;j<=8;j++>way[i][j]=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+path[k][1];y=y+path[k][2];//x,y代表走下一步后的坐標,通過k的增長,改變行走的方向if<x>=1&&x<=8&&y>=1&&y<=8>//判斷是否落在棋盤內,否則不存儲way[i][j]++;}}//init}//jisuan注釋：此類主要初始化各點的可走路徑,并且刪除不合法的點。首先初始化way數組為0,然后利用for循環嵌套實現64次運算,每次再嵌套一個執行8次的循環,利用k++實現改變行走路線,前提是path數組中已經存儲了馬的行走規則,根據每次到達的點判斷是否落在棋盤內,若合法則相應坐標格的way數組自加1,以此來計算出棋盤中各點的可走路線數,完成最優算法的準備階段。3.2Shuchu類算法實現publicclassshuchu{publicvoidcalcu<int[][]output,int[][]way>{intz,x,y,m,n,k,min;inti=0;intj=0;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}};n<"請輸入馬的起始位置坐標:xy<其中x,y均為正整數,0<x<9,0<y<9,輸入時兩數之間以空格隔開>">;Scannerscan=newScanner<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;//初始可選路徑最小值為8output[m][n]=z;//用output[][]來記錄所走路徑way[m][n]=0;//走過的點可選路徑設為0,沒走過設為可選路徑數for<k=1;k<=8;k++>//走最小可選路徑數的點{x=m+path[k][1];y=n+path[k][2];//x,y代表走下一步后的坐標,通過k的增長,改變行走的方向if<x>=1&&x<=8&&y>=1&&y<=8>if<way[x][y]!=0>//沒走過的點{--way[x][y];//可選路徑數減1,因為本點剛走過if<way[x][y]<min>//如果可選路徑數小于min{min=way[x][y];//使a[x][y]存放最小可選路徑數的點i=x;j=y;}}}//form=i;n=j;//下一個點的坐標}//for"64次"}//判斷合法elseSystem.out.println<"錯誤：坐標超出棋盤邊界！">;}//calu}//shuchu注釋：此類為主要最優算法的實現類。首先依然定義馬的行走路線,和一些循環中用到的變量。然后利用Scanner函數進行用戶輸入。橫縱坐標存入m和n。判斷起始坐標是否合法,合法則用一個64次的循環分別寫入output數組中馬的行走路線,假設min的值為8。用一個8次循環分別列出馬的可走路徑,若合法且是沒走過的點將對應的way數組減1,因為下次若走到此點,可選路徑數必然要減1,不可走已經走過的點。如果該點的可走路徑數<min中的值,則更新為此點的way數組值。最后將是min保持最小的點的坐標賦值給〔m,n,作為馬將走的下一個點將此點的output數組值更新為2。以此類推馬的整個行走路線就完成了,且已經將1～64分別寫入到output數組中.3.3Jframe類的實現importjava.awt.Color;importjavax.swing.*;importjava.awt.Graphics;importjava.awt.Font;publicclassJframeextendsJFrame{int[][]seed=newint[9][9];publicJframe<>{//窗體構造函數this.setSize<500,500>; setDefaultCloseOperation<JFrame.EXIT_ON_CLOSE>; setVisible<true>; }publicvoidpaint<Graphicsg>{//創建Graphics畫圖super.paint<g>; g.setColor<Color.black>; g.drawRect<50,50,400,400>;//畫棋盤邊界for<inti=1;i<=4;i++>for<intj=1;j<=4;j++> g.fillRect<100*j,100*i-50,50,50>;//畫棋盤黑格1for<inti=1;i<=4;i++>for<intj=1;j<=4;j++> g.fillRect<100*j-50,100*i,50,50>;//畫棋盤黑格2 g.setColor<Color.blue>; Fontnum=newFont<"楷體",Font.BOLD,25>; g.setFont<num>;//設置字體for<inti=1;i<=8;i++>for<intj=1;j<=8;j++> g.drawString<seed[i][j]+"",50*j+15,50*i+35>;//打印棋盤格中數字}publicvoidwrite<intoutput[][]>{//將結果數組引入Jframe類,并賦給數組seedfor<inti=1;i<=8;i++>for<intj=1;j<=8;j++>seed[i][j]=output[i][j]; } }//Jframe注釋:此類為圖形用戶界面,主要完成棋盤的繪制和結果的打印.創建構造函數,設置窗體大小,使窗體可見.創建Graphics<>畫圖函數,設置背景顏色為黑色,繪制棋盤邊框.因為國際象棋棋盤為黑白交替方格,所以將黑色部分用Rectfill<>函數畫出,就形成了棋盤,利用for循環將黑色方格分兩次畫完,設計的棋盤坐標如下:<50,50><400,50><50,400><400,400>圖3-1棋盤的設計每個格子的長寬是50,50。左斜線是第一次畫的黑格,右斜線是第二次畫的黑格.3.4Main類的實現publicclassMain{publicstaticvoidmain<String[]args>{inti,j;int[][]way=newint[9][9];//初始化可算路徑數數組int[][]output=newint[9][9];//初始化結果輸出數組 jisuanad=newjisuan<>; ad.init<way>;//運行計算類 shuchuaw=newshuchu<>; aw.calcu<output,way>;//運行輸出類 System.out.printf<"運行結果如下<稍后會以棋盤界面顯示,為便于看圖,相鄰兩步之間棋盤顏色不同>:\n">;for<i=1;i<=8;i++>{//輸出for<j=1;j<=8;j++> System.out.printf<"%6d",output[i][j]>; System.out.printf<"\n">; } Jframew=newJframe<>;//圖形用戶輸出 w.write<output>;//載入結果輸出數組 }//main }//Main注釋:創建way和output數組.調用類并創建對象,對象調用函數.在控制臺同樣輸出一份結果,和圖形用戶界面的相同.創建窗體,并傳入output數組參數流程圖如下：圖3-2Main類流程圖程序的源代碼參見附錄。第四章調試分析這次課程設計我遇到如下問題,最終通過調試分析都得到了很好的解決。4.1最優算法的求解,無從下手,最后借鑒前輩的思路想到了走最小度數點的算法。4.2從shuchu類計算的結果無法傳入Jframe函數,曾試過全局變量,但是分裝性不好,最后把結果數組當作形式參數傳入Jframe類的一個write〔函數。4.3無法在棋盤的格子上打印數字,因為drawstring〔函數只能打印字符型變量,而我的output是整形變量,最后利用drawstring〔output+"",50,50一個小技巧將int型轉化為string型。4.4剛開始棋盤畫得很麻煩,所以后期直接用填充色矩形畫出黑的,其余的就成了白的,并分兩步話出棋盤,感覺比較簡單。4.5開始無法使數組與棋盤坐標一一對應。程序運行截屏見附錄B。第五章總結5.1遇到的問題5.11最優算法的求解,無從下手,最后借鑒前輩的思路想到了走最小度數點的算法。5.12從shuchu類計算的結果無法傳入Jframe函數,曾試過全局變量,但是分裝性不好,最后把結果數組當作形式參數傳入Jframe類的一個write〔函數。5.13無法在棋盤的格子上打印數字,因為drawstring〔函數只能打印字符型變量,而我的output是整形變量,最后利用drawstring〔output+"",50,50一個小技巧將int型轉化為string型。5.14剛開始棋盤畫得很麻煩,所以后期直接用填充色矩形畫出黑的,其余的就成了白的,并分兩步話出棋盤,感覺比較簡單。5.15開始無法使數組與棋盤坐標一一對應。5.2收獲與體會總體感覺這個課題還是比較簡單的,不找出問題的根本,就無法理解自己獲得的是什么,在一個星期的課程設計中,我將掌握的專業理論知識很好地運用到對這個課題的理解中.做到了理論和實踐相結合,在實踐中加深了對專業理論知識的理解,并提升了對理論知識的運用能力,獲得了許多寶貴的經驗。5.21鞏固和加深了對數據結構的理解,提高綜合運用本課程所學知識的能力。5.22培養了我選用參考書,查閱手冊及文獻資料的能力。培養獨立思考,深入研究,分析問題、解決問題的能力。5.23過實際編譯系統的分析設計、編程調試,掌握應用軟件的分析方法和工程設計方法。5.24能夠按要求編寫課程設計報告書,能正確闡述設計和實驗結果,正確繪制系統和程序框圖。5.25通過這次課程設計,培養了我嚴肅認真的工作作風,逐步建立正確的生產觀念、經濟觀念和全局觀念。由于時間緊迫,我做的這個課程設計可能還不十分完善,但重要的是,這次課程設計讓我學到了很多知識。通過這次課程設計,我對數據結構課程有了進一步的了解和認識,對數據結構的理解上升到一個新的高度,也充分地了解到一個好的算法對于程序的重要性。最后再次感謝這次課程設計提供給我幫助的老師,同學們以及參考文獻的作者們,謝謝你們！參考文獻嚴蔚敏,吳偉民.數據結構〔c語言版.北京：清華大學出版社,2007[2]ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,,CliffordStein.IntroductiontoAlgorithms,SecondEdition.北京:高等教育出版社,2002[3][美]s巴斯.計算機算法：設計與分析引論.朱洪等譯.上海：復旦大學出版社,1985[4]RalphMorelli.Java面向對象程序設計〔第三版.北京：清華大學出版社,2008[5]張亦輝,馮華,胡潔.Java面向對象程序設計.北京：人民郵電出版社,2008附錄A源代碼-----------------------classjisuan-----------------------publicclassjisuan{//計算棋盤中各點可走路徑publicvoidinit<int[][]way>{inti,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}};//存放馬的行走規則,為了使坐標和棋盤一一對應定義8*3數組for<i=1;i<=8;i++>//先初始各點可走路徑為零for<j=1;j<=8;j++> way[i][j]=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+path[k][1]; y=y+path[k][2];//x,y代表走下一步后的坐標,通過k的增長,改變行走的方向if<x>=1&&x<=8&&y>=1&&y<=8>//判斷是否落在棋盤內,否則不存儲 way[i][j]++; } }//init }//jisuan--------------------------classshuchu--------------------importjava.util.Scanner;publicclassshuchu{publicvoidcalcu<int[][]output,int[][]way>{intz,x,y,m,n,k,min;inti=0;intj=0;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}}; System.out.println<"請輸入馬的起始位置坐標:xy<其中x,y均為正整數,0<x<9,0<y<9,輸入時兩數之間以空格隔開>">; Scannerscan=newScanner<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 output[m][n]=z;//用output[][]來記錄所走路徑 way[m][n]=0;//走過的點可選路徑設為0,沒走過設為可選路徑數for<k=1;k<=8;k++>{//走最小可選路徑數的點 x=m+path[k][1]; y=n+path[k][2];//x,y代表走下一步后的坐標,通過k的增長,改變行走的方向if<x>=1&&x<=8&&y>=1&&y<=8>if<way[x][y]!=0>{//沒走過的點 --way[x][y];//可選路徑數減1,因為本點剛走過if<way[x][y]<min>{//如果可選路徑數小于min min=way[x][y];//使a[x][y]存放最小可選路徑數的點 i=x; j=y; } } }//for m=i;n=j;//下一個點的坐標 }//for"64次" }//判斷合法else System.out.println<"錯誤：坐標超出棋盤邊界！">; }//calu }//shuchu--------------------------classJframe--------------------importjava.awt.Color;importjavax.swing.*;importjava.awt.Graphics;importjava.awt.Font;publicclassJframeextendsJFrame{int[][]seed=newint[9][9];publicJframe<>{//窗體構造函數this.setSize<500,500>;setDefaultCloseOperation<JFrame.EXIT_ON_CLOSE>; setVisible<