马踏棋盘 数据结构实践报告

1、主板问题摘要：棋盘在国际象棋8X8棋盘上，根据国际象棋规则中马的移动规则，在任意初始位置，每个正方形只进入一次，在整个棋盘上旋转64个正方形。了解堆栈的“后进先出”特性，并学习如何使用回溯。关键字：节板、递归、堆栈、回溯1.简介棋盘在国际象棋8X8棋盘上，根据国际象棋规则中马的移动规则，在任意初始位置，每个正方形只进入一次，在整个棋盘上旋转64个正方形。依次填充8，8个正方形，然后输出那条路。1，2. 64输出8，8个正方形。输入：任意起始位置；输出：没有重复踩踏棋盘的结果，行走路径显示为数字1-64。2.需求分析(1)如果需要输出一个8X8板，可以采用二维阵列方式实现。(2)输入马的起始位置

2、。必须确保输入的数字在规定的范围内，即0=X=7，0=Y=7。(3)确保马不会旅行和重复整个棋盘。(4)在棋盘上输出马的步行路线，把数字1，2，3显示为64。(。3.设计数据结构使用堆叠阵列作为储存结构。#define maxsize 100Structint I；int j；Int director stackmaxsize；4.算法设计4.1末的起始坐标Void location(int x，int y) /初始化马的位置坐标塔Stacktop。I=x；/堆叠起始位置的横座标Stacktop。j=y；/堆叠起始位置的垂直座标Stacktop。director=-1；axy=top 1；/标

3、签板Try(x，y)；/探险的马的步行路径4.2路径导航函数Void Try(int i，int j)int count，find，min，directorInt i1、j1、h、k、s；Intb 8=-2，-2，-1，1，2，1，-1，c 8=1，-1，-2，-2，-1，1，1/存储当前位置行和列坐标的每个马出口的增量数组Int b28，B18；for(h=0)；h=7；H) /将当前位置下一个位置的可执行路径中的条形数记录为数组b18 count=0；I=stacktop。I ch；J=stacktop。j bh；If(i=0i=7j=0j=7aij=0) /如果找到以下位置for(k=0

4、)；k=7；k)i1=I ck；J1=j bk；if(i1=0i1=7j 1=0 J1=7ai1J1=0)/如果找到以下位置计数；/记录条带数B1h=count；/b18上的条带for(h=0)；h=7；H) /根据可能路径栏数的大小，将其放入从最小到最大的排列的b28 min=9；for(k=0)；k=7；k)If(minb1k)min=B1k；B2h=k；s=k；B1s=9；find=0；Director=stacktop。directorfor(h=director 1)；h=7；H )/沿8方向查找I=stacktop。I cB2h；J=stacktop。j bB2h；if(I=0i=

5、7j=0j=7aIj=0)stacktop。director=h；/存储堆栈的查找方向塔/堆栈Stacktop。i=iStacktop。j=jStacktop。director=-1；/重新初始化下一个堆栈的方向aIj=top 1；find=1；/寻找下一个位置BreakIf(find！=1) astacktop。I stack top。j=0；/清除棋盘的显示塔-；/堆叠后If(top63)Try(i，j)；/递归4.3输出函数Void display()Int i、j；for(I=0)；I=7；I) for(j=0)；j=7；j)Printf(t%d ，aIj)；/汇出马的穿越路径prin

6、tf(“ n n”)；printf(“ n”)；5.程序实施5.1主函数Void main()Int i、j、x、y；for(I=0)；I=7；I) /初始化主板for(j=0)；j=7；j)aIj=0；输入printf( x y(0=0x=7y=0y=7)/确认输入的起始位置正确位置(x，y)；display()；Else printf(“错误 n”)；5.2执行结果(1)输入未满足时(2)正确输入时5.3算法分析(1)马的起始坐标开始包含横坐标、坐标和方向的堆叠阵列。输入马的起始位置，进入坐标起始函数，输入的横坐标和纵坐标进入堆栈，初始化方向，显示指示此位置已经过去的棋盘。位置将进入堆栈中

7、的第一个元素：路径导航函数。(2)路径导航函数路径导航函数有两个增量数组，每个出口对应于当前位置行和列坐标。要想让马在所有棋盘上漫游，必须有一定的步态法则。正在记录当前位置下一个位置的可执行路径中的条数，并按从最小到最大的顺序存储在一维数组中。开始导航，分别在8个方向导航，找到一个方向后，存储堆栈的搜索方向，重新初始化堆栈的搜索方向，将此位置显示为二维数组，然后使用递归导航到下一个新导航。如果在任何导航中找不到方向，请清除该位置的标记，清空堆栈，然后递归返回到最后一个查找方向(以前保存堆栈的查找方向)，跳过已找到的方向并执行导航，直到所有主板都旅行为止。(3)输出函数马在所有棋盘上漫游时，输出马的步行路线。因为以前把马的行走路径记录在二维排列中。此时，只需输出二维阵列的标记。6.设计经验这次讲座设计学到了很多，进一步加深了我对堆栈的理解，使使用更加熟练。在此之前，我并不是特别熟悉逆向归纳法，但这次设计让我学到了逆向归纳法的基本概念和基本用法。一件事有多种方法的时候，我们要集合所有方法，形成一个集合，然后利用一定的规律调用这个集合内的方法。起初我不能让马转动所有的棋盘，但知道回溯思想后，我修改了我的算法，最终让马转动了所有的棋盘。此外，考虑递归和非递归问题，两种方法测试的结果时间复杂度也没有太大差异(显