杭电数据结构马踏棋盘.doc

《数据结构》
课程设计报告
课程名称:
《数据结构》课程设计
课程设计题目:
马塔棋盘
姓名:

院系:
计算机学院
专业:
计算机科学与技术
年级:
大二
学号:

指导教师:
王立波
2012年5月17日

目录
1 课程设计的目的………………………………………………………………x
2 需求分析………………………………………………………………………x
3 课程设计报告内容……………………………………………………………x
1、概要设计……………………………………………………………………x
2、详细设计……………………………………………………………………x
3、测试结果……………………………………………………………………x
4、程序清单……………………………………………………………………x
4 小结…………………………………………………………………………x
5 参考文献………………………………………………………………x
课程设计的目的
熟练使用C++语言编写程序,解决实际问题;
了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力;
初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;
提高综合运用所学的理论知识和方法独立分析和解决问题的能力;
需求分析
1、任务:
(一):设置一个含有{x,y,di}变量的结构体。
定义马向八个方向走的所在位置坐标的变化
int htrx[lenx]={-2,-1,1,2,2,1,-1,-2};
htry[leny]={1,2,2,1,-1,-2,-2,-1};
(二):初始化数组mata[8][8],全部赋为0。
(三):判断该位置是否能走(是否已走过,或超出8X8的矩阵)
(四):对马走的下一个可能方向按一定顺序进行处理。将马可能走的下一个方向按照下下个方向能走的度进行从大到小的顺序压入栈中(不能通过的标记为-1)
(五):处理棋盘。
马的行走路线,并按求出的行走路线,将数字1,2,…,64依次填入8X8的方阵输出之。
定义curstep=1,mata[x][y]=1;((x,y)为用户输入的初始数据)
判断path是否为空,若不为空,
判断path的栈顶元素的di是否小于0
若di小于0,退栈。
否则若mata[x][y] >0((x,y)为栈顶元素的坐标) mata[x][y]=0(清除走过痕迹)
Curstep--;步伐值减一, 出栈
否则
mata[x][y]=++curstep;对马走过的位置进行标记
根据此位置,重新对马走的下一个可能方向进行排序。
若已走完64个位置
输出“马在此位置能走遍全部的格子”
则打印mata[8][8]数组
若path为空,则输出“马在此位置不能走遍全部的格子”
2、测试数据
在8*8的矩阵中输出1~64的数,且没有重复
3、课程设计报告内容
概要设计
(1)在分析题目要求的基础上,我首先设计了一个结构体,定义如下
struct Post
{
int x;
int y;
int di;//该位置能走的方向
};存储坐标信息。
测试结果:
4、小