《数据结构马踏棋盘课程设计报告》由会员分享，可在线阅读，更多相关《数据结构马踏棋盘课程设计报告（20页珍藏版）》请在金锄头文库上搜索。
1、附件 2：课程设计任务书学生姓名： 朱涛涛 专业班级： 0506 班 指导教师： 袁小玲 工作单位： 计算机科学系 题 目: 马踏棋盘的程序设计 初始条件：设计一个国际象棋的马踏遍棋盘的演示程序。将马随机放在国际象棋的 88 棋盘 Board88的某个方格中，马按走棋规则（见题集 p98）进行移动。要求每个方格只进入一次，走边棋盘上全部 64 个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字 1,2,3,64 依次填入一个 88的方阵，输出之。测试用例见题集 p98。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式
2、用 A4 纸打印（书写） ，并应包含如下内容： 1、 问题描述简述题目要解决的问题是什么。2、 设计存储结构设计、主要算法设计（用类 C 语言或用框图描述） 、测试用例设计；3、 调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4、 经验和体会（包括对算法改进的设想）5、 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出，6、 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为 0 分。时间安排：1、第 18 周（7 月 2 日至 7 月 8 日）完成。2、7 月 9 日 10：00 到计算中心检查程序、交
3、课程设计报告、源程序（CD 盘） 。指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日一. 问题描述本程序是一个马踏棋盘的演示程序,主要的问题描述为:在一个空白的 8*8 格的棋盘上,对于任意的输入坐标(18),表示马从此坐标开始以”日” 字走法,遍历整个棋盘,要求在整个遍历的过程中,每一个方格只走一次,不能重复.且在设计中不能使用递归的算法.本程序特点:我在程序中引用了一个 WINDOWS API,先算出全部的步法关键点,再在程序中画一个方格,然后在方格中按顺序输出各个值,运用了控制台的定位函数,能依次一步步把1,2,3,4,. ,64 这样的序列填入各个坐标中去,使得马的遍历
4、过程像动画一样的演示,一目了然.二. 设计1.存储结构设计#define CHESSBOARD 8typedef int chessboardCHESSBOARDCHESSBOARD;这个数组是整个棋盘的所有方格的集合.typedef struct stepintx,y; /the x-postion and y-position of a stepintdirection;/the last direction has stepped * pStep;上面这个结构体是用于保存在马踏棋盘的过程中所以经历的每个方格的坐标,以及对下一个方格的访问方向.struct stack_steppStep
5、pBase;pStep pTop;int total_size;这个结构体是一个栈的存储结构,用于保存已经遍历过的信息,用于在遍历过程中的回溯问题.2.主要算法设计（用类 C 语言或用框图描述）本程序的思想为:假设图中” 0”所在的点为任何一点 (中间点), 则可知道,对于当前的点”0”可以有 18 这八个方向的跳法 ,使得程序继续遍历下去 ,本程序正是采用的这 18 八个方向,且也是按这 8 个优先级进行搜索的,程序会对访问过的点的坐标和方向全压入堆栈中去,以便回溯,假设当遍历到” 1”时会出现死路的现象,此时会用 GetTop()返回当前堆顶元素,即”0” ,然后按 ”2”的方向进行搜索,
6、直到8 个方向全是死路时” 0”出栈 ,然后退回上一层结点 .如此循环,直到找出正确的顺序.本程序所使用的算法函数如下:void SetPos(int nX, int nY);void frame(int x, int y, int width, int height);/ the funcions below operate on stack_step;void Init_Stack(stack_stepbool IsEmpty(stack_step steps);bool Push(stack_stepvoid GetTop(stack_stepbool Converse(stack_st
7、epvoid Destroy(stack_step/the function below operate on getting the initial position of horsevoid Get_Position(intbool Can_Move(chessboard cb,int x,int y,int dir);/the function below is the kernel of this programvoid Move(intvoid Kernel_Run(chessboard chess,stack_stepvoid Show(stack_step& steps/*the
8、 order in steps is right*/,int y);其中有几个是对栈的常规操作函数,其它的有试探函数等,这里重点只讲一个函数,就是上述中黑体的函数,其详细的过程请看代码的注释部分.void Kernel_Run(chessboard chess,stack_step& steps,int x,int y)/本函数根据初始的 x,y(based on 18)进行对 chess 的全盘搜索,并会/将成功遍历后经过的各个坐标点依次压入 steps 堆栈中去intcount=1; /记录已经正确填入了多少个空格int xpos=x-1,ypos=y-1; / 保存当前的 x 和 y 的
9、坐标值int dir=1; / 当然马向下一个坐标跳过的方向int i, j,k=0; / 循环变量long p=1; /此变量用于在长时间的循环试探过程中向屏幕打点计数/用的step currentstep; /当前的马步assert(IsEmpty(steps); 在初始状态下,用于保存马步的栈应为空/初始化整个棋盘为 0for(i=0;i#include#include#include/the eight directions of a horse can run#define LEFT_UP 1#define UP_LEFT 2#define DOWN_LEFT 3#define LE
10、FT_DOWN 4#define RIGHT_DOWN 5#define DOWN_RIGHT 6#define UP_RIGHT 7#define RIGHT_UP 8#define CHESSBOARD 8 /the width and height of chessboard#define STACK_TOTAL 64#define STACK_INCREMENT 20typedef int chessboardCHESSBOARDCHESSBOARD;typedef struct stepint x,y; /the x-postion and y-position of a stepi
11、nt direction;/the last direction has stepped* pStep;structstack_steppStep pBase;pStep pTop;int total_size; void SetPos(int nX, int nY);void frame(int x, int y, int width, int height);/ the funcions below operate on stack_step;void Init_Stack(stack_stepbool IsEmpty(stack_step steps);bool Push(stack_s
12、tepbool Popup(stack_stepvoid GetTop(stack_stepbool Converse(stack_stepvoid Destroy(stack_step/the function below operate on getting the initial position of horsevoid Get_Position(intbool Can_Move(chessboard cb,int x,int y,int dir);/the function below is the kernel of this programvoid Move(intvoid Ke
13、rnel_Run(chessboard chess,stack_stepvoid Show(stack_step#endif/horse_main.cpp#include horse_head.hint main()int x,y;stack_step steps;chessboard chess;SYSTEMTIME st1,st2;int hour,min,sec;/ frame(0,0,30,30);Get_Position(x,y);Init_Stack(steps);:GetSystemTime(Kernel_Run(chess,steps,x,y);:GetSystemTime(h
14、our=st2.wHour-st1.wHour;min=st2.wMinute-st1.wMinute;sec=st2.wSecond-st1.wSecond;if(secdirection=s.direction;steps.pTop-x=s.x;steps.pTop-y=s.y;(steps.pTop)+;return true;bool Popup(stack_step& steps, step& s)if(IsEmpty(steps)return false;/ memcpy(steps.pTop)-;s.direction=steps.pTop-direction;s.x=steps
15、.pTop-x;s.y=steps.pTop-y;return true;void GetTop(stack_step& steps,step& s)if(IsEmpty(steps)exit(-1);/ memcpy(step* p=steps.pTop-1;s.direction=p-direction;s.x=p-x;s.y=p-y;void Destroy(stack_step& steps)if(steps.pBase=NULL)return ;free(steps.pBase);steps.pBase=steps.pTop=NULL;steps.total_size=0;void Get_Position(int& x,int& y)printf(-n);printf(input the initial position
