数据结构实验报告马踏棋盘
- 格式：doc
- 大小：76.50 KB
- 文档页数：8
--
-- 目 录
1 课程设计的目的………………………………………………………………x
2 需求分析………………………………………………………………………x
3 课程设计报告内容……………………………………………………………x
1、概要设计……………………………………………………………………x
2、详细设计……………………………………………………………………x
3、调试分析……………………………………………………………………x
4、用户手册……………………………………………………………………x
5、测试结果……………………………………………………………………x
6、程序清单……………………………………………………………………x
4 小结 …………………………………………………………………………x
5 参考文献 ………………………………………………………………x
2011年5月23日
1、 课程设计的目的
（1） 熟练使用栈和队列解决实际问题；
（2） 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；
（3） 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
（4） 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
2、 需求分析
*问题描述：将马随机放在国际象棋的8X8棋盘Bo阿rd[0..7,0..7]的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线 ，并按求出的行走路线，将数字1，2，…，64依次填入8X8的方阵输出之。
*测试数据：由读者指定,可自行指定一个马的初始位置。
*实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。
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，试探下一位置
4、总结
一、这次课程设计的心得体会通过实践我的收获如下：
1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。
2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。
二、根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点：
1、认真上好专业实验课，多在实践中锻炼自己。
2、写程序的过程中尽量在正确的基础上追求简洁。
3、在做设计的时候要有信心，有耐心，切勿浮躁。
4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用，不过也不能完全依赖课本。
5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。
6、参考文献
（1）万健主编，数据结构实用教程（C++版），电子工业出版社，2011
（2）网上搜索相关程序作为参考
7、程序运行结果： --
--
附件：
#include
using namespace std;
#include "SqStack.h"
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 path(64); //创建栈
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; //留下足迹，标注当前位置是马第几次走
e.seat.m_row=curpos.m_row;
e.seat.m_col=curpos.m_col;
e.di=0;
path.Push(e); //当前位置和方向入栈
curstep++;
if(curstep==65)
return true;
curpos=NextPos(curpos,e.di); }
else
curpos=NextPos(curpos,e.di++); //在棋盘之外自动进行下一次试探
}
else{ //当前位置已走过
if(!path.Empty()){
e=path.Top();
path.Pop();
curstep--;
while(e.di==7 && !path.Empty()){ //该位置已无路可走
m_chess[e.seat.m_row][e.seat.m_col]=0;
e=path.Top(); //退回一步 --
--
path.Pop();
curstep--;
}
if(e.di<7){ //没到可能的最后一个位置
e.di++; //换下一个位置
path.Push(e);
curstep++;
curpos=NextPos(e.seat,e.di);
}
}
}
}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;
chess.chessPath(first); --
-- cout<<"马走过的一条路径如下："<
chess.Print();
}
#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 ::SqStack(int m)
{
m_top = 0;
m_base = new ElemType[m];
m_size = m;
}//SqStack
//析构函数，将栈结构销毁。
template
SqStack ::~SqStack()
{
if (m_base != NULL) delete[] m_base;
}//~SqStack
//清空栈。
template
void SqStack ::Clear()
