數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--四子棋

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</b></p><p><b>　　1 需求分析</b></p><p>　　1.1 課題背景及意義</p><p>　　全球在使用的移動(dòng)電話已經(jīng)超過10億部，而且這個(gè)數(shù)字每天都在不斷增加。手機(jī)在作為一種便攜通信工具的同時(shí)，它的功能也在不斷的豐富，進(jìn)而推進(jìn)手機(jī)游戲的發(fā)展。根據(jù)

2、《2012手機(jī)游戲用戶行為分析報(bào)告》，隨著智能手機(jī)的普及和手機(jī)性能的提高，手機(jī)上的終端應(yīng)用越來(lái)越豐富，作為手機(jī)上的重要的娛樂應(yīng)用，手機(jī)游戲市場(chǎng)也在快速成長(zhǎng)，越來(lái)越多的用戶通過手機(jī)游戲來(lái)打發(fā)無(wú)聊的時(shí)間，其中76%的用戶單次玩手機(jī)游戲都在30分鐘左右。</p><p>　　結(jié)合個(gè)人水平和興趣愛好，本人將借本次課程設(shè)計(jì)機(jī)會(huì)設(shè)計(jì)一款休閑娛樂型的四子棋游戲，在娛樂自我，鍛煉編程設(shè)計(jì)能力的同時(shí)，希望也借此給身邊的朋友們帶來(lái)快

3、樂。</p><p><b>　　1.2 課題要求</b></p><p>　　A. 支持android手機(jī)的四子棋游戲</p><p>　　B. 設(shè)計(jì)一個(gè)7*6棋盤大小的四子棋雙人對(duì)戰(zhàn)游戲程序，先四子連線（橫、縱、斜）者勝。</p><p>　　C. 選做內(nèi)容：支持棋局錄制與重放 -- 悔棋和新開功能，圖形化操作界面&

4、lt;/p><p>　　1.3 軟件格式規(guī)定</p><p>　　A.程序所能達(dá)到的功能 :正確判斷輸贏并有相應(yīng)的語(yǔ)音和文字提示</p><p><b>　　B.測(cè)試的數(shù)據(jù)：</b></p><p>　　1)、正確的輸入： </p><p>　　提示：藍(lán)棋贏，并將藍(lán)棋變?yōu)榱硗庖环N顏色 -- 天藍(lán)和響起

5、贏局的音樂</p><p>　　2)、用戶誤輸入： </p><p>　　提示：親,我的悔棋能力有限啊!</p><p><b>　　1.4 設(shè)計(jì)目標(biāo)</b></p><p>　　A. 軟件名稱：Four In A Line（四子棋）</p><p>　　B. 軟件組成：FourInALine.a

6、pk（android系統(tǒng)應(yīng)用程序）</p><p>　　C. 制作平臺(tái)及相關(guān)調(diào)試工具：Eclipse ； AndroidSDK</p><p>　　D. 運(yùn)行環(huán)境：android手機(jī)/winxp/win7(PC平臺(tái)必須具有AndroidSDK)</p><p><b>　　E. 性能特點(diǎn)：</b></p><p>　　（

7、1）軟件由兩個(gè)可執(zhí)行文件組成，各具特點(diǎn):</p><p>　　FourInALine.apk為android系統(tǒng)應(yīng)用程序，體積小，界面友好，使用方便。</p><p>　?。?）方便重新開始游戲和悔棋。</p><p><b>　?。?）判贏用時(shí)少。</b></p><p>　　（4）個(gè)別其他功能可進(jìn)行再擴(kuò)展。</

8、p><p><b>　　2 概要設(shè)計(jì)</b></p><p>　　2.1問題解決的思路概述</p><p>　　首先是確定結(jié)構(gòu)化程序設(shè)計(jì)的流程圖，利用已存在的數(shù)據(jù)結(jié)構(gòu)來(lái)構(gòu)造一個(gè)存儲(chǔ)棋盤的結(jié)構(gòu)，接著把游戲?qū)崿F(xiàn)分成六個(gè)主要的模塊：實(shí)現(xiàn)悔棋的模塊、實(shí)現(xiàn)新開的模塊、實(shí)現(xiàn)音樂的模塊、實(shí)現(xiàn)繪圖的模塊，實(shí)現(xiàn)控制線程的模塊，實(shí)現(xiàn)判贏的模塊，然后各個(gè)模塊里面還要分成

9、若干種情況來(lái)考慮并通過函數(shù)的嵌套調(diào)用來(lái)實(shí)現(xiàn)其功能。最后，編寫main主函數(shù)以實(shí)現(xiàn)游戲的可玩性和正確性，調(diào)試程序并將不足的地方加以修改。總而言之，就是先用自頂向下、逐步細(xì)化的設(shè)計(jì)方法來(lái)分析并畫出程序設(shè)計(jì)流程圖；然后用自下而上、逐步積累的設(shè)計(jì)方法來(lái)寫出程序。</p><p>　　2.2 相關(guān)函數(shù)介紹說(shuō)明</p><p>　　在android版本程序定義一個(gè)用于存儲(chǔ)棋盤的二維數(shù)組變量：</

10、p><p>　　private static int[][] ChessBoardState;[1]</p><p>　?。?）android版本程序下定義的主要函數(shù)</p><p>　　public boolean isWin(int x, int y)// 判斷贏家，采用遍歷最后下的棋子在8個(gè)方向上的棋子</p><p>　　public v

11、oid back(Context context)// 悔棋函數(shù)</p><p>　　public void play()//游戲主線程</p><p>　　public void setXY(MyBackChessState myBackChessState)//處理?xiàng)ｍ斣?lt;/p><p>　　public Rect getRect(int[] xy)

12、 // 標(biāo)記二維數(shù)組對(duì)應(yīng)的矩形區(qū)域，也即是棋子該下的位置</p><p>　　public Rect getRect(int x, int y) // 標(biāo)記二維數(shù)組對(duì)應(yīng)的矩形區(qū)域，也即是棋子該下的位置</p><p>　　private int[] getIndexofXY() // 獲得當(dāng)前坐標(biāo)在二維數(shù)組中對(duì)

13、應(yīng)的索引。XY[0]是橫坐標(biāo)，也即是棋盤的第某列數(shù)；XY[1]是縱坐標(biāo)，也即是棋盤的第某橫。</p><p>　　private int searchEmptyTopTile(int x, int[][] chessboardstate) //返回當(dāng)列最上方無(wú)棋子的坐標(biāo),也即是棋盤的第某橫.</p><p>　　public void setChessBoardState(int[][]

14、 ChessBoardState)//保存棋盤狀態(tài)</p><p>　　public DrawGraph getChessBoardView() //獲得繪圖實(shí)例</p><p>　　public void setWinner(int player) //設(shè)置贏局提示(提示對(duì)應(yīng)玩家贏)</p><p>　　public void nextplayer(i

15、nt player) //設(shè)置下一玩家</p><p>　　public void newGame(Context context) //觸發(fā)開始新游戲</p><p>　　public boolean onTouch(View v, MotionEvent event) //綁定棋盤的觸摸事件</p><p>　　public static void play

16、(Context context, int resource) //播放音樂</p><p>　　private void updateView(Canvas canvas)// 更新游戲界面</p><p>　　public void showChess(Canvas canvas, int player, Rect rect) // 設(shè)置當(dāng)前玩家的棋子</p><

17、p>　　public void showLastChess(Canvas chess, int player, Rect rect)//顯示最后下的棋子</p><p>　　public void clearView(Canvas canvas) // 清空整個(gè)棋盤視圖</p><p>　　private void init() //初始化視圖</p><p

18、>　　public static Bitmap getBitmapFromResId(Context context, int resId) //獲得棋盤圖片資源</p><p>　　public static Bitmap zoomBitmap(Bitmap bitmap, float width, float height) //縮放棋子圖片資源</p><p>　　2.3 主程

19、序的流程基函數(shù)調(diào)用說(shuō)明</p><p>　?。?）主程序的簡(jiǎn)要流程圖</p><p><b>　　圖1 主程序流程圖</b></p><p>　?。?）各程序模塊之間的層次（調(diào)用）關(guān)系</p><p>　　調(diào)用“findViews()”和“initViews()”方法綁定各個(gè)控件，以便調(diào)用相應(yīng)的活動(dòng)界面，然后調(diào)用各模塊進(jìn)

20、行游戲。</p><p>　　在每一個(gè)功能模塊中都幾乎涉及到棋盤數(shù)組的存取，所以都要調(diào)用“getChessBoardState()”對(duì)數(shù)組變量初始化。</p><p>　　實(shí)現(xiàn)音樂的模塊“Music”類，首先要?jiǎng)?chuàng)建一個(gè)音頻播放實(shí)例，然后啟動(dòng)它。在游戲運(yùn)行中根據(jù)其他模塊是否調(diào)用其stop()方法或重新調(diào)用其play()方法。音樂模塊流程圖如下：</p><p>　　圖

21、2 音樂模塊流程圖</p><p>　　實(shí)現(xiàn)控制線程的模塊“Control”類，首先要調(diào)用getIndexofXY()方法計(jì)算用戶點(diǎn)擊的視圖坐標(biāo)對(duì)應(yīng)的棋盤二維數(shù)組坐標(biāo)。若此次點(diǎn)擊有效，調(diào)用悔棋模塊存儲(chǔ)此次操作和調(diào)用判贏模塊的isWin()方法判斷勝負(fù)，若贏局出現(xiàn)就再調(diào)用音樂模塊。最后調(diào)用繪圖更新整個(gè)游戲視圖。若此次點(diǎn)擊無(wú)效，直接返回?？刂凭€程模塊流程圖如下：</p><p>　　圖3 控制

22、線程模塊流程圖</p><p>　　實(shí)現(xiàn)判贏的模塊“Winner”類，首先調(diào)用“isWin()”方法判斷是否有贏局出現(xiàn)，然后在游戲運(yùn)行中根據(jù)其他模塊是否調(diào)用其getSameChess()方法來(lái)設(shè)置相同棋子或調(diào)用updateSameChess()方法來(lái)重置Winner類中的靜態(tài)變量?？刂凭€程模塊流程圖如下：</p><p>　　圖4 判贏模塊流程圖</p><p>　

23、　實(shí)現(xiàn)繪圖的模塊“DrawGraph”類，首先調(diào)用“onDraw()”以實(shí)現(xiàn)視圖初始化和棋盤繪制。然后再調(diào)用控制線程模塊的getRect()方法獲取棋子應(yīng)下的位置，接著調(diào)用getXY()方法和showLastChess()方法設(shè)置最后下的棋子。若有贏局出現(xiàn)，則調(diào)用判贏模塊的getSameChess()方法來(lái)設(shè)置相同棋子?？刂凭€程模塊流程圖如下：</p><p><b>　　圖5繪圖模塊流程圖</b

24、></p><p>　　實(shí)現(xiàn)悔棋的模塊“BackChess”類，首先調(diào)用“back()”判斷當(dāng)前棧是否為空，是則彈出提示信息并退出。否則彈出棧頂元素，重新賦值為0。然后調(diào)用控制線程模塊的getChessBoardView()方法獲得DrawGraph的實(shí)例，用于更新棋盤。最后調(diào)用控制線程模塊的setX Y()方法設(shè)置上一棋子的坐標(biāo)。控制線程模塊流程圖如下：</p><p><b

25、>　　圖6悔棋模塊流程圖</b></p><p>　　實(shí)現(xiàn)新開的模塊“New”類，首先調(diào)用“newGame()”新建棋盤數(shù)組，然后調(diào)用控制線程模塊的setChessBoardState()方法對(duì)棋盤數(shù)組進(jìn)行重新初始化, 然后調(diào)用控制線程模塊的getChessBoardView()方法獲得DrawGraph的實(shí)例, 更新棋盤。接著調(diào)用悔棋模塊的clearStack()方法清空原先棧中元素。最后調(diào)用

26、判贏模塊的updateSameChess()重置靜態(tài)變量和音樂模塊的play()方法重啟背景音樂。新開模塊流程圖如下：</p><p><b>　　圖7悔棋模塊流程圖</b></p><p><b>　　3 詳細(xì)設(shè)計(jì)</b></p><p>　　3.1 棋盤存儲(chǔ)的實(shí)現(xiàn)</p><p>　　棋盤的大小

27、一般都是固定的常量，所以可以用二維數(shù)組來(lái)存儲(chǔ)棋盤的狀態(tài)，其結(jié)構(gòu)簡(jiǎn)單且容易,是一種合理的數(shù)據(jù)結(jié)構(gòu)。二維數(shù)組定義如下：</p><p>　　private static int[][] ChessBoardState = new int[ROW][COLUMN];</p><p>　　3.2 各模塊主要算法</p><p>　　在四子棋游戲的程序設(shè)計(jì)中，每一部分都會(huì)調(diào)用

28、一些其他其它函數(shù)來(lái)輔助完成運(yùn)算（例如：對(duì)棋盤數(shù)組、當(dāng)前玩家和棋盤視圖的初始化，獲取棋子應(yīng)下的位置等），在這里主要說(shuō)明四子棋游戲的程序設(shè)計(jì)，其它函數(shù)的程序設(shè)計(jì)和具體調(diào)用關(guān)系請(qǐng)查看程序清單。</p><p>　　3.2.1判贏算法的實(shí)現(xiàn)</p><p>　　判贏算法是基于玩家棋子最后下的位置來(lái)進(jìn)行運(yùn)算，此算法在計(jì)算時(shí)分8個(gè)方向分別進(jìn)行局部遍歷。為此，我設(shè)計(jì)了8個(gè)for循環(huán)，一開始默認(rèn)相同棋子數(shù)

29、為1，然后從緊鄰當(dāng)前棋子的棋子開始遍歷，若遍歷經(jīng)過的棋子是當(dāng)前玩家的棋子，則相同棋子數(shù)+1，否則結(jié)束此方向的遍歷。每遍歷完同一直線上的兩個(gè)方向則進(jìn)行一次判斷，判斷相同棋子數(shù)是否>=4。是則返回true，否則進(jìn)入其他方向的遍歷。若所有方向均遍歷完后，相同棋子數(shù)未能>=4就返回false。</p><p>　　圖8 判贏算法原理圖</p><p>　　在算法設(shè)計(jì)時(shí)應(yīng)注意：</

30、p><p>　　每個(gè)方向起始遍歷的下標(biāo)； 每個(gè)方向遍歷的邊界；</p><p>　　每遍歷完一條直線方向得重置相同棋子數(shù)為1。</p><p>　　3.2.2悔棋算法的實(shí)現(xiàn)</p><p>　　悔棋借用了棧結(jié)構(gòu)，在棧中保存棋子在棋盤二維數(shù)組中的坐標(biāo)。在設(shè)計(jì)此算法時(shí)，我定義了一個(gè)保存坐標(biāo)數(shù)組的棧，將x和y坐標(biāo)打包成數(shù)組來(lái)存入棧。</

31、p><p>　　由于使用棧會(huì)出現(xiàn)棧空的現(xiàn)象，所以在程序設(shè)計(jì)時(shí)應(yīng)注意：</p><p>　　在出棧前確保棧未空；</p><p>　　在結(jié)合顯示最后棋子功能時(shí)，當(dāng)棧為空時(shí)，要特別處理顯示上一棋子的位置。</p><p>　　3.3 函數(shù)調(diào)用關(guān)系圖</p><p>　　此函數(shù)調(diào)用關(guān)系圖以android版本應(yīng)用程序來(lái)進(jìn)行說(shuō)明。此

32、函數(shù)調(diào)用關(guān)系圖主要描述了四子棋游戲的實(shí)現(xiàn)及實(shí)現(xiàn)各運(yùn)算所要調(diào)用的函數(shù)，詳情還請(qǐng)看程序清單。</p><p><b>　　圖9函數(shù)調(diào)用關(guān)系圖</b></p><p><b>　　4 調(diào)試分析</b></p><p>　　表1 調(diào)試過程情況表</p><p><b>　　5 用戶使用說(shuō)明<

33、/b></p><p>　　5.1 android版本應(yīng)用程序操作說(shuō)明</p><p>　?。?）運(yùn)行FourInALine.apk應(yīng)用程序后會(huì)出現(xiàn)主界面：</p><p>　　圖10主界面效果圖 圖11開始游戲效果圖 圖12游戲介紹效果圖</p><p>　　（2）用戶點(diǎn)擊相應(yīng)的功能按鈕：開始游戲、游戲

34、介紹、退出游戲進(jìn)入相應(yīng)界面。用戶可以點(diǎn)擊返回鍵回到主界面。</p><p>　?。?）用戶在游戲過程中，若想悔棋時(shí)可以點(diǎn)擊悔棋按鈕，程序會(huì)進(jìn)行相應(yīng)的操作。當(dāng)然，若想重新開始游戲可以隨時(shí)點(diǎn)擊新開按鈕。</p><p><b>　　6 測(cè)試結(jié)果</b></p><p>　　6.1 windows版本應(yīng)用程序測(cè)試結(jié)果：</p><

35、p><b>　　圖13 贏局效果圖</b></p><p><b>　　圖14 悔棋效果圖</b></p><p>　　圖15 ?？諘r(shí)悔棋效果圖</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1]嚴(yán)蔚敏，李冬梅，吳偉明等.數(shù)據(jù)結(jié)構(gòu)[M].北京：人民郵