资源描述：
《数据结构课程设计_马踏棋盘》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、学号：2012812044杭州师范大学钱江学院课程设计题目马踏棋盘算法研究教学院信息与机电工程分院专业计算机科学与技术班级计算机1201姓名吴秋浩指导教师王李冬2013年12月21日目录一．概述2二．总体方案设计3三．详细设计4四．最终输出5五．课程设计总结6参考文献7一概述1.课程设计的目的（1）课题描述设计一个国际象棋的马踏遍棋盘的演示程序。（2）课题意义通过“马踏棋盘”算法的研究，强化了个人对“栈”数据结构的定义和运用，同时也锻炼了自身的C语言编程能力。另一方面，通过对“马踏棋盘”算法的研
2、究，个人对“迷宫”、“棋盘遍历”一类的问题，有了深刻的认识，为今后解决以此问题为基础的相关的问题，打下了坚实的基础。（3）解决问题的关键点说明解决问题的关键首先要熟练掌握C语言编程技术，同时能够熟练运用“栈”数据结构。另外，态度也是非常重要的。在课程设计过程中，难免会遇到困难，但是不能轻易放弃，要肯花时间，能静得下心，积极查阅相关资料，积极与指导老师沟通。2.课程设计的要求（1）课题设计要求将马随机放在国际象棋的8×8棋盘Board[0～7][0～7]的某个方格中，马按走棋规则进行移动。要求每个
3、方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出之。程序由回溯法和贪心法实现，比较两种算法的时间复杂度。（2）课题设计的思路首先，搞清楚马每次在棋盘上有8个方向可走，定义两个一位数组，来存储马下一着点的水平和纵向偏移量。程序再定义一个8*8二维数组，初始所有元素置0，起始点元素置1。若为回溯法，初始方向数据（一维数组下标）入栈。随后，马从起始点开始，每次首先寻找下一可行的着点，然后记下方向，方向数
4、据入栈，把该位置元素置为合适的序列号，若无下一可行着点，则回溯，寻找下一方向位置着点，以此类推，直到64填入数组中，则输出二维数组，即为马可走的方案。若为贪婪法，选择下一出口的贪婪标准是在那些允许走的位置中，选择出口最少的那个位置。直到没有下一着点位置，若此时已标记到64，则找到可行方案，输出之。反之，改变初始寻找方向继续寻找，直到8种方向顺序都试过，若还是没有合适的方案，则说明以该起始点开始马无法踏遍棋盘。二总体方案设计1.回溯法算法思想按深度优先策略，从一条路往前走，能进则进，不能进则退回来
5、，换一条路再试，也就是说每当前进的路不通，我们总是返回到前一次的岔路口，选择下一条新的路线。（1）函数头文件定义和宏定义#include#include#defineN8//便于改变棋盘大小（2）栈数据结构定义typedefstruct{intb[N*N];//记录每次走的方向inttop;//栈指针}SqStack;（3）定义探寻路径函数Board[N][N]模拟N*N棋盘，填入1,2,3···64。x、y传递初始位置。boolHorsePath(intB
6、oard[][N],intx,inty){//初始化栈//定义方向数组//intxx[8]={1,2,2,1,-1,-2,-2,-1};//intyy[8]={2,1,-1,-2,-2,-1,1,2};//初始方向下表入栈//回溯法开始寻找合适方案（详见“详细设计”）}（4）定义主函数voidmain(){//定义基本变量及Board[N][N]数组//输入初始位置x0，y0//调用HorsePath（Board,x0,y0）;//输出方案}1.贪心法算法思想从问题的某一个初始解出发逐步逼近给定
7、的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。该算法存在问题：1.不能保证求得的最后解是最佳的；2.不能用来求最大或最小解问题；3.只能求满足某些约束条件的可行解的范围。（1）函数头文件定义和宏定义#include#defineN8//便于改变棋盘大小（2）程序要用到的一些全局变量的定义intxx[8]={1,2,2,1,-1,-2,-2,-1};intyy[8]={2,1,-1,-2,-2,-1,1,2};//控制马能走的8个方向int
8、Board[N][N]={0};//初始棋盘所有位置可走(3)定义FeassiblePath//计算每个点的后续着点个数intFeassiblePath(intx,inty,intstart){//函数体(详见“详细设计”)}(4)定义NextPath/*找出一个着点的后续着点中可走方位最少的，把着点到后续点的方向记下返回主函数*/intNextPath(intx,inty,intstart){//函数体(详见“详细设计”)}(5)定义主函数voidmain(){//输入初始位置x0，y0//定
