数据结构课程设计-马踏棋盘实验报告(仅供参考)
花草树木-彼得与狼的故事
一、问题描述
问题描述：将马随机放在国际象棋的8X8棋盘Bo
阿rd[0..7,0..7]的某个
方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走
遍棋盘上全部
64个方格。编制非递归程序，求出马的行走路线
，并按求出的行走路线，将数
字1，2，„，64依次填入8X8的方阵输出之。
测试数据：由读者指定,可自行指定一个马的初始位置。
实现提示：每次在多个可走位置中选
择一个进行试探，其余未曾试探过的可
走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔
棋)使用。并探
讨每次选择位置的“最佳策略”，以减少回溯的次数。
二、实验目的
熟练使用栈和队列解决实际问题；
（1）
了解并掌握数据结构与算法的设计方
法，具备初步的独立分析和设计能力；
（2）
初步掌握软件开发过程的问题分析、系
统设计、程序编码、测试等基本方法和
技能；
（3） 提高综合运用所学的理论知识和方法独
立分析和解决问题的能力；
7
6
8
5
1
4
2
3
三、设计过程
算法设计思想：
根据分析先建了2个结构体
struct
PosType 马的坐标位置类型
{
int m_row; 行值
int m_col; 列值
};
struct
DataType 栈的元素类型
{
PosType seat; 马在棋盘中的“坐标位置”
int di;
换方向的次数
};
chess::chess()
bool
chess::chessPath(PosType start)
在棋盘中进行试探寻找下一步位置并同时记录
位置，以及涉及到的入栈出栈
void
chess::Print() 打印马走的路径
PosType
chess::NextPos(PosType a,int
di)根据当前点的位置a和移动方向di，试探
下一位置
（1）、位置的存储表示方式
typedef struct
{
int x;
int y;
int from;
}Point;
（2）、栈的存储方式
#define STACKSIZE 70
#define STACKINCREASE
10
typedef struct Stack
{
Point
*top;
Point *base;
int
stacksize;
};
（3）设定栈的抽象数据类型定义：
ADT
Stack {
数据对象：D=｛a
i
|
a
i
∈ElemSet,i=1,2,„,n,n≥0｝
数据关系：R1={
, a
i
>|a
i-1
,
a
i
∈D,i=2,„,n}
约定a
n
端为栈顶，a
i
端为栈顶。
基本操作：
InitStack(&s)
操作结果：构造一个空栈s，
DestroyStack(&s)
初始条件：栈s已存在。
操作结果：栈s被销毁。
ClearStack(&s)
初始条件：栈s已存在。
操作结果：栈s清为空栈。
StackEmpty(&s)
初始条件：栈s已存在。
操作结果：若栈s为空栈，则返回TRUE，否则返回FALSE。
StackLength(s);
初始条件：栈s存在。
操作结果：返回s的元素个数，即栈的长度。
GetTop
(s,&e);
初始条件：栈s已存在且非空。
操作结果：用e返回s的栈顶元素。
Push(&s,e)
初始条件：栈s已存在。
操作结果：插入元素e为新的栈顶元素。
Pop(&s,&e)
初始条件：栈s存在且非空。
操作结果：删除栈顶元素，并用e返回。
stackTraverse(s,visit())
初始条件：栈s存在且非空。
操作结果：从栈底到栈顶依次对s的每个元素调用visit()。一旦visit()
失败，
则操作失败。
}ADT Stack
四、功能测试
如下图：输入1 5进行数据测试，
测试成功！
五、实验总结与体会
根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点：
1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。
2、培养了我选
用参考书，查阅手册及文献资料的能力。培养独立思考，深入研
究，分析问题、解决问题的能力。
3、认真上好专业实验课，多在实践中锻炼自己。
4、写程序的过程中尽量在正确的基础上追求简洁。
5、在做设计的时候要有信心，有耐心，切勿浮躁。
6、认真的学习课本知识，掌握课本中的
知识点，并在此基础上学会灵活运用，
不过也不能完全依赖课本。
7、在课余时间里多写程序
，熟练掌握在调试程序的过程中所遇到的常见错误，
以便能节省调试程序的时间。
六、参考文献
万健主编，数据结构实用教程（C++版），电子工业出版社，2011
课本《数据结构》
七、源代码
#include
using
namespace std;
#include
struct
PosType 马的坐标位置类型
{
int m_row; 行值
int m_col; 列值
};
struct
DataType 栈的元素类型
{
PosType seat;
马在棋盘中的“坐标位置”
int di; 换方向的次数
};
class chess
{
public:
chess();
bool
chessPath(PosType);
void Print();
private:
PosType NextPos(PosType c , int d
);
int m_chess[8][8]; 棋盘数组
};
chess::chess()
{
int i,j;
for(i=0;i<=7;i++)
for(j=0;j<=7;j++)
m_chess[i][j]=0;
}
bool
chess::chessPath(PosType start)
{
SqStack
PosType
curpos;
DataType e;
curpos=start
int curstep=1; 第几次走的位置
do{
if(curpos.m_row<=7 && curpos.m_row>=0 &&
curpos.m_col>=0 && curpos.m_col<=7)走在棋盘之内
{
if(m_chess[curpos.m_row][curpos.m_col]==0){
m_chess[curpos.m_row][curpos.m_col]=curstep;
留下足迹，标注当
前位置是马第几次走
.m_row=curpos.m_row;
.m_col=curpos.m_col;
=0;
(e); 当前位置和方向入栈
curstep++;
if(curstep==65)
return true;
curpos=NextPos(curpos,); }
else
curpos=NextPos(curpos,++);
在棋盘之外自动进行下一次试探
}
else{ 当前位置已走过
if(!()){
e=();
();
curstep--;
while(==7 && !()){ 该位置已无路可走
m_chess[.m_row][.m_col]=0;
e=();
退回一步
();
curstep--;
}
if(<7){ 没到可能的最后一个位置
++; 换下一个位置
(e);
curstep++;
curpos=NextPos(,);
}
}
}
}while(curstep<=64); 马已经走的步数
return false;
}
void
chess::Print()
{
int i,j;
for(i=0;i<8;i++)
{for(j=0;j<8;j++)
cout<
cout<
cout<
}
PosType chess::NextPos(PosType a,int
di)根据当前点的位置a和移动方向di，试探
下一位置
{
PosType
direct[8]={{2,1},{1,2},{-1,2}
,{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};
按照顺时针试探的8个位置
a.m_row+=direct[di].m_row;
a.m_col+=direct[di].m_col;
return a;
}
void main()
{
PosType first;
chess chess;
cout<<请输入马的初始位置（第几行第几列):
cin>>first.m_row>>first.m_col;
ath(first);
cout<<马走过的一条路径如下：
();
}
#define _SQSTACK_H_
定义顺序栈类
template
class
SqStack
{
public:
顺序栈类的各成员函数
SqStack(int m = 100);
~SqStack();
void Clear();
bool
Empty() const;
int Length() const;
ElemType & Top() const;
void Push(const
ElemType &e);
void Pop();
private:
顺序栈类的数据成员
ElemType *m_base; 基地址指针
int m_top; 栈顶指针
int m_size;
向量空间大小
};
构造函数，分配m个结点的顺序空间，构造一个空的顺序栈。
template
SqStack
{
m_top = 0;
m_base = new ElemType[m];
m_size = m;
}SqStack
析构函数，将栈结构销毁。
template
SqStack
{
if
(m_base != NULL) delete[] m_base;
}~SqStack
清空栈。
template
void SqStack
{
m_top = 0;
}Clear
判栈是否为空，若为空，则返回true，否则返回false。
template
bool SqStack
{
return m_top
== 0;
}Empty
求栈的长度。
template
int SqStack
{
return
m_top;
}Length
取栈顶元素的值。先决条件是栈不空。
template
ElemType &
SqStack
{
return
m_base[m_top - 1];
}Top
入栈，若栈满，则先扩展空间。插入e到栈顶。
template
void SqStack
{
if(m_top >= m_size){
若栈满，则扩展空间。
ElemType *newbase;
newbase = new
ElemType[m_size + 10];
for(int j = 0;
j < m_top; j++)
newbase[j] =
m_base[j];
delete[] m_base;
m_base = newbase;
m_size += 10;
}
m_base[m_top++] = e;
}Push
出栈，弹出栈顶元素。先决条件是栈非空。
template
void SqStack
{
m_top--;
}Pop