当前位置：文档之家 › 数据结构课程设计报告马踏棋盘

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

  • 格式：doc
  • 大小：293.50 KB
  • 文档页数：32

v .. .

..

. . . 资 料. . 前言

学习数据结构的最终目的是解决实际的应用问题，特别是非数值计算类型的应用问题，数据结构课程设计就是为此目的一次实际训练。要求我们在对题目进行独立分析的基础上，完成设计和开发，并最终接受严格的测试考核。以深化对数据结构课程中基本概念、理论和方法的理解，提升综合运用所学知识处理实际问题的能力，使我们的的程序设计能力与调试水平有一个明显的提升。

课程设计所安排的题目，都有一定的难度和深度，从抽象数据类型的提炼、数据结构选择到算法的设计，均由我们每个人自主完成。在一周的时间内，历经查找参考资料、使用技术手册、设计编码和撰写文档的实践，进一步升华对软件工程师和程序员人格素质的认识和理解。

本课程设计的主要设计内容是：

设计一个马踏棋盘问题的演示程序。

即将马随机地放在国际象棋的8*8棋盘的某个方格中，然后令马按走棋规则开始进行移动。要求马将棋盘上的每个方格进入且只进入一次，走遍全部64个方格。要求编制非递归程序，求出马的行走路线，将数字1，2，…，64依次填入一个8*8的方阵在屏幕上显示输出。

针对该问题本课程设计采用的是面向对象的开发语言Java，在Windows7, myeclipse8.5.0的平台上开发出来，并有图形界面。最终较好的实现了全部要求，达到了预期效果。从中我也学到了很多，不仅仅是课堂外的新知识，还有那种会查资料，会学习新知识的能力。

这个课程设计的顺利完成，离不开胡老师的指导和帮助，在他的细心指导和帮助下，我对马踏棋盘程序开发的整个流程有了深刻地了解和系统地掌握，在这里学生表示真诚地感谢。另外也谢谢这次课程设计提供给我帮助的同学们。此外，本课程设计还参考了一些文献资料，在此向这些文献资料的作者深表谢意。

本课程设计可作为数据结构和Java课程教学的参考案例。

由于时间仓促和本人水平所限，设计中难免有不当和欠妥之处，敬请老师不吝批评指正。

笔者

2016.6

v .. .

..

. . . 资 料. .

目录

摘要………………………………………………………………………………………………………………………………………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 v .. .

..

. . . 资 料. . 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 v .. .

..

. . . 资 料. . 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行移动,即在某方向前进两格接着在与原方向垂直的方向上前进一格) v .. .

..

. . . 资 料. . 本程序实现了马踏棋盘问题的求解,并能够演示起始位置在棋盘上任何位置的问题的实现.程序采用图形演示,使算法的描述更形象,更生动,使教学更能产生良好的效果。

第二章 概要设计

2.1系统描述

本程序采用myeclipse8.5.0来编制整个程序,这样既可以使大家对算法的实现有了一定的了解,也可以熟悉一下Java图形界面以及Java语言的命名规范。作为数据结构的课程设计,本人希望同时也能让大家顺便熟悉一下Java的基本语言结构和强大的开发能力。 v .. .

..

. . . 资 料. . 在马踏棋盘的课程设计中,我们严格按照面向对象的思想进行开发,其中有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. v

.. .

合集下载

马踏棋盘

马踏棋盘

马踏棋盘

学 院

专 业

学 号

学生姓名

指导教师

年 月 日

摘要：

国际象棋想必大家都玩过，但你有没有想过，让一个“马”遍历国际象棋8*8的棋盘，有没有可能？如果有可能，在给定起点的情况下，有多少种可能？下面，我们将用计算机来模拟“马”对棋盘的遍历.

关键字：

回溯算法 贪心算法 遍历

正文：

已知国际象棋为8×8棋盘，共64个格，规则中，马按照如图所示规则移动。将马放在任意方格中，令马遍历每个方格一次且仅一次，编制非递归程序，将数字1，2，„，64按照马的行走路线依次填入一个8×8的方阵，并输出结果。

通过结合图示，我们不难发现，当马的起始位置（i,j）确定的时候，可以走到下列8个位置之一：

(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-1,j-2)、(i-2,j-1)

但是，如果（i，j）靠近棋盘的边缘，上述有些位置可能超出棋盘范围，成为不可达的位置。8个可能位置可以用一维数组Htry1[0„7]和HTry2[0..7]来表示：

Htry1：

0 1 2 3 4 5 6 7

-2 -1 1 2 2 1 -1 -2

Htry2：

0 1 2 3 4 5 6 7

1 2 2 1 -1 -2 -2 -1

所以位于（i,j）的马可以走到新位置是在棋盘范围内的（i+

数据结构课程设计马的遍历

数据结构课程设计马的遍历

课 程 设 计 说 明 书

课程名称： 数据结构

设计题目： 马的遍历

院 系： 计算机科学与信息工程学院

学生姓名：

学 号：

专业班级：

指导教师：

2015 年 6 月 7 日

课 程 设 计 任 务 书

设计题目 马的遍历

学生姓名 所在院系 计算机科学与信息工程学院 专业、年级、班

设计要求：

任意行列数的棋盘中，马只能走“日”字。马从任意位置处出发，把棋盘的每一格都走一次，且只走一次。要求在屏幕上画出棋盘和马所有经过的路径。

学生应完成的工作：

1.分析题目要求

2.利用数据结构和c语言知识找出实现方法

3.编程完成实现

4.按要求撰写课程设计报告和设计总结。

参考文献阅读：

1.《c程序设计（第四版）》，谭浩强 清华大学出版社

2.《数据结构（c语言版）》，严蔚敏 吴伟民 清华大学出版社

工作计划：

1. 接到题目后用课余时间设计程序，

2. 第14周上机调试通过后，答辩，交报告（具体时间由各任课教师决定）。

任务下达日期： 2015年 4 月 28 日

任务完成日期： 2015年 6 月 6 日

指导教师（签名）： 学生（签名）：

马的遍历

摘 要：中国象棋中马采用“日”字走法，对棋盘上马所在的结点，一步内到达的结点最多有八个，所以可以采用类似图的深度优先遍历，以马所在点为初始点对整个棋盘进行遍历。然后按遍历的顺序输出结点 可以用一个二维数组chess[][]来表示棋盘，一开始用来存放步骤号，若走过了则把它赋值为0。对于动态演示问题，只要在“马”的位置显示“马”，已经走过的位置显示“●”，未走过的位置显示“┌”“ ┬”“ ┐”“├”等制表符，然后清屏，显示下一步，再清屏，依次类推。

马踏棋盘的实习报告

马踏棋盘的实习报告

马踏棋盘的实习报告

实习报告：马踏棋盘

一、实习单位及实习岗位简介

实习单位：ABC软件公司

实习岗位：算法工程师助理

二、实习内容和任务

作为算法工程师助理，我的主要任务是协助开发团队完成一个名为“马踏棋盘”的小游戏的设计和实现。该游戏是基于棋盘上的骑士的移动规则进行设计的。

具体任务及完成情况如下：

1.学习和理解“马踏棋盘”游戏的规则。

在开始设计游戏之前，首先需要深入了解和理解“马踏棋盘”的规则。通过查阅相关资料和与开发团队成员的讨论，我对游戏规则有了初步的认识和理解。

2.设计游戏的棋盘和角色。

根据游戏规则的要求，我与开发团队成员一起设计和绘制了游戏的棋盘和角色。棋盘采用8*8的方格，并且在其中的随机位置放置了一些障碍物，增加游戏的难度和挑战性。角色则是一个具有代表骑士的形象的图标。

3.实现骑士的移动和规则判断。 在游戏中，骑士可以根据特定的移动规则在棋盘上移动。根据游戏规则的要求，我编写了相应的算法，实现了骑士的移动和规则判断的功能。通过这个功能，用户可以通过点击棋盘上的方格，移动骑士来完成游戏的目标。

4.添加游戏的界面和交互。

除了基本的游戏功能以外，我们还为游戏设计了用户友好的界面和交互。通过游戏界面，用户可以清楚地看到棋盘和角色的位置，并且可以通过点击方格或者使用方向键来控制骑士的移动。同时，我们还添加了计时器和得分系统，提升了游戏的趣味性和挑战性。

5.进行游戏的测试和优化。

为了确保游戏的稳定性和良好的体验效果，我们进行了多轮的测试和优化。通过不断地发现和修复bug，我们最终完成了一个可以正常运行、界面友好、操作流畅的游戏。

三、实习收获和体会

在这次实习中，我通过与开发团队的合作，深入了解了算法在游戏开发中的应用。通过参与“马踏棋盘”游戏的设计和实现，我不仅加深了对算法和数据结构的理解，在实践中熟悉了常用的算法编程技巧，还提升了团队协作和解决问题的能力。

通过这次实习，我深刻体会到了算法在实际项目中的重要性和应用价值。算法的设计优化直接影响着游戏的性能和用户体验，而且在游戏中的算法也与实际生活中的问题有着密切的关联。同时，我也认识到了自己在算法设计和实现方面的不足之处，需要进一步提升自己的能力。 在团队合作中，我学会了与开发团队成员进行沟通和协作，更好地理解需求和完成任务。在这个过程中，我学到了如何更高效地运用算法解决问题，如何组织代码和进行测试，如何进行优化和调试等技能，这些对我今后的学习和工作都有很大的帮助。

马踏棋盘非递归算法

马踏棋盘非递归算法

马踏棋盘非递归算法

#include

struct point

{

int x,y;//马的位置

int dir;//这一次马行走的方向

};

struct stack

{

point p[64];//存储马的位置，方便回溯

};

int board [8][8];

int Htry1[8]={-2,-1,1,2,2,1,-1,-2};

int Htry2[8]={1,2,2,1,-1,-2,-2,-1};

bool chech[8][8]={0};//标记位置是否已经被占用

int main()

{

int i,j;

int top=0;

int z;

cout<<"请输入马的初始位置";

cin>>i;

cin>>j;

stack sta;

sta.p[top].x=i;

sta.p[top].y=j;

board [i][j]=top;

chech [i][j]=true;

int nx; int ny;

for(int u=0;u<64;u++)

sta.p[u].dir=0;//把每个结点的dir清零

for(z=0;;)

{

if(sta.p[top].x+Htry1[z]>=0&&sta.p[top].x+Htry1[z]<8&&

sta.p[top].y+Htry2[z]>=0&&sta.p[top].y+Htry2[z]<8&&

!chech [sta.p[top].x+Htry1[z]][sta.p[top].y+Htry2[z]]//检查要走的下个位置是否可行

)

{

nx=sta.p[top].x+Htry1[z];

ny=sta.p[top].y+Htry2[z];

sta.p[top].dir=z;

top++;

sta.p[top].x=nx;

sta.p[top].y=ny;

board [nx][ny]=top;

chech [nx][ny]=true;

z=-1;