马踏棋盘c报告数据结构课程设计

《马踏棋盘c报告数据结构课程设计》由会员分享，可在线阅读，更多相关《马踏棋盘c报告数据结构课程设计（6页珍藏版）》请在装配图网上搜索。

1、实现顺序栈或循环队列的存储一、实验目的(1) 、理解栈的特性“后进先出”和队列的特性“先进先出”。(2) 、仅仅认识到栈和队列是两种特殊的线性表是远远不够的，本次实验的目的在于更深入的了解栈和队列的特性，以便在实际问题背景下灵活运用他们。(3) 、在了解他特性的基础上，还将巩固对这种结构的构造方法的理解。二、实验环境(1) WindowsXP系统下(2) 编程环境：VC6.0+三、实验内容、要求：在国际象棋8X8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。编制程序，求出马的行走路线，并按求出的行走路线，将数字1,2,64依次填入一

2、个8X8的方阵，并输出它的行走路线(棋盘如图所示)。、输入：任意一个起始位置；输出：无重复踏遍棋盘的结果，以数字1-64表示行走路线。012345670811722H363454567(1) 、数据结构要求：采用顺序栈或者链栈实现。四、实验步骤为了实现上述程序功能，可以采用顺序栈或者链栈来存储它的数据，本实验所需要的存储空间不是很大，不需动态的开辟很多空间，所以采用相对简单的顺序栈来存储数据，既方便有简单，而用链栈在实现上相对比顺序栈复杂的一点。(一)、概要设计(1) 、顺序栈的抽象数据类型定义：ADTStack数据对象：D=ai|ai(0,1,9),i=0,1,2,n,n0数据关系：R=|a

3、i-i,a/D,i=1,2,nADTStack(2) 本程序包含三个模块：1、主程序模块：voidmain()定义变量；接受命令；处理命令；退出；2、起始坐标函数模块一一马儿在棋盘上的起始位置；3、探寻路径函数模块一一马儿每个方向进行尝试，直到试完整个棋盘；4、输出路径函数模块一一输出马儿行走的路径；各模块之间的调用关系:主程序模块起始坐标函数模探寻路径函数模输出路径函数模结束(二八详细设计(1)、定义头文件和预定义#include#defineMAXSIZE100#defineN8(2)、数据类型定义intboard88;/定义棋盘intHtry18=1,-1,-2,2,2,1,-1,-2;

4、intHtry28=2,-2,1,1,-1,-2,2,-1;/*存储马各个出口位置相对当前位置列下标的增量数组structStack/定义栈类型inti;/行坐标intj;/列坐标intdirector;/存储方向stackMAXSIZE;/定义一个栈数组inttop=-1;/栈指针/*存储马各个出口位置相对当前位置行下标的增量数组*/*/(3)、函数声明voidInitLocation(intxi,intyi);/intTryPath(inti,intj);/voidDisplay。；/马儿在棋盘上的起始位置坐标马儿每个方向进行尝试，直到试完整个棋盘输出马儿行走的路径(4)、起始坐标函数模块

5、voidInitLocation(intxi,intyi)intx,y;/top+;/stacktop.i=xi;/stacktop.j=yi;/stacktop.director=-1;/boardxiyi=top+1;/x=stacktop.i;/y=stacktop.j;/if(TryPath(x,y)/Display();/elseprintf(无解);定义棋盘的横纵坐标变量栈指针指向第一个栈首将起始位置的横坐标进栈将起始位置的纵坐标进栈将起始位置的尝试方向赋初值标记棋盘将起始位置的横坐标赋给棋盘的横坐标将起始位置的纵坐标赋给棋盘的纵坐标调用马儿探寻函数，如果马儿探寻整个棋盘返回1否则

6、返回0输出马儿的行走路径(5)、探寻路径函数模块intTryPath(inti,intj)intfind,director,number,min;inti1,j1,h,k,s;/定义几个临时变量定义几个临时变量inta8,b18,b28,d8;while(top-1)/for(h=0;h=0&i=0&j8)/如果找到下一位置for(k=0;k=0&i1=0&j18)如果找到下一位置记录条数/number+;/ah=number;/将条数存入数组a8中for(h=0;h8;h+)/min=9;for(k=0;kak)min=ak;dh=k;/根据可行路径条数小到大按下表排序放入数组将下表存入数组

7、d8中d8中s=k;as=9;director=stacktop.director;if(top=63)/return(1);find=0;/for(h=director+1;h=0&i=0&j8)/如果走完整个棋盘返回1/表示没有找到下一个位置向八个方向进行探寻如果找到下一位置find=1;/break;表示找到下一个位置boardstacktop.istacktop.j=0;/top-;/return(0);如果找到下一个位置进栈if(find=1)/stacktop.director=director;/top+;/stacktop.i=i;stacktop.j=j;stacktop.d

8、irector=-1;/boardij=top+1;/else/存储栈结点的方向栈指针前移进栈重新初始化下一栈结点的尝试方向标记棋盘否则退栈清除棋盘的标记栈指针前移退栈输出马儿在棋盘上走过的路径初始化棋盘(6)输出路径函数模块voidDisplay。inti,j;for(i=0;iN;i+)for(j=0;jN;j+)printf(t%d”,boardij);/printf(nn);printf(n”);(5)主程序模块voidmain()inti,j;intx,y;for(i=0;iN;i+)/for(j=0;jN;j+)boardij=0;for(;)printf(Pleaseinputi

9、mportpoint(1=x=8and1=y=1&x=1&y【Iluo1LnpintHRCfinx-4y-LPirB2936153S4334173027394635IS5128331837X4?42312&290吕右字*J.G2134041G4532257iRAl5ft22SR1257需5別57202342156SLni/Jke5Ftzocor：d_nuc结果2:t丄3孔口Qimpi.mpoi.tpo七1xandL1=yo乞42554251621223s迂丘-433和17&4收直2?&222jL35G63445?ZBG116呦S359G4SI12全牛V呂勺4b吕N3V缶Idlb、凶4G392?

10、401301133A473R311PI491qan5itrocontzJviui#七、实验体会通过本次实验的编写，能够掌握栈的性质以及它的应用。这次实验花了很多时间才完成，其实本应该早完成的，在检查的过程中有多多少少修改完美了一下，不过算法思想却没有改变。这个程序也让我头疼了几次，就是运行速度很慢，要等很久才能输出结果，这样的话很占内存资源，而且CPU的使用记录也很高，主要是它需要的运算太多，所以CPU使用记录也是很高的。虽然我也参考了一些优化的算法，可以找到最优路进走，但是这些最优算法都和栈的应用失去了联系，本次的实验主要目的就是要了解栈，所以不用栈来写该程序就失去了该实验的意义。在该程序的编制过程中留下了一些思考的问题，就是马儿从一个起点位置开始探寻，最后马儿探寻成功的路径会不会是不只一条路径，可能还有多条路径，由于时间和精力的限制没有去深究，但是这应该值的思考的。在用顺序栈来实现该程序之前，也尝试过用链栈来做，但是发现如果用链栈来做的话，在存储调用的时候不是很方便，或许用链栈来做应该是对自己的一种挑战。尽管没有用链栈做不过，用顺寻栈来做在编制该程序中也收获不小。