课程设计说明书课程名称：数据结构专业：班级：姓名：学号：指导教师：成绩：完成日期：年月日任务书摘要本文的研究工作在于利用计算机模拟人脑进行下黑白棋，计算机下棋是人工智能领域中的一个研究热点，多年以来，随着计算机技术和人工智能技术的不断发展，计算机下棋的水平得到了长足的进步该程序的最终胜负是由棋盘上岗双方的棋子的个数来判断的，多的一方为胜，少的一方为负。

所以该程序主要运用的战术有削弱对手行动战术、四角优先战术、在游戏开局和中局时，程序采用削弱对手行动力战术，即尽量减少对手能够落子的位置；在游戏终局时则采用最大贪吃战术，即尽可能多的吃掉对手的棋子；而四角优先战术则是贯穿游戏的始终，棋盘的四角围稳定角，不会被对手吃掉，所以这里是兵家的必争之地，在阻止对手进角的同时，自己却又要努力的进角。

关键词：黑白棋；编程；设计目录1.引言 (4)2.课题分析 (7)3.具体设计过程 (8)3.1设计思路 (8)3.2程序设计流程图 (8)3.3.函数实现说明 (12)4.程序运行结果 (14)5.软件使用说明 (18)6.结论 (21)参考文献 (21)附录：源代码 (22)1.引言数据结构在计算机科学界至今没有标准的定义。

个人根据各自的理解的不同而有不同的表述方法：Sartaj Sahni在他的《数据结构、算法与应用》一书中称：“数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。

这些联系可以通过定义相关的函数来给出。

”他将数据对象（data object）定义为“一个数据对象是实例或值的集合”。

Clifford A.Shaffer在《数据结构与算法分析》一书中的定义是：“数据结构是ADT（抽象数据类型Abstract Data Type）的物理实现。

”Lobert L.Kruse在《数据结构与程序设计》一书中，将一个数据结构的设计过程分成抽象层、数据结构层和实现层。

其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其运算，数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现。

数据结构具体指同一类数据元素中，各元素之间的相互关系，包括三个组成成分，数据的逻辑结构，数据的存储结构和数据运算结构。

1.1. 重要意义一般认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的。

对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。

在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。

许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。

许多时候，确定了数据结构后，算法就容易得到了。

有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。

不论哪种情况，选择合适的数据结构都是非常重要的。

选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。

这种洞见导致了许多种软件设计方法和程序设计语言的出现，面向对象的程序设计语言就是其中之一。

1.2. 研究内容在计算机科学中，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。

“数据结构”作为一门独立的课程在国外是从1968年才开始设立的。

1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。

“数据结构”在计算机科学中是一门综合性的专业基础课。

数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。

数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。

计算机是一门研究用计算机进行信息表示和处理的科学。

这里面涉及到两个问题：信息的表示，信息的处理。

而信息的表示和组织又直接关系到处理信息的程序的效率。

随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。

因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。

众所周知，计算机的程序是对信息进行加工处理。

在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。

数据的结构，直接影响算法的选择和效率。

计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（Algorithm），最后编出程序、进行测试、调整直至得到最终解答。

寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。

计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。

运算是由计算机来完成，这就要设计相应的插入、删除和修改的算法。

也就是说，数据结构还需要给出每种结构类型所定义的各种运算的算法。

数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体考虑。

一个数据元素由若干个数据项组成。

数据项是数据的不可分割的最小单位。

有两类数据元素：一类是不可分割的原子型数据元素，如：整数"5"，字符"N" 等；另一类是由多个款项构成的数据元素，其中每个款项被称为一个数据项。

例如描述一个学生的信息的数据元素可由下列6个数据项组成。

其中的出生日期又可以由三个数据项："年"、"月"和"日"组成，则称"出生日期"为组合项，而其它不可分割的数据项为原子项。

关键字指的是能识别一个或多个数据元素的数据项。

若能起唯一识别作用，则称之为"主" 关键字，否则称之为"次" 关键字。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

数据对象可以是有限的，也可以是无限的。

数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。

在早期，计算机主要用于科学和工程计算，进入八十年代以后，计算机主要用于数据处理。

据有关统计资料表明，现在计算机用于数据处理的时间比例达到80%以上，随着时间的推移和计算机应用的进一步普及，计算机用于数据处理的时间比例必将进一步增大。

2.课题分析编写一个《黑白棋游戏》的C程序，包括以下功能：初始状态：在一个8*8的棋盘中央交叉排放黑白棋子各两枚，白棋先走。

（1）每个棋手下棋时，摆子的位置必须是以自己的棋子能包围住对方一个或多个棋子，被包围住的对方棋子将成为自己的棋子。

包围的方向可以是上下左右以及斜线8个方向，只要能连成一线即可。

（2）当轮到某一个棋手下子，但是他没有可以包围对方棋子的位置时，他必须停步，让对方走棋，直到他可以走为止。

（3）当棋盘上一方的棋子为0或者下满64格，游戏结束，棋子少者输。

（4）当一局结束后，可以选择y/n选择是否继续下一局游戏3.具体设计过程3.1设计思路程序界面应是一个二维平面图，所以数据的表示用二维数组，数组两个下标可以表示棋盘上的位置，数组元素的值代表棋格中的状态，共有三种情况，分别是空格、黑棋和白棋。

这样给数组元素的取值设定为0、1、2，其中0代表空格，*代表白色棋子，0代表黑色棋子。

这样程序的主要工作是接收棋手按键操作，一旦接收到回车键，说明棋手摆子，先判断是不是有效位置，也就是能不能包围住对方棋子，如果能，便为棋子所在的位置往上下、左右、左上、左下、右上、右下8个方向寻找被包围住的所有棋子（必须是连续的，中间不能有空格），将这些被包围住的对方棋子都变成自己的棋子，然后对当前棋盘中的黑白棋个数进行统计并输出结果。

如果没有这样的位置可以落子，则停步，让对方走棋，重复上述步骤，直到游戏结束。

3.2程序设计流程图系统功能流程图，首先我们先初始化系统功能，定义各项函数，并初始化一些参数变量。

然后绘制棋盘。

然后按enter键进行游戏，当我们输入一个横纵坐标时，系统会判断此坐标是否合法，若合法则落子，并翻转相应的棋子。

最终判断双方的胜负情况。

如图3.1所示：图3.1程序整体流程图图3.2为下棋流程图。

首先我们进入游戏，然后由玩家先落子。

先判断落子位置是否已经有棋子了，若有则重新输入。

若没有，再判断是否能够引起棋子的翻转，若可以则落子，将对方的棋子变成自己的棋子，反之换由对方下子。

当一方走完之后，换另一方走。

如下图所示：图3.3为成绩运行流程图，当棋盘上的每一个格子都有棋子的时候，系统将遍历棋盘，然后根据棋盘上棋子的花色分别代表的是哪一方，在哪一方的成绩上+1.遍历完后，判断双方分数的大小，并输出结果。

如下图所示：3.3.函数实现说明(1)void main()主函数功能：在主函数中，首先定义使用到的常数、全局变量、函数原型说明。

盘状态用数组 a[8][8]，初值为0，表示空格。

函数的实体部分，开始初始化图形系统，然后通过调用函数display()先画出棋盘，调用make_move()和computer_move()进行人机对战函数开始游戏，一旦游戏结束后，关闭图形系统，程序结束。

(2)void display（）棋盘绘制函数功能：函数display()通过for循环，对棋盘界面进行了绘制用法：此函数调用方式为void display(char board[][SIZE]);说明：参数是一个二维数组，size为定义的长度。

值为8返回值：无(3)int valid_moves（）有效步骤函数功能：通过此函数来判断电脑或玩家下的棋子是否是有效的。

用法：此函数调用方式为int valid_moves(char board[][SIZE],intmoves[][SIZE],char player);说明：char board[][SIZE]为棋盘，int moves[][SIZE]为玩家输入的横纵坐标，char player为判断的玩家为电脑还是人返回值： int(4)void make_move（）下棋函数功能：定义坐标，控制变量并通过for循环来判断翻转棋子。

达到同一方向上将对方的棋子翻转为自己的棋子。

用法：此函数调用方式为void make_move(char board[][SIZE],int row,int col,char player)说明：int row,int col分别代表其中的横纵坐标返回值：无(5)void computer_move()电脑下棋函数功能：主函数通过调用该函数，获取电脑的下棋位置。