第七次实验 马踏棋盘问题

桂林电子科技大学

数学与计算科学学院综合性、设计性实验报告

实验报告 马踏棋盘

2.4题马踏棋盘 题目：设计一个国际象棋的马踏棋盘的演示程序 班级：姓名：学号：完成日期： 一．需求分析 （1）输入的形式和输入值的范围：输入马的初始行坐标X和列坐标Y， X和Y的范围都是[1,8]。 （2）输出形式： 以数组下表的形式输入，i为行标，j为列标，用空格符号隔开。以棋盘形式输出，每一格打印马走的步数，这种方式比较直观 （3）程序所能达到的功能：让马从任意起点出发都能够遍历整个8*8的 棋盘。 （4）测试数据，包括正确输入及输出结果和含有错误的输入及其输出结 果。数据可以任定，只要1<=x,y<=8就可以了。 正确的输出结果为一个二维数组，每个元素的值表示马行走的第几步，若输入有错，则程序会显示：“输入有误！请重新输入……”并且要求用户重新输入数据，直至输入正确为止。 二．概要设计 （1）、位置的存储表示方式 （2） typedef struct { int x; int y; int from; }Point; （2）、栈的存储方式 #define STACKSIZE 70 #define STACKINCREASE 10 typedef struct Stack { Point *top; Point *base; int stacksize; }; （1）、设定栈的抽象数据类型定义： ADT Stack { 数据对象：D=｛ai | ai∈ElemSet,i=1,2,…,n,n≥0｝ 数据关系：R1={|ai-1, ai∈D,i=2,…,n} 约定an端为栈顶，ai端为栈顶。 基本操作： InitStack(&s) 操作结果：构造一个空栈s， DestroyStack(&s) 初始条件：栈s已存在。 操作结果：栈s被销毁。 ClearStack(&s) 初始条件：栈s已存在。

马踏棋盘实验报告

西安郵電學院 数据结构 课内实验报告书 院系名称：计算机学院 实验题目：马踏棋盘 学生姓名： 专业名称：计算机科学与技术班级： 学号： 时间： 2011年10月10日指导教师：曾艳

一、实验题目：马踏棋盘 二、实验目的： 通过本次实验，熟练掌握抽象数据类型栈和队列的实现，学会使用栈和队列解决具体应用问题，从而体会栈和队列的特点。 三、实验要求： 设计一个国际象棋的马踏遍棋盘的演示程序。 要求：将马随机放在国际象棋的8×8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出之 四、设计与实现过程 （1）栈或队列的定义及其主要操作的实现 struct Chess { int x; int y; int h;/*h记录下一次需要试探的马字格式的下标值*/ }Chess1[65]; （2）主要算法的描述 void Handlechess(int m,int n) { int flag=1,i; double j=0.0;/*增加了j用于统计while循环的执行次数，很好奇循环到底执行了多少次*/ int chessx[8]={-2,-2,-1,-1,1,1,2,2};/*马字的格式的8个位置，按下标序依次试探*/ int chessy[8]={-1,1,-2,2,-2,2,-1,1}; for(i=1;i<=64;i++) Chess1[i].h=0;/*赋初值*/ chess[m][n]=flag; Chess1[flag].x=m; Chess1[flag].y=n; while(flag<64) { j+=1.0; for(i=Chess1[flag].h;i<8;i++)/*i的初值由Chess1[flag].h确定*/ { m=Chess1[flag].x+chessx[i]; n=Chess1[flag].y+chessy[i]; if((m>=0&&m<=7&&n>=0&&n<=7)&&(chess[m][n]==0))/*去掉了函数，改为直接用关系表达式判断，提高运行速度*/ { Chess1[flag].h=i+1;/*h记录下一次需试探马字格式位置的下标*/ flag++;

马踏棋盘数据结构实践报告

马踏棋盘问题 摘要： 马踏棋盘就是在国际象棋8X8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。理解栈的“后进先出”的特性以及学会使用回溯。 关键字：马踏棋盘、递归、栈、回溯 1．引言 马踏棋盘就是在国际象棋8X8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。 编制程序，求出马的行走路线，并按求出的行走路线，将数字1，2….64依次填入一个8X8的方阵，并输出它的行走路线。输入：任意一个起始位置；输出：无重复踏遍棋盘的结果，以数字1-64表示行走路线。 2．需求分析 （1）需要输出一个8X8的棋盘，可以采用二维数组的方法实现。 （2）输入马的起始位置，必须保证输入的数字在规定范围内，即0<=X<=7,0<=Y<=7。 （3）保证马能走遍整个棋盘，并且不重复。

（4）在棋盘上输出马的行走路线,标记好数字1、2、3直到64。 3．数据结构设计 采用栈数组为存储结构。 #define maxsize 100 struct { int i; int j; int director; }stack[maxsize]; 4．算法设计 4.1 马的起始坐标 void location(int x,int y) //马的位置坐标的初始化 { top++; stack[top].i=x; //起始位置的横坐标进栈 stack[top].j=y; //起始位置的竖坐标进栈 stack[top].director=-1;

a[x][y]=top+1; //标记棋盘Try(x,y); //探寻的马的行走路线 } 4.2 路径探寻函数 void Try(int i,int j) { int count,find,min,director; int i1,j1,h,k,s; int b[8]={-2,-2,-1,1,2,2,1,-1},c[8]={1,-1,-2,-2,-1,1,2,2} ; //存储马各个出口相对当前位置行、列坐标的增量数组 int b2[8],b1[8]; for(h=0;h<=7;h++) //用数组b1[8]记录当前位置的下一个位置的可行路径的条数 { count=0; i=stack[top].i+c[h]; j=stack[top].j+b[h]; if(i>=0&&i<=7&&j>=0&&j<=7&&a[i][j]==0) //如果找到下一个位置 { for(k=0;k<=7;k++) { i1=i+c[k]; j1=j+b[k]; if(i1>=0&&i1<=7&&j1>=0&&j1<=7&&a[i1]

马踏棋盘分析文档

数据结构课程设计 题目：马踏棋盘 院系： 班级： 学号： 姓名： 2014-2015年度第1学期

马踏棋盘 一．题目：马踏棋盘 (3) 二. 设计目标 (3) 三. 问题描述 (3) 四. 需求分析 (4) 五. 概要设计 (4) 第一步：定义四个常量和一个数据类型 (4) 第二步：构造函数 (4) 六. 详细设计（给出算法的伪码描述和流程图） (5) 流程图设计 (5) 代码分析 (9) 第一步：定义常量与变量 (9) 第二步：构造函数 (9) ●定义一个结构体类型 (9) ●创建一个初始化函数 (10) ●创建提示输入函数 (10) ●创建产生新节点函数 (11) ●创建计算路径函数 (12) ●创建入栈函数 (13) ●创建出栈函数 (13) ●创建输出函数 (13)

第三步：在主函数中调用其它函数 (15) 七. 测试分析 (16) 八. 使用说明 (16) 九. 测试数据 (16) 十．课程设计总结 (17) 一．题目：马踏棋盘 二. 设计目标 帮助学生熟练掌握顺序栈的基本操作，让学生深入了解栈的使 用，使得更深层次的灵活运用栈。 三. 问题描述 ○所谓的马踏棋盘是：将马随机放在国际象棋的8×8棋盘的某个方格中，马按走棋规则（马走日字）进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。由用户自行指定一个马的初始位置，求出马的行走路线，并按照求出的行走路线的顺序，将数字1、2、…、64依次填入一个8X8的方阵并输出。 从用户给出的初始位置开始判断，按照顺时针顺序，每次产生一个新的路点，并验证此路点的可用性，需要考虑的是当前路点是否超出棋盘范围和此路点是否已经走过。如果新路点可用，则入栈，并执行下一步，重复进行如上步骤，每次按照已走路点的位置生成新路点。如果一个路点的可扩展路数为0，进行回溯，直到找到一个马能踏遍棋盘的行走路线并输出。

数据结构 马踏棋盘 设计报告

《数据结构》 课程设计报告 课程名称：《数据结构》课程设计课程设计题目： 姓名： 院系： 专业： 年级： 学号： 指导教师： 2011年月日

目录 1、程序设计的目的 2、设计题目 3、分析 4、设计思想 5、算法 6、测试结果 7、调试分析 8、小结 1、课程设计的目的 1、熟练使用C++语言编写程序，解决实际问题； 2、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 3、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 4、提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 5、学习并熟悉栈的有关操作； 6、利用栈实现实际问题； 2、设计题目 【马踏棋盘】 *问题描述：将马随机放在国际象棋的8X8棋盘Bo阿rd[0..7,0..7]的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入8X8的方阵输出之。 *测试数据：由读者指定,可自行指定一个马的初始位置。 *实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳

策略”，以减少回溯的次数。 3、分析 确定输入值的范围，输入马的初始行坐标X和Y，X和Y的范围都是1到8之间。程序的功能是输出马走的步骤，要使马从任一起点出发，通过程序能找到下一个地点，然后遍历整个棋盘。每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。输出时可以用二维数组。 4、设计思想 输入马初始位置的坐标。将初始位置进栈，经过一个while循环，取出符合条件的栈顶元素。利用函数，找出栈顶元素周围未被占用的新位置，如果有，新位置入栈；否则弹出栈顶元素。再进行判断，最后输出。 位置的存储方式，栈的存储方式和一些操作函数为： #include #ifndef STACK_H #define STACK_H struct Point { int x; int y; int from; }; #define STACKSIZE 70 #define STACKINCREASE 10 struct Stack { Point *top; Point *base; int length;

数据结构课程设计报告_马踏棋盘

. 杭州师范大学钱江学院课程设计 题目马踏棋盘算法研究 教学院信息与机电工程分院 专业计算机科学与技术 班级计算机1201 姓名吴秋浩 指导教师王李冬 2013 年12 月21 日

目录 一．概述 (3) 二．总体方案设计 (3) 三．详细设计 (4) 四．最终输出 (7) 五．课程设计总结 (11) 参考文献 (15)

一概述 1.课程设计的目的 （1）课题描述 设计一个国际象棋的马踏遍棋盘的演示程序。 （2）课题意义 通过“马踏棋盘”算法的研究，强化了个人对“栈”数据结构的定义和运用，同时也锻炼了自身的C语言编程能力。另一方面，通过对“马踏棋 盘”算法的研究，个人对“迷宫”、“棋盘遍历”一类的问题，有了深刻 的认识，为今后解决以此问题为基础的相关的问题，打下了坚实的基础。 （3）解决问题的关键点说明 解决问题的关键首先要熟练掌握C语言编程技术，同时能够熟练运用“栈”数据结构。另外，态度也是非常重要的。在课程设计过程中，难免 会遇到困难，但是不能轻易放弃，要肯花时间，能静得下心，积极查阅相 关资料，积极与指导老师沟通。 2.课程设计的要求 （1）课题设计要求 将马随机放在国际象棋的8×8棋盘Board[0～7][0～7]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方 格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1， 2，…，64依次填入一个8×8的方阵，输出之。 程序由回溯法和贪心法实现，比较两种算法的时间复杂度。 （2）课题设计的思路 首先，搞清楚马每次在棋盘上有8个方向可走，定义两个一位数组，来存储马下一着点的水平和纵向偏移量。程序再定义一个8*8二维数组，初始 所有元素置0，起始点元素置1。若为回溯法，初始方向数据（一维数组下 标）入栈。随后，马从起始点开始，每次首先寻找下一可行的着点，然后记 下方向，方向数据入栈，把该位置元素置为合适的序列号，若无下一可行着 点，则回溯，寻找下一方向位置着点，以此类推，直到64填入数组中，则 输出二维数组，即为马可走的方案。若为贪婪法，选择下一出口的贪婪标准 是在那些允许走的位置中，选择出口最少的那个位置。直到没有下一着点位 置，若此时已标记到64，则找到可行方案，输出之。反之，改变初始寻找方 向继续寻找，直到8种方向顺序都试过，若还是没有合适的方案，则说明以 该起始 点开始马无法踏遍棋盘。

马踏棋盘c报告 数据结构课程设计

实现顺序栈或循环队列的存储 一、实验目的 （1）、理解栈的特性“后进先出”和队列的特性“先进先出”。 （2）、仅仅认识到栈和队列是两种特殊的线性表是远远不够的，本次实验的目的在于更深入的了解栈和队列的特性，以便在实际问题背景下灵活运用他们。 （3）、在了解他特性的基础上，还将巩固对这种结构的构造方法的理解。 二、实验环境 （1）Windows XP系统下 （2）编程环境：VC6.0++ 三、实验内容 （1）、要求：在国际象棋8×8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。编制程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，并输出它的行走路线（棋盘如图所示）。 （2）、输入：任意一个起始位置； 输出：无重复踏遍棋盘的结果，以数字1-64表示行走路线。 0 1 2 3 4 5 6 7 0 8 1 1 7 2 2 H 3 6 3 4 5 4 5 6 7 （3）、数据结构要求：采用顺序栈或者链栈实现。

四、实验步骤 为了实现上述程序功能，可以采用顺序栈或者链栈来存储它的数据，本实验所需要的存储空间不是很大，不需动态的开辟很多空间，所以采用相对简单的顺序栈来存储数据，既方便有简单，而用链栈在实现上相对比顺序栈复杂的一点。 （一）、概要设计 （1）、顺序栈的抽象数据类型定义： ADT Stack{ 数据对象：D={a i| a i∈（0，1，…，9），i=0,1，2，…，n，n≥0} 数据关系：R={< a i-1, a i >| a i-1, a i∈D,i=1,2，…，n} } ADT Stack （2）本程序包含三个模块： 1、主程序模块： void main(){ 定义变量； 接受命令； 处理命令； 退出； } 2、起始坐标函数模块——马儿在棋盘上的起始位置； 3、探寻路径函数模块——马儿每个方向进行尝试，直到试完整个棋盘； 4、输出路径函数模块——输出马儿行走的路径； 各模块之间的调用关系： 主程序模块 输入的初始位置是否正确 否 是 起始坐标函数模 探寻路径函数模 输出路径函数模 结束 （二）、详细设计

马踏棋盘

马踏棋盘 学院 专业 学号 学生姓名 指导教师 年月日

摘要： 国际象棋想必大家都玩过，但你有没有想过，让一个“马”遍历国际象棋8*8的棋盘，有没有可能？如果有可能，在给定起点的情况下，有多少种可能？下面，我们将用计算机来模拟“马”对棋盘的遍历. 关键字： 回溯算法贪心算法遍历 正文： 已知国际象棋为8×8棋盘，共64个格，规则中，马按 照如图所示规则移动。将马放在任意方格中，令马遍历每个方 格一次且仅一次，编制非递归程序，将数字1，2， (64) 照马的行走路线依次填入一个8×8的方阵，并输出结果。 通过结合图示，我们不难发现，当马的起始位置（i,j） 确定的时候，可以走到下列8个位置之一： (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) 但是，如果（i，j）靠近棋盘的边缘，上述有些位置可能超出棋盘范围，成为不可达的位置。8个可能位置可以用一维数组Htry1[0…7]和HTry2[0..7]来表示： Htry1： 0 1 2 3 4 5 6 7 -2 -1 1 2 2 1 -1 -2 Htry2： 0 1 2 3 4 5 6 7 1 2 2 1 -1 -2 -2 -1 所以位于（i,j）的马可以走到新位置是在棋盘范围内的（i+ Htry1[h],j+Htry2[h]）,其中h的取值是0~7. 整个问题，我们可以用两种算法来解决，既“回溯算法”与“贪心算法”我们先来看回溯算法： 搜索空间是整个棋盘上的8*8个点.约束条件是不出边界且每个点只能经过

马踏棋盘课程设计实验报告

《数据结构》 课 程 设 计 实 验 报 告 课程名称：《数据结构》课程设计 课程设计题目：马踏棋盘 姓名：邱可昉 院系：计算机学院 专业：计算机科学与技术 班级：10052313 学号：10051319 指导老师：王立波 2012年5月18日

目录 1.课程设计的目的 (3) 2.问题分析 (3) 3.课程设计报告内容 (3) （1）概要设计 (3) （2）详细设计 (3) （3）测试结果 (5) （4）程序清单 (6) 4.个人小结 (10)

1.课程设计的目的 《数据结构》是计算机软件的一门基础课程，计算机科学各领域及有关的应用软件都要用到各种类型的数据结构。学好数据结构对掌握实际编程能力是很有帮助的。为了学好《数据结构》，必须编写一些在特定数据结构上的算法，通过上机调试，才能更好地掌握各种数据结构及其特点，同时提高解决计算机应用实际问题的能力。 2.问题分析 *问题描述：将马随机放在国际象棋的8X8棋盘Bo阿rd[0..7,0..7]的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入8X8的方阵输出之。 *测试数据：由读者指定,可自行指定一个马的初始位置。 *实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。 3.课程设计报告内容 （1）概要设计 定义一张棋盘，定义一个栈保存马走的路径的点坐标和来自方向，用函数计算周围可走坐标，并检查正确性，当周围没有可走格子时退栈到最优位置，继续进行，然后将路径输出。 （2）详细设计 定义结构体，方向数组和Qioan类 struct Point { int x; //记录横坐标 int y; //记录纵坐标 int from; //前一个位置的方向 }; Point side[8]={0,0,0}; //记录可能的方向坐标 class Qipan{ public: Qipan(); ~Qipan(); void Setside(Point); //设置方向坐标 bool Getside(int,Point &); //将指定方向的坐标给特定指针 bool HorseVisit(Point); //输入开始点运行棋盘 bool Pass(Point); //输出路径 private: int **gezi; //棋盘格子 };

马踏棋盘c++课程设计

1．问题描述 设计一个国际象棋的马踏棋盘的演示程序 2．需求分析 (1)将马随即放在国际象棋的8×8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。 (2)编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1,2,……,64依次填入一个8×8的方阵，输出之。 (3)程序执行命令为： 1)输入起始方格坐标(X,Y) 2)求解第一组路径并显示,按Q键退出系统，按其他任意键求解并显示下一组路径。 (4)测试数据:(0,0),(1,2) 3概要设计 3.1[程序设计思路]. 按照顺时针顺序，每次产生一个新的路点，并验证此路点的可用性，需要考虑的问题包括是否超出棋盘和此点已经走过与否。如新路点可用，则入栈，并执行下一步，每次按照上一路点的位置生成新路点。如一个路点的可扩展路点数为0，则走不下去了，进行回溯。 3.2[存储结构设计] 8个可能位置可以用两个一维数组表示： 数组1： 0 1 2 3 4 5 6 7 -2 -1 1 1 2 2 1 -1 -2 数组2：0 1 2 3 4 5 6 7 1 2 2 1 -1 -2 -2 -1 位于（i,j）的马可以走到的新位置是在棋盘范围内的（I+数组1[h],j+数组2[h]）,其中h=0，1，…7。 每次在多个可走位置中选择其中一个进行试探，其中未曾试探过的可走位置用适当栈结构妥善管理，也备试探失败时的“回溯”（悔棋）使用，即用栈结构存储试探的路径来进行路径试探操作。 3.3[主要算法设计] 3.3.1栈类的定义和接口: template class MyStack {private:Type *bottom; // 元素存放的动态数组 int size,ptr; // 堆栈大小和当前栈顶元素索引 inline int extent(){…}; //当栈满时,自动扩充 public: //构造函数 MyStack() {bottom=new Type[BASESIZE];ptr=-1;size=BASESIZE;};//用默认大小初始化

马踏棋盘非递归算法

#include struct point { int x,y;//马的位置 int dir;//这一次马行走的方向 }; struct stack { point p[64];//存储马的位置，方便回溯 }; int board [8][8]; int Htry1[8]={-2,-1,1,2,2,1,-1,-2}; int Htry2[8]={1,2,2,1,-1,-2,-2,-1}; bool chech[8][8]={0};//标记位置是否已经被占用 int main() { int i,j; int top=0; int z; cout<<"请输入马的初始位置"; cin>>i; cin>>j; stack sta; sta.p[top].x=i; sta.p[top].y=j; board [i][j]=top; chech [i][j]=true; int nx; int ny; for(int u=0;u<64;u++) sta.p[u].dir=0;//把每个结点的dir清零 for(z=0;;) { if(sta.p[top].x+Htry1[z]>=0&&sta.p[top].x+Htry1[z]<8&& sta.p[top].y+Htry2[z]>=0&&sta.p[top].y+Htry2[z]<8&& !chech [sta.p[top].x+Htry1[z]][sta.p[top].y+Htry2[z]]//检查要走的下个位置是否可行 ) { nx=sta.p[top].x+Htry1[z];

ny=sta.p[top].y+Htry2[z]; sta.p[top].dir=z; top++; sta.p[top].x=nx; sta.p[top].y=ny; board [nx][ny]=top; chech [nx][ny]=true; z=-1; } else if(z==7)//如果不可行，而且是最好一次检查 { chech [sta.p[top].x][sta.p[top].y]=false; top--; while(1) { z=sta.p[top].dir; if(z!=7) break; else { chech [sta.p[top].x][sta.p[top].y]=false; top--; } } } if(top==-1||top==63)break;//如果回溯到-1，或者栈满，则退出循环 z++; } for(i=0;i<8;i++) { for(j=0;j<8;j++) cout<

数据结构实验报告马踏棋盘

目录 1 课程设计的目的 (x) 2 需求分析 (x) 3 课程设计报告内容 (x) 1、概要设计 (x) 2、详细设计 (x) 3、调试分析 (x) 4、用户手册 (x) 5、测试结果 (x) 6、程序清单 (x) 4 小结 (x) 5 参考文献 (x) 2011年5月23日 1、课程设计的目的 （1）熟练使用栈和队列解决实际问题； （2）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； （3）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； （4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 2、需求分析 *问题描述：将马随机放在国际象棋的8X8棋盘Bo阿rd[0..7,0..7]的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入8X8的方阵输出之。 *测试数据：由读者指定,可自行指定一个马的初始位置。 *实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。 3、课程设计报告内容 根据分析先建了2个结构体 struct PosType //马的坐标位置类型 {

int m_row; //行值 int m_col; //列值 }; struct DataType //栈的元素类型 { PosType seat; //马在棋盘中的“坐标位置” int di; //换方向的次数 }; chess::chess() bool chess::chessPath(PosType start) //在棋盘中进行试探寻找下一步位置并同时记录位置，以及涉及到的入栈出栈 void chess::Print() //打印马走的路径 PosType chess::NextPos(PosType a,int di)//根据当前点的位置a和移动方向di，试探下一位置 4、总结 一、这次课程设计的心得体会通过实践我的收获如下： 1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。 2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。 二、根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点： 1、认真上好专业实验课，多在实践中锻炼自己。 2、写程序的过程中尽量在正确的基础上追求简洁。 3、在做设计的时候要有信心，有耐心，切勿浮躁。 4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用，不过也不能完全依赖课本。 5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。 6、参考文献 （1）万健主编，数据结构实用教程（C++版），电子工业出版社，2011 （2）网上搜索相关程序作为参考 7、程序运行结果：

数据结构课程设计 马踏棋盘求全部解及演示程序

安徽工程大学信息10 课程设计 马踏棋盘的求解及演示设计 摘要 数据结构是计算机科学与技术专业的一门核心专业基础课程，是一门理论性强、思维抽象、难度较大的课程。我认为学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，我们应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。《数据结构》课程设计是计算机科学技术专业集中实践性环节之一，是学习完《数据结构》课程后进行的一次全面的综合练习。开设本课程设计实践的主要目的就是要达到理论与实际应用相结合，提高学生的动手能力，完成计算机应用能力的培养；本课程设计主要解决马踏棋盘的问题，找出踏遍棋盘的多种路径，并实现动态要是过程。 马踏棋盘问题，实际上是图论中的哈密顿通路问题，是典型的NP问题,求解的问题与算法设计有很大关系，如果采取穷举搜索的话，很容易陷入海量搜索的状态，耗费巨大的时间，使问题几乎不可解，因此马在棋盘上遍历采用算法当中的深度优先算法和启发式贪心算法，用栈来存储遍历过程，通过对栈的使用实现对所有路径的搜索。在调试过程发现，启发式贪心算法，针对于马踏棋盘问题有着极大的好处，就是无论从棋盘上哪个点开始，找到一条遍历完棋盘的通路是不需要回溯的，也就节省了大量的时间，而试探性的操作对于每个点都也只有168步，所以求出所有路径在不到一秒的时间内完成。 关键词：马踏棋盘；骑士周游；哈密顿通路;NP-完全问题；贪心算法；回溯法；

目录 马踏棋盘的求解及演示设计......................... 错误！未定义书签。目录........................................... 错误！未定义书签。第一章引言................................. 错误！未定义书签。第二章需求分析................................. 错误！未定义书签。 2.1问题描述....................................... 错误！未定义书签。 2.2基本要求....................................... 错误！未定义书签。 2.3具体需求....................................... 错误！未定义书签。 2.4开发环境....................................... 错误！未定义书签。第三章概要设计................................. 错误！未定义书签。 3.1 系统概述....................................... 错误！未定义书签。 3.2 系统描述....................................... 错误！未定义书签。 3.3逻辑设计....................................... 错误！未定义书签。第四章详细设计................................. 错误！未定义书签。 4.1 功能模块设计.................................. 错误！未定义书签。 4.2 数据结构设计.................................. 错误！未定义书签。 4.3算法设计....................................... 错误！未定义书签。第五章调试与分析............................... 错误！未定义书签。 5.1 调试分析....................................... 错误！未定义书签。第六章系统试用说明............................. 错误！未定义书签。 6.1 系统试用说明................................... 错误！未定义书签。第七章总结与体会............................... 错误！未定义书签。参考文献......................................... 错误！未定义书签。

马踏棋盘 正式作业

数据结构与算法分析课程设计报告 设计题目：马踏棋盘 专业计算机科学与技术 学号 姓名 年月日

<<马踏棋盘>> 数据结构课程设计 概要设计 功能模块化分析 通过对问题描述的分析，可知马踏棋盘问题所要求实现的功能大致由三个部分组成： ⑴接收用户输入的马的起始位置； ⑵从起始位置开始在棋盘上标记马按问题描述中的行走规则访问棋盘中每个格子的顺序； ⑶输出棋盘上标记的访问顺序。 系统结构的总体设计 ⑴输入模块：提示用户输入数据，接收用户输入的数据，即马的起始位置，并判断该位置是否在棋盘内。若该起始位置在棋盘内，则接着执行下一模块的功能；若该起始位置不在棋盘内，则提示用户输入无效，并要求用户再次输入； ⑵初始化模块：初始化所有的数据结构中的数据； ⑶棋盘遍历模块：采用特定算法，按照马的行走规则对棋盘进行遍历，每次访问一个格子时，要测试该格子是否在棋盘范围内，保存马的访问顺序； ⑷位置测试模块：接收格子的x和y坐标，判断该格子是否在棋盘内，然后根据该格子是否在棋盘内返回不同的信号； ⑸输出模块：将棋盘遍历模块中保存下来的讯号进行输出，输出格式遵从棋

盘格式； ⑹总控模块：负责调用个处理模块，完成马踏棋盘问题的求解。 处理方式设计 针对问题和核心模块，采用深度优先遍历思想和回溯算法的非递归形式。 ⑴深度优先遍历的基本思想 深度优先遍历可以从任意顶点开始访问图的顶点，然后把该顶点标记为已访问。在每次迭代的时侯，该算法紧接着处理与当前顶点邻接的未访问顶点。如果有若干个这样的顶点，可以任意选择一个顶点。凡在实际应用中，选择哪一个邻接的未访问候选顶点主要是由表示图的数据结构决定的。 ⑵回溯算法的基本思想 回溯法是穷举查找技术的一个变种。它每次只构造解的一个分量，然后按照下面的方法来评估这个部分构造解。如果一个部分构造解可以进一步构造而不会违反问题的约束，我们就接受对解的下一个分量所做的第一个合法选择。如果无法对下一分量进行合法的选择，就不必对剩下的任何分量再做任何选择了。在这种情况下，该算法进行回溯，把部分构造解的最后一个分量替换为它的下一个选择。 详细设计 详细设计的主要任务是根据概要设计对每个模块的定义进行设计，以实现其功能算法和外部接口所要求的模块内部的数据结构和程序的逻辑结构。 详细设计的目标有两个：实现模块功能的算法要逻辑上正确和算法描述要简明易懂。设计主要采用的工具是程序流程图。

马踏棋盘贪心算法

马踏棋盘的贪心算法实现 问题描述： 将马放到国际象棋8*8棋盘的某个方格上，马按照“马走日”的规则移动。为马寻找一条走遍棋盘每一格并且只经过一次的路径，并将数字1、2、3、、、、64依次填入到8*8 的方格中。 问题分析： 国际象棋中 "马"的移动规则叫做"马走日"。它下一步可移动的位置有8个，但是如果"马"位于棋盘的边界附近，它下一步可移动到的位置就不一定有8个了，因为要保证"马"每一步都走在棋盘中。 马踏棋盘的问题其实就是要将1，2，…，64填入到一个8*8的矩阵中，要求相邻的两个数按照"马"的移动规则放置在矩阵中。将矩阵填满并输出。这样在矩阵中从1，2…遍历到64就得到了马踏棋盘的行走路线。因此本题的最终目的是输出一个8*8的矩阵，在该矩阵中填有1，2…64这64个数字，相邻数字之间遵照"马走日"的规则。 假设最开始"马"位于棋盘的(0,0)的位置，接下来"马"有两处位置可走，即(1,2)和(2,1)。这时"马"是无法确定走2的位置最终是正确的，还是走3的位置最终是正确的。因此"马"只能任意先从一个路径走下去（例如从2的位置）。如果这条路是正确的，那当然是幸运的，如果不正确，则"马"要退回到第一步，继续从3的位置走下去。以后"马"走的每一步行走都遵循这个规则。这个过程就是一种深度搜索的过程，同时也是一种具有重复性操作的递归过程。 "马"的行走过程实际上就是一个深度探索的过程。"探索树"的根结点为"马"在棋盘中的初始位置（这里用4*4的棋盘示意）。接下来"马"有两种行走方式，于是根结点派生出两个分支。而再往下一步行走，根结点的两个孩子又能够分别派生出其他不同的"行走路线"分支，如此派生下去，就得到了"马"的所有可能的走步状态。探索树的叶子结点只可能有两种状态：一是该结点不能再派生出其他的"走步"分支了，也就是"马"走不通了；二是棋盘中的每个方格都被走到，即"马"踏遍棋盘。于是从该探索树的根结点到第二种情况的叶结点构成的路径就是马踏棋盘的行走过程。 贪心算法描述： 在此对上述方法进行改进。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法就是贪心算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。

数据结构 马踏棋盘

实现顺序栈或循环队列的存储 一需求分析 1.1 理解栈的特性“后进先出”和队列的特性“先进先出”。仅仅认识到栈和队列是两种特殊的线性表是远远不够的，本次实验的目的在于更深入的了解栈和队列的特性，以便在实际问题背景下灵活运用他们。在了解他特性的基础上，还将巩固对这种结构的构造方法的理解。 1.2 要求：在国际象棋8×8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。编制程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，并输出它的行走路线（棋盘如图所示）。 输入：任意一个起始位置； 输出：无重复踏遍棋盘的结果，以数字1-64表示行走路线。 0 1 2 3 4 5 6 7 0 8 1 1 7 2 2 H 3 6 3 4 5 4 5 6 7 二概要设计 为了实现上述程序功能，可以采用顺序栈或者链栈来存储它的数据，本实验所需要的存储空间不是很大，不需动态的开辟很多空间，所以采用相对简单的顺序栈来存储数据，既方便有简单，而用链栈在实现上相对比顺序栈复杂的一点。

2.1顺序栈的抽象数据类型定义： ADT Stack{ 数据对象：D={ai| ai∈（0，1，…，9），i=0,1，2，…，n，n≥0} 数据关系：R={< ai-1, ai >| ai-1, ai∈D,i=1,2，…，n} } ADT Stack 2.2本程序包含三个模块： 1、主程序模块： void main(){ 定义变量； 接受命令； 处理命令； 退出； } 2、起始坐标函数模块——马儿在棋盘上的起始位置； 3、探寻路径函数模块——马儿每个方向进行尝试，直到试完整个棋盘； 4、输出路径函数模块——输出马儿行走的路径； 2.3各模块之间的调用关系： 主程序模块 输入的初始位置是否正确 否 是 起始坐标函数模 探寻路径函数模 输出路径函数模 结束

数据结构马踏棋盘

实验二：栈和队列及其应用 题目：马踏棋盘 班级：姓名：学号： 一、问题描述 设计一个国际象棋的马踏遍棋盘的演示程序。 二、基本要求 将马随机放在国际象棋的8*8的棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。 编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1,2，……，64依次填入一个8*8的方阵，输出之。 三、概要设计 1.定义头文件和预定义 #include #define MAXSIZE 100 #define N 8 2.起始坐标函数：void InitLocation(int xi,int yi); 3.探寻路径函数：int TryPath(int i,int j); 4.输出路径函数：void Display(); 5.主程序：void main(); 四、详细设计 1.函数声明 void InitLocation(int xi,int yi); //马儿在棋盘上的起始位置坐标int TryPath(int i,int j); //马儿每个方向进行尝试，直到 试完整个棋盘 void Display(); //输出马儿行走的路径 2. 起始坐标函数模块 void InitLocation(int xi,int yi) { int x,y; //定义棋盘的横纵坐标变量

top++; //栈指针指向第一个栈首 stack[top].i=xi; //将起始位置的横坐标进栈 stack[top].j=yi; //将起始位置的纵坐标进栈 stack[top].director=-1; //将起始位置的尝试方向赋初值 board[xi][yi]=top+1; //标记棋盘 x=stack[top].i; //将起始位置的横坐标赋给棋盘的横坐标 y=stack[top].j; //将起始位置的纵坐标赋给棋盘的纵坐标 if(TryPath(x,y)) //调用马儿探寻函数，如果马儿探寻整个棋盘 返回1否则返回0 Display(); //输出马儿的行走路径 else printf("无解"); } 3. 探寻路径函数模块 int TryPath(int i,int j) { int find,director,number,min;//定义几个临时变量 int i1,j1,h,k,s; //定义几个临时变量 int a[8],b1[8],b2[8],d[8];//定义几个临时数组 while(top>-1) //栈不空时循环 { for(h=0;h<8;h++) //用数组a[8]记录当前位置的下一个位置的可 行路径的条数 { number=0; i=stack[top].i+Htry1[h]; j=stack[top].j+Htry2[h]; b1[h]=i; b2[h]=j; if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8) //如果找到下一位置 { for(k=0;k<8;k++) { i1=b1[h]+Htry1[k];