数据结构中国象棋实验报告

《数据结构中国象棋实验报告》由会员分享，可在线阅读，更多相关《数据结构中国象棋实验报告（43页珍藏版）》请在装配图网上搜索。

1、数据结构课程设计报告中国象棋姓名：林泽全学号：091402116班级：09网络工程一、 问题描述1. 象棋概述象棋，又称中国象棋（英文现译作chess）。在中国有着悠久的历史，属于二人对抗性游戏的一种，由于用具简单，趣味性强，成为流行极为广泛的棋艺活动。中国象棋是我国正式开展的78个体育运动项目之一，为促进该项目在世界范围内的普及和推广，现将“中国象棋”项目名称更改为“象棋”。此外，高材质的象棋也具有收藏价值，如：高档木材、玉石等为材料的象棋。更有文人墨客为象棋谱写了诗篇，使象棋更具有一种文化色彩。2. 棋子的初始棋位整个棋盘以“河界”分为相等的两部分。为了比赛记录和学习棋谱方便起见，现行规则

2、规定：按九条竖线从右至左用中文数字一至九来表示红方的每条竖线，用阿拉伯数字1只至9来表示黑方的每条竖线。己方的棋子始终使用己方的线路编号，无论棋子是否“过河”。对弈开始之前，红黑双方应该把棋子摆放在规定的位置。任何棋子每走一步，进就写“进”，退就写“退”，如果像车一样横着走，就写“平”。3. 象棋棋子象棋是一种双方对阵的竞技项目。棋子共有三十二个，分为红黑两组，各有十六个，由对弈的双方各执一组。棋子种类说明如下表：红方名称黑方名称每方棋子数可以到达的范围帅将1己方九宫内车车2全盘任何位置炮炮2全盘任何位置马马2全盘任何位置相象2己方区域内（实际上是7个特殊棋位）仕士2己方九宫内（实际上是5个特

3、殊棋位）兵卒5起始位置及向前一步的位置，敌方所有棋位帅与将；仕与士；相与象；兵与卒的作用完全相同，仅仅是为了区别红棋和黑棋而已。4. 棋子的走法 帅（将） 帅（将）是棋中的首脑，是双方竭力争夺的目标。它只能在九宫之内活动，可上可下，可左可右，每次走动只能按竖线或横线走动一格。帅与将不能在同一直线上直接对面，否则走方判负。 仕（士） 仕（士）是将（帅）的贴身保镖，它也只能在九宫内走动。它的行棋路径只有九宫内的斜线。 相（象） 相（象）的主要作用是防守，保护自己的帅（将）。它的走法是每次循对角线走两格，俗称“象飞田”。相（象）的活动范围限于河界以内的本方阵地，不能过河，且如果它走的田字中央有一个棋

4、子，就不能走，俗称“塞象眼”。 车 车在象棋中威力最大，无论横线、竖线均可行走，只要无子阻拦，步数不受限制。因此，一车可以控制十七个点，故有“一车十子寒”之称。 炮（炮） 炮（炮）在不吃子的时候，移动与车完全相同。当吃子时，己方和对方的棋子中间必须间隔1个棋子（无论对方或己方棋子），炮是象棋中唯一可以越子的棋种。 马 马走动的方法是一直一斜，即先横着或直着走一格，然后再斜着走一个对角线，俗称“马走日”。马一次可走的选择点可以达到四周的八个点，故有八面威风之说。如果在要去的方向有别的棋子挡住，马就无法走过去，俗称“蹩马腿”。 兵（卒） 兵（卒）在未过河前，只能向前一步步走，过河以后，除不能后退外

5、，允许左右移动，但也只能一次一步，即使这样，兵（卒）的威力也大大增强，故有“过河的卒子顶半个车”之说。5. 胜负的判定1) 当棋局中出现一下情况判负，对方取胜：a. 帅（将）被“将死”另一方走一步棋之后试图吃掉一方的帅（将），但该方的帅（将）却不能躲避；b. 困毙轮到一方行棋，但按规定，己方无棋可走；c. 由于子力悬殊，继续抵抗毫无意义的主动认输；d. 长打（即长捉、长将、长杀、或一将一要杀）的一方通常判负；e. 行棋违规、违纪、超时等情况判负。2) 当棋局中出现一下情况作和：a. 双方理论上无法取胜的简单局面；b. 符合“六十回合规定”从任意一步开始，六十回合内双方均无损失一子；c. 一方提

6、和，另一方同意和棋；d. 长跟、长兑、长拦、长献、一捉一闲、或一将一闲，循环三回合后可判和。6. 棋子的子力价值 车：象棋中实力最强的棋子，由于可以在棋盘线上飞快的移动，不论吃子与移动都十分方便，因此在全盘的价值都很高，其实力相当于双马、双炮、马炮，为其评估10分。其近、中、远程作战都适用。 炮：由于其“炮打隔子”因此中远程作战，其多用于牵制，和各子（主要是车）配合都很容易。在残局要依靠仕相的力量攻守（俗称“残局炮还家”）。开、中局由于子多，他的“炮架子”也多，实力略高于马，此时为他打5分。残局“炮架子”少，实力也相应减弱，但其依靠仕相防守力强于马（如单车可胜马双仕却难胜炮双仕），因此“求和易

7、留炮”，此时为其打4.5分。 其实力等于一马、双仕、双相、一仕一相。 马：中距离作战兵器。与炮相反，由于“蹩腿”，子力少时，实力较炮强。由于此性质，它易往开阔处跳，戍边反而不利。其实力相当于一炮、双相、双仕、一仕一相。 兵（卒）：开局时由于只能向前，几乎无攻击力，但有限疏通我方马路兼限制敌方马路的作用，为其打0.5分。过河后可以转弯，当靠近敌方九宫时威力大增，故有“小兵过河顶大车”、“过河卒子半个车”等说法。残局时，双方子力较少，兵的作用显现出来，过河的高兵，价值倍增为其打3分；低兵价值2分；因为底兵只对一楼的老将有威胁，所以底兵价值1分。过河的兵相当于一仕、一相。注意兵轻易不要沉底。 仕（士

8、）、相（象）：属于防守的棋子，一仕等于一相。开局阶段，老将不易受攻击为其打2分，正因为如此，开局人们不爱用马（炮）兑仕相。中、残局时矛头直指老将，此时急需仕相守卫，同时仕相还可配合炮攻防或走闲着以防困毙，因此不占便宜就不要轻易丢弃仕相，此时为其打3分。切记：缺仕宜兑车，缺相宜兑炮。花士象可防车，中联仕相可防炮。仕相宜中联，相不轻易散边。 帅（将）：全盘棋子争夺的目标，需要我方棋子保护。开局时不宜乱动免得自找麻烦。中、残局安全时可出帅助攻，如“铁门栓”。二、 基本要求程序的用户作为玩者的角色，计算机是对手。计算机可以实现简单地人机对战。三、 工具/准备工作需要一台计算机，其中安装有Visual

9、C+ 6.0集成开发环境软件。四、 分析与实现 首先是根据中国象棋的走法，规定各个棋子的走法。其具体实现方法用函数CanGo实现，BOOL CanGo(int manmap1112, int man, const POINT &from, const POINT &to)static int i, j;if(!IsNormal(ManToTypeman, to)/这个棋子不能放在目标位置/如果不是将/帅（将/帅可以“照相”）if(ManToTypeman!=RED_K & ManToTypeman!=BLACK_K)return FALSE;else if(ManToTypeman=RED_K

10、 &/走的是帅ManToTypemanmapto.xto.y=BLACK_K)/目标是将BOOL flag = FALSE;for(j=from.y-1; j0; j-)if(manmapfrom.xj!=32)if(ManToTypemanmapfrom.xj=BLACK_K)/照相flag = TRUE;break;if(flag)return TRUE;elsereturn FALSE;else if(ManToTypemanmapto.xto.y=RED_K)/走的是将，目标是帅BOOL flag = FALSE;for(j=from.y+1; jfrom.y)return FALSE

11、;/兵只走一步直线if(from.y-to.y+abs(to.x-from.x)1)return FALSE;break;case BLACK_B:/卒不回头if(to.y1)return FALSE;break;case RED_S:case BLACK_S:/士走斜线一步if(abs(from.y-to.y)1 | abs(to.x-from.x)1)return FALSE;break;case RED_X:case BLACK_X:/象走田if(abs(from.x-to.x)!=2 | abs(from.y-to.y)!=2)return FALSE;/象心if(manmap(fro

12、m.x+to.x)/2(from.y+to.y)/2!=32)return FALSE;break;case RED_K:case BLACK_K:/将帅只走一步直线if(abs(from.y-to.y)+abs(to.x-from.x)1)return FALSE;break;case RED_J:case BLACK_J:/车只能走直线if(from.y!=to.y & from.x!=to.x)return FALSE;/车经过的路线不能有棋子if(from.y=to.y)if(from.xto.x)for(i=from.x+1; ito.x; i+)if(manmapifrom.y!=

13、32)return FALSE;elsefor(i=to.x+1; ifrom.x; i+)if(manmapifrom.y!=32)return FALSE;elseif(from.yto.y)for(j=from.y+1; jto.y; j+)if(manmapfrom.xj!=32)return FALSE;elsefor(j=to.y+1; jfrom.y; j+)if(manmapfrom.xj!=32)return FALSE;break;case RED_P:case BLACK_P:/炮只能走直线if(from.y!=to.y & from.x!=to.x)return FAL

14、SE;/炮不吃子时经过的路线不能有棋子if(manmapto.xto.y=32)if(from.y=to.y)if(from.xto.x)for(i=from.x+1; ito.x; i+)if(manmapifrom.y!=32)return FALSE;elsefor(i=to.x+1; ifrom.x; i+)if(manmapifrom.y!=32)return FALSE;elseif(from.yto.y)for(j=from.y+1; jto.y; j+)if(manmapfrom.xj!=32)return FALSE;elsefor(j=to.y+1; jfrom.y; j+

15、)if(manmapfrom.xj!=32)return FALSE;else/吃子时int count = 0;if(from.y=to.y)if(from.xto.x)for(i=from.x+1; ito.x; i+)if(manmapifrom.y!=32)count+;if(count!=1)return FALSE;elsefor(i=to.x+1; ifrom.x; i+)if(manmapifrom.y!=32)count+;if(count!=1)return FALSE;elseif(from.yto.y)for(j=from.y+1; jto.y; j+)if(manma

16、pfrom.xj!=32)count+;if(count!=1)return FALSE;elsefor(j=to.y+1; jfrom.y; j+)if(manmapfrom.xj!=32)count+;if(count!=1)return FALSE;break;case RED_M:case BLACK_M:/马走日if(!(abs(to.x-from.x)=1 & abs(to.y-from.y)=2)|(abs(to.x-from.x)=2 & abs(to.y-from.y)=1)return FALSE;/找马脚if(to.x-from.x=2)i=from.x+1; j=fro

17、m.y;else if(from.x-to.x=2)i=from.x-1; j=from.y;else if(to.y-from.y=2)i=from.x; j=from.y+1;else if(from.y-to.y=2)i=from.x; j=from.y-1;/绊马脚if(manmapij!=32)return FALSE;break;default:break;return TRUE; 判断棋子的位置是不是合法，用函数IsNormal实现。具体是实现如下：BOOL IsNormal(const int &mantype, const POINT &point)if(point.x9 |

18、 point.y10)return FALSE;switch(mantype)case RED_K:/帅不能在红方宫外if(point.x6 | point.x4 |point.y7) return FALSE;/兵过河前不能左右移动if(point.y5 & point.x%2=0)return FALSE;break;case BLACK_K:/帅不能在红方宫外if(point.x6 | point.x3)return FALSE;break;case BLACK_S:/士只能在宫内特定点if(!(point.x=4 & point.y=1)|(point.x=4 & point.y=3)

19、|(point.x=5 & point.y=2)|(point.x=6 & point.y=1)|(point.x=6 & point.y=3)return FALSE;break;case BLACK_X:/七个相位if(!( point.x=1& point.y=3)|( point.x=3& point.y=1)|( point.x=3& point.y=5)|( point.x=5& point.y=3)|( point.x=7& point.y=1)|( point.x=7& point.y=5)|( point.x=9& point.y=3)return FALSE;break;c

20、ase BLACK_B:/兵不能在兵位后if(point.y4)return FALSE;/兵过河前不能左右移动if(point.y6 & point.x%2=0)return FALSE;break;default:break;return TRUE; 保存棋盘状态。其具体实现如下：void FixManMap(int map1112, POINT manpoint32, int side)memcpy(map, _defaultmap, 132*sizeof(int);static POINT *pman;static int i;for(i=0; ix)mappman-xpman-y =

21、 i; 规定各个位置不同的价值值：/兵卒在不同位置的价值，数字越大价值越高const int ManBPlus21211= 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 4, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 4, 4, 3, 2, 1, 0, 0, 1, 2, 3, 3, 3, 3, 3, 2, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0

22、, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

23、, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 2, 3, 3, 3, 3, 3, 2, 1, 0, 0, 1, 2, 3, 4, 4, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 4, 4, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0; 列出所有可能的走法。其具体实现方法如下：BOOL EnumList(int tmap1112

24、,POINT tmanposition32,int &tside,int *chessman,POINT *move,int &count)#define ADD(man,tx,ty) chessmancount=man;movecount.x=tx;movecount.y=ty;count+;if(tmaptxty=FistOfSide!tside)goto _NOKING;static int i, j, n, x, y;static BOOL flag;count = 0;for(n=FistOfSidetside; n=LastOfSidetside; n+)x = tmanposit

25、ionn.x;if(!x)continue;y = tmanpositionn.y;switch(n)case 0:if(tmanposition0.x=tmanposition16.x)/将帅在同一列flag = FALSE;for(j=tmanposition16.y+1; jtmanposition0.y; j+)if(tmapxj!=32)flag = TRUE;break;if(!flag)ADD(0, x, tmanposition16.y);j = y + 1;if(j=8 & NORED(x, j)ADD(0, x, j)i = x + 1;if(i=4 & NORED(i,

26、j)ADD(0, i, j)break;case 16:if(tmanposition0.x=tmanposition16.x)/将帅在同一列flag=FALSE;for(j=tmanposition16.y+1;jtmanposition0.y;j+)if(tmapxj!=32)flag=TRUE;break;if (!flag)ADD(16,x,tmanposition0.y);j=y+1;if(j=1 & NOBLACK(x,j)ADD(16,x,j)i=x+1;if(i=4 & NOBLACK(i,y)ADD(16,i,y)break;case 1:case 2:i=x+1;j=y+1

27、;if(i=6 & j=10 & NORED(i,j)ADD(n,i,j)i=x+1;j=y-1;if(i=8 & NORED(i,j)ADD(n,i,j)i=x-1;j=y+1;if(i=4 & j=4 & j=8 & NORED(i,j)ADD(n,i,j)break;case 17:case 18:i=x+1;j=y+1;if(i=6 & j=3 & NOBLACK(i,j)ADD(n,i,j)i=x+1;j=y-1;if(i=1 & NOBLACK(i,j)ADD(n,i,j)i=x-1;j=y+1;if(i=4 & j=4 & j=1 & NOBLACK(i,j)ADD(n,i,j)

28、break;case 3:case 4:i=x+2;j=y+2;if(i=9 & j=10 & NORED(i,j)if(NOMAN(x+1,y+1)ADD(n,i,j)i=x+2;j=y-2;if(i=6 & NORED(i,j)if(NOMAN(x+1,y-1)ADD(n,i,j)i=x-2;j=y+2;if(i=1 & j=1 & j=6 & NORED(i,j)if(NOMAN(x-1,y-1)ADD(n,i,j)break;case 19:case 20:i=x+2;j=y+2;if(i=9 & j=5 & NOBLACK(i,j)if(NOMAN(x+1,y+1)ADD(n,i,j

29、)i=x+2;j=y-2;if(i=1 & NOBLACK(i,j)if(NOMAN(x+1,y-1)ADD(n,i,j)i=x-2;j=y+2;if(i=1 & j=1 & j=1 & NOBLACK(i,j)if(NOMAN(x-1,y-1)ADD(n,i,j)break;case 5:case 6:i=x+1;if(NOMAN(i,y)i=x+2;j=y+1;if(i=9 & j=10 & NORED(i,j)ADD(n,i,j)i=x+2;j=y-1;if(i=1 & NORED(i,j)ADD(n,i,j)i=x-1;if(NOMAN(i,y)i=x-2;j=y+1;if(i=1 &

30、 j=1 & j=1 & NORED(i,j)ADD(n,i,j)j=y+1;if(NOMAN(x,j)i=x+1;j=y+2;if(i=9 & j=1 & j=10 & NORED(i,j)ADD(n,i,j)j=y-1;if(NOMAN(x,j)i=x+1;j=y-2;if(i=1 & NORED(i,j)ADD(n,i,j)i=x-1;j=y-2;if(i=1 & j=1 & NORED(i,j)ADD(n,i,j)break;case 21:case 22:i=x+1;if(NOMAN(i,y)i=x+2;j=y+1;if(i=9 & j=10 & NOBLACK(i,j)ADD(n,

31、i,j)i=x+2;j=y-1;if(i=1 & NOBLACK(i,j)ADD(n,i,j)i=x-1;if(NOMAN(i,y)i=x-2;j=y+1;if(i=1 & j=1 & j=1 & NOBLACK(i,j)ADD(n,i,j)j=y+1;if(NOMAN(x,j)i=x+1;j=y+2;if(i=9 & j=1 & j=10 & NOBLACK(i,j)ADD(n,i,j)j=y-1;if(NOMAN(x,j)i=x+1;j=y-2;if(i=1 & NOBLACK(i,j)ADD(n,i,j)i=x-1;j=y-2;if(i=1 & j=1 & NOBLACK(i,j)ADD

32、(n,i,j)break;case 7:case 8:i=x+1;while(i=1)if (NOMAN(i,y)ADD(n,i,y)elseif(NORED(i,y)ADD(n,i,y)break;i-;j=y+1;while(j=1)if (NOMAN(x,j)ADD(n,x,j)elseif(NORED(x,j)ADD(n,x,j)break;j-;break;case 23:case 24:i=x+1;while(i=1)if (NOMAN(i,y)ADD(n,i,y)elseif(NOBLACK(i,y)ADD(n,i,y)break;i-;j=y+1;while(j=1)if (N

33、OMAN(x,j)ADD(n,x,j)elseif(NOBLACK(x,j)ADD(n,x,j)break;j-;break;case 9:case 10:i=x+1;flag=FALSE;while(i=1)if(NOMAN(i,y) if(!flag)ADD(n,i,y)elseif(!flag)flag=TRUE;else if(NORED(i,y)ADD(n,i,y)break;i-;j=y+1;flag=FALSE;while(j=1)if(NOMAN(x,j) if(!flag)ADD(n,x,j)elseif(!flag)flag=TRUE;else if(NORED(x,j)A

34、DD(n,x,j)break;j-;break;case 25:case 26:i=x+1;flag=FALSE;while(i=1)if(NOMAN(i,y) if(!flag)ADD(n,i,y)elseif(!flag)flag=TRUE;else if(NOBLACK(i,y)ADD(n,i,y)break;i-;j=y+1;flag=FALSE;while(j=1)if(NOMAN(x,j)if(!flag)ADD(n,x,j)elseif(!flag)flag=TRUE;else if(NOBLACK(x,j)ADD(n,x,j)break;j-;break;case 11:cas

35、e 12:case 13:case 14:case 15:j=y-1;if(j=1 & NORED(x,j)ADD(n,x,j)if(y=5)i=x+1;if(i=1 & NORED(i,y)ADD(n,i,y)break;case 27:case 28:case 29:case 30:case 31:j=y+1;if(j=6)i=x+1;if(i=1 & NOBLACK(i,y)ADD(n,i,y)break;default :break;return TRUE;_NOKING:return FALSE; 对走法列表进行快速排序。其具体实现方法如下：void Mantis_QuickSort

36、(int A, int chessman, POINT targetpoint, int low, int high)int pivot;int pivot_man;POINT pivot_point;int scanUp, scanDown;int mid, k;POINT point;if(high-lowAlow)k = Ahigh;Ahigh = Alow;Alow = k;k = chessmanhigh;chessmanhigh = chessmanlow;chessmanlow = k;point = targetpointhigh;targetpointhigh = targe

37、tpointlow;targetpointlow = point;return;mid = (low + high) / 2;pivot=Amid;pivot_man=chessmanmid;pivot_point=targetpointmid;k=Amid;Amid=Alow;Alow=k;k=chessmanmid;chessmanmid=chessmanlow;chessmanlow=k;point=targetpointmid;targetpointmid=targetpointlow;targetpointlow=point;scanUp =low+1;scanDown = high;dowhile(scanUp=pivot)scanUp+;while(pivotAscanDown)scanDown-;if(scanUpscanDown)k=AscanUp;AscanUp=AscanDown;AscanDown=k;k=chessmanscanUp;chessmanscanUp=chessmanscanDown;chessmanscanDown=k;point=targetp