马踏棋盘-数据结构与算法课程设计

1、数据结构与算法设计课程设计任务书题 目马踏棋盘问题研究学生姓名学号专业班级数学0901设计内容与要求【问题描述】将马随机地放在国际象棋的8*8棋盘某个方格中，然后令马按走棋规则开始进行移动。马将棋盘上的每个方格进入且只进入一次，走遍全部64个方格。【软件功能】1. 用户可以输入一个起始位置。2. 有一个正确的起始位置后，用户可以得到一个棋盘，棋盘上的每个位置都将标有1-64中的某一个数字。3. 再输入一个起始位置后，将会得到一个新的棋盘。4. 利用GUI实现简单的图形用户界面【算法思想】1. 由键盘输入起始的x坐标和y坐标2. 判断坐标位置是否合法，如果不合法，则提示用户重新输入，如果合法，则

2、将坐标保存在马类中，并且将步数记录为第1步，将棋盘类入栈保存。接着调用探寻下一步路径的函数。3. 马将向可以走的方向进行尝试，如果尝试的这个位置可以行走，即马还没有走过，则记录下此位置以及是第几步所走的位置，并入栈保存。4. 再次调用探寻路径的函数，并且做步骤3中的做法。5. 直到马将棋盘上的64个方格都走完，则停止调用探寻路径的函数。此时，开始输出马所走的位置。即开始出栈。6. 栈遵循后进先出的原则，故出栈时，首先输出的是马走的最后一个位置，此时，在棋盘上对应的位置输入所记录的步数。依次循环出栈，当栈为空时，即输出完毕，得到一章带有马所走过的位置的棋盘。程序结束。【提交成果】1.“数据结构与

3、算法设计课程设计任务书”一份，打印装袋；2.“数据结构与算法设计课程设计报告”一份，打印装袋；3、上面两项内容的word文档，通过电子邮件交到指导教师。起止时间2012 年 6 月18日 至 2012 年7月 1 日指导教师签名 2012年 6 月 18 日 系（教研室）主任签名 2012年 6 月 18 日学生签名年 月 日注明：内容限1页数据结构与算法设计课程设计专业 数学与应用数学 班级 数学0901 学号 姓名 完成日期 指导教师1、 程序设计说明书【设计题目】马踏棋盘问题研究【问题描述】将马随机地放在国际象棋的8*8棋盘某个方格中，然后令马按走棋规则开始进行移动。马将棋盘上的每个方格

4、进入且只进入一次，走遍全部64个方格。【软件功能】1. 用户可以输入一个起始位置。2. 有一个正确的起始位置后，用户可以得到一个棋盘，棋盘上的每个位置都将标有1-64中的某一个数字。3. 再输入一个起始位置后，将会得到一个新的棋盘。4. 利用GUI实现简单的图形用户界面【算法思想】1. 由键盘输入起始的x坐标和y坐标2. 判断坐标位置是否合法，如果不合法，则提示用户重新输入，如果合法，则将坐标保存在马类中，并且将步数记录为第1步，将棋盘类入栈保存。接着调用探寻下一步路径的函数。3. 马将向可以走的方向进行尝试，如果尝试的这个位置可以行走，即马还没有走过，则记录下此位置以及是第几步所走的位置，并

5、入栈保存。4. 再次调用探寻路径的函数，并且做步骤3中的做法。5. 直到马将棋盘上的64个方格都走完，则停止调用探寻路径的函数。此时，开始输出马所走的位置。即开始出栈。6. 栈遵循后进先出的原则，故出栈时，首先输出的是马走的最后一个位置，此时，在棋盘上对应的位置输入所记录的步数。依次循环出栈，当栈为空时，即输出完毕，得到一章带有马所走过的位置的棋盘。程序结束。【逻辑结构设计】由用户输入起始位置，如果，输入合法，即输入的起始位置在棋盘中，则此位置即为马开始行走的起点，以此点为起点，以象棋中马的走法开始在棋盘中，找寻可以行走的位置，每个位置只能走一次，直到马将棋盘中的64个位置全都走过之后，在棋盘

6、上显示出马行走的轨迹；当用户在此输入一个合法的起始位置时，则可以得到一个新的棋盘。【存储结构设计】马的抽象数据类型：public class Horse public int step;/马行走的步数public int x=0;/马在棋盘上的横坐标public int y=0;/马仔棋盘上的纵坐标public Horse()/无参构造public int getStep() ;/获取步数public void setStep(int step) ;/设置步数public int getX() ;/获取x坐标public void setX(int x) ;/设置x坐标public int g

7、etY() ;/获取y坐标public void setY(int y) ;/设置y坐标栈的抽象数据类型：public class Stack int top; /栈顶指针Horse elements; /栈元素数组int StackSize; /栈最大容量public Stack ( ) ;/构造函数1public Stack ( int StackSize ); /构造函数2public boolean IsEmpty ( );/栈空否public boolean IsFull ( ) ;/栈满否public void Push (Horse item );/进栈public Horse

8、Pop( );/出栈public Horse GetTop( ) ;/取栈顶public void MakeEmpty ( ) ;/置空栈【基本操作设计】此程序功能简单，由于只需要用户输入一个起始位置的坐标即可，故设计了两个输入框用来输入起始位置的x坐标和y坐标，然后设计了一个按钮，用来开始计算马的行走轨迹及显示。【模块流程图】开始提示输入起始坐标x,y判断是否合法调用函数是提示重新输入否入栈找出下一步可走位置判断栈是否为空否否出栈输出路径是否重新输入起始坐标结束是是【界面设计】(1).主界面(2)用户输入错误时的错误提示界面【用户手册】(1) 输入正确的起始位置坐标.x 和 y(2) 坐标的

9、建立方向为：x坐标：从上到下，从1开始到8结束，即x代表第x行y坐标：从左到右，从1开始到8结束，即y代表第y列2、 程序上机调试报告【语法错误及其排除】(1) 空指针异常。在测试代码时经常遇见这个错误，原因是，变量没有被正确调用。调试这个错误时很麻烦的，需要一点一点去检查出现错误的语句以及相关的语句。经过仔细检查，果然是我在调用变量时出现的错误，一点点修改后，程序终于跑通了。(2) 数组下标越界异常。在使用数组时，定义好了数组的长度，数组的下标也就给定了，就是0-(长度-1),但我的使用时，将数组中的最后一项的下标直接给成了数组的长度，出现了错误。修改后经测试，程序运行良好。【算法错误及其排

10、除】(1) 标记好马儿尝试的方向后，编译运行，但是运行结果却不符合程序所要求的结果，说明在算法上肯定有错误，检查发现，马儿走的坐标没有控制后，马儿就会踏出棋盘以外，这样输出的结果就不对。调整后，输入结果正确。(2) 棋盘走过的位置没有被标记，使得在计算时出现了重复的位置。在走过的位置被标记之后，标记的位置马儿就不会再去走，这样就不会出现重复的位置。【测试数据】测试数据1：起始坐标（3,4）测试数据2：起始坐标（9,9）【输出结果】对于测试数据1：对于测试数据2：【程序性能评价】此程序的功能有些简单，但关键在于对于马儿行走的路径的计算上，在计算时对内存的使用有些大。故此程序注重的是算法的设计与计

11、算。【性能改进方向】此程序还有可以改进的地方，由问题可知，此棋盘的格子数是给定的，即指定了一个8*8的棋盘。改进的地方就在于，我们还可以设计为棋盘的格子数由用户输入，即由用户自己来确定棋盘的大小。【收获及体会】通过本次程序的编写，能够掌握栈的性质以及它的应用。这次实验花了很多时间才完成，其实本应该早完成的，在检查的过程中有多多少少修改完美了一下，不过算法思想却没有改变。课程设计是把我们所学的理论知识进行系统的总结并应用于实践的良好机会，有利于加强我们用知识理论来分析实际问题的能力，进而加强了我们对知识认识的实践度，巩固了我们的理论知识，深化了对知识的认识，并为走向社会打下一个良好的基础。3、

12、源程序代码（1） 马类public class Horse public int step;/马行走的步数public int x=0;/马在棋盘上的横坐标public int y=0;/马仔棋盘上的纵坐标public int getStep() return step;public void setStep(int step) this.step = step;public int getX() return x;public void setX(int x) this.x = x;public int getY() return y;public void setY(int y) this

13、.y = y;(2)顺序存储栈/顺序存储栈import java.io.*;/*“顺序栈”类的定义*/public class Stack int top; /栈顶指针Horse elements; /栈元素数组int StackSize; /栈最大容量/构造函数1public Stack ( ) StackSize=10; /缺省大小elements=new HorseStackSize; /数组top=-1; /空栈标志/构造函数2public Stack ( int StackSize ) this.StackSize=StackSize;elements=new HorseStackS

14、ize; /数组top=-1; /空栈标志/栈空否public boolean IsEmpty ( ) return top = -1; /栈满否public boolean IsFull ( ) return top = StackSize-1; /进栈public void Push (Horse item ) if ( IsFull ( ) ) return; /栈满/栈顶指针首先上抬，在栈顶位置存入新元素 elements+top = item; /出栈 public Horse Pop( ) /栈空，出栈失败if (IsEmpty ( ) return null; /送出栈顶元素，栈

15、顶指针下移return elementstop-; /取栈顶public Horse GetTop( ) /栈空if ( IsEmpty ( ) ) return null; /送出栈顶元素，栈顶指针不动return elementstop; /置空栈public void MakeEmpty ( ) top = -1; （3）计算棋盘中个点可走路径的类public class JiSuan / 计算棋盘中各点可走路径public void init(int way) int i, j, k, x, y;int path = 0, 0, 0 , 1, 1, 2 , 2, 1, -2 , 3,

16、-1, 2 , 4, -1, -2 , 5, 2, 1 , 6, 2, -1 , 7, -2, 1 , 8, -2, -1 ;/ 存放马的行走规则，为了使坐标和棋盘一一对应定义83数组for (i = 1; i = 8; i+)/ 先初始各点可走路径为零for (j = 1; j = 8; j+)wayij = 0;for (i = 1; i = 8; i+)/ 计算各点可走路径，如果合法 便存储for (j = 1; j = 8; j+)for (k = 1; k = 1 & x = 1 & y = 1 & m = 1 & n = 8) / 判断输入位置是否合法for (z = 1; z =

17、 64; z+) / 分64次写入Horse horse=new Horse();min = 8; / 初始可选路径最小值为8waymn = 0; / 走过的点可选路径设为0，没走过设为可选路径数for (k = 1; k = 1 & x = 1 & y = 8)if (wayxy != 0) / 没走过的点-wayxy; / 可选路径数减1，因为本点刚走过if (wayxy min) / 如果可选路径数小于 minmin = wayxy; / 使axy存放最小可选路径数的点i = x;j = y;/ forhorse.setX(m);/将x坐标存入马类中horse.setY(n);/将y坐标

18、存入马类中horse.setStep(z);/将步数存入马类中stack.Push(horse);/入栈m = i;n = j; / 下一个点的坐标 / for“64次”return stack;/ 判断合法elseSystem.out.println(错误：坐标超出棋盘边界！);return null;/ calu/ shuchu（5）GUI图形用户界面类package yanghao;import java.awt.*;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import javax.sw

19、ing.*;public class Jframe extends JFrame implements ActionListener int seed = new int99;/存储从栈中接收的步数的二维数组JButton jb;/定义的按钮JLabel jl1, jl2;/定义的标签JTextField jtf1, jtf2;/定义的输入框public Jframe() / 窗体构造函数setLayout(new BorderLayout();JPanel jp = new JPanel();jb = new JButton(确定);jb.addActionListener(this);jl

20、1 = new JLabel(x:);jl2 = new JLabel(y:);jtf1 = new JTextField(5);jtf2 = new JTextField(5);jp.add(jl1);jp.add(jtf1);jp.add(jl2);jp.add(jtf2);jp.add(jb);add(jp, BorderLayout.NORTH);this.setTitle(马踏棋盘);/设置标题this.setSize(600, 600);/设置界面的大小setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);setVisible(true);p

21、ublic void paint(Graphics g) / 创建Graphics画图super.paint(g);g.setColor(Color.black);g.drawRect(100, 100, 400, 400); / 画棋盘边界for (int i = 1; i = 4; i+)for (int j = 1; j = 4; j+)g.fillRect(100 * j + 50, 100 * i, 50, 50); / 画棋盘黑格1for (int i = 1; i = 4; i+)for (int j = 1; j = 4; j+)g.fillRect(100 * j, 100 * i + 50, 50, 50); / 画棋盘黑格2g.setColor(Color.blue);Font num = new Font(楷体, Font.BOLD, 25);g.setFont(num); /