扬州大学信息工程学院

《数据结构》

---课程设计报告

题 目： “井字棋”小游戏

班 级：

学 号：

姓 名：

指导教师：

一、课程题目

“井字棋”小游戏

二、需求分析

计算机和人对弈问题。计算机之所以能和人对弈是因为有人将对弈的策略事先已存入计算机。由于对弈的过程是在一定规则下随机进行的，所以，为使计算机能灵活对弈就必须对对弈过程中所有可能发生的情况以及相应的对策都考虑周全，并且，一个“好”的棋手在对弈时不仅要看棋盘当时的状态，还能预测棋局发展趋势，甚至最后结局。因此，在对弈问题中，计算机操作的对象是对弈过程中可能出现的棋盘状态——称为格局。

例如图1所示为井子棋的一个格局，而格局之间的关系是由比赛规则决定的。通常，这个关系不是线性的，因为从一个棋盘格局可以派生出几个格局，例如从图1所示的格局可以派生出5个格局，如图2所示，而从每一个新格局又可派生出4个可能出现的格局。因此，若将从对弈开始到结束的过程中所有可能出现的格局都画在一张图上，则可得到一颗倒长的“树”。树根是对弈开始之前的棋盘格局，而所有的“叶子”就是可能出现的结局，对弈的过程就是从树根沿树杈到某个叶子的过程。

“树”可以是某些非数值计算问题的数学模型，是一种数据结构。

图1 棋盘格局示例

图2 对弈树的局部

三、概要设计

该课题的数据类型比较简单，只需要一个Nodes类型记录棋子所在位置和当前状态即可。其中包括基本操作的函数有：初始化棋盘函数、判断当前位置是否为空函数、放置棋子函数、判断棋盘是否为满函数、判断输赢函数、棋局状态函数、选择最佳落子位置函数和打印棋盘函数。

int IsWin(int side)，其功能是依次从行、列、对角线判断是否有三个棋子连成一线。

int PostionValue()，可以返回四种状态，分别为电脑赢、玩家赢、平局和游戏正在进行。

Nodes BestMovement(int side)是该问题的关键模块，其功能为得到当前格局下最佳落子位置，具体实现将在详细设计中阐述。

int main()，主函数，游戏系统界面设计，其功能是引导玩家进入游戏，选择游戏模式（玩家先手或电脑先手），并显示游戏界面。

四、详细设计

（1）数据类型Nodes定义如下：

typedef struct {

int row; //行

int column; //列

int cond; //游戏状态

}Nodes;

（2）Nodes BestMovement(int side)作为实现该课题的关键模块，其算法设计借鉴了“四皇后”问题的解决思路（即回溯法）。很多问题用回溯和试探求解时，描述求解的状态不是一颗满的多叉树。当试探过程中出现的状态和问题所求解产生矛盾时，不再继续试探下去，这时出现的叶子结点不是问题的解的终结状态。这类问题的求解过程可看成是在约束条件下进行先序（根）遍历，并在遍历过程中剪去那些不满足条件的分支。

如图3所示，这是一个四叉树，树上每个结点表示一个局部布局或一个完整布局。根结点表示棋盘的初始状态：棋盘上无任何棋子。

图3 四皇后问题的棋盘状态树

依据以上分析，可以很容易得出一个结论。求得当前格局下最佳落子位置的过程，即为在约束条件下遍历一颗状态树的过程。遍历中访问结点的操作为，判断棋局是否仍在继续，若是，则转而求对手的最佳落子位置；否则就返回当前输赢状态。若返回结果为输，将棋子移至下一个位置；为平局，先将该位置暂存；为赢，将该位置作为最佳位置返回。

该模块的伪码算法如下：

Nodes BestMovement(int side) {

//从棋盘第一格开始依次尝试最佳位置。

if(游戏已经结束) 返回游戏结果;

else for(i=0; i

for(j=0; j

if(第i行第j列为空) {

在该位置放置一个棋子;

求对手的最佳位置; //node = BestMovement(opponent);

移走该位置的棋子;

if(该位置有更好的终结状态) 暂存该位置;

}

}

}

返回最佳位置;

}// BestMovement

五、测试数据及运行结果

图4 游戏界面（电脑先手）

图5 游戏结局

六、源程序

#include

#include

#define MAX_SIZE 3

#define FALSE 0

#define TRUE 1

#define EMPTY 0

#define HUMAN 1

#define COMPUTER 2

#define HUMAN_WIN 0

#define DRAW 1

#define COMPUTER_WIN 2

#define PLAYING 3

typedef struct {

int row;

int column;

int cond;

}Nodes;

int Board[MAX_SIZE][MAX_SIZE];

void InitBoard() {

int row,column;

for(row=0;row

for(column=0;column

Board[row][column]=EMPTY;

}

int IsEmpty(int row,int column) {

if(Board[row][column]==EMPTY)

return TRUE;

else

return FALSE;

}

void Place(int row,int column,int piece) {

Board[row][column]=piece;

}

int IsFull() {

int i=0,j=0;

for(i=0;i

for(j=0;j

if(Board[i][j]==EMPTY)

return FALSE;

}

return TRUE;

}

int IsWin(int side) {

int row,column;

//判断一行

for(row=0;row

for(column=0;column

if(Board[row][column]!=side)

break;

if(column>=MAX_SIZE)

return TRUE;

}

//判断一列

for(column=0;column

for(row=0;row

if(Board[row][column]!=side)

break;

if(row>=MAX_SIZE)

return TRUE;

}

//判断主对角线

if(Board[0][0]==side && Board[1][1]==side && Board[2][2]==side)

return TRUE;

//判断副对角线

if(Board[0][2]==side && Board[1][1]==side && Board[2][0]==side)

return TRUE;

return FALSE;

}

int PostionValue() {

return IsWin(COMPUTER)?COMPUTER_WIN:(IsWin(HUMAN)?HUMAN_WIN:(IsFull()?DRAW:PLAYING));

}

Nodes BestMovement(int side) {

Nodes node,bestNode;

int opponent;

int result;

int row,column,bestRow=0,bestColumn=0;

int condition;

if((result=PostionValue()) != PLAYING) {

node.cond=result;

return node;

}

if(side==COMPUTER) {

opponent=HUMAN;

condition=HUMAN_WIN;

}

else {

opponent=COMPUTER;

condition=COMPUTER_WIN;

}

for(row=0;row

for(column=0;column

if(IsEmpty(row, column)) {

Place(row,column,side);

node=BestMovement(opponent);

Place(row,column,EMPTY);

if((side==COMPUTER && node.cond>condition) || (side==HUMAN && node.cond

condition=node.cond;

bestRow=row;

bestColumn=column;

}

}

}

}

bestNode.row=bestRow;

bestNode.column=bestColumn;

bestNode.cond=condition;

return bestNode;

}

void Print() {

int row,column;

for(row=0;row

for(column=0;column

if(Board[row][column]==EMPTY)

printf(" ");

else if(Board[row][column]==HUMAN)

printf("X ");

else

printf("O ");

}

printf("\n");

}

}

int main() {

Nodes playNode;

int choice,first;

int a,b;

int result;

while(TRUE) {

while(TRUE) {

printf("请选择你要进行的操作：\n");

printf("1：开局\n");

printf("2：退出\n");

scanf("%d",&choice);

if(choice==1)

break;

if(choice==2)

exit(0);

printf("你的输入有误，请重新输入。\n");

}

system("cls");

InitBoard();

while(TRUE) {

printf("请决定人机对战时谁先走第一步？\n1：人\n2：电脑\n");

scanf("%d",&first);

if(first==1 || first==2) {

break;

}

printf("输入错误，请重新选择。\n");

}

system("cls");

printf("人的棋子为O，电脑的棋子X。\n");

if(first==1) {

while(TRUE) {

while(TRUE) {

printf("请输入你落子所在的行数，列数（格式：a b（a,b在0~2之间））：");

scanf("%d %d",&a,&b);

if(a>=0 && a=0 && b

break;

printf("你输入的位置不合法，请重新输入：\n");

}

Place(a,b,HUMAN);

Print();

if((result=PostionValue()) != PLAYING)

break;

playNode=BestMovement(COMPUTER);

Place(playNode.row,playNode.column,COMPUTER);

printf("电脑落子后的棋盘为：\n");

Print();

if((result=PostionValue()) != PLAYING)

break;

}

}

else if(first==2) {

while(TRUE) {

printf("电脑落子后棋盘状态为：\n");

playNode=BestMovement(COMPUTER);

Place(playNode.row,playNode.column,COMPUTER);

Print();

if((result=PostionValue()) != PLAYING)

break;

while(TRUE) {

printf("请输入你落子所在的行数，列数（格式：a b（a,b在0~2之间））：");

scanf("%d %d",&a,&b);

if(a>=0 && a=0 && b

break;

printf("你输入的位置不合法，请重新输入：\n");

}

Place(a,b,HUMAN);

Print();

if((result=PostionValue()) != PLAYING)

break;

}

}

if(result==COMPUTER_WIN)

printf("哈哈，你输了！\n");

else if(result==HUMAN_WIN)

printf("恭喜，你赢了！\n");

else

printf("平局！\n");

getchar();

printf("按任意键继续。\n");

getchar();

system("cls");

}

return 0;

}

数据结构课程设计报告