数据结构优秀课程设计优质报告模板.doc

课程设计说明书

课程名称： 数 据 结 构
专业： 班级：
姓名： 学号：

指导老师： 成绩：

完成日期： 年 月 日

任 务 书
题目：黑白棋系统
设计内容及要求：
1.课程设计任务内容
经过玩家和电脑双方交替下棋，在一个8行8列方格中，进行棋子相互交替翻转。反复循环下棋，最终让双方棋子填满整个方格。再依据循环遍历方格程序，判定玩家和电脑双方棋子数。进行大小判定，最红给出胜败一方。并依据y/n选项，判定是否要进行下一局游戏。
2.课程设计要求
实现黑白两色棋子对峙
开发环境：vc++6.0
实现目标：
（1） 熟悉利用c语言程序编写代码。
（2） 能够理清整个程序运行过程并绘画步骤图
（3） 了解怎样定义局部变量和整体变量；
（4） 学会上机调试程序，发觉问题，并处理
（5） 学习使用C++程序来了解游戏原理。
（6） 学习用文档书写程序说明

摘 要
本文研究工作在于利用计算机模拟人脑进行下黑白棋，计算机下棋是人工智能领域中一个研究热点，多年以来，伴随计算机技术和人工智能技术不停发展，计算机下棋水平得到了长足进步
该程序最终胜败是由棋盘上岗双方棋子个数来判定，多一方为胜，少一方为负。所以该程序关键利用战术有减弱对手行动战术、四角优先战术、在游戏开局和中局时，程序采取减弱对手行动力战术，即尽可能降低对手能够落子位置；在游戏终局时则采取最大贪吃战术，即尽可能多吃掉对手棋子；而四角优先战术则是贯穿游戏一直，棋盘四角围稳定角，不会被对手吃掉，所以这里是兵家必争之地，在阻止对手进角同时，自己却又要努力进角。
关键词：黑白棋；编程；设计

目 录

1.引 言 4
2.课题分析 7
3.具体设计过程 8
3.1设计思绪 8
3.2程序设计步骤图 8
3.3.函数实现说明 12
4.程序运行结果 14
5.软件使用说明 18
6.结论 21
参 考 文 献 23
附录：源代码 24

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.2 人机对战模块步骤图

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

开始
输出初始成绩
If[i][j]==0
If[i][j]==*
玩家score+1
电脑score+1
玩家score>电脑score
cscorescorescore
玩家赢
电脑赢
否
是
是
是
否
否
图3.3 成绩输出模块程序步骤图

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],int
moves[][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()电脑下棋函数
功效： 主函数经过调用该函数，获取电脑下棋位置。该函数分别又调用make_move();
valid_moves();new_score=best_move();函数，以获取最好下棋位置
使用方法：此函数调用方法为void computer_move(char board[][SIZE],int
moves[][SIZE],char player);
说明：int moves[][SIZE]为玩家输入横纵坐标，char player为判定玩家为电脑
还是人
返回值： 无

(6)int get_score()分数获取函数申明
功效：用此函数来获取电脑和玩家分数，方便判定最终胜败
使用方法：此函数调用方法为(char board[][SIZE],char player);
说明：char board[][SIZE]是一个二维数组，来控制棋盘变量。char player是代表玩
家一个参数
返回值： int

(7)int best_move（）
功效：best_move是电脑下子最好位置判定一个函数，经过不停地比较，用了两次
for循环，并遍历棋盘上*个数，来获取最好位置。
使用方法：此函数调用方法为int best_move(char board[][SIZE],int moves[][SIZE],
char player);
说明：同void computer_move()
返回值： int
4.程序运行结果

图4.1为初始界面,当我们选择运行程序时，便会出现以下图界面。依据上面文字内容，我们能够了解游戏规则。并按enter键，进行游戏。以下图所表示：

图4.1初始界面图

图4.2为进入游戏后首界面，下图是按enter键以后进入游戏界面。第一局游戏时，玩家棋子用0替换，电脑棋子用*替换。初始界面中，棋盘上便已经有了在棋盘正中央相互交叉棋子。这是初始界面一个情况。以下图所表示：

图4.2游戏首界面图

图4.3为运行过程中，双方对峙截图。在游戏过程中，轮到玩家下棋时候，系统会出现：输入坐标<行列>提醒，此时，我们输入方法是第一个为数字，代表棋盘横坐标，第二个为字母，代表棋盘纵坐标，中间无空格。以下图所表示：

图4.3对峙过程图

图4.4为对峙结束后，得到分值结果图。最终，系统会提醒，是否要重新开始游戏，我们能够经过y/n选择是否继续。假如选择y系统将会开始一局新游戏，并初始化棋盘。若输入n，系统将不再进行游戏，退出。以下图所表示：

图4.4双方对峙结果图

5.软件使用说明
黑白棋是一款娱乐型游戏，在和锻炼人脑力和反应能力。在本程序中，先切换到对应界面下，然后依据提醒来完成下一步操作。
在本程序中纵坐标是数字，横坐标是字母。依据坐标轴性质来确定每一步棋位置。并依据和之相对应提醒来完成结果。比如：电脑无棋可走，这是一步无效操作等。
图5.1为程序进入游戏后初始界面

图5.1程序初始界面图
下图为图5.2，是程序运行过程中截图。当我们输入1a是，提醒我们无效，请重新输入，当输入3f是，亦是如此。此程序过程是输入不正当过程。在做了对应操作后，再继续操作。玩家一定要依据提醒来进行下一步操作，所以上图正确坐标是6e。

图5.2无效运行过程图
图5.3是玩家要尽可能使盘上子来变成己方，避免无须要损失。
有是电脑会没有棋可走，你能够在继续走！

图5.3无棋可走情况图

6.结论

参 考 文 献

[1] 谭浩强.《C程序设计（第三版）》，清华大学出版社，.7
[2] 郭翠英.《C语言课程设计案例精编》, 中国水利水电出版社,.3
[3] 朱振元.《数据结构（面向对象语言描述）》，清华大学出版社，.2
[4] 张翔.《C语言函数大全》，电子工业出版社，.4
[5]徐金梧.《TURBO C实用大全》，机械工业出版社，1996.5

附录：源代码
#include <stdio.h>
#include <ctype.h>
#define SIZE 8
void display(char board[][SIZE]);
int valid_moves(char board[][SIZE],int moves[][SIZE],char player);
void make_move(char board[][SIZE],int row,int col,char player);
void computer_move(char board[][SIZE],int moves[][SIZE],char player);
int get_score(char board[][SIZE],char player);
int best_move(char board[][SIZE],int moves[][SIZE],char player);
void main()
{
char board[SIZE][SIZE]={0};
int moves[SIZE][SIZE]={0};
int row=0;
int col=0;
int no_of_games=0;
int no_of_moves=0;
int invalid_moves=0;
int comp_score=0;
int user_score=0;
char y=0;
char x=0;
char again=0;
int player=0;
printf("●玩法说明\n");
printf("1.开辟新局者持黑子，加入者持白子。\n");
printf(" 我先执白棋 - (*)\n 你执黑棋 - (0).\n");
printf("\n祝你好运! 请按enter键，进行游戏.\n");
scanf("%c",&again);
do
{
player=++no_of_games%2;
no_of_moves=4;
for(row=0;row<SIZE;row++)
for(col=0;col<SIZE;col++)
board[row][col]=' ';
board[SIZE/2-1][SIZE/2-1]=board[SIZE/2][SIZE/2]='0';
board[SIZE/2-1][SIZE/2]=board[SIZE/2][SIZE/2-1]='*';
do
{display(board);
if(player++%2)
{
if(valid_moves(board,moves,'0'))
{
for(;;)
{
fflush(stdin);
printf("输入你要下子位置(行列)：: ");
scanf("%d%c",&x,&y);
y=tolower(y)-'a';
x--;
if(x>=0&&y>=0&&x<SIZE&&y<SIZE&&moves[x][y])
{
make_move(board,x,y,'0');
no_of_moves++;
break;
}
else
printf("不是有效位置，请重新输入。\n");
}
}
else
if(++invalid_moves<2)
{
fflush(stdin);
printf("\n没有可下位置，电脑下棋。\n");
scanf("%c",&again);
}
else
printf("\n没有多出位置，本局游戏结束。\n");
}
else
{
if(valid_moves(board,moves,'*'))
{
invalid_moves=0;
computer_move(board,moves,'*');
no_of_moves++;
}
else
{
if(++invalid_moves<2)
printf("\n没有可下位置，你下棋。\n");
else
printf("\n没有多出位置，本局游戏结束。\n");
}
}
}while(no_of_moves<SIZE*SIZE&&invalid_moves<2);
display(board);
comp_score=user_score=0;
for(row=0;row<SIZE;row++)
for(col=0;col<SIZE;col++)
{
comp_score+=board[row][col]=='*';
user_score+=board[row][col]=='0';
}
printf("最终分数：");
printf("电脑： %d\t玩家： %d\n\n",comp_score,user_score);
fflush(stdin);
printf("你还想玩一次吗？(y/n):");
scanf("%c",&again);
}while(tolower(again)=='y');

printf("\n谢谢使用此游戏。\n");
}
void display(char board[][SIZE])
{
int row=0;
int col=0;
char col_label='a';
printf("\n ");
for(col=0;col<SIZE;col++)
printf(" %c",col_label+col);
printf("\n");
for(row=0;row<SIZE;row++)
{
printf(" +");
for(col=0;col<SIZE;col++)
printf("---+");
printf("\n%2d|",row+1);
for(col=0;col<SIZE;col++)
printf(" %c |",board[row][col]);
printf("\n");
}
printf(" +");
for(col=0;col<SIZE;col++)
printf("---+");
printf("\n");
}
int valid_moves(char board[][SIZE],int moves[][SIZE],char player)
{
int rowdelta=0;
int coldelta=0;
int row=0;
int col=0;
int x=0;
int y=0;
int no_of_moves=0;
char opponent=(player=='0')?'*':'0';
for(row=0;row<SIZE;row++)
for(col=0;col<SIZE;col++)
moves[row][col]=0;
for(row=0;row<SIZE;row++)
for(col=0;col<SIZE;col++)
{
if(board[row][col]!=' ')
continue;
for(rowdelta=-1;rowdelta<=1;rowdelta++)
for(coldelta=-1;coldelta<=1;coldelta++)
{
if(row+rowdelta<0||row+rowdelta>=SIZE||
col+coldelta<0||col+coldelta>=SIZE||
(rowdelta==0&&coldelta==0))
continue;
if(board[row+rowdelta][col+coldelta]==opponent)
{
x=row+rowdelta;
y=col+coldelta;
for(;;)
{
x+=rowdelta;
y+=coldelta;
if(x<0||x>=SIZE||y<0||y>=SIZE)
break;
if(board[x][y]==' ')
break;
if(board[x][y]==player)
{
moves[row][col]=1;
no_of_moves++;
break;
}
}
}
}
}
return no_of_moves;
}
void make_move(char board[][SIZE],int row,int col,char player)
{
int rowdelta=0;
int coldelta=0;
int x=0;
int y=0;
char opponent=(player=='0')?'*':'0';
board[row][col]=player;
for(rowdelta=-1;rowdelta<=1;rowdelta++)
for(coldelta=-1;coldelta<=1;coldelta++)
{
if(row+rowdelta<0||row+rowdelta>=SIZE||
col+coldelta<0||col+coldelta>=SIZE||
(rowdelta==0&&coldelta==0))
continue;
if(board[row+rowdelta][col+coldelta]==opponent)
{
x=row+rowdelta;
y=col+coldelta;
for(;;)
{
x+=rowdelta;
y+=coldelta;
if(x<0||x>=SIZE||y<0||y>=SIZE)
break;
if(board[x][y]==' ')
break;
if(board[x][y]==player)
{
while(board[x-=rowdelta][y-=coldelta]==opponent)
board[x][y]=player;
break;}
}
}
}
}
int get_score(char board[][SIZE],char player)
{
int score=0;
int row=0;
int col=0;
char opponent=player=='0'?'*':'0';
for(row=0;row<SIZE;row++)
for(col=0;col<SIZE;col++)
{
score-=board[row][col]==opponent;
score+=board[row][col]==player;
}
return score;
}
int best_move(char board[][SIZE],int moves[][SIZE],char player)
{
int row=0;
int col=0;
int i=0;
int j=0;
char opponent=player=='0'?'*':'0';
char new_board[SIZE][SIZE]={0};
int score=0;
int new_score=0;
for(row=0;row<SIZE;row++)
for(col=0;col<SIZE;col++)
{
if(!moves[row][col])
continue;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
new_board[i][j]=board[i][j];
make_move(new_board,row,col,player);
new_score=get_score(new_board,player);
if(score<new_score)
score=new_score;
}
return score;
}
void computer_move(char board[][SIZE],int moves[][SIZE],char player)
{
int row=0;
int col=0;
int best_row=0;
int best_col=0;
int i=0;
int j=0;
int new_score=0;
int score=100;
char temp_board[SIZE][SIZE];
int temp_moves[SIZE][SIZE];
char opponent=player=='0'?'*':'0';
for(row=0;row<SIZE;row++)
for(col=0;col<SIZE;col++)
{
if(moves[row][col]==0)
continue;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
temp_board[i][j]=board[i][j];
make_move(temp_board,row,col,player);
valid_moves(temp_board,temp_moves,opponent);
new_score=best_move(temp_board,temp_moves,opponent);
if(new_score<score)
{
score=new_score;
best_row=row;
best_col=col;
}}
make_move(board,best_row,best_col,player
}

姓名

班级

学号

课设题目

老师评语：

老师署名：
年 1月13日