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

《数据结构》

课

程

设

计

实

验

报

告

课程名称：《数据结构》课程设计

课程设计题目：马踏棋盘

姓名：邱可昉

院系：计算机学院

专业：计算机科学与技术

班级：10052313 学号：10051319 指导老师：王立波

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类

struct Point

{

int x; //记录横坐标

int y; //记录纵坐标

int from; //前一个位置的方向

};

Point side[8]={0,0,0}; //记录可能的方向坐标

class Qipan{

public:

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 gezi[8][8]={0};

Point begin;

cout<<"请输入马的初始位置x和y：";

cout<

cout<<"其中1<=x,y<=8,如：1 1 "<

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,如：1 1 "<

cout<<"输入：" ;

cin>>begin.x>>begin.y;

}

begin.x--;

begin.y--;

begin.from=0;

Qipan A; //定义Qipan类的对象A

s=A.HorseVisit(begin); //A运行函数HorseVisit }

return 0;

}

（3）测试结果

对于一次死路后退栈次数进行测试1次用时很长且为运行出来

2次

3次

4次

5次

6次

又测试了其他几个点得出一次死路退栈5次能尽量少的减少退栈次数其他几个点的数据

（4）程序清单

#include

#include "SqStack.h"

using namespace std;

#define MAXSIZE 70

#define N 8

struct Point

{

int x; //记录横坐标

int y; //记录纵坐标

int from; //前一个位置的方向

};

Point side[8]={0,0,0}; //记录可能的方向坐标

class Qipan{

public:

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; i

gezi[i]=new int[N];

}

for(i=0; i

for(j=0; j

gezi[i][j]=0;

}

Qipan::~Qipan(){ //销毁棋盘

for(int i=0; i

if(gezi[i]==NULL)

delete[] gezi[i];

}

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;i<8;i++) {

side[i].x = round[i].x;

side[i].y = round[i].y;

}

}

bool Qipan::Getside(int i,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) //判断坐标正确性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 cc[65]={0}; //保存棋盘路径

Point cur,next; //定义当前点，下一个点

horseVisit.Push(begin); //把起始点压栈

gezi[begin.x][begin.y]=count; //在棋盘上记录步数

while(count<64) { //后续63步走法

cur=horseVisit.Top(); //从栈中提取当前点

Setside(cur); //设置当前点周围方向坐标

bool flag = false; //定义标志

for(int i=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次

int j=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(int i=1;i<65;i++)

cout<

cout<

cout<<"您是否需要继续运行该程序（y--继续：n--退出）:";

cin>>yn;

cout<

if(yn=='y'||yn=='Y') s=true;

else s=false;

return s;

}

int main(){

bool s=true;

while(s){

int count=0;

int gezi[8][8]={0};

Point begin;

cout<<"请输入马的初始位置x和y：";

cout<

cout<<"其中1<=x,y<=8,如：1 1 "<

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,如：1 1 "<

cout<<"输入：" ;

cin>>begin.x>>begin.y;

}

begin.x--;

begin.y--;

begin.from=0;

Qipan A; //定义Qipan类的对象A

s=A.HorseVisit(begin); //A运行函数HorseVisit }

return 0;

}

4.个人小结

这是第二次写数据结构课程设计的代码，相对于第一次的生疏，这次已经能比较熟练地知晓题目应该如何编写的框架了，但具体实现的想法还是在网络中寻找了思路，然后写出了代码，一开始调试时一直出错，结果是自己在一个while循环的判断条件处多加了一个“！”，这导致了我一直无法运行起程序，后来在自习检查代码后发现了这一点，由此看出，数据结构编写程序不仅要对学习的只是能够灵活运用在编写代码的时候还要仔细仔细再仔细。

我要在以后的学习中注意以下几点：

1.认真上好专业课，多在实践中锻炼自己。

2.写程序要考虑周到，严密。

3.在做设计的时候要有信心，有耐心，不浮躁。

4.认真学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。

5.在课余时间多写程序，熟练掌握在调试程序过程中常见的错误，一边节约调试程序的时间。