数据结构课程设计马踏棋盘.doc

前言
学习数据结构的最终目的是解决实际的应用问题，特别是非数值计算类型的应用问题，数据结构课程设计就是为此目的一次实际训练。规定我们在对题目进行独立分析的基础上，完毕设计和开发，并最终接受严格的测试考核。以深化对数据结构课程中基本概念、理论和方法的理解，提高综合运用所学知识解决实际问题的能力，使我们的的程序设计能力与调试水平有一个明显的提高。
课程设计所安排的题目，都有一定的难度和深度，从抽象数据类型的提炼、数据结构选择到算法的设计，均由我们每个人自主完毕。在一周的时间内，历经查找参考资料、使用技术手册、设计编码和撰写文档的实践，进一步升华对软件工程师和程序员人格素质的结识和理解。
本课程设计的重要设计内容是： 设计一个马踏棋盘问题的演示程序。
即将马随机地放在国际象棋的8*8棋盘的某个方格中，然后令马按走棋规则开始进行移动。规定马将棋盘上的每个方格进入且只进入一次，走遍所有64个方格。规定编制非递归程序，求出马的行走路线，将数字1，2，…，64依次填入一个8*8的方阵在屏幕上显示输出。
针对该问题本课程设计采用的是面向对象的开发语言Java，在Windows7, myeclipse8.5.0的平台上开发出来，并有图形界面。最终较好的实现了所有规定，达成了预期效果。从中我也学到了很多，不仅仅是课堂外的新知识，尚有那种会查资料，会学习新知识的能力。
这个课程设计的顺利完毕，离不开胡老师的指导和帮助，在他的细心指导和帮助下，我对马踏棋盘程序开发的整个流程有了深刻地了解和系统地掌握，在这里学生表达真诚地感谢。此外也谢谢这次课程设计提供应我帮助的同学们。此外，本课程设计还参考了一些文献资料，在此向这些文献资料的作者深表谢意。
本课程设计可作为数据结构和Java课程教学的参考案例。
由于时间仓促和本人水平所限，设计中难免有不妥和欠妥之处，敬请老师不吝批评指正。

笔者
2023.6

目录
摘要………………………………………………………………………………………………………………………………………3
第一章 需求分析………………………………………………………………………………………………………………….4
第二章 概要设计………………………………………………………………………………………………………………….5
2.1系统描述。。。。………………………………………………………………….5
2.2运营环境…………………………………………………………………………..5
2.3马踏棋盘流程…………………………………………………5
2.4算法设计
第三章 具体设计
3.1 Jisuan类实现
3.2
3.3
3.4
Disizhang
4.1
4,2
4.3
Diwu
5.1
5.2
Cankaowenxian
Fulu

摘要
本课程设计中的程序实现了马踏棋盘问题的求解,并可以演示起始位置在棋盘上任何位置的问题的实现.程序采用图形演示,使算法的描述更形象,更生动,使教学更能产生良好的效果。对于该程序，我严格按照面向对象的思想进行开发,其中有Jisuan类, Shuchu类, Jframe类和Main四个类。其中Jisuan类重要是初始化各点的可走途径，并且删除不合法的点；Shuchu类重要最优算法的实现；Jframe类为图形用户界面的设计,重要完毕棋盘的绘制和结果的打印；Main类重要是负责整个程序的控制。最终调试运营通过，实现了所有规定，取得了抱负效果。
关键词：数据结构 马踏棋盘 Java 图形界面

Abstract
This course design of the program realization horses on board the solution, and to demonstrate the starting position on the board of the realization of the problem any position. The program using graphical presentation, the method of more image, the more vivid description, and make the teaching more can produce good effect. For the program, I in strict accordance with the object-oriented ideas of development, including Jisuan class, Shuchu class, Jframe classes and Main four classes. Among them Jisuan kind basically is the initial points of walk path, and remove not legal point; Shuchu main kinds of the realization of the optimal algorithm; Jframe class for the graphical user interface design, the main finish drawing the board and results of the print; Main kinds of major is responsible for the entire process control. Final test and operation, realize the requirements through all, make the ideal effect.
Key words: data structure horse on board Java graphical interface

第一章 需求分析
数据结构课程设计是计算机科学与技术专业学生必做的集中实践性环节之一，是学习完《数据结构》课程后进行的一次全面的综合练习。其目的在于通过课程设计，使学生可以得到较系统的技能训练，从而巩固和加深对数据结构的基础理论知识的理解，培养学生综合运用所学理论知识解决实际问题的能力，使学生成为具有扎实的计算机理论基础和较强的独立动手能力的复合型、应用型人才。
马踏棋盘问题是一个古老而著名的问题,它最初是由大数学家Euler提出的.
问题是这样的:国际象棋中的棋子(叫作马)在一个空棋盘内移动,问它能否通过64格中的每一格且只通过一次?(马按L行移动,即在某方向前进两格接着在与原方向垂直的方向上前进一格)
本程序实现了马踏棋盘问题的求解,并可以演示起始位置在棋盘上任何位置的问题的实现.程序采用图形演示,使算法的描述更形象,更生动,使教学更能产生良好的效果。

第二章 概要设计

2.1系统描述
本程序采用myeclipse8.5.0来编制整个程序,这样既可以使大家对算法的实现有了一定的了解,也可以熟悉一下Java图形界面以及Java语言的命名规范。作为数据结构的课程设计,本人希望同时也能让大家顺便熟悉一下Java的基本语言结构和强大的开发能力。
在马踏棋盘的课程设计中,我们严格按照面向对象的思想进行开发,其中有Jisuan类, Shuchu类, Jframe类和Main类。读者应注意各个类之间的关系,以便也能顺道理解Java中类的思想。

2.2运营环境
本程序是在windows7, myeclipse8.5.0的环境下运营的。

2.3马踏棋盘流程
将马随机地放在国际象棋的8*8棋盘Board[8][8]的某个方格中，然后令马按走棋规则开始进行移动。规定马将棋盘上的每个方格进入且只进入一次，走遍所有64个方格。

2.4算法设计
2.4.1 设计思想
① 运用某种算法直接找到最优解，算出最优途径，而不是一步步尝试碰到错误回溯。
②设一数组与棋盘坐标一一相应（1，1）到（8，8），存放每个棋盘格上应算出的途径数字。
③ 途径从1～64存放到与棋盘数组中相应的数组中，将数组当形参传到图形用户界面，运用Graphics绘制棋盘并打印数组。
④ 建立主函数，调用计算途径类和绘制棋盘类。
2.4.2程序结构说明
程序的运营关系如图2-1.

图2-1 程序运营关系图
2.4.3算法结构设计
①最优算法设计
准备阶段：
(a) 按国际象棋马的走法，最多有8种也许，创建数组int path[][]={{0,0,0},{1,1,2},{2,1,-2},{3,-1,2},{4,-1,-2},{5,2,1},{6,2,-1},{7,-2,1},{8,-2,-1}}存放8中也许，为了满足与棋盘一一相应故用3×8数组。
(b) 创建数组int [][]way=new int[9][9]存放棋盘每点可走的途径数。
(c) 创建数组int [][]output=new int[9][9]存放最终绘制棋盘格中输出的数字，即行走路线。
(d) 计算出棋盘上每点的可走途径数，存入way数组，超过棋盘边界的点被舍弃，让数组与棋盘一一相应。
计算阶段：
(a) 从用户输入起始点坐标，存入m，n。
(b) 先假设每个点最小可走途径数为min=8。
(c) 根据way数组中已经存放的值与假设的最小可走途径数为8比较，若小于8则存入min，如此循环最多8次，找出使min值最小的点，设为下次要走的点，依次类推，直至找出64个点，即最优途径。
②用户输入
运用java提供的Scanner函数从操作台进行输入。
③图形用户界面
运用Jframe窗体建立图形用户界面，编写构造函数，用Graphics()函数绘制矩形并填充颜色，画出棋盘表格，并运用drawString()在相应的棋盘坐标中打印出output数组中数字。

第三章 具体设计
3.1 Jisuan类实现
public class jisuan { //计算棋盘中各点可走途径
public void init(int[][]way){

int i,j,k,x,y;
intpath[][]={{0,0,0},{1,1,2},{2,1,-2},{3,-1,2},{4,-1,-2},{5,2,1},{6,2,-1},{7,-2,1},{8,-2,-1}}; //存放马的行走规则，为了使坐标和棋盘一一相应，定义8×3数组

for(i=1;i<=8;i++) //先初始各点可走途径为零
for(j=1;j<=8;j++)
way[i][j]=0;

for(i=1;i<=8;i++) //计算各点可走途径，假如合法便存储
for(j=1;j<=8;j++)
for(k=1;k<=8;k++)
{ x=i;y=j;
x=x+path[k][1];
y=y+path[k][2]; //x,y代表走下一步后的坐标，通过k的增长，改变行走的方向
if(x>=1&&x<=8&&y>=1&&y<=8) //判断是否落在棋盘内，否则不存储
way[i][j]++ ; }

}//init
}//jisuan

注释：
此类重要初始化各点的可走途径，并且删除不合法的点。
一方面初始化way数组为0，然后运用for循环嵌套实现64次运算，每次再嵌套一个执行8次的循环，运用k++实现改变行走路线，前提是path数组中已经存储了马的行走规则，根据每次到达的点判断是否落在棋盘内，若合法则相应坐标格的way数组自加1，以此来计算出棋盘中各点的可走路线数，完毕最优算法的准备阶段。

3.2 Shuchu类算法实现
public class shuchu {
public void calcu(int[][]output,int[][]way){
int z,x,y,m,n,k,min;
int i=0;int j=0;
int path[][]={{0,0,0},{1,1,2},{2,1,-2},{3,-1,2},{4,-1,-2},{5,2,1},{6,2,-1},{7,-2,1},{8,-2,-1}};

System.out.println("请输入马的起始位置坐标:x y(其中x,y均为正整数,0<x<9,0<y<9,输入时两数之间以空格隔开)");
Scanner scan=new Scanner(System.in); //从键盘输入起始点坐标
m=scan.nextInt();
n=scan.nextInt();

if(m>=1&&m<=8&&n>=1&&n<=8) //判断输入位置是否合法
{
for(z=1;z<=64;z++) //分64次写入
{
min = 8; //初始可选途径最小值为8
output[m][n]=z; //用output[][]来记录所走途径
way[m][n]=0; //走过的点可选途径设为0，没走过设为可选途径数
for(k=1;k<=8;k++) //走最小可选途径数的点
{
x=m+path[k][1];
y=n+path[k][2]; //x,y代表走下一步后的坐标，通过k的增长，改变行走的方向
if(x>=1&&x<=8&&y>=1&&y<=8)
if(way[x][y]!=0) //没走过的点
{

--way[x][y]; //可选途径数减1，由于本点刚走过
if(way[x][y]<min) //假如可选途径数小于min
{
min=way[x][y]; //使a[x][y]存放最小可选途径数的点
i=x;
j=y;}
}
}//for
m=i;n=j; //下一个点的坐标
} //for“64次”

}//判断合法
else
System.out.println("错误：坐标超过棋盘边界！");
}//calu

}//shuchu

注释：
此类为重要最优算法的实现类。
一方面仍然定义马的行走路线，和一些循环中用到的变量。然后运用Scanner函数进行用户输入。横纵坐标存入m和n。
判断起始坐标是否合法，合法则用一个64次的循环分别写入output数组中马的行走路线，假设min的值为8。
用一个8次循环分别列出马的可走途径，若合法且是没走过的点将相应的way数组减1，由于下次若走到此点，可选途径数必然要减1，不可走已经走过的点。假如该点的可走途径数<min中的值，则更新为此点的way数组值。
最后将是min保持最小的点的坐标赋值给（m，n），作为马将走的下一个点将此点的output数组值更新为2。
以此类推马的整个行走路线就完毕了，且已经将1～64分别写入到output数组中.

3.3Jframe类的实现
import java.awt.Color;
import javax.swing.*;
import java.awt.Graphics;
import java.awt.Font;

public class Jframe extends JFrame{
int [][]seed=new int[9][9];
public Jframe(){ //窗体构造函数
this.setSize(500,500);
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
setVisible(true);
}

public void paint(Graphics g){ //创建Graphics画图
super.paint(g);
g.setColor(Color.black);
g.drawRect(50,50,400,400); //画棋盘边界
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
g.fillRect(100*j, 100*i-50, 50, 50); //画棋盘黑格1
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
g.fillRect(100*j-50, 100*i, 50, 50); //画棋盘黑格2
g.setColor(Color.blue);
Font num=new Font("楷体",Font.BOLD,25);
g.setFont(num); //设立字体
for(int i=1;i<=8;i++)
for(int j=1;j<=8;j++)
g.drawString(seed[i][j]+"", 50*j+15,50*i+35); //打印棋盘格中数字
}

public void write(int output[][]){ //将结果数组引入Jframe类，并赋给数组seed
for(int i=1;i<=8;i++)
for(int j=1;j<=8;j++)
seed[i][j]=output[i][j];
}
} //Jframe
注释:
此类为图形用户界面,重要完毕棋盘的绘制和结果的打印.
创建构造函数,设立窗体大小,使窗体可见.
创建Graphics()画图函数,设立背景颜色为黑色,绘制棋盘边框.由于国际象棋棋盘为黑白交替方格,所以将黑色部分用Rectfill()函数画出,就形成了棋盘,运用for循环将黑色方格分两次画完,设计的棋盘坐标如下:

(50,50) (400,50)

(50,400) (400,400)
图3-1 棋盘的设计
每个格子的长宽是50,50。
左斜线是第一次画的黑格,右斜线是第二次画的黑格.

3.4Main类的实现

public class Main {
public static void main(String[] args) {
int i,j;
int [][]way=new int[9][9]; //初始化可算途径数数组
int [][]output=new int[9][9]; //初始化结果输出数组

jisuan ad=new jisuan();
ad.init(way); //运营计算类
shuchu aw=new shuchu();
aw.calcu(output, way); //运营输出类

System.out.printf("运营结果如下(稍后会以棋盘界面显示,为便于看图,相邻两步之间棋盘颜色不同):\n");
for(i=1;i<=8;i++){ //输出
for(j=1;j<=8;j++)
System.out.printf("%6d",output[i][j]);
System.out.printf("\n");
}

Jframe w=new Jframe(); //图形用户输出
w.write(output); //载入结果输出数组
} //main
} //Main
注释:
创建way和output数组.
调用类并创建对象,对象调用函数.
在控制台同样输出一份结果,和图形用户界面的相同.
创建窗体,并传入output数组参数

流程图如下：

图3-2 Main类流程图
程序的源代码参见附录。

第四章 调试分析
这次课程设计我碰到如下问题，最终通过调试分析都得到了很好的解决。
4.1最优算法的求解，无从下手，最后借鉴前辈的思绪想到了走最小度数点的算法。
4.2 从shuchu类计算的结果无法传入Jframe函数，曾试过全局变量，但是分装性不好，最后把结果数组当作形式参数传入Jframe类的一个write（）函数。
4.3无法在棋盘的格子上打印数字，由于drawstring（）函数只能打印字符型变量，而我的output是整形变量，最后运用drawstring（output+“”，50，50）一个小技巧将int型转化为string型。
4.4刚开始棋盘画得很麻烦，所以后期直接用填充色矩形画出黑的，其余的就成了白的，并分两步话出棋盘，感觉比较简朴。
4.5开始无法使数组与棋盘坐标一一相应。
程序运营截屏见附录B。

第五章 总结
5.1碰到的问题
5.11最优算法的求解，无从下手，最后借鉴前辈的思绪想到了走最小度数点的算法。
5.12 从shuchu类计算的结果无法传入Jframe函数，曾试过全局变量，但是分装性不好，最后把结果数组当作形式参数传入Jframe类的一个write（）函数。
5.13无法在棋盘的格子上打印数字，由于drawstring（）函数只能打印字符型变量，而我的output是整形变量，最后运用drawstring（output+“”，50，50）一个小技巧将int型转化为string型。
5.14刚开始棋盘画得很麻烦，所以后期直接用填充色矩形画出黑的，其余的就成了白的，并分两步话出棋盘，感觉比较简朴。
5.15开始无法使数组与棋盘坐标一一相应。

5.2收获与体会
总体感觉这个课题还是比较简朴的，不找出问题的主线,就无法理解自己获得的是什么,在一个星期的课程设计中，我将掌握的专业理论知识很好地运用到对这个课题的理解中.做到了理论和实践相结合，在实践中加深了对专业理论知识的理解，并提高了对理论知识的运用能力，获得了许多宝贵的经验。
5.21 巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。
5.22 培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，进一步研究，分析问题、解决问题的能力。
5.23 过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。
5.24 可以按规定编写课程设计报告书，能对的阐述设计和实验结果，对的绘制系统和程序框图。
5.25 通过这次课程设计，培养了我严厉认真的工作作风，逐步建立对的的生产观念、经济观念和全局观念。
由于时间紧迫，我做的这个课程设计也许还不十分完善，但重要的是，这次课程设计让我学到了很多知识。通过这次课程设计，我对数据结构课程有了进一步的了解和结识，对数据结构的理解上升到一个新的高度，也充足地了解到一个好的算法对于程序的重要性。
最后再次感谢这次课程设计提供应我帮助的老师，同学们以及参考文献
的作者们，谢谢你们！
参考文献
【1】 严蔚敏，吴伟民.数据结构（c语言版）.北京：清华大学出版社，2023
【2】Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,，Clifford Stein.
Introduction to Algorithms, Second Edition. 北京: 高等教育出版社, 2023
【3】【美】s巴斯.计算机算法：设计与分析引论.朱洪等译.上海：复旦大学出版社，1985
[4] Ralph Morelli. Java面向对象程序设计（第三版）.北京：清华大学出版社， 2023
【5】张亦辉，冯华，胡洁.Java面向对象程序设计.北京：人民邮电出版社，2023

附录A 源代码

-----------------------class jisuan-----------------------
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,-1,2},{4,-1,-2},{5,2,1},{6,2,-1},{7,-2,1},{8,-2,-1}};//存放马的行走规则，为了使坐标和棋盘一一相应定义8*3数组

for(i=1;i<=8;i++) //先初始各点可走途径为零
for(j=1;j<=8;j++)
way[i][j]=0;

for(i=1;i<=8;i++) //计算各点可走途径，假如合法便存储
for(j=1;j<=8;j++)
for(k=1;k<=8;k++){
x=i;y=j;
x=x+path[k][1];
y=y+path[k][2]; //x,y代表走下一步后的坐标，通过k的增长，改变行走的方向
if(x>=1&&x<=8&&y>=1&&y<=8) //判断是否落在棋盘内，否则不存储
way[i][j]++;
}
} //init
} //jisuan

--------------------------class shuchu--------------------
import java.util.Scanner;

public class shuchu {
public void calcu(int[][]output,int[][]way){
int z,x,y,m,n,k,min;
int i=0;int j=0;
int path[][]={{0,0,0},{1,1,2},{2,1,-2},{3,-1,2},{4,-1,-2},{5,2,1},{6,2,-1},{7,-2,1},{8,-2,-1}};

System.out.println("请输入马的起始位置坐标:x y(其中x,y均为正整数,0<x<9,0<y<9,输入时两数之间以空格隔开)");
Scanner scan=new Scanner(System.in); //从键盘输入起始点坐标
m=scan.nextInt();
n=scan.nextInt();

if(m>=1&&m<=8&&n>=1&&n<=8){ //判断输入位置是否合法
for(z=1;z<=64;z++){ //分64次写入
min = 8; //初始可选途径最小值为8
output[m][n]=z; //用output[][]来记录所走途径
way[m][n]=0; //走过的点可选途径设为0，没走过设为可选途径数
for(k=1;k<=8;k++){ //走最小可选途径数的点
x=m+path[k][1];
y=n+path[k][2]; //x,y代表走下一步后的坐标，通过k的增长，改变行走的方向
if(x>=1&&x<=8&&y>=1&&y<=8)
if(way[x][y]!=0){ //没走过的点
--way[x][y]; //可选途径数减1，由于本点刚走过
if(way[x][y]<min){ //假如可选途径数小于 min
min=way[x][y]; //使a[x][y]存放最小可选途径数的点
i=x;
j=y;
}
}
} //for
m=i;n=j; //下一个点的坐标
} //for“64次”
} //判断合法
else
System.out.println("错误：坐标超过棋盘边界！");
} //calu
} //shuchu

--------------------------class Jframe--------------------
import java.awt.Color;
import javax.swing.*;
import java.awt.Graphics;
import java.awt.Font;

public class Jframe extends JFrame{
int [][]seed=new int[9][9];
public Jframe(){ //窗体构造函数
this.setSize(500,500);
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
setVisible(true);
}

public void paint(Graphics g){ //创建Graphics画图
super.paint(g);
g.setColor(Color.black);
g.drawRect(50,50,400,400); //画棋盘边界
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
g.fillRect(100*j, 100*i-50, 50, 50); //画棋盘黑格1
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
g.fillRect(100*j-50, 100*i, 50, 50); //画棋盘黑格2
g.setColor(Color.blue);
Font num=new Font("楷体",Font.BOLD,25);
g.setFont(num); //设立字体
for(int i=1;i<=8;i++)
for(int j=1;j<=8;j++)
g.drawString(seed[i][j]+"", 50*j+15,50*i+35); //打印棋盘格中数字
}
public void write(int output[][]){ //将结果数组引入Jframe类，并赋给数组seed
for(int i=1;i<=8;i++)
for(int j=1;j<=8;j++)
seed[i][j]=output[i][j];
}
} //Jframe

--------------------------class Main----------------------
public class Main {
public static void main(String[] args) {
int i,j;
int [][]way=new int[9][9]; //初始化可算途径数数组
int [][]output=new int[9][9]; //初始化结果输出数组

jisuan ad=new jisuan();
ad.init(way); //运营计算类
shuchu aw=new shuchu();
aw.calcu(output, way); //运营输出类

System.out.printf("运营结果如下(稍后会以棋盘界面显示,为便于看图,相邻两步之间棋盘颜色不同):\n");
for(i=1;i<=8;i++){ //输出
for(j=1;j<=8;j++)
System.out.printf("%6d",output[i][j]);
System.out.printf("\n");
}

Jframe w=new Jframe(); //图形用户输出
w.write(output); //载入结果输出数组
} //main
} //Main
附录B 运营截屏
4.1第一次输入坐标(6,6)

图4-1 第一次输入截图

图4-2 第一次运营结果截图
（其中数字编号即为马踏棋盘的顺序）

4.2第二次输入坐标(8,1)

图4-3 第二次输入截图

图4-4 第二次运营结果截图

4.3第三次输入坐标(5,9)