马踏棋盘课程设计实验报告.docx
- 文档编号:16329618
- 上传时间:2023-07-12
- 格式:DOCX
- 页数:13
- 大小:161.18KB
马踏棋盘课程设计实验报告.docx
《马踏棋盘课程设计实验报告.docx》由会员分享,可在线阅读,更多相关《马踏棋盘课程设计实验报告.docx(13页珍藏版)》请在冰点文库上搜索。
马踏棋盘课程设计实验报告
《数据结构》
课
程
设
计
实
验
报
告
课程名称:
《数据结构》课程设计
课程设计题目:
马踏棋盘
*************************
院系:
计算机学院
专业:
计算机科学与技术
班级:
10052313
学号:
********
*************************
2012年5月18日
1.课程设计的目的………………………………………………………3
2.问题分析………………………………………………………………3
3.课程设计报告内容……………………………………………………3
(1)概要设计………………………………………………………3
(2)详细设计………………………………………………………3
(3)测试结果………………………………………………………5
(4)程序清单………………………………………………………6
4.个人小结……………………………………………………………10
1.课程设计的目的
《数据结构》是计算机软件的一门基础课程,计算机科学各领域及有关的应用软件都要用到各种类型的数据结构。
学好数据结构对掌握实际编程能力是很有帮助的。
为了学好《数据结构》,必须编写一些在特定数据结构上的算法,通过上机调试,才能更好地掌握各种数据结构及其特点,同时提高解决计算机应用实际问题的能力。
2.问题分析
*问题描述:
将马随机放在国际象棋的8X8棋盘Bo阿rd[0..7,0..7]的某个方格中,马按走棋规则进行移动。
要求每个方格上只进入一次,走遍棋盘上全部64个方格。
编制非递归程序,求出马的行走路线,并按求出的行走路线,将数字1,2,…,64依次填入8X8的方阵输出之。
*测试数据:
由读者指定,可自行指定一个马的初始位置。
*实现提示:
每次在多个可走位置中选择一个进行试探,其余未曾试探过的可走位置必须用适当结构妥善管理,以备试探失败时的“回溯”(悔棋)使用。
并探讨每次选择位置的“最佳策略”,以减少回溯的次数。
3.课程设计报告内容
(1)概要设计
定义一张棋盘,定义一个栈保存马走的路径的点坐标和来自方向,用函数计算周围可走坐标,并检查正确性,当周围没有可走格子时退栈到最优位置,继续进行,然后将路径输出。
(2)详细设计
定义结构体,方向数组和Qioan类
structPoint
{
intx;//记录横坐标
inty;//记录纵坐标
intfrom;//前一个位置的方向
};
Pointside[8]={0,0,0};//记录可能的方向坐标
classQipan{
public:
Qipan();
~Qipan();
voidSetside(Point);//设置方向坐标
boolGetside(int,Point&);//将指定方向的坐标给特定指针
boolHorseVisit(Point);//输入开始点运行棋盘
boolPass(Point);//输出路径
private:
int**gezi;//棋盘格子
};
然后对每个函数进行定义
Qipan:
:
Qipan(){//构造函数构建棋盘
……
}
Qipan:
:
~Qipan(){//销毁棋盘
……
}
voidQipan:
:
Setside(Pointcur){//根据输入的当前点设置下一个点的可能方向坐标
……
}
boolQipan:
:
Getside(inti,Point&next){//根据方向把将坐标赋给下一个点
……
}
boolQipan:
:
HorseVisit(Pointbegin){//棋盘运行
……
}
最后是主函数,设计一些用户界面
intmain(){
bools=true;
while(s){
intcount=0;
intgezi[8][8]={0};
Pointbegin;
cout<<"请输入马的初始位置x和y:
";
cout< cout<<"其中1<=x,y<=8,如: 11"< cout<<"输入: "; cin>>begin.x>>begin.y;//输入起始点,并判断正确性 while(begin.x>8||begin.x<1||begin.y>8||begin.y<1){ cout<<"输入有误,请重新输入x和y: "< cout<<"其中1<=x,y<=8,如: 11"< cout<<"输入: "; cin>>begin.x>>begin.y; } begin.x--; begin.y--; begin.from=0; QipanA;//定义Qipan类的对象A s=A.HorseVisit(begin);//A运行函数HorseVisit } return0; } (3)测试结果 对于一次死路后退栈次数进行测试 1次用时很长且为运行出来 2次 3次 4次 5次 6次 又测试了其他几个点得出一次死路退栈5次能尽量少的减少退栈次数 其他几个点的数据 (4)程序清单 #include #include"SqStack.h" usingnamespacestd; #defineMAXSIZE70 #defineN8 structPoint { intx;//记录横坐标 inty;//记录纵坐标 intfrom;//前一个位置的方向 }; Pointside[8]={0,0,0};//记录可能的方向坐标 classQipan{ public: Qipan(); ~Qipan(); voidSetside(Point);//设置方向坐标 boolGetside(int,Point&);//将指定方向的坐标给特定指针 boolHorseVisit(Point);//输入开始点运行棋盘 boolPass(Point);//输出路径 private: int**gezi;//棋盘格子 }; Qipan: : Qipan(){//构造函数构建棋盘 inti,j; gezi=newint*[N]; for(i=0;i gezi[i]=newint[N]; } for(i=0;i for(j=0;j gezi[i][j]=0; } Qipan: : ~Qipan(){//销毁棋盘 for(inti=0;i if(gezi[i]==NULL) delete[]gezi[i]; } if(gezi==NULL) delete[]gezi; } voidQipan: : Setside(Pointcur){//根据输入的当前点设置下一个点的可能方向坐标 Pointround[]={{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(inti=0;i<8;i++){ side[i].x=round[i].x; side[i].y=round[i].y; } } boolQipan: : Getside(inti,Point&next){//根据方向把将坐标赋给下一个点 next.x=side[i-1].x; next.y=side[i-1].y; if(next.x<0||next.y<0||next.x>7||next.y>7)//判断坐标正确性 returnfalse; else returntrue; } boolQipan: : HorseVisit(Pointbegin){//棋盘运行 SqStack intcount=1;//定义count初始值为1,用于记录棋盘步数 charyn;//用于根据用户输入来选择执行或退出程序 bools;//通过yn来改变s真值改变程序运行 intcc[65]={0};//保存棋盘路径 Pointcur,next;//定义当前点,下一个点 horseVisit.Push(begin);//把起始点压栈 gezi[begin.x][begin.y]=count;//在棋盘上记录步数 while(count<64){//后续63步走法 cur=horseVisit.Top();//从栈中提取当前点 Setside(cur);//设置当前点周围方向坐标 boolflag=false;//定义标志 for(inti=cur.from+1;i<=8;i++){ if(Getside(i,next)&&(gezi[next.x][next.y]==0)){//如果设置方向正确,且格子为走过则运行 flag=true; gezi[next.x][next.y]=++count; cur=horseVisit.Top(); horseVisit.Pop(); cur.from=i; horseVisit.Push(cur); next.from=0; horseVisit.Push(next); break; } } if(! flag){//如果for循环执行完毕没有找到周围可走的格子,则退栈5次 intj=0; while(j<5&&horseVisit.Length()>1){//根据测试连续退栈五次最优化,退栈次数比较少 cur=horseVisit.Top(); horseVisit.Pop(); gezi[cur.x][cur.y]=0; count--; j++; } } } while(! horseVisit.Empty()){//上面运行完毕后,如果栈非空则取栈顶,计算出对应步数的格子序号保存起来输出路径 cur=horseVisit.Top(); horseVisit.Pop(); cc[count--]=(cur.x*8+cur.y+1); } horseVisit.Clear();//释放栈空间 cout<<"马踏棋盘的路线为: ";//输出路径 for(inti=1;i<65;i++) cout< cout< cout<<"您是否需要继续运行该程序(y--继续: n--退出): "; cin>>yn; cout< if(yn=='y'||yn=='Y')s=true; elses=false; returns; } intmain(){ bools=true; while(s){ intcount=0; intgezi[8][8]={0}; Pointbegin; cout<<"请输入马的初始位置x和y: "; cout< cout<<"其中1<=x,y<=8,如: 11"< cout<<"输入: "; cin>>begin.x>>begin.y;//输入起始点,并判断正确性 while(begin.x>8||begin.x<1||begin.y>8||begin.y<1){ cout<<"输入有误,请重新输入x和y: "< cout<<"其中1<=x,y<=8,如: 11"< cout<<"输入: "; cin>>begin.x>>begin.y; } begin.x--; begin.y--; begin.from=0; QipanA;//定义Qipan类的对象A s=A.HorseVisit(begin);//A运行函数HorseVisit } return0; } 4.个人小结 这是第二次写数据结构课程设计的代码,相对于第一次的生疏,这次已经能比较熟练地知晓题目应该如何编写的框架了,但具体实现的想法还是在网络中寻找了思路,然后写出了代码,一开始调试时一直出错,结果是自己在一个while循环的判断条件处多加了一个“! ”,这导致了我一直无法运行起程序,后来在自习检查代码后发现了这一点,由此看出,数据结构编写程序不仅要对学习的只是能够灵活运用在编写代码的时候还要仔细仔细再仔细。 我要在以后的学习中注意以下几点: 1.认真上好专业课,多在实践中锻炼自己。 2.写程序要考虑周到,严密。 3.在做设计的时候要有信心,有耐心,不浮躁。 4.认真学习课本知识,掌握课本中的知识点,并在此基础上学会灵活运用。 5.在课余时间多写程序,熟练掌握在调试程序过程中常见的错误,一边节约调试程序的时间。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 棋盘 课程设计 实验 报告