马踏棋盘实验报告单(含代码)

《马踏棋盘实验报告单(含代码)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机学院《数据结构》课程设计报告课题名称：马踏棋盘课题负责人（学号/姓名）：黎贵涛110520121同组成员名单（姓名）：刘伟110520131林建彪110520104指导教师：孔令寅评阅成绩：评阅意见：提交报告时间：2021年8月7日项目成员序号学号姓名职责任务说明1110520131刘伟小组成员1.需求分析2.用户使用说明3.测试结果2110520121黎贵涛组长1.概要设计2.详细设计3110520104林建彪小组成员1概要设计2.调试分析一、【问题描述】设计一个国际象棋的马踏棋盘的演示过程。基本要求:将马随机放在国际象棋的8*8棋盘Board[8][8]的某个方格中，马按走棋规则

2、进行移动，要求每个方格只进行一次，走遍整个棋盘的全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8*8的方阵，输出之。测试数据：可自行制定一个马的初始位置（i，j），0<=I,j<=7。二、【实验目的】1、对数据结构基本理论和存储结构及算法设计有更深入的理解；2、了解栈的特性，以便在实际问题背景下灵活运用他们；3、提高在世纪设计操作中系统分析、结构确定、算法选择、数学建模和信息加工的能力。三、【设计过程】81726354第1步：实现提示一般来说，当马位于位置（i,j）时，可以走到下列8个位置之一：（i-2，j+1），(i-1，j+2)

3、（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）靠近棋盘的边缘，上述有些位置可能要超出棋盘位置，成为不允许的位置。8个可能位置可以用一位数组HTry1[0…7]和HTry2[0…7]来表示：01234567-2-11221-1-21221-1-2-2-1（表-2）位于（i，j）的马可以走到新位置是在棋盘范围内的（i+HTry1[h],j+HTry2[h]），其中h=0…7。第2步：需求分析（1）输入的形式和输入值的范围：输入马的初始行坐标X和列坐标Y，X和Y的范围都是[1,8]。（2）输出形式：

4、以数组下表的形式输入，i为行标，j为列标，用空格符号隔开。以棋盘形式输出，每一格打印马走的步数，这种方式比较直观（3）程序所能达到的功能：让马从任意起点出发都能够遍历整个8*8的棋盘。（4）测试数据，包括正确输入及输出结果和含有错误的输入及其输出结果。数据可以任定，只要1<=x,y<=8就可以了。正确的输出结果为一个二维数组，每个元素的值表示马行走的第几步，若输入有错，则程序会显示：“输入有误！请重新输入……”并且要求用户重新输入数据，直至输入正确为止。第3步，算法设计思想：1、输入马所在初始位置的坐标值，考虑到用户的输入习惯，此处1<=x，y<=8；2、将输入的初始值进栈；3、设置一个w

5、hile循环，循环条件为count<64；4、取出栈顶元素；5、定义flag标志变量的值；6、按照setpossible函数顺时针顺序优先原则，找栈顶元素周围未被占用的新位置。7、若存在该位置，则令order的值等于该新位置的坐标，并入栈；8、否则弹出栈顶元素；9、再次回到第③步while循环进行判断；10、输出一个8*8的方阵，所示数字即为相应步骤。第4步，算法框图：开始输入初始坐标X,Y判断X,Y是否合法？Initstack建立新栈并且将初始位置入栈count<64GetTop取栈顶元素；找出所有可走位置根据for循环及优先原则查找是否存在下一个坐标？调用push函数将其压缩进栈调用D

6、leteTop函数将栈顶元素弹出输出否是否是否是第5步，存储结构设计：（1）、位置的存储表示方式typedefstruct{intx;inty;intfrom;}Point;（2）、栈的存储方式#defineSTACKSIZE70#defineSTACKINCREASE10typedefstructStack{Point*top;Point*base;intstacksize;};第6步，设计功能分析与实现（1）、设定栈的抽象数据类型定义：ADTStack{数据对象：D=｛ai

7、ai∈ElemSet,i=1,2,…,n,n≥0｝数据关系：R1={

8、ai-1,ai∈D,i=

9、2,…,n}约定an端为栈顶，ai端为栈顶。基本操作：InitStack(&s)操作结果：构造一个空栈s，DestroyStack(&s)初始条件：栈s已存在。操作结果：栈s被销毁。ClearStack(&s)初始条件：栈s已存在。操作结果：栈s清为空栈。StackEmpty(&s)初始条件：栈s已存在。操作结果：若栈s为空栈，则返回OK，否则返回ERROR。StackLength(s);初始条件：栈s存在。操作结果：返