搜索
课程设计说明书课程名称：数据结构设计题目：马的遍历院系：计算机科学与信息工程学院学生姓名：学号：专业班级：指导教师：2015年6月7日课程设计任务书设计题目马的遍历学生姓名所在院系计算机科学与信息工程学院专业、年级、班设计要求：任意行列数的棋盘中，马只能走“日”字。马从任意位置处出发，把棋盘的每一格都走一次，且只走一次。要求在屏幕上画出棋盘和马所有经过的路径。学生应完成的工作：1.分析题目要求2.利用数据结构和c语言知识找出实现方法3.编程完成实现4.按要求撰写课程设计报告和设计总结。参考文献阅读：1.《c程序设计（第四版）》，谭浩强清华大学出版社2.《数据结构（c语言版）》，严蔚敏吴伟民清华大学出版社工作计划：1.接到题目后用课余时间设计程序，2.第14周上机调试通过后，答辩，交报告（具体时间由各任课教师决定）。任务下达日期：2015年4月28日任务完成日期：2015年6月6日指导教师（签名）：学生（签名）：马的遍历摘要：中国象棋中马采用“日”字走法，对棋盘上马所在的结点，一步内到达的结点最多有八个，所以可以采用类似图的深度优先遍历，以马所在点为初始点对整个棋盘进行遍历。然后按遍历的顺序输出结点可以用一个二维数组chess[][]来表示棋盘，一开始用来存放步骤号，若走过了则把它赋值为0。对于动态演示问题，只要在“马”的位置显示“马”，已经走过的位置显示“●”，未走过的位置显示“┌”“┬”“┐”“├”等制表符，然后清屏，显示下一步，再清屏，依次类推。关键词：深度优先遍历；回溯法；数组存储棋盘；动态演示；目录1.设计背景..........................................................................................................................11.1问题描述.................................................................................................................................11.2基本要求.................................................................................................................................12.设计方案..........................................................................................................................12.1问题分析和任务定义.......................................................................................................12.2概要设计和数据结构的选择........................................................................................23.方案实施..........................................................................................................................33.1数据结构设计.......................................................................................................................33.2功能函数设计.......................................................................................................................43.3编码实现.................................................................................................................................54.结果与结论.....................................................................................................................144.1输入初始数据....................................................................................................................144.2判断能否遍历....................................................................................................................144.3动态演示..............................................................................................................................145.收获与致谢.....................................................................................................................156．参考文献.........................................................................................................................1511.设计背景1.1问题描述：中国象棋是10*9的棋盘，马的走法是“马走日”，这里忽略了“蹩脚马”的情况，使马的遍历问题简单化。马在棋盘上遍历采用算法当中的优先算法和回溯法；从入口出发，按某一方向向前探索，若能走通并且从未走过，即某处可到达，则到达新店，否则探索下一个方向；如果发生“阻塞”的情况，就是后面走不通的情况，则沿原路返回到前一点，换一个方向再继续试探，知道找到一条通路，或无路可走又返回到入口点。期盼中马的遍历采用数组进行存储，同时因为有回溯，所以采用栈的方法，并且为了最后打印方便，采用的是顺序栈的方法。同时还有八个方向的数组，和为栈设计的每个点周围的八个方向那些可以走的数组。1.2基本要求：棋盘有10行9列，利用chess来表示一个棋盘，chess[i][j]=0或1；其中0表示通路，1表示不通，当从某点向下试探时，中间点的8个方向可以试探；棋盘采用数组形式，并且这里的数组比棋盘的数组规模稍大，因为为了保证边缘点也有八个方向可以走，使问题能够简单化，不用再判断当前点的试探方向有几个。2.设计方案2.1问题分析和任务定义：中国象棋中马采用“日”字走法，对棋盘上马所在的结点，一步内到达的结点最多有八个，即假设马所在点的坐标为（i，j），那么其它八个结点的坐标为（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-2,j+1）,（i-1,j+2）把这些点看作马所在2点的邻接点，所以可以采用类似图的深度优先遍历，以马所在点为初始点对整个棋盘进行遍历。然后按遍历的顺序输出结点可以用一个二维数组chess[][]来表示棋盘，一开始用来存放步骤号，若走过了则把它赋值为0。对于动态演示问题，只要在“马”的位置显示“马”，已经走过的位置显示“●”，未走过的位置显示“┌”“┬”“┐”“├”等制表符，然后清屏，显示下一步，再清屏，依次类推。棋盘的规格限制在20*20以内，起始点当然不能超出棋盘的范围，每输入一组数据，首先判断是否可以全部走完，如果可以，则动态演示，否则重新输入数据。2.2概要设计和数据结构的选择：该算法需要定义一个二维数组chess[][]用来表示棋盘，整形变量step存放步骤号，count存放运算次数。定义8个函数(f1,f2,f3,f4,f5,f6,f7,f8)用来表示按8种规则走，定义一个h函数用来统计8种规则中有几种是可走的，再定义一个test函数用来测试是否可以走完，如果可以走完则返回值为1，否则返回0。test函数和f1,f2,f3,f4,f5,f6,f7,f8八个函数是一个递归调用关系。然后通过主函数调用test函数，实现动态演示功能。具体过程见下图：33.方案实施3.1数据结构设计：同上面述，棋盘采用数组形式，并且这里的数组比棋盘的数组规模稍大，因为为了判断的方便，这里在棋盘周围个加了两层“墙”。具体数据结构定义如下：intchess[23][23]/*chess[23][23]用来表示棋盘；intf1(intx,inty),f2(intx,inty),f3(intx,inty),f4(intx,inty),f5(intx,inty),f6(intx,inty),f7(intx,inty),f8(intx,inty);/*申明函数，这些函数就是用来表示八种走的规则*/inth(intx,inty)4/*h函数用来测试（x，y）位置处，下一步可以跳的位置数，返回值为sum*/{intsum;/*用来记录下一步可以跳的位置数*/sum=0;if(chess[x-1][y-2]==0)sum++;if(chess[x-2][y+1]==0)sum++;if(chess[x+2][y+1]==0)sum++;if(chess[x+2][y-1]==0)sum++;if(chess[x-2][y-1]==0)sum++;if(chess[x-1][y+2]==0)sum++;if(chess[x+1][y-2]==0)sum++;if(chess[x+1][y+2]==0)sum++;return(sum);/*每找到一个位置sum++，最后返回sum值就是在(x,y)处可走的位置数*/}3.2功能函数设计：（1）测试函数模块inttest(intx,inty)/*test函数测试第step步为(x,y)位置的情况下，是否可以走完棋盘，如果可以返回1,否则返回0*/（2）主函数：voidmain()5进入主函数后提示用户输入棋盘大小，只能输入小于23的数，其他的数字则提示输入错误，重新输入。然后提示输入起点位置，这里的起点位置就是日常生活观念中的顺序，开始点是(1,1),而不是数组中的初始位置(0,0),输入错误则提示重新输入。3.3编码实现：#includestdio.h#includeiostreamintchess[23][23],step=0,m=0,n=0,count=0;/*chess[23][23]用来表示棋盘；step是步骤数；m和n是棋盘的规格行和列；count是运算次数；*/intf1(intx,inty),f2(intx,inty),f3(intx,inty),f4(intx,inty),f5(intx,inty),f6(intx,inty),f7(intx,inty),f8(intx,inty);/*申明函数，这些函数就是用来表示八种走的规则*/inth(intx,inty)/*h函