数据结构课程设计报告四子棋

1、韶关学院计算机科学学院数据结构课程设计题 目： 四子棋学生姓名：刘晓锋学 号：11115011038专 业：计算机科学与技术班 级：11级（1）班 指导教师姓名及职称：陈正铭 讲师 起止时间： 2013 年 3 月 2013 年 5 月1 需求分析1.1 课题背景及意义全球在使用的移动电话已经超过10亿部，而且这个数字每天都在不断增加。手机在作为一种便携通信工具的同时，它的功能也在不断的丰富，进而推进手机游戏的发展。根据2012手机游戏用户行为分析报告，随着智能手机的普及和手机性能的提高，手机上的终端应用越来越丰富，作为手机上的重要的娱乐应用，手机游戏市场也在快速成长，越来越多的用户通过手机游

2、戏来打发无聊的时间，其中76%的用户单次玩手机游戏都在30分钟左右。结合个人水平和兴趣爱好，本人将借本次课程设计机会设计一款休闲娱乐型的四子棋游戏，在娱乐自我，锻炼编程设计能力的同时，希望也借此给身边的朋友们带来快乐。1.2 课题要求 a. 支持android手机的四子棋游戏b. 设计一个7*6棋盘大小的四子棋双人对战游戏程序，先四子连线（横、纵、斜）者胜。c. 选做内容：支持棋局录制与重放 - 悔棋和新开功能，图形化操作界面1.3 软件格式规定a.程序所能达到的功能 :正确判断输赢并有相应的语音和文字提示b.测试的数据：1)、正确的输入： 提示：蓝棋赢，并将蓝棋变为另外一种颜色 - 天蓝和响

3、起赢局的音乐2)、用户误输入： 提示：亲,我的悔棋能力有限啊!1.4 设计目标a. 软件名称：four in a line（四子棋）b. 软件组成：fourinaline.apk（android系统应用程序）c. 制作平台及相关调试工具：eclipse ； androidsdkd. 运行环境：android手机/winxp/win7(pc平台必须具有androidsdk)e. 性能特点：（1）软件由两个可执行文件组成，各具特点:fourinaline.apk为android系统应用程序，体积小，界面友好，使用方便。（2）方便重新开始游戏和悔棋。（3）判赢用时少。（4）个别其他功能可进行再扩展。

4、2 概要设计2.1问题解决的思路概述首先是确定结构化程序设计的流程图，利用已存在的数据结构来构造一个存储棋盘的结构，接着把游戏实现分成六个主要的模块：实现悔棋的模块、实现新开的模块、实现音乐的模块、实现绘图的模块，实现控制线程的模块，实现判赢的模块，然后各个模块里面还要分成若干种情况来考虑并通过函数的嵌套调用来实现其功能。最后，编写main主函数以实现游戏的可玩性和正确性，调试程序并将不足的地方加以修改。总而言之，就是先用自顶向下、逐步细化的设计方法来分析并画出程序设计流程图；然后用自下而上、逐步积累的设计方法来写出程序。2.2 相关函数介绍说明 在android版本程序定义一个用于存储棋盘的

5、二维数组变量：private static int chessboardstate;1（1）android版本程序下定义的主要函数public boolean iswin(int x, int y)/ 判断赢家，采用遍历最后下的棋子在8个方向上的棋子public void back(context context)/ 悔棋函数public void play()/游戏主线程public void setxy(mybackchessstate mybackchessstate)/处理栈顶元素public rect getrect(int xy) / 标记二维数组对应的矩形区域，也即是棋子该下的位

6、置public rect getrect(int x, int y) / 标记二维数组对应的矩形区域，也即是棋子该下的位置private int getindexofxy() / 获得当前坐标在二维数组中对应的索引。xy0是横坐标，也即是棋盘的第某列数；xy1是纵坐标，也即是棋盘的第某横。private int searchemptytoptile(int x, int chessboardstate) /返回当列最上方无棋子的坐标,也即是棋盘的第某横.public void setchessboardstate(int chessboardstate)/保存棋盘状态public drawgr

7、aph getchessboardview() /获得绘图实例public void setwinner(int player) /设置赢局提示(提示对应玩家赢)public void nextplayer(int player) /设置下一玩家public void newgame(context context) /触发开始新游戏public boolean ontouch(view v, motionevent event) /绑定棋盘的触摸事件public static void play(context context, int resource) /播放音乐private void

8、 updateview(canvas canvas)/ 更新游戏界面public void showchess(canvas canvas, int player, rect rect) / 设置当前玩家的棋子public void showlastchess(canvas chess, int player, rect rect)/显示最后下的棋子public void clearview(canvas canvas) / 清空整个棋盘视图private void init() /初始化视图public static bitmap getbitmapfromresid(context con

9、text, int resid) /获得棋盘图片资源public static bitmap zoombitmap(bitmap bitmap, float width, float height) /缩放棋子图片资源2.3 主程序的流程基函数调用说明（1）主程序的简要流程图结束输出结果显示相应界面与信息调用相应的模块运行游戏main()选择操作（开始游戏、游戏介绍、退出游戏）图1 主程序流程图（2）各程序模块之间的层次（调用）关系调用“findviews()”和“initviews()”方法绑定各个控件，以便调用相应的活动界面，然后调用各模块进行游戏。在每一个功能模块中都几乎涉及到棋盘数组的

10、存取，所以都要调用“getchessboardstate()”对数组变量初始化。实现音乐的模块“music”类，首先要创建一个音频播放实例，然后启动它。在游戏运行中根据其他模块是否调用其stop()方法或重新调用其play()方法。音乐模块流程图如下：图2 音乐模块流程图实现控制线程的模块“control”类，首先要调用getindexofxy()方法计算用户点击的视图坐标对应的棋盘二维数组坐标。若此次点击有效，调用悔棋模块存储此次操作和调用判赢模块的iswin()方法判断胜负，若赢局出现就再调用音乐模块。最后调用绘图更新整个游戏视图。若此次点击无效，直接返回。控制线程模块流程图如下：图3 控

11、制线程模块流程图实现判赢的模块“winner”类，首先调用“iswin()”方法判断是否有赢局出现，然后在游戏运行中根据其他模块是否调用其getsamechess()方法来设置相同棋子或调用updatesamechess()方法来重置winner类中的静态变量。控制线程模块流程图如下：图4 判赢模块流程图实现绘图的模块“drawgraph”类，首先调用“ondraw()”以实现视图初始化和棋盘绘制。然后再调用控制线程模块的getrect()方法获取棋子应下的位置，接着调用getxy()方法和showlastchess()方法设置最后下的棋子。若有赢局出现，则调用判赢模块的getsameches

12、s()方法来设置相同棋子。控制线程模块流程图如下：图5绘图模块流程图实现悔棋的模块“backchess”类，首先调用“back()”判断当前栈是否为空，是则弹出提示信息并退出。否则弹出栈顶元素，重新赋值为0。然后调用控制线程模块的getchessboardview()方法获得drawgraph的实例，用于更新棋盘。最后调用控制线程模块的setx y()方法设置上一棋子的坐标。控制线程模块流程图如下：图6悔棋模块流程图实现新开的模块“new”类，首先调用“newgame()”新建棋盘数组，然后调用控制线程模块的setchessboardstate()方法对棋盘数组进行重新初始化, 然后调用控制线

13、程模块的getchessboardview()方法获得drawgraph的实例, 更新棋盘。接着调用悔棋模块的clearstack()方法清空原先栈中元素。最后调用判赢模块的updatesamechess()重置静态变量和音乐模块的play()方法重启背景音乐。新开模块流程图如下：图7悔棋模块流程图3 详细设计3.1 棋盘存储的实现棋盘的大小一般都是固定的常量，所以可以用二维数组来存储棋盘的状态，其结构简单且容易,是一种合理的数据结构。二维数组定义如下：private static int chessboardstate = new introwcolumn;3.2 各模块主要算法 在四子棋游

14、戏的程序设计中，每一部分都会调用一些其他其它函数来辅助完成运算（例如：对棋盘数组、当前玩家和棋盘视图的初始化，获取棋子应下的位置等），在这里主要说明四子棋游戏的程序设计，其它函数的程序设计和具体调用关系请查看程序清单。3.2.1判赢算法的实现 判赢算法是基于玩家棋子最后下的位置来进行运算，此算法在计算时分8个方向分别进行局部遍历。为此，我设计了8个for循环，一开始默认相同棋子数为1，然后从紧邻当前棋子的棋子开始遍历，若遍历经过的棋子是当前玩家的棋子，则相同棋子数+1，否则结束此方向的遍历。每遍历完同一直线上的两个方向则进行一次判断，判断相同棋子数是否=4。是则返回true，否则进入其他方向的

15、遍历。若所有方向均遍历完后，相同棋子数未能=4就返回false。图8 判赢算法原理图在算法设计时应注意：每个方向起始遍历的下标； 每个方向遍历的边界；每遍历完一条直线方向得重置相同棋子数为1。3.2.2悔棋算法的实现悔棋借用了栈结构，在栈中保存棋子在棋盘二维数组中的坐标。在设计此算法时，我定义了一个保存坐标数组的栈，将x和y坐标打包成数组来存入栈。由于使用栈会出现栈空的现象，所以在程序设计时应注意：在出栈前确保栈未空；在结合显示最后棋子功能时，当栈为空时，要特别处理显示上一棋子的位置。3.3 函数调用关系图此函数调用关系图以android版本应用程序来进行说明。此函数调用关系图主要描述了四子棋

16、游戏的实现及实现各运算所要调用的函数，详情还请看程序清单。图9函数调用关系图4 调试分析表1 调试过程情况表序号时间出现问题解决方法12013-3-20想new一个更新棋盘的类，在传参时无法驾驭context参数将一个系统获得的更新棋盘的实例传给主控制线程，在主控制线程中调用更新view的方法postinvalidate()22013-3-26调用getindexofxy()后，提示超出数组索引对getindexofxy()处理后的数据进行判断，不对无用数据进行操作32013-3-26在设置最后下的棋子时，栈提示空值异常当栈为空时，将上一棋子的坐标设为空，在取坐标时，不对空值数据进行操作420

17、13-3-29计算棋子应下位置时，棋子位置未能与棋盘相匹配重新计算棋子位置的公式，添加棋盘边沿的偏移量52013-4-4计算下一玩家时，公式出错重新计算下一玩家的公式，关键是初值的设置62013-4-8判赢算法在重新开始游戏时出错，即相同棋子数未能=4均提示玩家赢重置相同棋子数的值为1,或限制此变量的作用域72013-4-8赢局出现后依旧可以下棋设置赢局开关，赢了为true，否则为false82013-4-16重新开始游戏时，玩家顺序紊乱重置当前玩家的值为092013-4-27重新开始游戏时，栈中元素异常，一直有悔棋成功的提示当重新开始游戏时，清空栈中元素102013-5-4更新视图时进入死循环在绘图模块中移除postinvalidate()方法5 用户使用说明5.1 android版本应用程序操作说明（1）运行fourinali