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

姓 名： 刘旭
学 院： 计算机与通信学院
班 级： 通信工程101班
指导老师： 文志诚

目录
一、需求分析 3
1.1 开发背景 3
2.2 功能简介 3
二、系统设计 4
2.1 函数一览 4
2.2 “封面”的设计 4
2.3 二维数组与控制台 5
2.4 键盘操作 6
2.5判定 7
2.6 悔棋的实现 8
三、调试运行 9
3.1 进入界面 9
3.2 棋盘的初始状态 10
3.3 激战中…… 10
3.4 游戏结束 11
四、解决问题的关键 11
五、课设总结 11
六、附录 12
6.1 画图代码 12
6.2 初始化 14
6.3 Play函数 14
一、需求分析
1.1 开发背景
学习了数据结构该门课程，对于枯燥无味的理论知识，我们是否能够通过所学的知识在课程设计中做出有趣味东西，然后让我们对于数据结构更加的感兴趣呢？于是我和我的室友陈明建开始酝酿着写些什么东西。上个学期就已经写了通讯录那之类的链式结构，这次我们决心有所改变，我们学习了栈、队列、树、图，字典树有人选了，我们就来写一个基于图的小程序，五子棋，对，图的简单应用，于是我们开始着手来写这个小小的程序，祝我们好运！

2.2 功能简介
既然是五子棋，我们要做的是时时刻刻的将整个图（以下称为棋局）的状态呈现出来，那么界面就是必不可少的。MFC不会？没关系，我们就用基于控制台的字符输出来构建这个棋局吧，当然这只是第一步，详细如下：
拥有一个良好的进入界面，以及必要的选项；
拥有一个二维的数组来记录和更新实时的状态，并且能够有一种方法在DOS界面下绘制出整个棋局的实时状态（包括棋盘和棋子）；
能够通过键盘上的按键完成所选位置的移动和选定操作；
能够在每一次的走棋后判定是否游戏结束（棋盘走满或者是一方胜出）；
能够完成悔棋的功能，并保证这之间的棋局绘图能够与二维数组数据同步，做到真正意义上的悔棋。
二、详细设计
2.1 函数一览

2.2 “封面”的设计
首先还是讲些题外话，该程序由于与控制台有密切的关系，于是在代码中使用了不少 conio.h 中的函数，当然在显示时又使用了windows.h 中的 Sleep( )函数，正是有了这些函数的使用，程序才得以顺利完成，尤其是后面频繁使用的gotoxy( ) 函数。
进入正题，由于是一个小的程序，因此将每一个功能分成一个一个的函数，这样将在以后的修改和完成进度上都有很大的帮助。由上面的函数一览可以知道这个“封面”就是在Logo( ) 函数里面实现的，函数实现过程中使用了Sleep( )函数，使之有动态效果：
void Logo( )
{
char Wel[30]= { "Made By Lyush&& Mirs Chen" };
printf( "\t\t\t 欢迎试用五子棋系统\n" );
printf( "\t\t " );
for( int i= 0; i< strlen( Wel ); ++i )
{
putchar( Wel[i] );
Sleep( 200 ); // 可使字符一个一个的输出
}
putchar( 10 ); // 换行对应的 ASCII 码值为十进制的 10
}
2.3 二维数组与控制台
二维数组是用来使得整个棋盘的信息全部记录下来，因此在结构体中二维数组的声明是最关键的。
struct
{
int Status[MAX/2+2][MAX/2+2];
int MINBOX;
int Step;
char Graph[3][3];
char *FillGraph[9];
Sta Stack;
} ChessBoard;

声明全局变量是为了使得各函数能够更方便地使用到这个结构体，现假设某点的坐标为( 1, 1 )，那么如何在屏幕上打印这个点呢？这就利用到了ChangeCoordinates( )与gotoxy( ) 函数，前者使坐标进行转换，后者让光标走到所指的那个点，其实主要还是因为类似“┣、╋、●、○”在横向上所占都是两个英文字母的距离，因此在控制台上反映的就是和数组下标倍数关系了。部分代码如下：
HANDLE hConsole= GetStdHandle( STD_OUTPUT_HANDLE );

void ChangeCoordinates( int _X, int _Y, int *X, int *Y )
{
*X= ( _X- 1 )* 2
*Y= ( _Y- 1 )* 4;
}

void gotoxy( int x, int y ) //这是光标的函数
{
COORD coord;
coord.Y= x; // 在实际的应用过程中发现交换x与y的赋值
coord.X= y; // 更好理解，即横行位x，纵行为y。
SetConsoleCursorPosition( hConsole, coord );
}
2.4 键盘操作
在刚开始写这个五子棋的时候是以坐标来确定玩家的每一步棋，但后来发现这样操作性实在是差，键盘操作是更好的选择。这里又要用到一个函数 getch( ),其作用是无回显的接受从键盘输入的字符，让屏幕不会出现你输入的字符且等待着按回车确定……
有了这个宝贝函数，马上得到 “↑” 对应的ASCII码为 -32和72 两个连着的数值，依次可得其他对应的ASCII码。 后面在使玩家一和玩家二分离操作，玩家一则是利用 W、S、A、D + space来操作， 玩家二则是 上下左右+ enter。配合ChangeCoordinates( )与gotoxy( ) 函数，完成对走棋的控制。部分代码如下：
if( Opreat[0]== 13&& Ply== 2|| Opreat[0]== 32&& Ply== 1 )
{
if( ChessBoard.Status[Move_X][Move_Y]== 0 )
{
int TTop= ++ChessBoard.Stack.Top;
ChessBoard.Status[Move_X][Move_Y]= Ply;
ChessBoard.Stack.Record[TTop][0]= Move_X;
ChessBoard.Stack.Record[TTop][1]= Move_Y;
printf( "%s", Graph );
return true; // 该次走棋操作有效
}
else { … }
}
if( Opreat[0]== -32&& Opreat[1]== 72|| Opreat[0]== 'w'|| Opreat[0]== 'W' )
{// 凡是接受了“上操作”，则Move_X的值减一，
if( Currect( Move_X- 1, Move_Y ) )
{
Move_X-= 1;
}
}
else if( … )
{
…
}
// 这是接下来的转换操作
ChangeCoordinates( Move_X, Move_Y, &Temp_X, &Temp_Y );
Gotoxy( Temp_X, Temp_Y );
2.5判定
对于每次走棋后，首先应该做的就是判定一否有五个棋子已经连成一线，也是一个简单的搜索过程，由于每次走的点不一定是最外部的点，因此从每次走的点的两头同时搜索，当遇到两端同时结束时，搜索结束。当满足五子时游戏结束。当然，当棋盘被走满时，游戏亦结束。代码如下：
bool Legal( int Point )
{
if( Point< 1|| Point> MAX/ 2+ 1 )
return false;
else
return true;
}

//搜索45度角是否为满足ChessBoard.MINBOX 以X正轴为参考轴
if( !Flag )
{
Count= 1;
for( int i1= X- 1, j1= Y+ 1, i2= X+ 1, j2= Y- 1 ; Legal( i1 )&& Legal( j1 )|| Legal( i2 )&& Legal( j2 ) ; i1--, j1++, i2++, j2-- )
{
int LastCount= Count;
if( Legal( i1 )&& Legal( j1 )&& ChessBoard.Status[i1][j1]== Ply )
{
Count++;
}
if( Legal( i2 )&& Legal( j2 )&& ChessBoard.Status[i2][j2]== Ply )
{
Count++;
}
if( LastCount== Count )
break;
if( Count== ChessBoard.MINBOX )
{
Flag= 1;
return true;
}
}
}
2.6 悔棋的实现
虽说下棋悔棋是一种不道义的行为，但是如果双方约定好了，未尝不可。在没写悔棋之前，只是记录了“上一次”的位置，声明了Last_X， Last_Y; 当然既然要求悔棋，那么直接调用栈顶元素，即可定位上次走棋的位置。那么悔棋呢，取出“上一次”的位置，判定位置（不同的位置对应不同的填充图形类型）在二维数组中撤销走棋时所赋予的 Ply 值（玩家一走时，其值为1，玩家二走时，其值为2），重新将 ChessBoard.Status[ Last_X ][ Last_Y ] 赋为0。代码如下：

int GetFillType( int X, int Y )
{
if( X== 1 )
{
if( Y== 1 )
return 0;
else if( Y== 16 )
return 2;
else
return 1;
}
else if( X== 16 )
{
if( Y== 1 )
return 6;
else if( Y== 16 )
return 8;
else
return 7;
}
else
{
if( Y== 1 )
return 3;
else if( Y== 16 )
return 5;
else
return 4;
}
}

bool Retract( int *X, int *Y )
{
int Temp_X, Temp_Y, TTop, FillType;
if( !StackEmpty( ) )
{
TTop= ChessBoard.Stack.Top--;
*X= ChessBoard.Stack.Record[TTop][0];
*Y= ChessBoard.Stack.Record[TTop][1];
ChessBoard.Status[*X][*Y]= 0;// 将该点置为真正意义上的空点
FillType= GetFillType( *X, *Y );
ChangeCoordinates( *X, *Y, &Temp_X, &Temp_Y );
Gotoxy( Temp_X, Temp_Y );
printf( "%s", ChessBoard.FillGraph[FillType] );
return true;
}
else
{
Gotoxy( 9, 65 );
printf( "您已不能悔棋" );
Sleep( 300 );
Gotoxy( 9, 65 );
printf( " " );
return false;
}
}

三、调试运行
3.1 进入界面

3.2 棋盘的初始状态

3.3 激战中……

3.4 游戏结束

四、解决问题的关键

这个五子棋的程序并没有什么复杂的算法，只是利用了简单的图知识和一个栈的应用，在这里主要的关键问题就是如何将程序有条理的写下来，有一个好的逻辑思维。将程序分成了多个功能函数，尽量的让一个函数的功能单一，只是在内部调用了其他的函数以辅助改函数功能的实现，比如判定坐标是否越界，坐标是否合法，悔棋的点的位置状态…… 这样便能做到各个击破，程序的形成也就变得畅通许多了。

五、课设总结

刚开始写这个程序，认为一定要用到 graphics.h, 无奈电脑TC不兼容，因此只好强行来画这个界面了，使用输入法里面的制表符，效果还不错，通过一长串的if … else … 最好还是画出来了，这个时候觉得控制台的简单图形还是能够画出来的，并且可以尽量去美化它的界面。后面的附录中将给出画棋盘和棋子的源代码。在程序设计的过程中，尤其是为源程序加上悔棋的功能，这期间总是有许多意想不到的错误，比如加上后，有时走了5个连子棋，但是程序并没有判定输赢，而是可以继续走、有时没有五个却已经结束了，光标没有复位，悔棋后，玩家的走棋顺序没有跟着改变……通过后来的一步步修改终于使得这些问题都一一解决了，比如说对 Prompt（ 提示 ） 函数引进了返回值，判断该次操作是否成功，如果下了棋则为 true， 如果是悔棋就是 false 了，这样便使得后面的操作更规范了和统一了。

六、附录
#include
#include
#include
#include
#include
#include
#include
#define MAX 31
#define STA_1 1
#define STA_2 2
#define STA_0 0

HANDLE hConsole= GetStdHandle( STD_OUTPUT_HANDLE );

void HideCursor( )
{
CONSOLE_CURSOR_INFO cursor_info = {1, 0};
SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &cursor_info);
}

typedef struct
{
int Record[260][2];
int Base;
int Top;
} Sta;

struct
{
int Status[MAX/2+2][MAX/2+2];
int MINBOX;
int Step;
char Graph[3][3];
char *FillGraph[9];
Sta Stack;
} ChessBoard;

void Gotoxy( int x, int y ) //这是光标的函数
{
COORD coord;
coord.Y= x;
coord.X= y;
SetConsoleCursorPosition( hConsole, coord );
}

void Logo( )
{
char Wel[30]= { "Made By Lyush&& Mirs Chen" };

printf( "\t\t\t 欢迎试用五子棋系统\n" );
printf( "\t\t " );
for( int i= 0; i< strlen( Wel ); ++i )
{
putchar( Wel[i] );
Sleep( 200 );
}
putchar( 10 );
}

int Login( )
{
int Mode, Skip= 0;
char Request;
if( !Skip )
{
printf( "\n\n在这儿你能DIY( Do it youself! )你的棋子，每个棋子接受一个汉字" );
printf( " Y Orz N\n" );
scanf( "%c", &Request );
if( Request== 'Y'|| Request== 'y' )
{
printf( "玩家一的 DIY 棋子 -->" );
scanf( "%s", ChessBoard.Graph[1] );
ChessBoard.Graph[1][2]= '\0';
printf( "玩家二的 DIY 棋子 -->" );
scanf( "%s", ChessBoard.Graph[2] );
ChessBoard.Graph[2][2]= '\0';
}
}
printf( "\n\n请选择先手玩家:___ \n\n");
printf( "\n\n\t\t\t\t\t\t1 对应 玩家一 2 对应 玩家二\n" );
if( Request== 'Y'|| Request== 'y' )
Gotoxy( 10, 16 ); //原函数是 第一个参数为列，后一个参数为行，把Gotoxy函数做了更改
else
Gotoxy( 8, 16 );
scanf( "%d", &Mode );
if( Mode!= 1&& Mode!= 2 )
return Mode% 2+ 1;
else
return Mode;
}

void InitChessBiard( )
{
int TTop= ChessBoard.Stack.Top;
fflush( stdin );
ChessBoard.Step= 0;
ChessBoard.Stack.Top= 0;
ChessBoard.Stack.Base= 0;
ChessBoard.Stack.Record[TTop][0]= 8; // 栈的0号位存储初始化的棋盘位置
ChessBoard.Stack.Record[TTop][1]= 8;
ChessBoard.MINBOX= 5;
ChessBoard.FillGraph[0]="┏";
ChessBoard.FillGraph[1]="┳"
ChessBoard.FillGraph[2]="┓";
ChessBoard.FillGraph[3]="┣";
ChessBoard.FillGraph[4]="╋";
ChessBoard.FillGraph[5]="┫";
ChessBoard.FillGraph[6]="┗";
ChessBoard.FillGraph[7]="┻";
ChessBoard.FillGraph[8]="┛";
strcpy( ChessBoard.Graph[1], "○" );
strcpy( ChessBoard.Graph[2], "●" );
memset( ChessBoard.Status, 0, sizeof( ChessBoard.Status ) );
}

bool Legal( int Point )
{
if( Point< 1|| Point> MAX/ 2+ 1 )
return false;
else
return true;
}

bool Currect( int X, int Y )
{
if( Legal( X )&& Legal( Y ) )
return true;
else
return false;
}

void ChangeCoordinates( int _X, int _Y, int *X, int *Y )
{
*X= ( _X- 1 )* 2;
*Y= ( _Y- 1 )* 4;
}

void Draw( )
{
// 画棋盘
for( int i= 1; i<= MAX; ++i )
{
for( int j= 1; j<=MAX; ++j )
{
if i== 1 )
{
if( j== 1 )
printf( "┏" );
else if( j== MAX )
printf( "┓\n" );
else if( j%2 )
printf( "┳" ); // 横向占两个坐标位，竖向占一个坐标位
else
printf( "━" );
}
else if( i== MAX )
{
if( j== 1 )
printf( "┗" );
else if( j== MAX )
printf( "┛\n" );
else if( j%2 )
printf( "┻" );
else
printf( "━" );
}
else
{
if( j== 1 )
{
if( i% 2 )
printf( "┣" );
else
printf( "┃" );
}
else if( j== MAX )
{
if( i% 2 )
printf( "┫\n" );
else
printf( "┃\n" );
}
else
{
if( i% 2 )
{
if( j% 2 )
printf( "╋" );
else
printf( "━" );
}
else
{
if( j% 2 )
printf( "┃" );
else
printf( " " );
}
}
}
}
}
// 画棋子
for( int i= 1; i<= MAX/ 2+ 1; ++i )
{
for( int j= 1; j<= MAX/ 2+ 1; ++j )
{
int Temp_X, Temp_Y;
ChangeCoordinates( i, j, &Temp_X, &Temp_Y );
if( ChessBoard.Status[i][j]== 1 )
{
Gotoxy( Temp_X, Temp_Y );
printf( "○" );
}
else if( ChessBoard.Status[i][j]== 2 )
{
Gotoxy( Temp_X, Temp_Y );
printf( "●" );
}
}
}
}

int GetFillType( int X, int Y )
{
if( X== 1 )
{
if( Y== 1 )
return 0;
else if( Y== 16 )
return 2;
else
return 1;
}
else if( X== 16 )
{
if( Y== 1 )
return 6;
else if( Y== 16 )
return 8;
else
return 7;
}
else
{
if( Y== 1 )
return 3;
else if( Y== 16 )
return 5;
else
return 4;
}
}

bool StackEmpty( )
{
if( ChessBoard.Stack.Top== ChessBoard.Stack.Base )
return true;
else
return false;
}

bool Retract( int *X, int *Y )
{
int Temp_X, Temp_Y, TTop, FillType;
if( !StackEmpty( ) )
{
TTop= ChessBoard.Stack.Top--;
*X= ChessBoard.Stack.Record[TTop][0];
*Y= ChessBoard.Stack.Record[TTop][1];
ChessBoard.Status[*X][*Y]= 0;// 将该点置为真正意义上的空点
FillType= GetFillType( *X, *Y );
ChangeCoordinates( *X, *Y, &Temp_X, &Temp_Y );
Gotoxy( Temp_X, Temp_Y );
printf( "%s", ChessBoard.FillGraph[FillType] );
return true;
}
else
{
Gotoxy( 9, 65 );
printf( "您已不能悔棋" );
Sleep( 300 );
Gotoxy( 9, 65 );
printf( " " );
return false;
}
}

bool Prompt( int Ply, int Last_X, int Last_Y )
{
int Move_X= Last_X, Move_Y= Last_Y;
int Temp_X, Temp_Y;
char Opreat[2];
char *Graph= ChessBoard.Graph[Ply];
Gotoxy( 1, 65 );
printf( "按退格键悔棋" );
Gotoxy( 3, 65 );
if( Ply== 1 )
{
printf( "玩家一走棋：" );
Gotoxy( 5, 65 );
printf( "通过w s a d" );
}
else
{
printf( "玩家二走棋：" );
Gotoxy( 5, 65 );
printf( "通过↑↓←→" );
}
Gotoxy( 7, 65 );
printf( "按空格或回车" );
ChangeCoordinates( Move_X, Move_Y, &Temp_X, &Temp_Y );
Gotoxy( Temp_X, Temp_Y );
while( 1 )
{
Opreat[0]= getch( );
if( Opreat[0]== 8 )
{
if( Retract( &Move_X, &Move_Y ) )
return false; // 该次操作为伪操作
else
{
Gotoxy( Temp_X, Temp_Y );
continue;
}
}
else
{
if( Opreat[0]== 13&& Ply== 2|| Opreat[0]== 32&& Ply== 1 )
{
if( ChessBoard.Status[Move_X][Move_Y]== 0 )
{
int TTop= ++ChessBoard.Stack.Top;
ChessBoard.Status[Move_X][Move_Y]= Ply;
ChessBoard.Stack.Record[TTop][0]= Move_X;
ChessBoard.Stack.Record[TTop][1]= Move_Y;
printf( "%s", Graph );
return true; // 该次走棋操作有效
}
else
{
Gotoxy( 9, 65 );
printf( "此步无效" );
Sleep( 300 );
Gotoxy( 9, 65 );
printf( " " );
Gotoxy( Temp_X, Temp_Y );
continue;
}