数据结构课程设计双人五子棋.doc

1、目录1 课程设计任务与要求21.1 课程设计目的21.2 问题描述22 总体设计32.1 功能模块化分析32.2 系统结构的总体设计32.3 处理方式设计53 详细设计53.1 全局数据结构53.2 测试模块63.3 输入模块63.4 初始化模块64 测试75 课程设计总结105.1 该课程设计的特点105.2 存在的不足105.3 心得体会10参考文献11附录：源代码11双人五子棋1 课程设计任务与要求1.1 课程设计目的数据结构是计算机专业一门重要的专业技术基础课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术。本课程将为整个专业

2、的学习以及软件设计水平的提高打下良好的基础。为了学好数据结构，必须掌握编写一些在特定数据结构上的算法，并通过上机调试，更好地掌握各种数据结构及其特点，此次数据结构课程设计目的正在于此。数据结构在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及到计算机的硬件的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。因此，可以认为“数据结构”是介于数学，计算机硬件和计算机软件三者之间的一门核心课程。在计算机科学中，数据结构不仅是一般的程序设计（特别是非数值计

3、算的程序）的基础，而且是设计和实现编译程序、操作系统、数据库系统用其他系统程序和大型应用程序的重要基础。“数据结构”的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型的观点来讨论数据，已成为一种新的趋势，越来越被人们所注视。经过本次课程设计，我们对于数据结构基本理论和存储结构及算法设计将有更加深入的理解，并提高我们在实际设计操作中系统分析、结构确定、算法选择、数学建模和信息加工的能力，提高我们的C/C+语言程序设计能力，以及培养学我们编写程序设计文档的能力。1.2 问题描述（1）问题说明实现双人对战，一方五子连成一条直线即赢

4、得此盘，五子不论是在一条直线或斜线上都可以。（2）设计棋盘 棋盘上横竖都可以放19颗棋子。（3）输入要求 由用户指定，可以把棋子放在棋盘上得任意位置。（4）输出要求 当任意一方的五子连成一条直线都将显示该棋手胜出。2 总体设计2.1 功能模块化分析通过问题描述的分析，可知双人五子棋问题要求实现的功能大概大致由三个部分组成：（1）棋盘的实现（2）双人对战（3）输出战况2.2 系统结构的总体设计根据问题的性质，使用结构化设计方法。结构化设计方法（Structured Design, SD）是一种面向数据流的设计方法，是基于模块化、自顶向下、逐层细化、结构化程序设计等程序设计基础的设计方式，它需要明

5、确数据处理的类型。根据对问题的分析可知，双人五子棋问题属于变换型数据处理问题。因此，可以将整个问题划分5个大模块。输入模块、初始化模块、位置测试模块、输出模块。总体模块。（1）输入模块：提示用户输入数据，接受用户的输入。若该位置上没有棋子，就可以放入棋子，如果棋盘上没有五个一样的棋子连成一个线，则下个棋手继续输入数据，以此循环，知道有胜出者，或者棋盘上所有位置都棋子则停止游戏。（2）初始化模块：初始化所有的数据结构中的数据。（3）位置测试模块：按照接受到双方的五子棋在棋盘上的位置，判断该位置是否可以落子，根据测试返回不同的信号。（4）输出模块：根据测试返回的信号，输出战况。（5）总控模块：负责

6、调用处理模块，完成双人五子棋问题的求解。五子棋问题的软件结构图如图1。 图1 双人五子棋流程图2.3 处理方式设计针对问题和核心模块，采用深度优先遍历思想和回溯算法的非递归形式。（1）深度优先遍历的基本思想深度优先遍历可以从任意顶点开始访问图的顶点，然后把该顶点标记为已访问。在每次迭代的时候，该算法紧接着处理与当前顶点邻接的未访问顶点。如果有若干个这样的顶点，可以任意选择一个顶点。凡在实际应用中，选择哪一个邻接的未访问候选顶点主要是由表示图的数据结构决定的。（2）回溯算法的基本思想回溯法是穷举查找技术的一个变种。它每次只构造解的一个分量，然后按照下面的方法来评估这个部分构造解。如果一个部分构造

7、解可以进一步构造而不会违反问题的约束，我们就接受对解的下一个分量所做的第一个合法选择。如果无法对下一分量进行合法的选择，就不必对剩下的任何分量再做任何选择了。在这种情况下，该算法进行回溯，把部分构造解的最后一个分量替换为它的下一个选择。3 详细设计 详细设计的主要任务是根据概要设计对每个模块的定义进行设计，以实现其功能算法和外部接口所要求的模块内部的数据结构和程序的逻辑结构。详细设计的目标有两个：实现模块功能的算法要逻辑上正确和算法描述要简明易懂。传统软件开发方法的详细设计主要是用结构化程序设计法。详细设计的表示工具有图形工具和语言工具。图形工具有程序流程图、PAD（Problem Analy

8、sis Diagram）图、NS（由Nassi和Shneidermen开发，简称NS）图。语言工具有伪码和PDL（Program Design Language）等。本次设计主要采用的工具是程序流程图。3.1 全局数据结构int gPlayOrder:指示当前行棋方。struct point gCursor:光标在期盼上的位置。char gChessBoard1919：用于记录棋盘上各点的状态。3.2 测试模块（1）核心函数test（）。（2）接口接受上级模块传送来的数据。3.3 输入模块（1）int ChessGo(int Order,struct point Cursor) /*判断交叉点

9、上有无棋子*/ if(gChessBoardCursor.xCursor.y=CHESSNULL) /*若没有棋子, 则可以落子*/ gotoxy(Cursor.x+MAPXOFT,Cursor.y+MAPYOFT); textcolor(LIGHTBLUE); putch(Order); gotoxy(Cursor.x+MAPXOFT,Cursor.y+MAPYOFT); gChessBoardCursor.xCursor.y=Order; return TRUE; else return FALSE;用来实现输入，使棋子落入棋盘，让用户进行对战。（2）接口不接受任何数据。3.4 初始化模块

10、（1）void Init(void) int i,j; char *Msg= Player1 key:, UP-w, DOWN-s, LEFT-a, RIGHT-d, DO-space, , Player2 key:, UP-up, DOWN-down, LEFT-left, RIGHT-right, DO-ENTER, , exit game:, ESC, NULL, ;使界面初始化和数据初始化。（2）接口不接受任何数据。4 测试测试是使用人工或者自动手段来运行或测试某个系统的过程,其目的在于检验它是否满足规定的需求或弄清预期结果与实际结果之间的差别.其主要阶段包括单元测试、集成测试、确认测

11、试和系统测试。测试方法主要有白盒测试法和黑盒测试法；其中,白盒测试也称结构测试或逻辑驱动测试，它是按照程序内部的结构测试程序，通过测试来检测产品内部动作是否按照设计规格说明书的规定正常进行，检验程序中的每条通路是否都能按预定要求正确工作；黑盒测试也称功能测试，它是通过测试来检测每个功能是否都能正常使用。在测试中，把程序看作一个不能打开的黑盒子，在完全不考虑程序内部结构和内部特性的情况下，在程序接口进行测试，它只检查程序功能是否按照需求规格说明书的规定正常使用，程序是否能适当地接收输入数据而产生正确的输出信息。黑盒测试着眼于程序外部结构，不考虑内部逻辑结构，主要针对软件界面和软件功能进行测试。确

12、认测试采用黒盒测试法进行测试。测试用例设计：表4 测试用例输入数据预期结果从上到下一方五颗棋子连在一起Win从左至右一方五颗棋子连在一起Win从左至右上一方五颗棋子连在一起Win从左至右下一方五颗棋子连在一起Win其他情况没有输出测试结果：经过测试，实际结果符合预期结果。图2 测试用例1图3 测试用例2图4 用例测试3图5 用例测试45 课程设计总结5.1 该课程设计的特点本次课程设计是围绕数据结构进行。根据问题描述可知，需要解决问题并不复杂，整个问题只需要实现一个功能，那就是输出马按特定规则在棋盘上的遍历顺序。但是，为了实现该单一功能，却需要优秀的算法和数据结构以保证实现的时间和空间效率。由

13、于所有的操作都是在棋盘上进行，因此，我们理所当然会想到将整个棋盘抽象成一个数据结构二维数组，但是一个二维数组不足以存储马的遍历过程需要保存的诸如访问标记、前驱访问节点等等信息，因此我采用了一个结构体，结构体设置几个简单的整型变量来保存各种信息。基本的数据结构设计好后，我们还需要基于该数据结构的好的算法来实现。之前，我使用了广度优先搜索对马的路径进行搜索，但由于输出结果依然难以辨认马的行走路径，因此，我改换成深度优先搜索和回溯法来寻找马的路径，将回溯是需要的信息保存在棋盘的数据结构中，这就相当于，用深度搜索遍历一个由马的行走路径所构成的一颗解的空间树，马的行走路径实际上就是从这颗解空间树的根节点

14、到叶子节点过程中经过的所有节点所组成的路径。5.2 存在的不足虽然设计的程序完成了题目描述所需要实现的功能，但是仍然存在不尽人意的地方。那就是运行结果，由于题目仅要求输出序号，实际上输出的序号是难于理解的，辨认出其中的路径也是比较困难的。5.3 心得体会经过二个星期的上机实践学习，使我对数据结构有了更进一步的认识和了解，要想学好它要重在实践，要通过不断的上机操作才能更好地学习它，通过实践，我也发现我的好多不足之处，首先是自己在指法上还不行，经常按错字母，通过学习也有所改进；再有对数据结构、算法和软件工程等通过实践，使我在这几个方面的认识有所提高。通过实践的学习，我认到学好计算机要重视实践操作，

15、不仅仅是学习数据结构，以及其它的计算机方面的知识都要重在实践，所以后在学习过程中，我会更加注视实践操作，使自己便好地学好计算机。参考文献1 肖孟强，曲秀清.软件工程原理、方法与应用.M.北京：中国水利水电出版社，2005年10月.2 (美)Anany Levitin.算法设计与分析基础（第二版）.M .(潘彦译).背景：清华大学出版社，2007年1月.3 SaItaj sahni.数据结构、算法与应用.M.2004年12月第一版.北京：机械工业出版社.4 严薇敏.数据结构(C语言版).M.2003年5月第一版.北京：清华大学出版社.附录：源代码#include #include #includ

16、e #include #include #define CROSSRU 0xbf /*右上角点*/#define CROSSLU 0xda /*左上角点*/#define CROSSLD 0xc0 /*左下角点*/#define CROSSRD 0xd9 /*右下角点*/#define CROSSL 0xc3 /*左边*/#define CROSSR 0xb4 /*右边*/#define CROSSU 0xc2 /*上边*/#define CROSSD 0xc1 /*下边*/#define CROSS 0xc5 /*十字交叉点*/*定义棋盘左上角点在屏幕上的位置*/#define MAPXOF

17、T 5#define MAPYOFT 2/*定义1号玩家的操作键键码*/#define PLAY1UP 0x1157/*上移-W*/#define PLAY1DOWN 0x1f53/*下移-S*/#define PLAY1LEFT 0x1e41/*左移-A*/#define PLAY1RIGHT 0x2044/*右移-D*/#define PLAY1DO 0x3920/*落子-空格键*/*定义2号玩家的操作键键码*/#define PLAY2UP 0x4800/*上移-方向键up*/#define PLAY2DOWN 0x5000/*下移-方向键down*/#define PLAY2LEFT

18、0x4b00/*左移-方向键left*/#define PLAY2RIGHT 0x4d00/*右移-方向键right*/#define PLAY2DO 0x1c0d/*落子-回车键Enter*/*若想在游戏中途退出, 可按 Esc 键*/#define ESCAPE 0x011b/*定义棋盘上交叉点的状态, 即该点有无棋子 */*若有棋子, 还应能指出是哪个玩家的棋子 */#define CHESSNULL 0 /*没有棋子*/#define CHESS1 O/*一号玩家的棋子*/#define CHESS2 X/*二号玩家的棋子*/*定义按键类别*/#define KEYEXIT 0/*退出

19、键*/#define KEYFALLCHESS 1/*落子键*/#define KEYMOVECURSOR 2/*光标移动键*/#define KEYINVALID 3/*无效键*/*定义符号常量: 真, 假 - 真为1, 假为0 */#define TRUE 1#define FALSE 0/*/* 定义数据结构 */*棋盘交叉点坐标的数据结构*/struct point int x,y;/*/*自定义函数原型说明 */void Init(void);int GetKey(void);int CheckKey(int press);int ChangeOrder(void);int Ches

20、sGo(int Order,struct point Cursor);void DoError(void);void DoOK(void);void DoWin(int Order);void MoveCursor(int Order,int press);void DrawCross(int x,int y);void DrawMap(void);int JudgeWin(int Order,struct point Cursor);int JudgeWinLine(int Order,struct point Cursor,int direction);void ShowOrderMsg(

21、int Order);void EndGame(void);/*/*/* 定义全局变量 */int gPlayOrder; /*指示当前行棋方 */struct point gCursor; /*光标在棋盘上的位置 */char gChessBoard1919;/*用于记录棋盘上各点的状态*/*/*/*主函数*/void main() int press; int bOutWhile=FALSE;/*退出循环标志*/ Init();/*初始化图象，数据*/ while(1) press=GetKey();/*获取用户的按键值*/ switch(CheckKey(press)/*判断按键类别*/

22、 /*是退出键*/ case KEYEXIT: clrscr();/*清屏*/ bOutWhile = TRUE; break; /*是落子键*/ case KEYFALLCHESS: if(ChessGo(gPlayOrder,gCursor)=FALSE)/*走棋*/ DoError();/*落子错误*/ else DoOK();/*落子正确*/ /*如果当前行棋方赢棋*/ if(JudgeWin(gPlayOrder,gCursor)=TRUE) DoWin(gPlayOrder); bOutWhile = TRUE;/*退出循环标志置为真*/ /*否则*/ else /*交换行棋方*/

23、 ChangeOrder(); ShowOrderMsg(gPlayOrder); break; /*是光标移动键*/ case KEYMOVECURSOR: MoveCursor(gPlayOrder,press); break; /*是无效键*/ case KEYINVALID: break; if(bOutWhile=TRUE) break; /*游戏结束*/ EndGame();/*/*界面初始化，数据初始化*/void Init(void) int i,j; char *Msg= Player1 key:, UP-w, DOWN-s, LEFT-a, RIGHT-d, DO-spac

24、e, , Player2 key:, UP-up, DOWN-down, LEFT-left, RIGHT-right, DO-ENTER, , exit game:, ESC, NULL, ; /* 先手方为1号玩家 */ gPlayOrder = CHESS1; /* 棋盘数据清零, 即棋盘上各点开始的时候都没有棋子 */ for(i=0;i19;i+) for(j=0;j19;j+) gChessBoardij=CHESSNULL; /*光标初始位置*/ gCursor.x=gCursor.y=0; /*画棋盘*/ textmode(C40); DrawMap(); /*显示操作键说明*

25、/ i=0; textcolor(BROWN); while(Msgi!=NULL) gotoxy(25,3+i); cputs(Msgi); i+; /*显示当前行棋方*/ ShowOrderMsg(gPlayOrder); /*光标移至棋盘的左上角点处*/ gotoxy(gCursor.x+MAPXOFT,gCursor.y+MAPYOFT);/*画棋盘*/void DrawMap(void) int i,j; clrscr(); for(i=0;i19;i+) for(j=0;j19;j+) DrawCross(i,j);/*画棋盘上的交叉点*/void DrawCross(int x,

26、int y) gotoxy(x+MAPXOFT,y+MAPYOFT); /*交叉点上是一号玩家的棋子*/ if(gChessBoardxy=CHESS1) textcolor(LIGHTBLUE); putch(CHESS1); return; /*交叉点上是二号玩家的棋子*/ if(gChessBoardxy=CHESS2) textcolor(LIGHTBLUE); putch(CHESS2); return; textcolor(GREEN); /*左上角交叉点*/ if(x=0&y=0) putch(CROSSLU); return; /*左下角交叉点*/ if(x=0&y=18) p

27、utch(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; /*棋盘中间的交叉点

28、*/ putch(CROSS);/*交换行棋方*/int ChangeOrder(void) if(gPlayOrder=CHESS1) gPlayOrder=CHESS2; else gPlayOrder=CHESS1; return(gPlayOrder);/*获取按键值*/int GetKey(void) char lowbyte; int press; while (bioskey(1) = 0) ;/*如果用户没有按键，空循环*/ press=bioskey(0); lowbyte=press&0xff; press=press&0xff00 + toupper(lowbyte);

29、return(press);/*落子错误处理*/void DoError(void) sound(1200); delay(50); nosound();/*赢棋处理*/void DoWin(int Order) 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); delay(50); nosound(); te

30、xtcolor(RED+BLINK); gotoxy(25,20); if(Order=CHESS1) cputs(PLAYER1 WIN!); else cputs(PLAYER2 WIN!); gotoxy(25,21); cputs(n); getch();/*走棋*/int ChessGo(int Order,struct point Cursor) /*判断交叉点上有无棋子*/ if(gChessBoardCursor.xCursor.y=CHESSNULL) /*若没有棋子, 则可以落子*/ gotoxy(Cursor.x+MAPXOFT,Cursor.y+MAPYOFT); te

31、xtcolor(LIGHTBLUE); putch(Order); gotoxy(Cursor.x+MAPXOFT,Cursor.y+MAPYOFT); gChessBoardCursor.xCursor.y=Order; return TRUE; else return FALSE;/*判断当前行棋方落子后是否赢棋*/int JudgeWin(int Order,struct point Cursor) int i; for(i=0;i4;i+) /*判断在指定方向上是否有连续5个行棋方的棋子*/ if(JudgeWinLine(Order,Cursor,i) return TRUE; re

32、turn FALSE;/*判断在指定方向上是否有连续5个行棋方的棋子*/int JudgeWinLine(int Order,struct point Cursor,int direction) int i; struct point pos,dpos; const int testnum = 5; int count; switch(direction) case 0:/*在水平方向*/ pos.x=Cursor.x-(testnum-1); pos.y=Cursor.y; dpos.x=1; dpos.y=0; break; case 1:/*在垂直方向*/ pos.x=Cursor.x;

33、 pos.y=Cursor.y-(testnum-1); dpos.x=0; dpos.y=1; break; case 2:/*在左下至右上的斜方向*/ pos.x=Cursor.x-(testnum-1); pos.y=Cursor.y+(testnum-1); dpos.x=1; dpos.y=-1; break; case 3:/*在左上至右下的斜方向*/ pos.x=Cursor.x-(testnum-1); pos.y=Cursor.y-(testnum-1); dpos.x=1; dpos.y=1; break; count=0; for(i=0;itestnum*2+1;i+)

34、/*?i=0&pos.x=0&pos.y=testnum) return TRUE; else count=0; pos.x+=dpos.x; pos.y+=dpos.y; return FALSE;/*移动光标*/void MoveCursor(int Order,int press) switch(press) case PLAY1UP: if(Order=CHESS1&gCursor.y0) gCursor.y-; break; case PLAY1DOWN: if(Order=CHESS1&gCursor.y0) gCursor.x-; break; case PLAY1RIGHT:

35、if(Order=CHESS1&gCursor.x0) gCursor.y-; break; case PLAY2DOWN: if(Order=CHESS2&gCursor.y0) gCursor.x-; break; case PLAY2RIGHT: if(Order=CHESS2&gCursor.x18) gCursor.x+; break; gotoxy(gCursor.x+MAPXOFT,gCursor.y+MAPYOFT);/*游戏结束处理*/void EndGame(void) textmode(C80);/*显示当前行棋方*/void ShowOrderMsg(int Order

36、) gotoxy(6,MAPYOFT+20); textcolor(LIGHTRED); if(Order=CHESS1) cputs(Player1 go!); else cputs(Player2 go!); gotoxy(gCursor.x+MAPXOFT,gCursor.y+MAPYOFT);/*落子正确处理*/void DoOK(void) sound(500); delay(70); sound(600); delay(50); sound(1000); delay(100); nosound();/*检查用户的按键类别*/int CheckKey(int press) if(press=ESCAPE) return KEYEXIT;/*是退出键*/ else if ( ( press=PLAY1DO & gPlayOrder=CHESS1) | ( press=PLAY2DO & gPlayOrder=CHESS2) ) return KEYFALLCHESS;/*是落子键*/ else if ( press=P