《马踏棋盘_实验报告重点讲义资料》由会员分享，可在线阅读，更多相关《马踏棋盘_实验报告重点讲义资料（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：在走不通时退回上一步格点，并使不通的格点元素归零。void MarkPrint(PosType pos) Init1pos.xpos.y = 0;/如果不通标记为零 （4）下个格点寻找函数NextPos：寻找某个格点走棋的下一个位置，且使下个位置在Init288中数值最小（目的是使棋子能最大可能性的走遍棋盘）。对于某个非回溯位置，从他
