数据结构
课程设计报告
题学专
目
马踏棋盘
院____计算机学院______业_计算机科学与技术
年级班别____2005级7班__学号3105007083
学生姓名______林春茂指导教师______刘添添_______
2007年6月
f问题描述
设计一个国际象棋的马踏棋盘的演示程序。
基本要求
将马随机放在国际象棋88的棋盘Board88的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘全部的64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，364一次填入一个88的方阵输出之
测试数据
可自行指定一个马的初始位置（ij）0ij7。
实现提示
一般说来，当马位于位置（ij）时，可以走到下列8个位置之一（i2j1）i1j2i1j2i2j1i2j1i1j2i1j2i2j1但是，如果（i，j）靠近棋盘的边缘，上述有些位置可能超出棋盘范围，成为不允许的位置。8个可能位置可以用一维数组Htry107和HTry207来表示：Htry1072Htry20711122
11
2221
3231
4142
515212
6
6
位于（ij）的马可以走到新位置是在棋盘范围内的（iHtry1hjHtry2h）其中h017
选作内容
1求出从某一七点出发的多条至全部行走路线。2探讨每次选择位置的“最佳策略”，以减少回溯的次数。3演示寻找行走路线的回溯过程。
f一．需求分析
1．输入的形式和输入值的范围；分开输入马的初始行坐标X和列坐标Y，X和Y的范围都是［07］。2．输出的形式；一共提供了2种输出方式：（1）以数组下标形式输入，代表起始位置，i表示行标，j表示列标。（2）以棋盘形式输出，每一格打印马走的步数，这种方式比较直观。3．程序所能达到的功能；（1）让马从任一起点出发都能够历遍整个8×8的棋盘。（2）能寻找多条不同的行走路径。4．测试数据，包括正确的输入及输出结果和含有错误的输入及其输出结果。数据可以任定，只要0X70Y7就可以了。正确的输出结果为一个2维数组，每个元素的值表示马行走的第几步。若输入有错，程序会显示“输入错误，请重新输入”并且要求用户重新输入数据，直至输入正确为止。
二．概要设计
1．设定栈的抽象数据类型定义：ADTStack数据对象：Daiai∈CharSeti12
数据关系R1ai1aiai1ai∈Di2
基本操作这里仅列举本题中使用的操作I
itStackS操作结果构建一个空栈。PushSe操作结果在栈顶插入新的元素。Pop（Se）操作结果：将栈顶元素弹出。SetTopSe操作结果：将e设为栈顶元素。GetTopSe操作结果：将r