马踏棋盘课程设计

1、课程设计题目1 问题描述 将马随机放在国际象棋的8*8棋盘board88的某个方格中，马按走棋规则进行移动，要求每个方格上只进入一次，走遍棋盘上全部64个方格2 基本要求（1） 采用图形界面实现该游戏。（2） 从键盘输入马的初始位置。（3） 编制程序，求出马的行走路线 ，并按求出的行走路线，将数字1，2，64依次填入一个8* 8的方阵，并输出之。3系统分析与设计3.1 数据结构逻辑结构为线性结构，用顺序栈。坐标点用已结构体来表示，并将其的位置放在sstep的栈中，而且将每走一步的坐标放在另一栈s1中3.2 算法设计1.程序框架及功能模块划分：2.设计功能的分析与实现void exit(poin

2、t p)参数：point 功能：计算出下一步可能位置,按其各个位置下一个位置的和压栈到s中 算法描述：接受参数传来的值，按次序加上int horizontal=2,1,-1,-2,-2,-1,1,2;int vertical=-1,-2,-2,-1,1,2,2,1;再根据legal函数来判断是否合法（x(07),y(07)）是，则保存在point ap中，再按各自下一步的数目从大到小排序。最后，将ap中的点压栈。int number(point p)参数：point 功能：找出当前位置下一步的各种可能位置,计算可能之和算法描述：接受参数传来的值，按次序加上int horizontal=2,1,

3、-1,-2,-2,-1,1,2;int vertical=-1,-2,-2,-1,1,2,2,1;再根据legal函数来判断是否合法（x(07),y(07)）是，则加1并将值返回void next(point p)参数：point 功能：/找出各个位置并将其步数记录算法描述：将其步数记录在board的相应位置，并将这点压栈到s1,判断步数是否小于64，再根据这四个条件选择执行其中的一个，再递归调用next.bool legal(point p)参数：point 功能：判断是否可行，合法（是否在棋盘上，是否走过）算法描述 ：用这样的语句if(p.x>=0)&&(p.x<

4、;n)&&(p.y<n)&&(p.y>=0)&&(boardp.xp.y=0)return true;elsereturn false;4 测试数据及结果 测试数据和运行输出及结果分析 输入x(0-7),y(0-7)0 0 1 34 3 18 49 32 13 16 4 19 56 33 14 17 50 31 57 2 35 48 55 52 15 12 20 5 60 53 36 47 30 51 41 58 37 46 61 54 11 26 6 21 42 59 38 27 64 29 43 40 23 8 45 62 25

5、10 22 7 44 39 24 9 28 63press any key to continue输入x(0-7),y(0-7)0 9输入不合法,重输入!输入x(0-7!),y(0-7!)4 5 30 27 10 49 40 25 8 5 11 48 29 26 9 6 39 24 28 31 56 45 50 41 4 7 47 12 51 42 19 44 23 38 32 57 46 55 52 1 18 3 13 64 53 60 43 20 37 22 58 33 62 15 54 35 2 17 63 14 59 34 61 16 21 36press any key to con

6、tinue5 总结调试过程中遇到的主要问题，是如何解决的；问题1：只走到63步原因：第64步就走完了，并且s62中只有一个元素，这个判断条件(sstep.base=sstep.top&&number(p2)=0)满足就进入了，而始终不能走完解决方法：改了判断条件，改为(sstep.base=sstep.top&&number(p2)=0)&&step!=n*n-1)解决方案：用initstack(s1)初始化问题3：冒泡排序超出边界原因：循环次数大解决方案：减少循环次数看了其他同学，都差不多，我已经按马的下一位置最难的先走，再走难度次之的位置。

7、函数的功能尽量单一，调用函数时要注意是否修改了其他参数的值。一定要静下心去做。调试也很重要，从中能知道错在哪里。用vc+一定要学会这功能。 6 附录：源程序清单/sqstack.h#pragma once#define ok 1#define error 0#define overflow -2#define stack_init_size8#definestackincrement 57typedef struct int x,y;point;typedef point selemtype;typedef int status;typedef struct selemtype * base;

8、selemtype * top;int stacksize;sqstack;status initstack(sqstack &s);status push(sqstack &s,selemtype e);status pop(sqstack &s,selemtype &e);/sqstack.cpp#include "sqstack.h"#include <stdio.h>#include <malloc.h>status initstack(sqstack &s)s.base = ( selemtype *

9、 )malloc(stack_init_size*sizeof(selemtype);if(!s.base) return overflow;s.top = s.base;s.stacksize = stack_init_size;return ok;status push(sqstack &s,selemtype e)if (s.top-s.base>=s.stacksize)s.base=(selemtype * )realloc(s.base,(stack_init_size+stackincrement)*sizeof(selemtype);if (!s.base)ret

10、urn overflow;s.top = s.base + s.stacksize;s.stacksize+=stackincrement;*s.top+ = e;return ok;status pop(sqstack &s,selemtype &e)if(s.top=s.base)return error;e = *-s.top;return ok;/horse.cpp#include <stdio.h>#include <malloc.h>#include "sqstack.h"int horizontal=2,1,-1,-2,

11、-2,-1,1,2;int vertical=-1,-2,-2,-1,1,2,2,1;int board88=0;int step=1;sqstack s65;sqstack s1;#define n 8void exit(point p);/计算出下一步可能位置，按其各个位置下一个位置的和压栈到s中int number(point p);/找出当前位置下一步的各种可能位置,计算可能之和void next(point p);/找出各个位置并将其步数记录bool legal(point p);/判断是否可行void main()point p;printf("输入x(0-%d),y(0

12、-%d)n",n-1,n-1);scanf("%d%d",&p.x,&p.y);while(!(p.x>=0)&&(p.x<n)&&(p.y<n)&&(p.y>=0)printf("输入不合法,重输入!n");printf("输入x(0-%d!),y(0-%d!)n",n-1,n-1);scanf("%d%d",&p.x,&p.y);initstack(s1);/初始化栈next(p);for (int

13、 i=0;i<n;i+)/打印棋盘for (int j=0;j<n;j+)printf("%5d",boardij);printf("n");int number(point p)/找出当前位置下一步的各种可能位置,计算可能之和point p1;int j=0;for(int i=0;i<8;i+)p1.x=p.x+horizontali;p1.y=p.y+verticali;if(legal(p1)j+;return (j);void next(point p)/找出各个位置并将其步数记录point p1,p2;initstack(s

14、step);boardp.xp.y=step;push(s1,p);if(step<n*n)exit(p);pop(sstep,p2);if (sstep.base=sstep.top&&number(p2)=0)&&step!=n*n-1)pop(s1,p1);boardp1.xp1.y=0;-step;while (sstep.base=sstep.top)pop(s1,p1);boardp1.xp1.y=0;step-; pop(sstep,p2);step+;next(p2);/退栈，悔棋else if(number(p2)=0&&

15、sstep.base!=sstep.top)pop(sstep,p2);step+;next(p2);else if (number(p2)!=0&&sstep.base=sstep.top)step+;next(p2);else step+;next(p2);void exit(point p)/计算出下一步可能位置，按其各个位置下一个位置的和压栈到s中point temp; point p1; int j=0; point ap8=0; for(int i=0;i<8;i+) p1.x=p.x+horizontali; p1.y=p.y+verticali; if(legal(p1) apj=p1; j+;/将下一步的可能位置储存在ap中for(int count=0;count<number(p)-1;count+) /使用冒泡法，对下一步的八个规则的从大到小排序 for(int k=0;k<number(p)-1;k+)if (number(apk)<number(apk+1)tem