双人五子棋.docx
《双人五子棋.docx》由会员分享，可在线阅读，更多相关《双人五子棋.docx（29页珍藏版）》请在冰点文库上搜索。
双人五子棋
双人五子棋
1课程设计任务与要求
课程设计目的
《数据结构》是计算机专业一门重要的专业技术基础课程。
本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术。
本课程将为整个专业的学习以及软件设计水平的提高打下良好的基础。
为了学好《数据结构》，必须掌握编写一些在特定数据结构上的算法，并通过上机调试，更好地掌握各种数据结构及其特点，此次《数据结构》课程设计目的正在于此。
《数据结构》在计算机科学中是一门综合性的专业基础课。
《数据结构》的研究不仅涉及到计算机的硬件的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储中的分配问题。
在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。
因此，可以认为“数据结构”是介于数学，计算机硬件和计算机软件三者之间的一门核心课程。
在计算机科学中，《数据结构》不仅是一般的程序设计（特别是非数值计算的程序）的基础，而且是设计和实现编译程序、操作系统、数据库系统用其他系统程序和大型应用程序的重要基础。
“数据结构”的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型的观点来讨论数据，已成为一种新的趋势，越来越被人们所注视。
经过本次课程设计，我们对于数据结构基本理论和存储结构及算法设计将有更加深入的理解，并提高我们在实际设计操作中系统分析、结构确定、算法选择、数学建模和信息加工的能力，提高我们的C/C++语言程序设计能力，以及培养学我们编写程序设计文档的能力。
问题描述
（1）问题说明
实现双人对战，一方五子连成一条直线即赢得此盘，五子不论是在一条直线或斜线上都可以。
（2）设计棋盘
棋盘上横竖都可以放19颗棋子。
（3）输入要求
由用户指定，可以把棋子放在棋盘上得任意位置。
（4）输出要求
当任意一方的五子连成一条直线都将显示该棋手胜出。
2总体设计
功能模块化分析
通过问题描述的分析，可知双人五子棋问题要求实现的功能大概大致由三个部分组成：
（1）棋盘的实现
（2）双人对战
（3）输出战况
系统结构的总体设计
根据问题的性质，使用结构化设计方法。
结构化设计方法（StructuredDesign,SD）是一种面向数据流的设计方法，是基于模块化、自顶向下、逐层细化、结构化程序设计等程序设计基础的设计方式，它需要明确数据处理的类型。
根据对问题的分析可知，双人五子棋问题属于变换型数据处理问题。
因此，可以将整个问题划分5个大模块。
输入模块、初始化模块、位置测试模块、输出模块。
总体模块。
（1）输入模块：
提示用户输入数据，接受用户的输入。
若该位置上没有棋子，就可以放入棋子，如果棋盘上没有五个一样的棋子连成一个线，则下个棋手继续输入数据，以此循环，知道有胜出者，或者棋盘上所有位置都棋子则停止游戏。
（2）初始化模块：
初始化所有的数据结构中的数据。
（3）位置测试模块：
按照接受到双方的五子棋在棋盘上的位置，判断该位置是否可以落子，根据测试返回不同的信号。
（4）输出模块：
根据测试返回的信号，输出战况。
（5）总控模块：
负责调用处理模块，完成双人五子棋问题的求解。
五子棋问题的软件结构图如图1。
图1双人五子棋流程图
处理方式设计
针对问题和核心模块，采用深度优先遍历思想和回溯算法的非递归形式。
（1）深度优先遍历的基本思想
深度优先遍历可以从任意顶点开始访问图的顶点，然后把该顶点标记为已访问。
在每次迭代的时候，该算法紧接着处理与当前顶点邻接的未访问顶点。
如果有若干个这样的顶点，可以任意选择一个顶点。
凡在实际应用中，选择哪一个邻接的未访问候选顶点主要是由表示图的数据结构决定的。
（2）回溯算法的基本思想
回溯法是穷举查找技术的一个变种。
它每次只构造解的一个分量，然后按照下面的方法来评估这个部分构造解。
如果一个部分构造解可以进一步构造而不会违反问题的约束，我们就接受对解的下一个分量所做的第一个合法选择。
如果无法对下一分量进行合法的选择，就不必对剩下的任何分量再做任何选择了。
在这种情况下，该算法进行回溯，把部分构造解的最后一个分量替换为它的下一个选择。
3详细设计
详细设计的主要任务是根据概要设计对每个模块的定义进行设计，以实现其功能算法和外部接口所要求的模块内部的数据结构和程序的逻辑结构。
详细设计的目标有两个：
实现模块功能的算法要逻辑上正确和算法描述要简明易懂。
传统软件开发方法的详细设计主要是用结构化程序设计法。
详细设计的表示工具有图形工具和语言工具。
图形工具有程序流程图、PAD（ProblemAnalysisDiagram）图、NS（由Nassi和Shneidermen开发，简称NS）图。
语言工具有伪码和PDL（ProgramDesignLanguage）等。
本次设计主要采用的工具是程序流程图。
全局数据结构
intgPlayOrder:
指示当前行棋方。
structpointgCursor:
光标在期盼上的位置。
chargChessBoard[19][19]：
用于记录棋盘上各点的状态。
测试模块
（1）核心函数test（）。
（2）接口接受上级模块传送来的数据。
输入模块
（1）
intChessGo（intOrder,structpointCursor）
{
/*判断交叉点上有无棋子*/
if（gChessBoard[][]==CHESSNULL）
{
/*若没有棋子,则可以落子*/
gotoxy+MAPXOFT,+MAPYOFT）;
textcolor（LIGHTBLUE）;
putch（Order）;
gotoxy+MAPXOFT,+MAPYOFT）;
gChessBoard[][]=Order;
returnTRUE;
}
else
returnFALSE;
}
用来实现输入，使棋子落入棋盘，让用户进行对战。
（2）接口不接受任何数据。
初始化模块
（1）
voidInit（void）
{
inti,j;
char*Msg[]=
{
"Player1key:
",
"UP----w",
"DOWN--s",
"LEFT--a",
"RIGHT-d",
"DO----space",
"",
"Player2key:
",
"UP----up",
"DOWN--down",
"LEFT--left",
"RIGHT-right",
"DO----ENTER",
"",
"exitgame:
",
"ESC",
NULL,
};
使界面初始化和数据初始化。
（2）接口不接受任何数据。
4测试
测试是使用人工或者自动手段来运行或测试某个系统的过程,其目的在于检验它是否满足规定的需求或弄清预期结果与实际结果之间的差别.其主要阶段包括单元测试、集成测试、确认测试和系统测试。
测试方法主要有白盒测试法和黑盒测试法；其中,白盒测试也称结构测试或逻辑驱动测试，它是按照程序内部的结构测试程序，通过测试来检测产品内部动作是否按照设计规格说明书的规定正常进行，检验程序中的每条通路是否都能按预定要求正确工作；黑盒测试也称功能测试，它是通过测试来检测每个功能是否都能正常使用。
在测试中，把程序看作一个不能打开的黑盒子，在完全不考虑程序内部结构和内部特性的情况下，在程序接口进行测试，它只检查程序功能是否按照需求规格说明书的规定正常使用，程序是否能适当地接收输入数据而产生正确的输出信息。
黑盒测试着眼于程序外部结构，不考虑内部逻辑结构，主要针对软件界面和软件功能进行测试。
确认测试采用黒盒测试法进行测试。
⑴测试用例设计：
表4测试用例
输入数据
预期结果
从上到下一方五颗棋子连在一起
Win
从左至右一方五颗棋子连在一起
Win
从左至右上一方五颗棋子连在一起
Win
从左至右下一方五颗棋子连在一起
Win
其他情况
没有输出
⑵测试结果：
经过测试，实际结果符合预期结果。
图2测试用例1
图3测试用例2
图4用例测试3
图5用例测试4
5课程设计总结
该课程设计的特点
本次课程设计是围绕数据结构进行。
根据问题描述可知，需要解决问题并不复杂，整个问题只需要实现一个功能，那就是输出马按特定规则在棋盘上的遍历顺序。
但是，为了实现该单一功能，却需要优秀的算法和数据结构以保证实现的时间和空间效率。
由于所有的操作都是在棋盘上进行，因此，我们理所当然会想到将整个棋盘抽象成一个数据结构——二维数组，但是一个二维数组不足以存储马的遍历过程需要保存的诸如访问标记、前驱访问节点等等信息，因此我采用了一个结构体，结构体设置几个简单的整型变量来保存各种信息。
基本的数据结构设计好后，我们还需要基于该数据结构的好的算法来实现。
之前，我使用了广度优先搜索对马的路径进行搜索，但由于输出结果依然难以辨认马的行走路径，因此，我改换成深度优先搜索和回溯法来寻找马的路径，将回溯是需要的信息保存在棋盘的数据结构中，这就相当于，用深度搜索遍历一个由马的行走路径所构成的一颗解的空间树，马的行走路径实际上就是从这颗解空间树的根节点到叶子节点过程中经过的所有节点所组成的路径。
存在的不足
虽然设计的程序完成了题目描述所需要实现的功能，但是仍然存在不尽人意的地方。
那就是运行结果，由于题目仅要求输出序号，实际上输出的序号是难于理解的，辨认出其中的路径也是比较困难的。
心得体会
经过二个星期的上机实践学习，使我对数据结构有了更进一步的认识和了解，要想学好它要重在实践，要通过不断的上机操作才能更好地学习它，通过实践，我也发现我的好多不足之处，首先是自己在指法上还不行，经常按错字母，通过学习也有所改进；再有对数据结构、算法和软件工程等通过实践，使我在这几个方面的认识有所提高。
通过实践的学习，我认到学好计算机要重视实践操作，不仅仅是学习数据结构，以及其它的计算机方面的知识都要重在实践，所以后在学习过程中，我会更加注视实践操作，使自己便好地学好计算机。
参考文献
[1]肖孟强，曲秀清.软件工程——原理、方法与应用.[M].北京：
中国水利水电出版社，2005年10月.
[2]（美）AnanyLevitin.算法设计与分析基础（第二版）.[M].（潘彦译）.背景：
清华大学出版社，2007年1月.
[3]SaItajsahni.数据结构、算法与应用.[M].2004年12月第一版.北京：
机械工业出版社.
[4]严薇敏.《数据结构（C语言版）》.[M].2003年5月第一版.北京：
清华大学出版社.
附录：
源代码
#include<>
#include<>
#include<>
#include<>
#include<>
#defineCROSSRU0xbf/*右上角点*/
#defineCROSSLU0xda/*左上角点*/
#defineCROSSLD0xc0/*左下角点*/
#defineCROSSRD0xd9/*右下角点*/
#defineCROSSL0xc3/*左边*/
#defineCROSSR0xb4/*右边*/
#defineCROSSU0xc2/*上边*/
#defineCROSSD0xc1/*下边*/
#defineCROSS0xc5/*十字交叉点*/
/*定义棋盘左上角点在屏幕上的位置*/
#defineMAPXOFT5
#defineMAPYOFT2
/*定义1号玩家的操作键键码*/
#definePLAY1UP0x1157/*上移--'W'*/
#definePLAY1DOWN0x1f53/*下移--'S'*/
#definePLAY1LEFT0x1e41/*左移--'A'*/
#definePLAY1RIGHT0x2044/*右移--'D'*/
#definePLAY1DO0x3920/*落子--空格键*/
/*定义2号玩家的操作键键码*/
#definePLAY2UP0x4800/*上移--方向键up*/
#definePLAY2DOWN0x5000/*下移--方向键down*/
#definePLAY2LEFT0x4b00/*左移--方向键left*/
#definePLAY2RIGHT0x4d00/*右移--方向键right*/
#definePLAY2DO0x1c0d/*落子--回车键Enter*/
/*若想在游戏中途退出,可按Esc键*/
#defineESCAPE0x011b
/*定义棋盘上交叉点的状态,即该点有无棋子*/
/*若有棋子,还应能指出是哪个玩家的棋子*/
#defineCHESSNULL0/*没有棋子*/
#defineCHESS1'O'/*一号玩家的棋子*/
#defineCHESS2'X'/*二号玩家的棋子*/
/*定义按键类别*/
#defineKEYEXIT0/*退出键*/
#defineKEYFALLCHESS1/*落子键*/
#defineKEYMOVECURSOR2/*光标移动键*/
#defineKEYINVALID3/*无效键*/
/*定义符号常量:
真,假---真为1,假为0*/
#defineTRUE1
#defineFALSE0
/**********************************************************/
/*定义数据结构*/
/*棋盘交叉点坐标的数据结构*/
structpoint
{
intx,y;
};
/**********************************************************/
/*自定义函数原型说明*/
voidInit（void）;
intGetKey（void）;
intCheckKey（intpress）;
intChangeOrder（void）;
intChessGo（intOrder,structpointCursor）;
voidDoError（void）;
voidDoOK（void）;
voidDoWin（intOrder）;
voidMoveCursor（intOrder,intpress）;
voidDrawCross（intx,inty）;
voidDrawMap（void）;
intJudgeWin（intOrder,structpointCursor）;
intJudgeWinLine（intOrder,structpointCursor,intdirection）;
voidShowOrderMsg（intOrder）;
voidEndGame（void）;
/**********************************************************/
/**********************************************************/
/*定义全局变量*/
intgPlayOrder;/*指示当前行棋方*/
structpointgCursor;/*光标在棋盘上的位置*/
chargChessBoard[19][19];/*用于记录棋盘上各点的状态*/
/**********************************************************/
/**********************************************************/
/*主函数*/
voidmain（）
{
intpress;
intbOutWhile=FALSE;/*退出循环标志*/
Init（）;/*初始化图象，数据*/
while
（1）
{
press=GetKey（）;/*获取用户的按键值*/
switch（CheckKey（press））/*判断按键类别*/
{
/*是退出键*/
caseKEYEXIT:
clrscr（）;/*清屏*/
bOutWhile=TRUE;
break;
/*是落子键*/
caseKEYFALLCHESS:
if（ChessGo（gPlayOrder,gCursor）==FALSE）/*走棋*/
DoError（）;/*落子错误*/
else
{
DoOK（）;/*落子正确*/
/*如果当前行棋方赢棋*/
if（JudgeWin（gPlayOrder,gCursor）==TRUE）
{
DoWin（gPlayOrder）;
bOutWhile=TRUE;/*退出循环标志置为真*/
}
/*否则*/
else
/*交换行棋方*/
ChangeOrder（）;
ShowOrderMsg（gPlayOrder）;
}
break;
/*是光标移动键*/
caseKEYMOVECURSOR:
MoveCursor（gPlayOrder,press）;
break;
/*是无效键*/
caseKEYINVALID:
break;
}
if（bOutWhile==TRUE）
break;
}
/*游戏结束*/
EndGame（）;
}
/**********************************************************/
/*界面初始化，数据初始化*/
voidInit（void）
{
inti,j;
char*Msg[]=
{
"Player1key:
",
"UP----w",
"DOWN--s",
"LEFT--a",
"RIGHT-d",
"DO----space",
"",
"Player2key:
",
"UP----up",
"DOWN--down",
"LEFT--left",
"RIGHT-right",
"DO----ENTER",
"",
"exitgame:
",
"ESC",
NULL,
};
/*先手方为1号玩家*/
gPlayOrder=CHESS1;
/*棋盘数据清零,即棋盘上各点开始的时候都没有棋子*/
for（i=0;i<19;i++）
for（j=0;j<19;j++）
gChessBoard[i][j]=CHESSNULL;
/*光标初始位置*/
==0;
/*画棋盘*/
textmode（C40）;
DrawMap（）;
/*显示操作键说明*/
i=0;
textcolor（BROWN）;
while（Msg[i]!
=NULL）
{
gotoxy（25,3+i）;
cputs（Msg[i]）;
i++;
}
/*显示当前行棋方*/
ShowOrderMsg（gPlayOrder）;
/*光标移至棋盘的左上角点处*/
gotoxy+MAPXOFT,+MAPYOFT）;
}
/*画棋盘*/
voidDrawMap（void）
{
inti,j;
clrscr（）;
for（i=0;i<19;i++）
for（j=0;j<19;j++）
DrawCross（i,j）;
}
/*画棋盘上的交叉点*/
voidDrawCross（intx,inty）
{
gotoxy（x+MAPXOFT,y+MAPYOFT）;
/*交叉点上是一号玩家的棋子*/
if（gChessBoard[x][y]==CHESS1）
{
textcolor（LIGHTBLUE）;
putch（CHESS1）;
return;
}
/*交叉点上是二号玩家的棋子*/
if（gChessBoard[x][y]==CHESS2）
{
textcolor（LIGHTBLUE）;
putch（CHESS2）;
return;
}
textcolor（GREEN）;
/*左上角交叉点*/
if（x==0&&y==0）
{
putch（CROSSLU）;
return;
}
/*左下角交叉点*/
if（x==0&&y==18）
{
putch（CROSSLD）;
return;
}
/*右上角交叉点*/
if（x==18&&y==0）
{
putch（CROSSRU）;
return;
}
/*右下角交叉点*/
if（x==18&&y==18）
{
putch（CROSSRD）;
return;
}
/*左边界交叉点*/
if（x==0）
{
putch（CROSSL）;
return;
}
/*右边界交叉点*/
if（x==18）
{
putch（CROSSR）;
return;
}
/*上边界交叉点*/
if（y==0）
{
putch（CROSSU）;
return;
}
/*下边界交叉点*/
if（y==18）
{
putch（CROSSD）;
return;
}
/*棋盘中间的交叉点*/
putch（CROSS）;
}
/*交换行棋方*/
intChangeOrder（void）
{
if（gPlayOrder==CHESS1）
gPlayOrder=CHESS2;
else
gPlayOrder=CHESS1;
return（gPlayOrder）;
}
/*获取按键值*/
intGetKey（void）
{
charlowbyte;
intpress;
while（bioskey
（1）==0）
;/*如果用户没有按键，空循环*/
press=bioskey（0）;
lowbyte=press&0xff;
press=press&0xff00+toupper（lowbyte）;
return（press）;
}
/*落子错误处理*/
voidDoError（void）
{
sound（1200）;
delay（50）;
nosound（）;
}
/*赢棋处理*/
voidDoWin（intOrder）
{
sound（1500）;delay（100）;
sound（0）;delay（50）;
sound（800）;delay（100）;
sound（0）;delay（50）;
sound（1500）;delay（100）;
sound（0）;delay（50）;
sound（800）;delay（100）;
sound（0）;dela
升级会员 