《马踏棋盘_实验报告重点讲义资料.doc》由会员分享，可在线阅读，更多相关《马踏棋盘_实验报告重点讲义资料.doc（14页珍藏版）》请在三一办公上搜索。
1、西安交通大学实验报告课程 数据结构专题实验 实验名称 马踏棋盘 第 1 页 共 9 页系别_ 自动化 实 验 日 期 2015 年 11 月 8 日专业班级 自动化43班 实 验 报 告 日 期 2015 年 11月 15 日姓 名 李欣阳 学号 2140504066 报 告 退 发 ( 订正 、 重做 )同 组 人 无 教 师 审 批 签 字 一、实验目的通过本次试验，熟练掌握抽象数据类型栈和队列的实现，学会用栈和队列解决具体应用问题，从而体会栈和队列的特点。二、实验内容与要求设计一个国际象棋的马踏棋盘的演示程序，满足：将马随机放在国际象棋88棋盘Broad88的某方格中，马按走棋规则进行移
2、动。可以允许回溯，最终成功走遍棋盘上64个方格。编制非递归程序，求出马的行走路线，按求出的行走路线，将数字1，2，3，64依次填入一个88方阵，并输出该方阵。三、问题分析3.1 下一个位置的确定一般来说,当马处于位置( i ，j )时，可以走到下列八个位置之一，这些位置称之为该位置的邻接位置：( i-2，j+1 )，( i-1，j+2 )，( i+1，j+2 )，( i +2，j+1 )( i+2，j+1 )，( i+1，j -2)，( i-1，j-2 )，( i-2，j -1 )给以上八个位置依次编号，在棋盘上显示如下图：图1 某位置的八个邻接位置但是如果( i ，j )靠近棋盘边缘，八个邻
3、接位置中可能有些位置超出棋盘范围，那些不允许的位置就不能成为下一步的选择。这八个邻接位置可以用两个一维数组HTry18和HTry28来表示：HTry18= -2，-1，1，2，2，1，-1，-2HTry28= 1，2，2，1，-1，-2，-2，-1位于( i ，j )的马可以走到的新位置是在棋盘范围内的(i+ HTry1h，j+ HTry2h)，其中h=0，1， ，7。每次在所有可走的位置中选择一个进行试探，已经走过的位置标记为步数（比如第5步走到该格，则该格标记为5），未走过的位置标记为0。为了使马能最大可能性的走完整个棋盘并且减小计算次数，应该让马优先走难走的地方，即邻接位置最少的那些位置
4、（主要指四角和边缘）。在棋盘上标记出每个位置的邻接位置，如下图：2344443234666643468888644688886446888864468888643466664323444432图2 每个位置的临接位置数3.2 回溯的方法如果仅仅是搜索邻接位置最小的位置作为走棋的下一步，仍然有很大几率不能把棋盘走遍，因此当棋子走到的位置其八个邻接位置全部之前已经走过，就要设计回溯算法，使得棋子能够退回上一步转而寻求另一个方向。为了满足这种需求，需要定义一个栈结构，每当成功走一步，就把所走位置的坐标和这次移动的步数入栈，当走到某一位置无法进行下一步时，就要把原来栈顶的元素Pop出来，转而换一条路径
5、继续探索，如果还是无法找到正确路径，那么久再次Pop栈顶元素，以此类推。如果回溯过程中栈空，也就说明无论怎样都不能找到合适的路径，即在该起始位置无法走遍棋盘。3.3 表格的构建及动态演示的实现为了构建棋盘表格，只需要在每次输出之后添加符号“|”，并在每行输出完成之后，额外输出一行“-”即可，输出表格线时要根据具体情况调整“-”的数目即可。动态演示的实现需要每一步都输出一次步数标记数组Init1，间隔时间调用Sleep函数。由于Init1的初始化是所有元素赋值为零，在输出该数组时难免出现没走过的空位置显示为零的情况。因此为了使输出结果简洁美观，在输出数组之前先通过if语句把所有为零的位置（尚未走
6、过的位置）转化为空格后再输出，而非零的位置原样输出即可。四、栈结构及基本操作4.1 栈的说明及抽象数据类型本实验采用栈这一线性数据结构来实现，栈是限定仅在表尾进行插入或者删除操作的线性表，表尾称为栈顶，表头称为栈底。栈的抽象数据类型及基本操作定义如下： ADT Stack数据对象：D=ai|aiElemSet, i=1,2, ,n, n0数据关系：R1=|ai-1,aiD, i=1,2, ,n 约定an端为栈顶，a1端为栈底。基本操作：InitStack( &S )操作结果：构造一个空栈S。DestroyStack ( S )初始条件：栈S已存在。操作结果：栈S被销毁。Push( &S, e
7、)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop( &S, &e )初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。StackEmpty ( S )初始条件：栈S已存.操作结果：若栈S非空则返回TURE，否则返回FALSE。ADT Stack4.2 顺序栈的定义栈的顺序存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时设定指针top指示栈顶元素在顺序栈中的位置。顺序栈的存数示意图及C语言定义为：typedef struct int stacksize;SElemType *base;SElemType *top;SqStack;/顺序
8、栈结构体4.3顺序栈基本操作的算法描述(1)栈的初始化：生成一个规定大小的空表，表尾表示栈顶，表头表示栈底。int InitStack(SqStack &S) S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType); if(!S.base) return 0; S.top = S.base; S.stacksize = STACK_INIT_SIZE; return 1;/栈的初始化（2）入栈操作:将元素x压入栈的top中，即顺序表表尾增加一个节点，栈顶指针后移一个节点int Push(SqStack &S,SElemTy
9、pe e) if(S.top - S.base = S.stacksize ) S.base = (SElemType*)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMENT )*sizeof(SElemType); if(!S.base) return 0; S.top = S.base +S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return 1;/入栈函数（3）出栈操作:从栈中删除栈顶元素*top。实现手段：如果是空栈则返回0，如果栈非空，那么只需要把栈顶指针后移一个节点即可。
10、int Pop(SqStack &S,SElemType &e) if(S.top = S.base) return 0; e = *-S.top; return 1;/出栈函数(4)判断栈空函数：主需要判断栈顶指针是否等于栈底指针，如果相等则栈空返回0，否则栈不空返回1。int StackEmpty(SqStack &S) if(S.base = S.top) return 1; else return 0; /判断栈空（5）销毁栈函数：首先令栈顶指针等于栈底指针，相当于使栈变空，然后栈长置零即可。void DestroyStack(SqStack &S) S.base = S.top; S
11、.stacksize = 0;/销毁栈五、算法设计为了实现算法功能，并满足结果动态演示的需求，该算法的基本部分应该包括以下几个模块：（1）栈结构的定义及其基本操作函数，这是所有涉及栈结构的程序锁必须具备的模块。（2）棋盘输出函数Print(int curstep)，其中curstep是一个坐标形式的参量，需要在算法一开始给出定义。其中棋盘是一个预先定义的88的二维数组，用于存储走棋步骤，当棋子在移动的第n步走到该方格，则该位置的元素赋值为n。为了在窗口显示棋盘，在打印棋盘时应该通过循环语句同时打印出棋盘网格，借助“+”“-”等符号构建网格。Print函数的C语言定义如下void Print(i
12、nt curstep)for(int j = 0; j 8; j+)printf(-+);printf(n); for(int i = 0; i 8; i+) for(int j = 0; j 8; j+) if(Init1ij=0)printf( |);else printf(%3d|,Init1ij); printf(n); for(int j = 0; j 8; j+) printf(-+); printf(n); printf(n);printf(n);/打印棋盘 Init1（3）走棋辅助函数FootPrint、MarkPrint和Pass判断一个位置是否能通过函数Pass：该位置在I
13、nit1数组中对应值如果为零则可以通过不为零则不能通过。int Pass(PosType &curpos) if(!Init1curpos.xcurpos.y) return 1; else return 0;/判断一个位置是否可以通过，为零则可以通过，不为零则不能通过轨迹标记函数FootPrint：用于在棋盘数组Init1中标记出走过的方格，并是对应数组元素变为走棋步数。void FootPrint(PosType &curpos,int curstep)Init1curpos.xcurpos.y = curstep;/把Init1当前坐标所示位置标记为步数回溯归零函数MarkPrint：在
14、走不通时退回上一步格点，并使不通的格点元素归零。void MarkPrint(PosType pos) Init1pos.xpos.y = 0;/如果不通标记为零 （4）下个格点寻找函数NextPos：寻找某个格点走棋的下一个位置，且使下个位置在Init288中数值最小（目的是使棋子能最大可能性的走遍棋盘）。对于某个非回溯位置，从他的八个邻接位置中依次找起，返回在Init288中数值最小那个邻接位置；如果是回溯位置，则不必从第一个邻接位置找起，只需要从失败邻接位置的下一个开始找。其C语言定义如下：PosType NextPos(PosType curpos,int x) PosType Min
15、Curpos,temp; MinCurpos.x = -1;MinCurpos.y = -1;/起始最小的方向，无意义 for(;x 8; x+) temp.x = curpos.x + HTry1x;temp.y = curpos.y + HTry2x; if(temp.x 7 | temp.y 7 | Init1temp.xtemp.y) continue;if(MinCurpos.x = -1 & MinCurpos.y = -1) MinCurpos = temp;else if( Init2MinCurpos.xMinCurpos.y Init2temp.xtemp.y )MinCu
16、rpos= temp;if(MinCurpos.x = -1 & MinCurpos.y = -1)return curpos; return MinCurpos;/寻找下一个位置，且此位置在Init288中最小；如果没有下个位置，返回原来位置（5）走棋函数Move：把以上的辅助函数进行有机的连接，包括构造回溯用的栈；走通时在棋盘数组中相应位置记录步数，走不通时回溯上一步等部分，算法思路见问题分析部分。其C语言定义如下：int Move(PosType start) SqStack S; PosType Mincurpos,curpos; SElemType RecNext; int curs
17、tep; InitStack(S); curpos = start; curstep = 1; do if(Pass(curpos) FootPrint(curpos,curstep); RecNext.renext = 0; RecNext.seat= curpos; system(cls); Print(curstep); Sleep(300); Push(S,RecNext); if(curstep = 64) /走到第64步结束 Print(curstep); DestroyStack(S); return 1; curpos = NextPos(curpos,RecNext.rene
18、xt); curstep +; else if(!StackEmpty(S) Pop(S,RecNext); curstep -; while(RecNext.renext = 7 & !StackEmpty(S) MarkPrint(RecNext.seat); Pop(S,RecNext); curstep -; /此路不通，标记为零 ，原路退回，直到找到能通的位置 if(RecNext.renext 7) Mincurpos = curpos; RecNext.renext +; curpos = NextPos(RecNext.seat,RecNext.renext); while(M
19、incurpos.x = curpos.x & Mincurpos.y = curpos.y & RecNext.renext 7) RecNext.renext +; curpos = NextPos(RecNext.seat,RecNext.renext); Push(S,RecNext); curstep +; /找到通的路之后，变换下一步，不再重复之前的路 if(StackEmpty(S) printf(从该位置不能走遍棋盘); /栈空则无法走遍棋盘 while(!StackEmpty(S); DestroyStack(S); return 0;/走棋函数（6）主函数main：连接以上
20、各函数，主要功能是实现初始位置的输入，及初始位置不合法时的提示，用于提高程序的适用性。六、程序测试及检验1.编译并运行程序，输入初始坐标（2，1），窗口截图如下下图是程序运行窗口动态演示过程的截图，其中数字方格表示马在第几部走到该位置，空方格表示马还未走过的位置。下图是程序运行完毕后的窗口截图，结果显示该起始点能使棋子走遍全棋盘，走棋顺序如棋盘表格所示：1.编译并运行程序，输入初始坐标（3，5），窗口截图如下下图是程序运行窗口动态演示过程的截图：下图是程序运行完毕后的窗口截图，结果显示该起始点能使棋子走遍全棋盘，走棋顺序如棋盘表格所示：七、程序优缺点分析优点：（1）输出的结果包含规整的棋盘，程
21、序能实现动态演示，程序的输出结果美观得体。 （2）由于Init2棋盘的定义，使得棋子能先走不易走通的位置（四角和边缘），大大提高了棋子走遍棋盘的成功率，且简化了算法，减小了需要回溯的步骤。缺点：（1）棋盘网格由简单的运算符“+”“-”构建，形式上还不够美观。（2）对于一些初始位置，想要走遍棋盘需要很多步回溯，结果输出较慢，算法仍需改进。八、程序代码（C语言）#include#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#include typedef struct int x; int y;PosType; /记录坐标位
22、置typedef struct PosType seat; int renext; SElemType; /用于记录某一位置的下一个方向typedef struct int stacksize; SElemType *base; SElemType *top;SqStack; /顺序栈的定义 int Init188 = 0 ;/初始化期盼用于记录行走路线 int Init288 = 2,3,4,4,4,4,3,2, 3,4,6,6,6,6,4,3, 4,6,8,8,8,8,6,4, 4,6,8,8,8,8,6,4, 4,6,8,8,8,8,6,4, 4,6,8,8,8,8,6,4, 3,4,6
23、,6,6,6,4,3, 2,3,4,4,4,4,3,2,; /初始化棋盘，并标记每个位置所能跳的方向数目 int HTry18 = -2, -1, 1, 2, 2, 1, -1, -2;int HTry28 = 1, 2, 2, 1, -1, -2, -2, -1;/在某一位置共有八个方向可以走 int InitStack(SqStack &S) S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType); if(!S.base) return 0; S.top = S.base; S.stacksize = STACK_IN
24、IT_SIZE; return 1;/栈的初始化 int Pop(SqStack &S,SElemType &e) if(S.top = S.base) return 0; e = *-S.top; return 1;/出栈函数 int Push(SqStack &S,SElemType e) if(S.top - S.base = S.stacksize ) S.base = (SElemType*)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMENT )*sizeof(SElemType); if(!S.base) return 0; S.top =
25、 S.base +S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return 1;/入栈函数 void DestroyStack(SqStack &S) S.base = S.top; S.stacksize = 0;/销毁栈 int StackEmpty(SqStack &S) if(S.base = S.top) return 1; else return 0;/判断栈空 void Print(int curstep)for(int j = 0; j 8; j+)printf(-+);printf(n); for(int
26、i = 0; i 8; i+) for(int j = 0; j 8; j+) if(Init1ij=0)printf( |); else printf(%3d|,Init1ij);/为零的位置转化为空格后输出，不为零则原样输出 printf(n); for(int j = 0; j 8; j+) printf(-+); printf(n); /在输出的同时构建棋盘表格 printf(n);printf(n);/打印棋盘 Init1 void MarkPrint(PosType pos) Init1pos.xpos.y = 0;/如果不通标记为零 void FootPrint(PosType
27、&curpos,int curstep) Init1curpos.xcurpos.y = curstep;/把Init1当前坐标所示位置标记为步数 PosType NextPos(PosType curpos,int x) PosType MinCurpos,temp; MinCurpos.x = -1; MinCurpos.y = -1;/起始最小的方向，无意义 for(;x 8; x+) temp.x = curpos.x + HTry1x; temp.y = curpos.y + HTry2x; if(temp.x 7 | temp.y 7 | Init1temp.xtemp.y) co
28、ntinue; if(MinCurpos.x = -1 & MinCurpos.y = -1) MinCurpos = temp; else if( Init2MinCurpos.xMinCurpos.y Init2temp.xtemp.y ) MinCurpos= temp; if(MinCurpos.x = -1 & MinCurpos.y = -1) return curpos; return MinCurpos;/寻找下一个位置，且此位置在Init288中最小；如果没有下个位置，返回原来位置 int Pass(PosType &curpos) if(!Init1curpos.xcurp
29、os.y) return 1; else return 0;/判断一个位置是否可以通过，为零则可以通过，不为零则不能通过 int Move(PosType start) SqStack S; PosType Mincurpos,curpos; SElemType RecNext; int curstep; InitStack(S); curpos = start; curstep = 1; do if(Pass(curpos) FootPrint(curpos,curstep); RecNext.renext = 0; RecNext.seat= curpos; system(cls); Pr
30、int(curstep); Sleep(500); /每隔0.5s输出依次，实现动态演示 Push(S,RecNext); if(curstep = 64) /走到第64步结束 Print(curstep); DestroyStack(S); return 1; curpos = NextPos(curpos,RecNext.renext); curstep +; else if(!StackEmpty(S) Pop(S,RecNext); curstep -; while(RecNext.renext = 7 & !StackEmpty(S) MarkPrint(RecNext.seat); Pop(S,RecNext); curstep -; /此路不通，标记为零 ，原路退回，直到找到能通的位置 if(RecNext.renext 7) Mincurpos = curpos; RecNext.renext +; curpos = NextPos(RecNext.seat,RecNext.renext); while(Mincurpos.x = curpos.x & Mincurpos.y = curpos.y & RecNext.renext 7|start.y7)printf(起始位置有误);Move(start); /main函数
