数据结构实验报告马踏棋盘

1、目 录1 课程设计的目的x2 需求分析x3 课程设计报告内容x1、概要设计x2、详细设计x3、调试分析x4、用户手册x5、测试结果x6、程序清单x4 小结 x5 参考文献 x2011年5月23日1、 课程设计的目的（1） 熟练使用栈和队列解决实际问题；（2） 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；（3） 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；（4） 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；2、 需求分析*问题描述：将马随机放在国际象棋的8X8棋盘Bo阿rd0.7,0.7的某个方格中，马按走棋规则进行移动。要求每个

2、方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线 ，并按求出的行走路线，将数字1，2，64依次填入8X8的方阵输出之。*测试数据：由读者指定,可自行指定一个马的初始位置。*实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。3、课程设计报告内容根据分析先建了2个结构体struct PosType /马的坐标位置类型int m_row; /行值int m_col;/列值;struct DataType /栈的元素类型PosType se

3、at; /马在棋盘中的“坐标位置” int di;/换方向的次数;chess:chess()bool chess:chessPath(PosType start) /在棋盘中进行试探寻找下一步位置并同时记录位置，以及涉及到的入栈出栈void chess:Print() /打印马走的路径PosType chess:NextPos(PosType a,int di)/根据当前点的位置a和移动方向di，试探下一位置4、总结一、这次课程设计的心得体会通过实践我的收获如下：1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，

4、深入研究，分析问题、解决问题的能力。二、根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点： 1、认真上好专业实验课，多在实践中锻炼自己。2、写程序的过程中尽量在正确的基础上追求简洁。3、在做设计的时候要有信心，有耐心，切勿浮躁。4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用，不过也不能完全依赖课本。5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。 6、参考文献（1）万健主编，数据结构实用教程（C+版），电子工业出版社，2011（2）网上搜索相关程序作为参考7、程序运行结果：附件：#include <iost

5、ream>using namespace std;#include "SqStack.h"struct PosType /马的坐标位置类型int m_row; /行值int m_col;/列值;struct DataType /栈的元素类型PosType seat; /马在棋盘中的“坐标位置” int di;/换方向的次数;class chesspublic:chess();bool chessPath(PosType);void Print();private:PosType NextPos(PosType c , int d );int m_chess88; /

6、棋盘数组;chess:chess()int i,j;for(i=0;i<=7;i+)for(j=0;j<=7;j+)m_chessij=0;bool chess:chessPath(PosType start)SqStack<DataType> path(64); /创建栈PosType curpos;DataType e;curpos=start ;int curstep=1; /第几次走的位置doif(curpos.m_row<=7 && curpos.m_row>=0 && curpos.m_col>=0 &

7、;& curpos.m_col<=7)/走在棋盘之内if(m_chesscurpos.m_rowcurpos.m_col=0)m_chesscurpos.m_rowcurpos.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); elsecurpos=NextPos(curp

8、os,e.di+); /在棋盘之外自动进行下一次试探else /当前位置已走过if(!path.Empty()e=path.Top();path.Pop();curstep-;while(e.di=7 && !path.Empty() /该位置已无路可走m_chesse.seat.m_rowe.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);wh

9、ile(curstep<=64); /马已经走的步数return false;void chess:Print()int i,j;for(i=0;i<8;i+)for(j=0;j<8;j+)cout<<m_chessij<<'t' /输出对齐，水平制表cout<<endl;cout<<endl;PosType chess:NextPos(PosType a,int di)/根据当前点的位置a和移动方向di，试探下一位置PosType direct8=2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,

10、-2,2,-1;/按照顺时针试探的8个位置a.m_row+=directdi.m_row;a.m_col+=directdi.m_col;return a;void main()PosType first;chess chess;cout<<"请输入马的初始位置（第几行第几列):"cin>>first.m_row>>first.m_col;chess.chessPath(first);cout<<"马走过的一条路径如下："<<endl; chess.Print(); #define _SQSTA

11、CK_H_/定义顺序栈类template <class ElemType>/声明一个类模板class SqStackpublic: /顺序栈类的各成员函数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; /栈

12、顶指针int m_size; /向量空间大小;/构造函数，分配m个结点的顺序空间，构造一个空的顺序栈。template <class ElemType>SqStack <ElemType>:SqStack(int m)m_top = 0;m_base = new ElemTypem;m_size = m;/SqStack/析构函数，将栈结构销毁。template <class ElemType>SqStack <ElemType>:SqStack()if (m_base != NULL) delete m_base;/SqStack/清空栈。te

13、mplate <class ElemType>void SqStack <ElemType>:Clear()m_top = 0;/Clear/判栈是否为空，若为空，则返回true，否则返回false。template <class ElemType>bool SqStack <ElemType>:Empty() constreturn m_top = 0;/Empty/求栈的长度。template <class ElemType>int SqStack <ElemType>:Length() constreturn m_t

14、op;/Length/取栈顶元素的值。先决条件是栈不空。template <class ElemType>ElemType & SqStack <ElemType>:Top() constreturn m_basem_top - 1;/Top/入栈，若栈满，则先扩展空间。插入e到栈顶。template <class ElemType>void SqStack <ElemType>:Push(const ElemType &e) if(m_top >= m_size)/若栈满，则扩展空间。 ElemType *newbase; newbase = new ElemTypem_size +