数据结构课程设计

题目马的遍历问题。

系 (部) 电子与信息工程系。

班级 15级计算机科学与技术。

姓名白天宇。

学号2015022020

指导教师付争方。

2024年06月20日。

电子与信息工程系。

课程设计任务书。

计算机教研室制。

马的遍历问题。

白天宇。安康学院计算机科学与技术15级陕西省安康市 725000

摘要：中国象棋中马采用“日”字走法，对棋盘上马所在的结点，一步内到达的结点最多有八个，即假设马所在点的坐标为（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）把这些点看作马所在点的邻接点，所以可以采用类似图的深度优先遍历，以马所在点为初始点对整个棋盘进行遍历。然后按遍历的顺序输出结点。

关键字：象棋；遍历；数组。

中国象棋中马采用“日”字走法，对棋盘上马所在的结点，一步内到达的结点最多有八个，即假设马所在点的坐标为（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）把这些点看作马所在点的邻接点，所以可以采用类似图的深度优先遍历，以马所在点为初始点对整个棋盘进行遍历。然后按遍历的顺序输出结点。

可以用一个二维数组chess[来表示棋盘，一开始用来存放步骤号，若走过了则把它赋值为0。

对于动态演示问题，只要在“马”的位置显示“马”，已经走过的位置显示“●”未走过的位置显示等制表符，然后清屏，显示下一步，再清屏，依次类推。

棋盘的规格限制在20*20以内，起始点当然不能超出棋盘的范围，每输入一组数据，首先判断是否可以全部走完，如果可以，则动态演示，否则重新输入数据。

该算法需要定义一个二维数组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函数，实现动态演示功能。具体过程见下图：调。用。

调用递归调用。流程图：n

yyny首先从起始点开始看它的八个方向中有几个方向可以走，假如有5个方向可走，再看这5个位置下一步分别有几步可走，把这个值赋给一个数组s，再对数组进行从小到大排序，然后从5步中s值最小的走，依次递归，每次从s值最小的走，如果步骤号step等于棋盘规格m*n，则说明全部走完了；如果遇到无路可走的情况，step--，退回到上一步，当一直退到起始点时候，说明无法全部遍历。

main()

scanf("%d",&m);

scanf("%d",&n);/输入棋盘大小*/

scanf("%d",&x0);

scanf("%d",&y0);/初始位置*/

if((x0>=1&&x0<=m)&&y0>=1&&y0<=n))

if(test(x0+1,y0+1)==1)

输出棋盘；}

上机调试过程遇到主要问题是：当第一次的数据无解，再重新进入系统，输入一组正确的有解的数据时，可以演示，但是演示完最后一步后不能退出，按回车键仍然可以输出全是白点的棋盘，如果第一次输入超过范围的数据，再重新进入系统，则可以正常退出。经过重新仔细阅读程序，模拟计算机的运算，发现我一开始定义全局变量count(用来存放运算次数)，初值为0，尽管第一次运算的一组无解数据，但是计算机还是会运算并返回一个值（这个值会比较大），所以第二次数据数据时，count的初值不再是0，而第一次运算返回的那个比较大的值，而我在输出棋盘时用的又是cou=1;cou<=count;cou++循环，所以会不停的输出且不退出，如果输入数据超过范围，系统会先判断，而没有运算，count仍然为0。

所以我在运算无解后把count再赋值为0。

我一开始准备采用图的深度优先遍历，但是图的深度优先有个缺点，就是再找下一个遍历点时，总是在未遍历的点中随机找一个进行遍历。我对它进行了改进，对下一个可遍历点的可遍历点数进行排序，然后选择值小的那条路径进行遍历，这样减少了运算次数。提高了时间性能。

对于n*n的棋盘，该算法若遇到最好情况（即每次s的都为1），它时间复杂度为n2 ，最坏情况（每次s都为8）它时间复杂度为n16,所以时间复杂度在n2 和n16之间。空间复杂度为n2。

1）运行程序，进入欢迎界面，回车进入演示系统；

2）根据提示输入棋盘的行数（小于20的正整数）和列数（小于20的正整数），起始点。

的行坐标（小于棋盘行数的正整数）和列坐标（小于棋盘列数的正整数），若您输入的数据超出范围，系统将自动提示，您可以回车重新进入系统。若您输入完全符合要求，系统将正式开始运算；

3）若您输入的数据可以令马走完棋盘上全部的位置，系统将提示可以走完，您可以回。

车查看演示过程，每显示一步，您可以根据系统提示，回车演示下一步，马每走一步，系统会在走过位置上标记上白点，当走到最后一步时，您可以按任意键退出；若您输入的数据无解，即无法让马全部走完棋盘（如5x5的棋盘从第1行，第2列走），系统将提示您无法走完（对与于不同无解的情况，系统运算时间将不同，越复杂运算时间越长，所以提示可能会有点滞后），您可以回车重新进入系统数据新的数据。

注：程序编译运行环境为microsoft visual c++ 6.0

可以走完的情况：

动态演示（部分过程）

无解的情况：

#include <>

#include

int chess[23][23],step=0,m=0,n=0,count=0;

/* chess[23][23]用来表示棋盘；

step是步骤数；

m和n是棋盘的规格行和列；

count是运算次数；*/

int f1(int x,int y),f2(int x,int y),f3(int x,int y),f4(int x,int y),f5(int x,int y),f6(int x,int y),f7(int x,int y),f8(int x,int y);

/*申明函数，这些函数就是用来表示八种走的规则*/

int h(int x,int y) /h函数用来测试（x，y）位置处，下一步可以跳的位置数，返回值为sum */

int test(int x,int y) /test函数测试第step步为(x,y)位置的情况下，是否可以走完棋盘，如果可以返回1,否则返回0*/

int s[9],a[9];

int min,i,j,k;

count++;

step++;

chess[x][y]=step;

if(step==m*n)

return(1); 如果已经走到了m×n的话，表示满足结束条件，返回1 */

s[1]=h(x-2,y+1);/统计(x，y)处的下一步的八个位置的sum值*/

s[2]=h(x-1,y+2);

s[3]=h(x+1,y+2);

s[4]=h(x+2,y+1);

s[5]=h(x+2,y-1);

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了