马踏棋盘课程设计实验报告.doc

数据结构课程设计实验报告课程名称：数据结构课程设计 课程设计题目：马踏棋盘 姓名：邱可昉 院系：计算机学院 专业：计算机科学与技术 班级：10052313 学号：10051319 指导老师：王立波 2012年5月18日目录1. 课程设计的目的32. 问题分析33. 课程设计报告内容3（1） 概要设计3（2） 详细设计3（3） 测试结果5（4） 程序清单64. 个人小结 101.课程设计的目的数据结构是计算机软件的一门基础课程，计算机科学各领域及有关的应用软件都要用到各种类型的数据结构。学好数据结构对掌握实际编程能力是很有帮助的。为了学好数据结构，必须编写一些在特定数据结构上的算法，通过上机调试，才能更好地掌握各种数据结构及其特点，同时提高解决计算机应用实际问题的能力。2.问题分析*问题描述：将马随机放在国际象棋的8X8棋盘Bo阿rd0.7,0.7的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线 ，并按求出的行走路线，将数字1，2，64依次填入8X8的方阵输出之。*测试数据：由读者指定,可自行指定一个马的初始位置。*实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。3.课程设计报告内容（1）概要设计定义一张棋盘，定义一个栈保存马走的路径的点坐标和来自方向，用函数计算周围可走坐标，并检查正确性，当周围没有可走格子时退栈到最优位置，继续进行，然后将路径输出。（2） 详细设计定义结构体，方向数组和Qioan类struct Point int x; /记录横坐标 int y; /记录纵坐标 int from;/前一个位置的方向 ;Point side8=0,0,0; /记录可能的方向坐标 class Qipanpublic:Qipan();Qipan();void Setside(Point);/设置方向坐标 bool Getside(int,Point &);/将指定方向的坐标给特定指针 bool HorseVisit(Point);/输入开始点运行棋盘 bool Pass(Point);/输出路径 private:int *gezi;/棋盘格子 ;然后对每个函数进行定义Qipan:Qipan()/构造函数构建棋盘 Qipan:Qipan()/销毁棋盘 void Qipan:Setside(Point cur)/根据输入的当前点设置下一个点的可能方向坐标 bool Qipan:Getside(int i,Point &next ) /根据方向把将坐标赋给下一个点 bool Qipan:HorseVisit(Point begin)/棋盘运行 最后是主函数，设计一些用户界面int main()bool s=true;while(s)int count=0;int gezi88=0;Point begin;cout请输入马的初始位置x和y：;coutendl;cout其中1=x,y=8,如：1 1 endl;coutbegin.xbegin.y;/输入起始点，并判断正确性 while(begin.x8|begin.x8|begin.y1)cout输入有误，请重新输入x和y：endl; cout其中1=x,y=8,如：1 1 endl;coutbegin.xbegin.y;begin.x-; begin.y-; begin.from=0; Qipan A;/定义Qipan类的对象A s=A.HorseVisit(begin);/A运行函数HorseVisitreturn 0;（3）测试结果对于一次死路后退栈次数进行测试1次用时很长且为运行出来2次3次4次5次6次又测试了其他几个点得出一次死路退栈5次能尽量少的减少退栈次数其他几个点的数据（4）程序清单#include#include SqStack.husing namespace std;#define MAXSIZE 70#define N 8struct Point int x; /记录横坐标 int y; /记录纵坐标 int from;/前一个位置的方向 ;Point side8=0,0,0; /记录可能的方向坐标 class Qipanpublic:Qipan();Qipan();void Setside(Point);/设置方向坐标 bool Getside(int,Point &);/将指定方向的坐标给特定指针 bool HorseVisit(Point);/输入开始点运行棋盘 bool Pass(Point);/输出路径 private:int *gezi;/棋盘格子 ;Qipan:Qipan()/构造函数构建棋盘 int i,j; gezi = new int *N;for(i=0; iN; i+)gezii=new intN;for(i=0; iN; i+)for(j=0; jN; j+)geziij=0;Qipan:Qipan()/销毁棋盘 for(int i=0; iN;i+) if(gezii=NULL)delete gezii;if(gezi=NULL)delete gezi;void Qipan:Setside(Point cur)/根据输入的当前点设置下一个点的可能方向坐标 Point round = cur.x-2,cur.y-1,0,cur.x-1,cur.y-2,0,cur.x+1,cur.y-2,0,cur.x+2,cur.y-1,0,cur.x+2,cur.y+1,0,cur.x+1,cur.y+2,0,cur.x-1,cur.y+2,0,cur.x-2,cur.y+1,0,; for(int i=0;i8;i+) sidei.x = roundi.x; sidei.y = roundi.y; bool Qipan:Getside(int i,Point &next ) /根据方向把将坐标赋给下一个点 next.x = sidei-1.x; next.y = sidei-1.y; if(next.x0 | next.y7 | next.y7)/判断坐标正确性 return false; else return true; bool Qipan:HorseVisit(Point begin)/棋盘运行 SqStack horseVisit(MAXSIZE);/新建栈 int count=1;/定义count初始值为1，用于记录棋盘步数 char yn;/用于根据用户输入来选择执行或退出程序 bool s;/通过yn来改变s真值改变程序运行 int cc65=0;/保存棋盘路径 Point cur,next; /定义当前点，下一个点 horseVisit.Push(begin); /把起始点压栈 gezibegin.xbegin.y=count; /在棋盘上记录步数 while(count64) /后续63步走法 cur=horseVisit.Top();/从栈中提取当前点 Setside(cur);/设置当前点周围方向坐标 bool flag = false; /定义标志 for(int i=cur.from+1;i=8;i+) if(Getside(i,next)&(gezinext.xnext.y=0) /如果设置方向正确，且格子为走过则运行 flag = true; gezinext.xnext.y= +count; cur=horseVisit.Top(); horseVisit.Pop(); cur.from=i; horseVisit.Push(cur); next.from = 0; horseVisit.Push(next); break; if(!flag) /如果for循环执行完毕没有找到周围可走的格子，则退栈5次 int j=0; while(j1) /根据测试连续退栈五次最优化，退栈次数比较少 cur=horseVisit.Top();horseVisit.Pop(); gezicur.xcur.y = 0;count-;j+; while(!horseVisit.Empty()/上面运行完毕后，如果栈非空则取栈顶，计算出对应步数的格子序号保存起来输出路径 cur=horseVisit.Top();horseVisit.Pop(); cccount-=(cur.x*8+cur.y+1);horseVisit.Clear();/释放栈空间 cout马踏棋盘的路线为：;/输出路径 for(int i=1;i65;i+) coutcci ; coutendl; coutyn; coutendl; if(yn=y|yn=Y) s=true; else s=false; return s;int main()bool s=true;while(s)int count=0;int gezi88=0;Point begin;cout请输入马的初始位置x和y：;coutendl;cout其中1=x,y=8,如：1 1 endl;coutbegin.xbegin.y;/输入起始点，并判断正确性 while(begin.x8|begin.x8|begin.y1)cout输入有误，请重新输入x和y：endl; cout其中1=x,y=8,如：1 1 endl;coutbegin.xbegin.y;begin.x-; begin.y-; begin.from=0; Qipan A;/定义Qipan类的对象A s=A.HorseVisit(begin);/A运行函数HorseVisitreturn 0;4.个人小结这是第二次写数据结构课程设计的代码，相对于第一次的生疏，这次已经能比较熟练地知晓题目应该如何编写的框架了，但具体实现的想法还是在网络中寻找了思路，然后写出了代码，一开始调试时一直出错，结果是自己在一个while循环的判断条件处多加了一个“！”，这导致了我一直无法运行起