数据结构课程设计-马踏棋盘实验报告(仅供参考).doc

一、问题描述 问题描述：将马随机放在国际象棋的8X8棋盘Bo阿rd0.7,0.7的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线 ，并按求出的行走路线，将数字1，2，64依次填入8X8的方阵输出之。 测试数据：由读者指定,可自行指定一个马的初始位置。 实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。817263542、 实验目的 熟练使用栈和队列解决实际问题；（1） 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；（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 10typedef struct Stack Point *top; Point *base; int stacksize;（3）设定栈的抽象数据类型定义： ADT Stack 数据对象：D=ai | aiElemSet,i=1,2,n,n0 数据关系：R1=|ai-1, aiD,i=2,n 约定an端为栈顶，ai端为栈顶。 基本操作： 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、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。 6、 参考文献万健主编，数据结构实用教程（C+版），电子工业出版社，2011课本数据结构七、源代码#include using namespace std;#include SqStack.hstruct 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; / 棋盘数组;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 path(64); /创建栈PosType curpos;DataType e;curpos=start ;int curstep=1; /第几次走的位置doif(curpos.m_row=0 & curpos.m_col=0 & 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(curpos,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.di7) /没到可能的最后一个位置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;i8;i+)for(j=0;j8;j+)coutm_chessijt; /输出对齐，水平制表coutendl;coutendl;PosType chess:NextPos(PosType a,int di)/根据当前点的位置a和移动方向di，试探下一位置PosType direct8=2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1;/按照顺时针试探的8个位置a.m_row+=directdi.m_row;a.m_col+=directdi.m_col;return a;void main()PosType first;chess chess;coutfirst.m_rowfirst.m_col;chess.chessPath(first);cout马走过的一条路径如下：endl; chess.Print(); #define _SQSTACK_H_/定义顺序栈类template /声明一个类模板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; /栈顶指针int m_size; /向量空间大小;/构造函数，分配m个结点的顺序空间，构造一个空的顺序栈。template SqStack :SqStack(int m)m_top = 0;m_base = new ElemTypem;m_size = m;/SqStack/析构函数，将栈结构销毁。template SqStack :SqStack()if (m_base != NULL) delete m_base;/SqStack/清空栈。template void SqStack :Clear()m_top = 0;/Clear/判栈是否为空，若为空，则返回true，否则返回false。template bool SqStack :Empty() constreturn m_top = 0;/Empty/求栈的长度。template int SqStack :Length() constreturn m_top;/Length/取栈顶元素的值。先决条件是栈不空。template ElemType & SqStack :Top() constreturn m_basem_top - 1;/Top/入栈，若栈满，则先扩展空间。插入e到栈顶。template void SqStack :Push(const ElemType &e) if(m_top = m_size)/若栈满，则扩展空间。 ElemTyp