数据结构课程设计报告(井字棋)（大全）.docx

数据结构课程设计报告(井字棋)（大全）

第一篇：数据结构课程设计报告(井字棋)（大全）目录一、设计课题名„„„„„„„„„„„„„„„„„1二、设计目的„„„„„„„„„„„„„„„„„„1三、问题描述及需求分析…………………………………1四、概要设计„„„„„„„„„„„„„„„„„„五、详细设计„„„„„„„„„„„„„„„„„„六、测试数据及测试结果…………………………………七、课程设计小结„„„„„„„„„„„„„„„„八、用户手册………………………………………………1578一、设计课题名井字棋（人机对弈）二、设计目的1、课程设计是《数据结构》课程教学必不可缺的一个重要环节；2、通过课程设计加深课堂教学内容的理解和巩固；3、将《数据结构》课程的教学内容与解决实际问题结合起来，培养理论联系实际的学风；4、提高程序设计能力、培养自学能力；5、提高分析问题、解决问题的能力；6、提高收集资料、查找参考书的能力；7、锻炼书写报告的能力。三、问题描述及需求分析本设计的主要完成的是井字棋的人机对弈问题，即计算机与人交替落子，当行、列或对角有连续三个相同一方棋时，则判定一方胜利，若无此情形则为和局。要完成此设计则需一判定胜负函数及一计算机自行落子函数，一旦这两个函数完成则此程序主要部分可完成。四、概要设计完成此程序需一合理数据结构，因其为井字棋游戏程序则此结构中应包含一存储当前棋局的数组；又因计算机在判定在何位置落子最佳时，需一搜索树因而我在设计时设置了一PARENT域和CHILD域；除了主程序外，它还包括具有以下功能的函数：(1)棋盘初始化函数：voidInit()；(2)打印棋盘函数：voidPrintQP()；(3)用户输入落子位置函数：voidUserInput()；(4)判断当前棋局是否有一方获胜，并判断哪一方获胜的函数：intIsWin(States)；(5)评估函数值计算函数：inte_fun(States)；(6)极大极小值算法主函数：intAutoDone()。五、详细设计设计步骤:(1)选定算法；(2)建立一个简单的应用程序（如字符界面程序）来测试算法；(3)选定要实现的其他功能（如双人对弈、悔棋、难易级别选定、联机对战等）；(4)实现井字棋程序。数据结构设计：structState该结构表示棋盘的某个状态，也可看做搜索树中的一个节点{intQP[3][3];棋盘格局inte_fun；当前状态的评估函数值intchild[9];儿女节点的下标intparent;双亲节点的下标intbestChild;最优节点（评估函数值最大或最小）的儿女节点下标}States[MAX_NUM];用来保存搜索树中状态节点的数组我使用了States[MAX_NUM]数组来保存生成的状态节点，通过State结构中的parent、child域构成了一个搜索树，并通过bestChild域保存了一条从根节点到叶节点的最优解路径。特别的，States[0]作为根节点保存了当前的棋局状态。为了保存当前对弈过程的状态信息，我定义了以下常量：constintMAX_NUM=1000;扩展生成状态节点的最大数目constintNO_BLANK=-1001;表示没有空格constintTREE_DEPTH=3;搜索树的最大深度constintNIL=1001;表示空算法设计及算法分析：本程序采用的核心算法是极大极小值算法，这种算法的思想是“考虑双方对弈若干步之后，从可能的走法中选一步相对较好的走法来走”，并且“在有限的搜索深度范围内进行求解”。整个算法在AutoDone函数中实现，其实现过程分为以下几步：(1)为了获得最优的落子位置，在算法中首先要生成搜索树。其中，我把States[0]作为树根节点，根节点所在的层是极大层（MAX层），然后通过向棋盘中没有落子的空格添一个对方的棋子生成下一层（极小层，MIN层）的树节点，如果当前树的高度大于等于TREE_DEPTH（>=1）全局变量，则停止生成节点，否则则继续生成下一层节点（如果当前节点层为MIN层，则下一层为MAX层，否则，则下一层为MIN层）。生成每一层时可为每一层的属性（MAX或MIN）做标记，生成每个节点时，应计算这个节点的评估函数值，并将其保存在状态节点的e_fun域中。(2)因为层次遍历会修改非叶节点的极大极小值，而且非叶节点原来的极大极小值会对其来自其子女节点的极大极小值产生影响（比如，如果一个非叶节点的极大极小值大于或小于其子女节点中的最大者或小于其中的最小者，则导致其评估函数值无法更新）。所以非叶节点没有必要也不能保存。这一步的源代码如下所示：tag=States[s_count].parent;//设置最底层标志，以区分叶节点和非叶节点。for(i=0;iif(i>tag)//保留叶