数据结构课程设计报告(井字棋)由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“井字棋课程设计报告”。
目录
一、设计课题名„„„„„„„„„„„„„„„„„ 1
二、设计目的„„„„„„„„„„„„„„„„„„ 1
三、问题描述及需求分析………………………………… 1
四、概要设计„„„„„„„„„„„„„„„„„„
五、详细设计„„„„„„„„„„„„„„„„„„
六、测试数据及测试结果…………………………………
七、课程设计小结„„„„„„„„„„„„„„„„
八、用户手册………………………………………………1 5 7 8
一、设计课题名
井字棋（人机对弈）
二、设计目的1、课程设计是《数据结构》课程教学必不可缺的一个重要环节；
2、通过课程设计加深课堂教学内容的理解和巩固；
3、将《数据结构》课程的教学内容与解决实际问题结合起来，培养理论联系实际的学风；
4、提高程序设计能力、培养自学能力 ；
5、提高分析问题、解决问题的能力；
6、提高收集资料、查找参考书的能力；
7、锻炼书写报告的能力。
三、问题描述及需求分析
本设计的主要完成的是井字棋的人机对弈问题，即计算机与人交替落子，当行、列或对角有连续三个相同一方棋时，则判定一方胜利，若无此情形则为和局。
要完成此设计则需一判定胜负函数及一计算机自行落子函数，一旦这两个函数完成则此程序主要部分可完成。
四、概要设计
完成此程序需一合理数据结构，因其为井字棋游戏程序则此结构中应包含一存储当前棋局的数组；又因计算机在判定在何位置落子最佳时，需一搜索树因而我在设计时设置了一PARENT域和CHILD域；
除了主程序外，它还包括具有以下功能的函数：(1)棋盘初始化函数：void Init()；(2)打印棋盘函数：void PrintQP()；
(3)用户输入落子位置函数：void UserInput()；
(4)判断当前棋局是否有一方获胜，并判断哪一方获胜的函数：int IsWin(State s)；(5)评估函数值计算函数：int e_fun(State s)；(6)极大极小值算法主函数：int AutoDone()。
五、详细设计
设计步骤:
(1)选定算法；
(2)建立一个简单的应用程序（如字符界面程序）来测试算法；
(3)选定要实现的其他功能（如双人对弈、悔棋、难易级别选定、联机对战等）；
第1页
共8页(4)实现井字棋程序。
数据结构设计：
struct
State
该结构表示棋盘的某个状态，也可看做搜索树中的一个节点 { int QP[3][3];
棋盘格局
int e_fun；
当前状态的评估函数值
int child[9];
儿女节点的下标
int parent;
双亲节点的下标
int bestChild;
最优节点（评估函数值最大或最小）的儿女节点下标 } States[MAX_NUM];用来保存搜索树中状态节点的数组
我使用了States[MAX_NUM]数组来保存生成的状态节点，通过State结构中的parent、child域构成了一个搜索树，并通过bestChild域保存了一条从根节点到叶节点的最优解路径。特别的，States[0]作为根节点保存了当前的棋局状态。为了保存当前对弈过程的状态信息，我定义了以下常量：
const int MAX_NUM=1000;
扩展生成状态节点的最大数目 const int NO_BLANK=-1001;表示没有空格 const int TREE_DEPTH=3;
搜索树的最大深度 const int NIL=1001;表示空
算法设计及算法分析：
本程序采用的核心算法是极大极小值算法，这种算法的思想是“考虑双方对弈若干步之后，从可能的走法中选一步相对较好的走法来走”，并且“在有限的搜索深度范围内进行求解”。整个算法在AutoDone函数中实现，其实现过程分为以下几步：
(1)为了获得最优的落子位置，在算法中首先要生成搜索树。其中，我把States[0]作为树根节点，根节点所在的层是极大层（MAX层），然后通过向棋盘中没有落子的空格添一个对方的棋子生成下一层（极小层，MIN层）的树节点，如果当前树的高度大于等于TREE_DEPTH（>=1）全局变量，则停止生成节点，否则则继续生成下一层节点（如果当前节点层为MIN层，则下一层为MAX层，否则，则下一层为MIN层）。生成每一层时可为每一层的属性（MAX或MIN）做标记，生成每个节点时，应计算这个节点的评估函数值，并将其保存在状态节点的e_fun域中。
(2)因为层次遍历会修改非叶节点的极大极小值，而且非叶节点原来的极大极小值会对其来自其子女节点的极大极小值产生影响（比如，如果一个非叶节点的极大极小值大于或小于其子女节点中的最大者或小于其中的最小者，则导致其评估函数值无法更新）。所以非叶节点没有必要也不能保存。这一步的源代码如下所示：
tag=States[s_count].parent;//设置最底层标志，以区分叶节点和非叶节点。
第2页
共8页 for(i=0;i
if(i>tag)//保留叶节点的评估函数值
{
States[i].e_fun=e_fun(States[i]);
}
else //抹去非叶节点的评估函数值
States[i].e_fun=NIL;}(3)然后，通过层次遍历获得每个非叶节点的评估函数值，同时将非叶节点的bestChild域指向最佳子女，从而形成一条从根节点到叶节点的最佳解路径。这一步的源代码如下所示：
while(!IsOK)//寻找最佳落子的循环
{
for(int i=s_count;i>tag;i--)
{
if(max_min)//取子女节点的最大值
{
if(States[States[i].parent].e_fun
{
States[States[i].parent].e_fun=States[i].e_fun;
//设置父母节点的最大最小值
States[States[i].parent].bestChild=i;
//设置父母节点的最佳子女的下标
}
}
else//取子女节点的最小值
{
if(States[States[i].parent].e_fun>States[i].e_fun||States[States[i].parent].e_fun==NIL)
{
States[States[i].parent].e_fun=States[i].e_fun;
//设置父母节点的最大最小值
States[States[i].parent].bestChild=i;
//设置父母节点的最佳子女的下标
}
}
}
s_count=tag;//将遍历的节点上移一层
max_min=!max_min;//如果该层都是MAX节点，则它的上一层都是MIN节点，反之亦然。
if(States[s_count].parent!=NIL)//如果当前遍历的层中不包含根节点，//则tag标志设为上一层的最后一个节点的下标
第3页
共8页
tag=States[s_count].parent;
else
IsOK=true;
//否则结束搜索
}(4)最后，将当前的棋局更新为其最优子女节点的棋局，并获得落子的位置。这一步的源代码如下所示：
//取落子的位置，将x,y坐标保存在变量pos_x和pos_y中，//并将根（当前）节点中的棋局设为最佳子女节点的棋局 for(int x=0;x
for(int y=0;y
{
if(States[States[0].bestChild].QP[x][y]!=States[0].QP[x][y])
{
pos_x=x;pos_y=y;
}
States[0].QP[x][y]=States[States[0].bestChild].QP[x][y];
} } 在我采用的算法中，可以通过增加生成树的层数，即增加TREE_DEPTH的值来提高计算机的智商。这相当于增加了计算机向前预测的步数。对井字棋来说，因为井字棋有9个格，所以TREE_DEPTH的最大值可以设为9。TREE_DEPTH＝3时，计算机会综合考虑以后3步的走法。当TREE_DEPTH＝3时，程序生成的最大状态节点数为：1＋9＋9×8＋9×8×7＝585个。
总结：
在本程序中的井字棋程序使用了极大极小值算法，这种算法的思想是“考虑双方对弈若干步之后，从可能的走法中选一步相对较好的走法来走”，并且“在有限的搜索深度范围内进行求解”。
最大最小值算法的核心是将搜索树的层分为MAX层和MIN层，MAX层和MIN层交替相邻（即，一个节点如果在MAX层，则其子女节点在MIN层；如果在MIN层，则其子女节点在MAX层），在MAX层的节点的评估函数值取其子女节点中的最大者，在MIN层的节点的评估函数值取其子女节点中的最小者。
此外，需要定义一个评估函数来计算叶节点的评估函数值，要注意将某方获胜的状态节点的评估函数值设为计算机能表示的最大数（无穷大）或最小数（无穷小）以表明在该状态下有一方获胜。
最后，还要“在有限的搜索深度范围内进行求解”，如果搜索深度太大，则在状态数较多的情况下会使时间耗费或空间耗费达到无法忍受的程度。
第4页
共8页
六、测试数据及测试结果
图一：程序初始运行界面
图二：人机对弈初始界面
第5页
共8页
图三：人机对弈一方胜利界面
图四：双人对弈界面
第6页
共8页
图五：双人对弈一方胜利界面
七、课程设计小结
心得体会：
通过本次《数据结构》课程设计，从看到设计要求，到选择课题再到自己构思，设计数据结构，构造算法，编写源代码，再到一个星期的上机调试，我充分认识到书本上的知识只是数据结构的基础知识，认识到将知识有机融合并运用到实际生活中的重要性。
本次课程设计的主要数据结构涉及到树的存储结构，我选择了用数组来存储相关内容，设计了一个parent域和child域。通过本次的课程设计、上机实验，原本对于树的存储结构相对比较生疏的我，现在能较为熟练的掌握树的各种存储结构，并能比较纯熟的选择适合的存储结构。在此次程序调试运行过程中我认识到一个可操作的好的程序必须有个良好的界面，因为只有这样才能实现与用户的互动，便于用户使用，才能充分发挥出一个好程序应有的功效。而一个好的编程工作者，应当在编程之前充分了解用户的需求，使用户能方便使用此程序的各项功能。
当然由于时间比较仓促、所学比较有限，对于此课程设计的模块尚不完全，因此功能还需完善，有较多地方有待改进，希望通过将来的进一步学习，我能完善此程序，将其功能设计的更加完全，能让用户更方便的使用。
存在问题：
（1）在游戏进行过程中不能退出游戏界面；
（2）双人对弈时不能清楚鉴别两人身份，落子时可能出现错误，且在游戏进行中不可提前判断平局情况；
第7页
共8页（3）不可进行悔棋，人机对弈难度的选择。
改进措施：
双人对弈时可设一姓名判别函数，确定双人身份； 设定判定树提前预测平局情况；
可对树的深度进行设置，借以改变对弈难度； 设一数组保存前一阶段棋局，在悔棋时可调出。
八、用户手册
按键说明：
1：进入人机对弈界面； 2：进入双人对弈界面； 3：退出。
具体说明：
（1）进入具体对弈界面后会出现提示信息，按提示信息输入相关内容即可；（2）所输入的棋子的行列号为整数，其分别为11，12，13，21，22，23，31，32，33；其中前一位数为行号，后一位数为列号；
（3）盘界面上0代表所在位置为空，若为0则代表此位置可落子；在人机对弈则1代表计算机所落之子，-1代表人所落之子；在双人对弈则1代表第二个人所落之子，-1代表第一人所落之子；
（4）双人对弈时需先自行对下棋双方进行编号（1和2），而后根据提示输入谁为先手的信息，进而进入游戏。
注意：
（1）进入游戏后不可中途退出游戏，需在决出胜负后按3方可退出；（2）在游戏进行期间若发现所输落子位置出错，可自行更改或按系统出错提示重新输入。
第8页
共8页
