数据结构课程设计 马踏棋盘求全部解及演示程序
安徽工程大学信息10 课程设计
马踏棋盘的求解及演示设计
摘要
数据结构是计算机科学与技术专业的一门核心专业基础课程，是一门理论性强、思维抽象、难度较大的课程。我认为学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，我们应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。《数据结构》课程设计是计算机科学技术专业集中实践性环节之一，是学习完《数据结构》课程后进行的一次全面的综合练习。开设本课程设计实践的主要目的就是要达到理论与实际应用相结合，提高学生的动手能力，完成计算机应用能力的培养；本课程设计主要解决马踏棋盘的问题，找出踏遍棋盘的多种路径，并实现动态要是过程。
马踏棋盘问题，实际上是图论中的哈密顿通路问题，是典型的NP问题,求解的问题与算法设计有很大关系，如果采取穷举搜索的话，很容易陷入海量搜索的状态，耗费巨大的时间，使问题几乎不可解，因此马在棋盘上遍历采用算法当中的深度优先算法和启发式贪心算法，用栈来存储遍历过程，通过对栈的使用实现对所有路径的搜索。在调试过程发现，启发式贪心算法，针对于马踏棋盘问题有着极大的好处，就是无论从棋盘上哪个点开始，找到一条遍历完棋盘的通路是不需要回溯的，也就节省了大量的时间，而试探性的操作对于每个点都也只有168步，所以求出所有路径在不到一秒的时间内完成。
关键词：马踏棋盘；骑士周游；哈密顿通路;NP-完全问题；贪心算法；回溯法；
目录
马踏棋盘的求解及演示设计......................... 错误！未定义书签。目录........................................... 错误！未定义书签。第一章引言................................. 错误！未定义书签。第二章需求分析................................. 错误！未定义书签。
2.1问题描述....................................... 错误！未定义书签。
2.2基本要求....................................... 错误！未定义书签。
2.3具体需求....................................... 错误！未定义书签。
2.4开发环境....................................... 错误！未定义书签。第三章概要设计................................. 错误！未定义书签。
3.1 系统概述....................................... 错误！未定义书签。
3.2 系统描述....................................... 错误！未定义书签。
3.3逻辑设计....................................... 错误！未定义书签。第四章详细设计................................. 错误！未定义书签。
4.1 功能模块设计.................................. 错误！未定义书签。
4.2 数据结构设计.................................. 错误！未定义书签。
4.3算法设计....................................... 错误！未定义书签。第五章调试与分析............................... 错误！未定义书签。
5.1 调试分析....................................... 错误！未定义书签。第六章系统试用说明............................. 错误！未定义书签。
6.1 系统试用说明................................... 错误！未定义书签。第七章总结与体会............................... 错误！未定义书签。参考文献......................................... 错误！未定义书签。
第一章引言
本课程设计主要研究马踏棋盘的问题，即骑士周游问题，是将马随机放在国际象棋的8×8棋盘的某个方格中,“马”按照走棋规则进行移动，要求每个方格只进入一次,走遍棋盘上全部64个方格。许多知名的数学家，如德莫弗(De Moivre)、欧拉(Euler)与范德蒙德(Vandermonde)等人，在过去的200年中都研究过这个问题，今天从数据结构的角度，解决这一问题。力求以最快的速度，即最高的效率来解决问题。已知穷举法是几乎不可能完成的，而与解决迷宫问题的回溯法，也要占用大量的时间，这里采用贪心算法来解决这一问题，并找出多有的遍历路径。
第二章需求分析
2.1 问题描述
马随机放在国际象棋的8×8棋盘的某个方格中,“马”按照走棋规则进行移动，要求每个方格只进入一次,走遍棋盘上全部64个方格。设计一个国际象棋的马踏遍棋盘的演示程序。
2.2基本要求
设计合适的数据结构，编制递归以及非递归程序,求出马的行走路线,并按求出的马的行走路线,将路线1,2,…,64依次填入一个8×8的方阵,输出之，若有多种走法，则能将全部的输出。必须要能够将踏遍棋盘的过程显示在计算机屏幕上。
要求：
（1）描述设计所涉及的数据模型，设计高效的数据结构完成总体设计，搭好框架，确定人机对话的界面（要求界面上能动态体现出演示的过程），实现功能；
（2）界面友好，函数功能要划分好
（3）要有算法设计的流程图
（4）程序要加必要的注释
（5）要提供程序测试方案
2.3具体需求
1、首先要找到马踏棋盘棋盘的多条路径。
2、实现马踏棋盘的动态演示过程。
3、优化算法，提高算法效率，以递归与非递归的方式实现
2.4开发环境
开发环境：Windows 8
辅助工具：Visual Studio 2012 ,MyEclipse 10.5
运行环境：Windows XP/Vista/7/8
第三章 概要设计
3.1 系统概述
3.11 系统流程图
3.12 主函数main()的执行流程
求解多条路径子系统： 自动演示路径子系统
N
Y
马踏棋盘演示系统
求解多条路径
自动演示路径
开始
输入起始点
判断合法性
N
Y
3.2 系统描述
通过VS2012完成的寻找多条路径的子系统，通过java 来实现马踏棋盘的动态演示子系统。在寻找多条路径的子系统中，通过启发式贪心算法，将某点的下一步最少通往其它落脚点，将该点确定为最佳落点。每次只走下一步通向其他点最少的点。用栈记录探寻的过程，将走过的点标记为1，试探而没有走的点标记为0.最后通过寻找出栈标志为0的点来寻找其他路径。在动态显示模块式通过java 的线程机制是先的自动动画演示。
3.3逻辑设计
抽象数据类型
棋盘上某点的位置坐标结构体Postion 把个方向试探的增量位置数组direct[8]
棋盘某点通向其他点的可到达数的二位数组access[8][8] 链栈
用来记录可到达下一位置坐标的数组 ：nextPath[8]; 用来记录整个遍历过程的数组： tourpos[64];
遍历(找出一条路径)
tour(Postion)
打印找到的路径
fprint()
寻找其他路径
other_Path （Postion ）
打印全部路径
结束
开始
寻找下一步
next_Path(Postion )
// 开始移动
domoving(Postion )
//尝试下一步的移动extAccessible();
While(hasM orePath())
递归调用 tour ( nextPath[arrayPos]);
结束
第四章详细设计
4.1 功能模块设计
4.1.2创建模块
本模块创建棋盘，以及棋盘上每一点的可到达数，一个向8个方向试探的增量数组。
以及记录整个遍历流程的链栈。
选择或设计数据结构的存储结构，实现存储结构的基本运算、设计的模块构成、各模块的简要说明、流程图、调用关系表等。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。
4.1.3操作模块
实现对棋盘的周游，并找到多条路径
4.1.4 显示模块
将找到的所有路径显示在屏幕上，并统计找到的路径数。
4.1.5自动演示模块
通过Java的Applet和线程机制，实现对找到的路径进行动态演示。
4.2 数据结构设计
4.2.1数据设计
定义棋盘上某点的位置坐标结构体Postion
typedef struct
{
int x;
int y;
}Postion;
定义把个方向试探的增量位置数组
Postion direct[8]={{1,2},{2,1},{2,-1},{1,-2}，{-1,-2},{-2,-1},{-1,2},{-2,1}};
定义棋盘某点通向其他点的可到达数的二位数组 int access[8][8] = { {2,3,4,4,4,4,3,2}, {3,4,6,6,6,6,4,3}, {4,6,8,8,8,8,6,4}, {4,6,8,8,8,8,6,4}, {4,6,8,8,8,8,6,4}, {4,6,8,8,8,8,6,4}, {3,4,6,6,6,6,4,3}, {2,3,4,4,4,4,3,2}
};
定义一个以 某一棋盘上的点和标志的类型，作为栈的存储数据
typedef struct { Postion p;
int flag; } DataType ; 定义一个链栈：
typedef struct node //定义结点结构 {
DataType data; struct node *next;
}StackNode ,*PStackNode ;
//////////////////////////////////////// typedef struct //定义一个栈 { PStackNode top;
}LinkStack ,*PLinkStack ;
用来记录可到达下一位置坐标的数组 ：Postion nextPath[8];
8
7
6
5
4
3
2
1
用来记录整个遍历过程的数组：Postion tourpos[64];
4.3算法设计
寻找下一条路径：
开始
流程图：略：
算法描述：
应考察每一方格的可到达性。使用数组accessibility []表示可达到数,并当马踏棋盘时，程序动态修正剩余格子的可达到数。accessibility [ arrayPos ] = 0 表明格子已经被占据。
算法：void next_Path(Postion P)
{
Postion testPos;
for (int i = 0 ; i < 8 ; i++ )
{//有八种到达的情况
testPos.x = P.x + direct[ i ].x;//得出X,Y坐标的测试位置
testPos.y = P.y + direct[ i ].y;
if (checkPath(testPos))
{//判断测试位置是否在棋盘内
nextPath[arrayPos]=testPos ;//由测试位置给出正确X,Y坐标
accessibility [ arrayPos ] = access [testPos.x][testPos.y]; //利用对应的X,Y坐标得出相应的可到达的路径总数
if (accessibility [ arrayPos ] > 0 ) // accessibility [ arrayPos ] = 0 表明格子已经被占据
arrayPos ++ ;
}//寻找空格子结束
}// 结束for循环,寻找结束
countAccessibility = arrayPos ;//统计可达到数
if (countAccessibility > 0 )
{
sortAll();
}
arrayPos = -1 ;
}
////////////////////////////////////////////////////////////////
2.使用冒泡法来查询最小数。
void sortAll ()
{ //冒泡排序法.冒泡排序的基本概念是：依次比较相邻的两个数，将大数放在前面，小数
放在后面。//保持稳定性
int temp;
Postion temps;
for ( int i = 0 ; i < countAccessibility - 1 ; i ++ )
{
for ( int j = i + 1; j < countAccessibility ; j ++ )
{
if ( accessibility [ i ] > accessibility [ j ] )
{
temps=nextPath[i];
nextPath[i]=nextPath[j];
nextPath[j]=temps;
temp = accessibility [ i ];
accessibility [ i ] = accessibility [ j ];
accessibility [ j ] = temp;
}//end of if
}// end of inner for
}// end of outer for
}// end of sortAll
3.//////////////////////////////////////////////
3、向下一步移动，将当前要走的结点入栈，标记为1，其他可到达但没有走的点入栈，标记为0 如果当前坐标走过，那么它可以到达的其它点的可到达数应该-1
最后将该点的可到达数更新为0
void domoving(Postion P)
{
for ( int i = 0 ; i < countAccessibility ; i ++ )
{
DataType q;
q.p=nextPath[i];
if(i==0)
{
q.flag=1;
} else
{
q.flag=0;
}
Push_LinkStack(S,q);
access[ nextPath[i].x ][ nextPath[i].y ] -- ;
}
//直到没有路径了
access[ P.x ][ P.y] = 0 ;//当前位置置0
}
4、打印路径：打印8×8棋盘，在棋盘中显示马跳的步骤：
void fprint()
{ //输出路径
int order[8][8]={0}; //-----初始化
for(int k=0;k<64;k++)
{
order[tourpos[k].x][tourpos[k].y]=k;
}
cout<<"\n 棋盘表示\n";
cout<<" 0 1 2 3 4 5 6 7\n" ;
cout<<" +----+----+----+----+----+----+----+----+\n";
for(int i=0;i<8;i++)
{
printf(" ");
printf("%2d",i);
for(int j=0;j<8;j++)
{
printf("| %2d ",order[i][j]);
}
printf("|");
printf("\n");
if(i==7)
printf(" +----+----+----+----+----+----+----+----+");
else
printf(" +----+----+----+----+----+----+----+----+");
printf("\n");
}
printf(" ");
}
5、寻找其他路径：
算法描述：
将栈中存储的路径出栈，判断标记是否为0，并累计标记为1的个数count_next，即走过的步数，方便撤销走过的步骤，根据count_next来撤销走过的步骤，先将在access[][]撤销，即还原为1，将当前为flag为0的复制到下一步的tourpos[]数组中，之后将tourpos[]后面的步骤还原为0，再结束后，在寻找下一条路径，若找不到，则继续出栈，向前回溯。
void other_Path()
{//寻找其他路径
int count=0;
int recount=0,coutpath=0,count_next=0;
DataType Ps[169];
while(!Empty_LinkStack(S))
{ int flag=0;
Pop_LinkStack(S,&Ps[count]);
if(Ps[count].flag!=0)
{
count_next++;
}
if(Ps[count].flag==0)
{
access[ tourpos[63-count_next].x][tourpos[63-count_next].y]=1;
tourpos[63-count_next]=Ps[count].p;
for(int i=0;i { access[ tourpos[63-i].x][tourpos[63-i].y]=1; tourpos[63-i].x=0; tourpos[63-i].y=0; } access[ tourpos[63-count_next].x][tourpos[63-count_next].y]=0; for(int j=count_next;j>0;j--) { if(! tour_next( tourpos[63-j],63-j)) { flag=1; break; } } if(flag!=1){ coutpath++; fprint(); } } count++; } cout< cout<<"周游结束共找到"< } 动态演示：根据JAVA线程机制，每隔800毫秒动画演示1步。 public void run() { //启动线程后将自动调用run（）方法，在run（）方法内产生一个控制动画的循环int delay = 800; while(true){ count = 0; for(int i=0;i<64;i++){ repaint(); //repaint（）将调用paint（）方法画一帧图像 count++; if(recount>63) { final Frame from= new Frame(); JOptionPane.showMessageDialog(from, "周游完成"); return; } try { Thread.sleep(delay); } catch (Exception e) { } } } } 第五章调试与分析 5.1 调试分析 经过对程序的编制，调试和运行，使我更好的掌握了栈基本性质和有关马的遍历问题的解决方法，熟悉了各种调用的数据类型，在调试和运行过程中使我更加的了解和熟悉程序运行的环境，提高了我对程序调试分析的能力和对错误的纠正能力。 5.1.1、 首先要检测贪心算法的可用性，先找出一条路径;检测输出的路径是否合法 5.1.2、 完成一条路径的输出之后，进行栈的检查，检查栈中存储的元素是否正确能否满足回溯的标准，经过检测栈的合法性才能对栈中元素进行操作，最后就是，实现对其他路径的寻找，并统计路径的条数。 第六章系统试用说明 6.1 系统试用说明 系统提示用户输入测试坐标，输入坐标应满足必须为整数，且大于等于0，小于8 两点之间以空格隔开。 及满足在棋盘上点的的要求。 测试数据：0 0 ；1 0；7 7，2 3 第七章总结与体会 通过本次课程设计掌握了关于数据结构的很多内容如算法的设计，栈的使用，对图的深度优先遍历算法有了更深入的了解，对于马踏棋盘这一问题，有了独到研究和见解，让学习的理论与实际应用相结合，提高了我的动手能力，以及独立解决问题的能力，如使用Java来动态演示马踏棋盘的步骤，本来学习java 是对于用于动画的线程机制就没有深入了解，经过这次的课程设计，在网上查阅资料，在几天内，我学会了如何使用java的线程机制来实现动画演示程序，可对以说是一个不小的受获。对数据结构的应用上也得到很大的提升，前面做实验都是一些验证性的实验，只是把书上的代码输进去，检测它的正确性，和它的算法思想，而这次是在问题的前提下，来确定数据结构，在算法思想的前提下，来确定算法的使用，并根据各种可行的算法来确定最优的算法，即时空效率最高。并且在写出解决查找多种路径的算法后，很有成就感，因为在网上，这一问题只有求出一条路径的方法，也没有动态演示的，很不符合课程设计的要求，并且发现，如果只找一条路径的话，要是算法用的灵活，可以说没学数据结构之前也可解决，所以在找到所有路径的时候内心很喜悦，大概这就是编程的乐趣吧。本次数据结构课程设计确实收益匪浅。 参考文献 ××××××××××××××××××××××××××××××××××××××××××× 参考文献书写格式应符合GB7714－87《文后参考文献著录规则》。常用参考文献编写项目和顺序规定如下： 先安排中文(按姓氏笔划排序)，后安排英语（或其他语种）(按字母先后排列)； 注释置于页脚，参考文献置于文末。参考文献只列出最主要的、且是公开发表的文献，非正式公开发表的资料不列。 文献主要类型格式如下： 期刊：[序号] 作者．篇名[J]． 附录// NP_compelte.cpp : 定义控制台应用程序的入口点。 // // NP_compelte.cpp : 定义控制台应用程序的入口点。 // #include"stdafx.h" #include using namespace std; #define Max 100 typedef struct { int dx; int dy; }direct_increment; direct_increment direct_ay[8]={{1,2},{2,1},{2,-1},{-1,-2},{-2,-1},{1,-2},{-1,2},{-2,1}}; int access[8][8] = { {2,3,4,4,4,4,3,2}, {3,4,6,6,6,6,4,3}, {4,6,8,8,8,8,6,4}, {4,6,8,8,8,8,6,4}, {4,6,8,8,8,8,6,4}, {4,6,8,8,8,8,6,4}, {3,4,6,6,6,6,4,3}, {2,3,4,4,4,4,3,2} }; int accessibility[8]; int countAccessibility; typedef struct { int x; int y; }Postion; static Postion nextPath[8]; static Postion tourpos[64]; static int arrayPos=0; static int ownAccessibility ;//当前棋子的可到达数 static int countMoving=-1; bool success = false; ////////////////////////////////////// typedef struct{ Postion p; int flag; } DataType; typedef struct node//定义结点结构 { DataType data; struct node *next; }StackNode,*PStackNode; //////////////////////////////////////// typedef struct//定义一个栈 { PStackNode top; }LinkStack,*PLinkStack; ///////////////////////////////////////// //////////////////////////////////////// PLinkStack Init_LinkStack() //初始化函数 { PLinkStack S; S=(PLinkStack)new(LinkStack); if(S) S->top->next=NULL; return (S); } ///////////////////////////////////////////////////// bool Empty_LinkStack(PLinkStack S)//判断栈空函数 { return (S->top==NULL); } ////////////////////////////////////////////////////// int Push_LinkStack(PLinkStack S,DataType x) // 入栈函数{ PStackNode p; p= new (StackNode); if(!p) { return 0; } p->data=x; p->next=S->top; S->top=p; return 1; } ///////////////////////////////////////////////////// int Pop_LinkStack(PLinkStack S,DataType *x)//出栈函数 { PStackNode p; if(Empty_LinkStack(S)) return 0; else { *x=S->top->data; p=S->top; S->top=S->top->next; delete(p); return 1; } } //////////////////////////////////////////////////// int GetTop_LinkStack(PLinkStack S,DataType *x)//取栈顶元素{ if(Empty_LinkStack(S)) return 0; else { *x=S->top->data; return 0; } } //////////////////////////////////////////////////// void Destroy_LinkStack(PLinkStack *LS) //销毁栈函数 { PStackNode p,q; if(*LS) { p=(*LS)->top; while(p) { q=p; p=p->next; delete(q); } delete(*LS); } *LS=NULL; return; } PLinkStack S=Init_LinkStack(); ////////////////////////////////////////// bool checkPath(Postion P) {//判断测试位置是否在棋盘内 if(P.x>=0&&P.x<8&&P.y>=0&&P.y<8) { return true; }else { return false; } } /////////////////////////////////////////////////// ////////////////////////////////////////////////// void sortAll () { //冒泡排序法.冒泡排序的基本概念是：依次比较相邻的两个数，将大数放在前面，小数放在后面。//保持稳定性 int temp; Postion temps; for ( int i = 0 ; i < countAccessibility - 1 ; i ++ ) { for ( int j = i + 1; j < countAccessibility ; j ++ ) { if ( accessibility [ i ] > accessibility [ j ] ) { temps=nextPath[i]; nextPath[i]=nextPath[j]; nextPath[j]=temps; temp = accessibility [ i ]; accessibility [ i ] = accessibility [ j ]; accessibility [ j ] = temp; }//end of if }// end of inner for }// end of outer for }// end of sortAll ////////////////////////////////////////////// void next_Path(Postion P) { Postion testPos; for (int i = 0 ; i < 8 ; i++ ) {//有八种到达的情况 testPos.x = P.x + direct_ay[ i ].dx;//得出X,Y坐标的测试位置 testPos.y = P.y + direct_ay[ i ].dy; if (checkPath(testPos)) {//判断测试位置是否在棋盘内 nextPath[arrayPos]=testPos ;//由测试位置给出正确X,Y坐标 accessibility [ arrayPos ] = access [testPos.x][testPos.y]; //利用对应的X,Y坐标得出相应的可到达的路径总数 if (accessibility [ arrayPos ] > 0 ) // accessibility [ arrayPos ] = 0 表明格子已经被占据 arrayPos ++ ; }//寻找空格子结束 }// 结束for循环,寻找结束 countAccessibility = arrayPos ;//统计可达到数 if (countAccessibility > 0 ) { sortAll(); } arrayPos = -1 ; } //////////////////////////////////////////////////////////////// bool hasMorePath() { // arrayPos + 1 指向下一个可行的 if ( (arrayPos + 1 ) < countAccessibility ) { return true; } else { return false; } }// hasMoreAccessible()方法结束 //////////////////////////////////////////////////////////////// void nextAccessible() 西安郵電學院 数据结构 课内实验报告书 院系名称：计算机学院 实验题目：马踏棋盘 学生姓名： 专业名称：计算机科学与技术班级： 学号： 时间： 2011年10月10日指导教师：曾艳 一、实验题目：马踏棋盘 二、实验目的： 通过本次实验，熟练掌握抽象数据类型栈和队列的实现，学会使用栈和队列解决具体应用问题，从而体会栈和队列的特点。 三、实验要求： 设计一个国际象棋的马踏遍棋盘的演示程序。 要求：将马随机放在国际象棋的8×8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出之 四、设计与实现过程 （1）栈或队列的定义及其主要操作的实现 struct Chess { int x; int y; int h;/*h记录下一次需要试探的马字格式的下标值*/ }Chess1[65]; （2）主要算法的描述 void Handlechess(int m,int n) { int flag=1,i; double j=0.0;/*增加了j用于统计while循环的执行次数，很好奇循环到底执行了多少次*/ int chessx[8]={-2,-2,-1,-1,1,1,2,2};/*马字的格式的8个位置，按下标序依次试探*/ int chessy[8]={-1,1,-2,2,-2,2,-1,1}; for(i=1;i<=64;i++) Chess1[i].h=0;/*赋初值*/ chess[m][n]=flag; Chess1[flag].x=m; Chess1[flag].y=n; while(flag<64) { j+=1.0; for(i=Chess1[flag].h;i<8;i++)/*i的初值由Chess1[flag].h确定*/ { m=Chess1[flag].x+chessx[i]; n=Chess1[flag].y+chessy[i]; if((m>=0&&m<=7&&n>=0&&n<=7)&&(chess[m][n]==0))/*去掉了函数，改为直接用关系表达式判断，提高运行速度*/ { Chess1[flag].h=i+1;/*h记录下一次需试探马字格式位置的下标*/ flag++; 2.4题马踏棋盘 题目：设计一个国际象棋的马踏棋盘的演示程序 班级：姓名：学号：完成日期： 一．需求分析 （1）输入的形式和输入值的范围：输入马的初始行坐标X和列坐标Y， X和Y的范围都是[1,8]。 （2）输出形式： 以数组下表的形式输入，i为行标，j为列标，用空格符号隔开。以棋盘形式输出，每一格打印马走的步数，这种方式比较直观 （3）程序所能达到的功能：让马从任意起点出发都能够遍历整个8*8的 棋盘。 （4）测试数据，包括正确输入及输出结果和含有错误的输入及其输出结 果。数据可以任定，只要1<=x,y<=8就可以了。 正确的输出结果为一个二维数组，每个元素的值表示马行走的第几步，若输入有错，则程序会显示：“输入有误！请重新输入……”并且要求用户重新输入数据，直至输入正确为止。 二．概要设计 （1）、位置的存储表示方式 （2） typedef struct { int x; int y; int from; }Point; （2）、栈的存储方式 #define STACKSIZE 70 #define STACKINCREASE 10 typedef struct Stack { Point *top; Point *base; int stacksize; }; （1）、设定栈的抽象数据类型定义： ADT Stack { 数据对象：D=｛ai | ai∈ElemSet,i=1,2,…,n,n≥0｝ 数据关系：R1={ 马踏棋盘问题 摘要： 马踏棋盘就是在国际象棋8X8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。理解栈的“后进先出”的特性以及学会使用回溯。 关键字：马踏棋盘、递归、栈、回溯 1．引言 马踏棋盘就是在国际象棋8X8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。 编制程序，求出马的行走路线，并按求出的行走路线，将数字1，2….64依次填入一个8X8的方阵，并输出它的行走路线。输入：任意一个起始位置；输出：无重复踏遍棋盘的结果，以数字1-64表示行走路线。 2．需求分析 （1）需要输出一个8X8的棋盘，可以采用二维数组的方法实现。 （2）输入马的起始位置，必须保证输入的数字在规定范围内，即0<=X<=7,0<=Y<=7。 （3）保证马能走遍整个棋盘，并且不重复。 （4）在棋盘上输出马的行走路线,标记好数字1、2、3直到64。 3．数据结构设计 采用栈数组为存储结构。 #define maxsize 100 struct { int i; int j; int director; }stack[maxsize]; 4．算法设计 4.1 马的起始坐标 void location(int x,int y) //马的位置坐标的初始化 { top++; stack[top].i=x; //起始位置的横坐标进栈 stack[top].j=y; //起始位置的竖坐标进栈 stack[top].director=-1; a[x][y]=top+1; //标记棋盘Try(x,y); //探寻的马的行走路线 } 4.2 路径探寻函数 void Try(int i,int j) { int count,find,min,director; int i1,j1,h,k,s; int b[8]={-2,-2,-1,1,2,2,1,-1},c[8]={1,-1,-2,-2,-1,1,2,2} ; //存储马各个出口相对当前位置行、列坐标的增量数组 int b2[8],b1[8]; for(h=0;h<=7;h++) //用数组b1[8]记录当前位置的下一个位置的可行路径的条数 { count=0; i=stack[top].i+c[h]; j=stack[top].j+b[h]; if(i>=0&&i<=7&&j>=0&&j<=7&&a[i][j]==0) //如果找到下一个位置 { for(k=0;k<=7;k++) { i1=i+c[k]; j1=j+b[k]; if(i1>=0&&i1<=7&&j1>=0&&j1<=7&&a[i1] 数据结构课程设计 题目：马踏棋盘 院系： 班级： 学号： 姓名： 2014-2015年度第1学期 马踏棋盘 一．题目：马踏棋盘 (3) 二. 设计目标 (3) 三. 问题描述 (3) 四. 需求分析 (4) 五. 概要设计 (4) 第一步：定义四个常量和一个数据类型 (4) 第二步：构造函数 (4) 六. 详细设计（给出算法的伪码描述和流程图） (5) 流程图设计 (5) 代码分析 (9) 第一步：定义常量与变量 (9) 第二步：构造函数 (9) ●定义一个结构体类型 (9) ●创建一个初始化函数 (10) ●创建提示输入函数 (10) ●创建产生新节点函数 (11) ●创建计算路径函数 (12) ●创建入栈函数 (13) ●创建出栈函数 (13) ●创建输出函数 (13) 第三步：在主函数中调用其它函数 (15) 七. 测试分析 (16) 八. 使用说明 (16) 九. 测试数据 (16) 十．课程设计总结 (17) 一．题目：马踏棋盘 二. 设计目标 帮助学生熟练掌握顺序栈的基本操作，让学生深入了解栈的使 用，使得更深层次的灵活运用栈。 三. 问题描述 ○所谓的马踏棋盘是：将马随机放在国际象棋的8×8棋盘的某个方格中，马按走棋规则（马走日字）进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。由用户自行指定一个马的初始位置，求出马的行走路线，并按照求出的行走路线的顺序，将数字1、2、…、64依次填入一个8X8的方阵并输出。 从用户给出的初始位置开始判断，按照顺时针顺序，每次产生一个新的路点，并验证此路点的可用性，需要考虑的是当前路点是否超出棋盘范围和此路点是否已经走过。如果新路点可用，则入栈，并执行下一步，重复进行如上步骤，每次按照已走路点的位置生成新路点。如果一个路点的可扩展路数为0，进行回溯，直到找到一个马能踏遍棋盘的行走路线并输出。 《数据结构》 课程设计报告 课程名称：《数据结构》课程设计课程设计题目： 姓名： 院系： 专业： 年级： 学号： 指导教师： 2011年月日 目录 1、程序设计的目的 2、设计题目 3、分析 4、设计思想 5、算法 6、测试结果 7、调试分析 8、小结 1、课程设计的目的 1、熟练使用C++语言编写程序，解决实际问题； 2、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 3、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 4、提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 5、学习并熟悉栈的有关操作； 6、利用栈实现实际问题； 2、设计题目 【马踏棋盘】 *问题描述：将马随机放在国际象棋的8X8棋盘Bo阿rd[0..7,0..7]的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入8X8的方阵输出之。 *测试数据：由读者指定,可自行指定一个马的初始位置。 *实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳 策略”，以减少回溯的次数。 3、分析 确定输入值的范围，输入马的初始行坐标X和Y，X和Y的范围都是1到8之间。程序的功能是输出马走的步骤，要使马从任一起点出发，通过程序能找到下一个地点，然后遍历整个棋盘。每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。输出时可以用二维数组。 4、设计思想 输入马初始位置的坐标。将初始位置进栈，经过一个while循环，取出符合条件的栈顶元素。利用函数，找出栈顶元素周围未被占用的新位置，如果有，新位置入栈；否则弹出栈顶元素。再进行判断，最后输出。 位置的存储方式，栈的存储方式和一些操作函数为： #include . 杭州师范大学钱江学院课程设计 题目马踏棋盘算法研究 教学院信息与机电工程分院 专业计算机科学与技术 班级计算机1201 姓名吴秋浩 指导教师王李冬 2013 年12 月21 日 目录 一．概述 (3) 二．总体方案设计 (3) 三．详细设计 (4) 四．最终输出 (7) 五．课程设计总结 (11) 参考文献 (15) 一概述 1.课程设计的目的 （1）课题描述 设计一个国际象棋的马踏遍棋盘的演示程序。 （2）课题意义 通过“马踏棋盘”算法的研究，强化了个人对“栈”数据结构的定义和运用，同时也锻炼了自身的C语言编程能力。另一方面，通过对“马踏棋 盘”算法的研究，个人对“迷宫”、“棋盘遍历”一类的问题，有了深刻 的认识，为今后解决以此问题为基础的相关的问题，打下了坚实的基础。 （3）解决问题的关键点说明 解决问题的关键首先要熟练掌握C语言编程技术，同时能够熟练运用“栈”数据结构。另外，态度也是非常重要的。在课程设计过程中，难免 会遇到困难，但是不能轻易放弃，要肯花时间，能静得下心，积极查阅相 关资料，积极与指导老师沟通。 2.课程设计的要求 （1）课题设计要求 将马随机放在国际象棋的8×8棋盘Board[0～7][0～7]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方 格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1， 2，…，64依次填入一个8×8的方阵，输出之。 程序由回溯法和贪心法实现，比较两种算法的时间复杂度。 （2）课题设计的思路 首先，搞清楚马每次在棋盘上有8个方向可走，定义两个一位数组，来存储马下一着点的水平和纵向偏移量。程序再定义一个8*8二维数组，初始 所有元素置0，起始点元素置1。若为回溯法，初始方向数据（一维数组下 标）入栈。随后，马从起始点开始，每次首先寻找下一可行的着点，然后记 下方向，方向数据入栈，把该位置元素置为合适的序列号，若无下一可行着 点，则回溯，寻找下一方向位置着点，以此类推，直到64填入数组中，则 输出二维数组，即为马可走的方案。若为贪婪法，选择下一出口的贪婪标准 是在那些允许走的位置中，选择出口最少的那个位置。直到没有下一着点位 置，若此时已标记到64，则找到可行方案，输出之。反之，改变初始寻找方 向继续寻找，直到8种方向顺序都试过，若还是没有合适的方案，则说明以 该起始 点开始马无法踏遍棋盘。 实现顺序栈或循环队列的存储 一、实验目的 （1）、理解栈的特性“后进先出”和队列的特性“先进先出”。 （2）、仅仅认识到栈和队列是两种特殊的线性表是远远不够的，本次实验的目的在于更深入的了解栈和队列的特性，以便在实际问题背景下灵活运用他们。 （3）、在了解他特性的基础上，还将巩固对这种结构的构造方法的理解。 二、实验环境 （1）Windows XP系统下 （2）编程环境：VC6.0++ 三、实验内容 （1）、要求：在国际象棋8×8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。编制程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，并输出它的行走路线（棋盘如图所示）。 （2）、输入：任意一个起始位置； 输出：无重复踏遍棋盘的结果，以数字1-64表示行走路线。 0 1 2 3 4 5 6 7 0 8 1 1 7 2 2 H 3 6 3 4 5 4 5 6 7 （3）、数据结构要求：采用顺序栈或者链栈实现。 四、实验步骤 为了实现上述程序功能，可以采用顺序栈或者链栈来存储它的数据，本实验所需要的存储空间不是很大，不需动态的开辟很多空间，所以采用相对简单的顺序栈来存储数据，既方便有简单，而用链栈在实现上相对比顺序栈复杂的一点。 （一）、概要设计 （1）、顺序栈的抽象数据类型定义： ADT Stack{ 数据对象：D={a i| a i∈（0，1，…，9），i=0,1，2，…，n，n≥0} 数据关系：R={< a i-1, a i >| a i-1, a i∈D,i=1,2，…，n} } ADT Stack （2）本程序包含三个模块： 1、主程序模块： void main(){ 定义变量； 接受命令； 处理命令； 退出； } 2、起始坐标函数模块——马儿在棋盘上的起始位置； 3、探寻路径函数模块——马儿每个方向进行尝试，直到试完整个棋盘； 4、输出路径函数模块——输出马儿行走的路径； 各模块之间的调用关系： 主程序模块 输入的初始位置是否正确 否 是 起始坐标函数模 探寻路径函数模 输出路径函数模 结束 （二）、详细设计 《数据结构》 课 程 设 计 实 验 报 告 课程名称：《数据结构》课程设计 课程设计题目：马踏棋盘 姓名：邱可昉 院系：计算机学院 专业：计算机科学与技术 班级：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; //棋盘格子 }; 目录 1 课程设计的目的 (x) 2 需求分析 (x) 3 课程设计报告内容 (x) 1、概要设计 (x) 2、详细设计 (x) 3、调试分析 (x) 4、用户手册 (x) 5、测试结果 (x) 6、程序清单 (x) 4 小结 (x) 5 参考文献 (x) 2011年5月23日 1、课程设计的目的 （1）熟练使用栈和队列解决实际问题； （2）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； （3）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； （4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 2、需求分析 *问题描述：将马随机放在国际象棋的8X8棋盘Bo阿rd[0..7,0..7]的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入8X8的方阵输出之。 *测试数据：由读者指定,可自行指定一个马的初始位置。 *实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。 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，试探下一位置 4、总结 一、这次课程设计的心得体会通过实践我的收获如下： 1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。 2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。 二、根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点： 1、认真上好专业实验课，多在实践中锻炼自己。 2、写程序的过程中尽量在正确的基础上追求简洁。 3、在做设计的时候要有信心，有耐心，切勿浮躁。 4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用，不过也不能完全依赖课本。 5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。 6、参考文献 （1）万健主编，数据结构实用教程（C++版），电子工业出版社，2011 （2）网上搜索相关程序作为参考 7、程序运行结果： 马踏棋盘 学院 专业 学号 学生姓名 指导教师 年月日 摘要： 国际象棋想必大家都玩过，但你有没有想过，让一个“马”遍历国际象棋8*8的棋盘，有没有可能？如果有可能，在给定起点的情况下，有多少种可能？下面，我们将用计算机来模拟“马”对棋盘的遍历. 关键字： 回溯算法贪心算法遍历 正文： 已知国际象棋为8×8棋盘，共64个格，规则中，马按 照如图所示规则移动。将马放在任意方格中，令马遍历每个方 格一次且仅一次，编制非递归程序，将数字1，2， (64) 照马的行走路线依次填入一个8×8的方阵，并输出结果。 通过结合图示，我们不难发现，当马的起始位置（i,j） 确定的时候，可以走到下列8个位置之一： (i-2,j+1)、(i-1,j+2)、(i+1,j+2)、(i+2,j+1)、(i+2,j-1)、 (i+1,j-2)、(i-1,j-2)、(i-2,j-1) 但是，如果（i，j）靠近棋盘的边缘，上述有些位置可能超出棋盘范围，成为不可达的位置。8个可能位置可以用一维数组Htry1[0…7]和HTry2[0..7]来表示： Htry1： 0 1 2 3 4 5 6 7 -2 -1 1 2 2 1 -1 -2 Htry2： 0 1 2 3 4 5 6 7 1 2 2 1 -1 -2 -2 -1 所以位于（i,j）的马可以走到新位置是在棋盘范围内的（i+ Htry1[h],j+Htry2[h]）,其中h的取值是0~7. 整个问题，我们可以用两种算法来解决，既“回溯算法”与“贪心算法”我们先来看回溯算法： 搜索空间是整个棋盘上的8*8个点.约束条件是不出边界且每个点只能经过 安徽工程大学信息10 课程设计 马踏棋盘的求解及演示设计 摘要 数据结构是计算机科学与技术专业的一门核心专业基础课程，是一门理论性强、思维抽象、难度较大的课程。我认为学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，我们应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。《数据结构》课程设计是计算机科学技术专业集中实践性环节之一，是学习完《数据结构》课程后进行的一次全面的综合练习。开设本课程设计实践的主要目的就是要达到理论与实际应用相结合，提高学生的动手能力，完成计算机应用能力的培养；本课程设计主要解决马踏棋盘的问题，找出踏遍棋盘的多种路径，并实现动态要是过程。 马踏棋盘问题，实际上是图论中的哈密顿通路问题，是典型的NP问题,求解的问题与算法设计有很大关系，如果采取穷举搜索的话，很容易陷入海量搜索的状态，耗费巨大的时间，使问题几乎不可解，因此马在棋盘上遍历采用算法当中的深度优先算法和启发式贪心算法，用栈来存储遍历过程，通过对栈的使用实现对所有路径的搜索。在调试过程发现，启发式贪心算法，针对于马踏棋盘问题有着极大的好处，就是无论从棋盘上哪个点开始，找到一条遍历完棋盘的通路是不需要回溯的，也就节省了大量的时间，而试探性的操作对于每个点都也只有168步，所以求出所有路径在不到一秒的时间内完成。 关键词：马踏棋盘；骑士周游；哈密顿通路;NP-完全问题；贪心算法；回溯法； 目录 马踏棋盘的求解及演示设计......................... 错误！未定义书签。目录........................................... 错误！未定义书签。第一章引言................................. 错误！未定义书签。第二章需求分析................................. 错误！未定义书签。 2.1问题描述....................................... 错误！未定义书签。 2.2基本要求....................................... 错误！未定义书签。 2.3具体需求....................................... 错误！未定义书签。 2.4开发环境....................................... 错误！未定义书签。第三章概要设计................................. 错误！未定义书签。 3.1 系统概述....................................... 错误！未定义书签。 3.2 系统描述....................................... 错误！未定义书签。 3.3逻辑设计....................................... 错误！未定义书签。第四章详细设计................................. 错误！未定义书签。 4.1 功能模块设计.................................. 错误！未定义书签。 4.2 数据结构设计.................................. 错误！未定义书签。 4.3算法设计....................................... 错误！未定义书签。第五章调试与分析............................... 错误！未定义书签。 5.1 调试分析....................................... 错误！未定义书签。第六章系统试用说明............................. 错误！未定义书签。 6.1 系统试用说明................................... 错误！未定义书签。第七章总结与体会............................... 错误！未定义书签。参考文献......................................... 错误！未定义书签。 1．问题描述 设计一个国际象棋的马踏棋盘的演示程序 2．需求分析 (1)将马随即放在国际象棋的8×8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。 (2)编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1,2,……,64依次填入一个8×8的方阵，输出之。 (3)程序执行命令为： 1)输入起始方格坐标(X,Y) 2)求解第一组路径并显示,按Q键退出系统，按其他任意键求解并显示下一组路径。 (4)测试数据:(0,0),(1,2) 3概要设计 3.1[程序设计思路]. 按照顺时针顺序，每次产生一个新的路点，并验证此路点的可用性，需要考虑的问题包括是否超出棋盘和此点已经走过与否。如新路点可用，则入栈，并执行下一步，每次按照上一路点的位置生成新路点。如一个路点的可扩展路点数为0，则走不下去了，进行回溯。 3.2[存储结构设计] 8个可能位置可以用两个一维数组表示： 数组1： 0 1 2 3 4 5 6 7 -2 -1 1 1 2 2 1 -1 -2 数组2：0 1 2 3 4 5 6 7 1 2 2 1 -1 -2 -2 -1 位于（i,j）的马可以走到的新位置是在棋盘范围内的（I+数组1[h],j+数组2[h]）,其中h=0，1，…7。 每次在多个可走位置中选择其中一个进行试探，其中未曾试探过的可走位置用适当栈结构妥善管理，也备试探失败时的“回溯”（悔棋）使用，即用栈结构存储试探的路径来进行路径试探操作。 3.3[主要算法设计] 3.3.1栈类的定义和接口: template 实现顺序栈或循环队列的存储 一需求分析 1.1 理解栈的特性“后进先出”和队列的特性“先进先出”。仅仅认识到栈和队列是两种特殊的线性表是远远不够的，本次实验的目的在于更深入的了解栈和队列的特性，以便在实际问题背景下灵活运用他们。在了解他特性的基础上，还将巩固对这种结构的构造方法的理解。 1.2 要求：在国际象棋8×8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。编制程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，并输出它的行走路线（棋盘如图所示）。 输入：任意一个起始位置； 输出：无重复踏遍棋盘的结果，以数字1-64表示行走路线。 0 1 2 3 4 5 6 7 0 8 1 1 7 2 2 H 3 6 3 4 5 4 5 6 7 二概要设计 为了实现上述程序功能，可以采用顺序栈或者链栈来存储它的数据，本实验所需要的存储空间不是很大，不需动态的开辟很多空间，所以采用相对简单的顺序栈来存储数据，既方便有简单，而用链栈在实现上相对比顺序栈复杂的一点。 2.1顺序栈的抽象数据类型定义： ADT Stack{ 数据对象：D={ai| ai∈（0，1，…，9），i=0,1，2，…，n，n≥0} 数据关系：R={< ai-1, ai >| ai-1, ai∈D,i=1,2，…，n} } ADT Stack 2.2本程序包含三个模块： 1、主程序模块： void main(){ 定义变量； 接受命令； 处理命令； 退出； } 2、起始坐标函数模块——马儿在棋盘上的起始位置； 3、探寻路径函数模块——马儿每个方向进行尝试，直到试完整个棋盘； 4、输出路径函数模块——输出马儿行走的路径； 2.3各模块之间的调用关系： 主程序模块 输入的初始位置是否正确 否 是 起始坐标函数模 探寻路径函数模 输出路径函数模 结束 #include ny=sta.p[top].y+Htry2[z]; sta.p[top].dir=z; top++; sta.p[top].x=nx; sta.p[top].y=ny; board [nx][ny]=top; chech [nx][ny]=true; z=-1; } else if(z==7)//如果不可行，而且是最好一次检查 { chech [sta.p[top].x][sta.p[top].y]=false; top--; while(1) { z=sta.p[top].dir; if(z!=7) break; else { chech [sta.p[top].x][sta.p[top].y]=false; top--; } } } if(top==-1||top==63)break;//如果回溯到-1，或者栈满，则退出循环 z++; } for(i=0;i<8;i++) { for(j=0;j<8;j++) cout< 学习数据结构的最终目的是解决实际的应用问题，特别是非数值计算类型的 应用问题，数据结构课程设计就是为此目的一次实际训练。要求我们在对题目进 行独立分析的基础上，完成设计和开发，并最终接受严格的测试考核。以深化对 数据结构课程中基本概念、理论和方法的理解，提升综合运用所学知识处理实际 问题的能力，使我们的的程序设计能力与调试水平有一个明显的提升。 课程设计所安排的题目，都有一定的难度和深度，从抽象数据类型的提炼、 数据结构选择到算法的设计，均由我们每个人自主完成。在一周的时间内，历经 查找参考资料、使用技术手册、设计编码和撰写文档的实践，进一步升华对软件 工程师和程序员人格素质的认识和理解。 本课程设计的主要设计内容是：设计一个马踏棋盘问题的演示程序。 即将马随机地放在国际象棋的8*8棋盘的某个方格中，然后令马按走棋规则 开始进行移动。要求马将棋盘上的每个方格进入且只进入一次，走遍全部64个 方格。要求编制非递归程序，求出马的行走路线，将数字1，2，…，64依次填 入一个8*8的方阵在屏幕上显示输出。 针对该问题本课程设计采用的是面向对象的开发语言Java，在 Windows7, myeclipse8.5.0的平台上开发出来，并有图形界面。最终较好的实现了全部要求，达到了预期效果。从中我也学到了很多，不仅仅是课堂外的新知识，还有那种会查资料，会学习新知识的能力。 这个课程设计的顺利完成，离不开胡老师的指导和帮助，在他的细心指导和 帮助下，我对马踏棋盘程序开发的整个流程有了深刻地了解和系统地掌握，在这 里学生表示真诚地感谢。另外也谢谢这次课程设计提供给我帮助的同学们。此外， 本课程设计还参考了一些文献资料，在此向这些文献资料的作者深表谢意。 本课程设计可作为数据结构和Java课程教学的参考案例。 由于时间仓促和本人水平所限，设计中难免有不当和欠妥之处，敬请老师不吝批评指正。 笔者 2016.6 数据结构与算法分析课程设计报告 设计题目：马踏棋盘 专业计算机科学与技术 学号 姓名 年月日 <<马踏棋盘>> 数据结构课程设计 概要设计 功能模块化分析 通过对问题描述的分析，可知马踏棋盘问题所要求实现的功能大致由三个部分组成： ⑴接收用户输入的马的起始位置； ⑵从起始位置开始在棋盘上标记马按问题描述中的行走规则访问棋盘中每个格子的顺序； ⑶输出棋盘上标记的访问顺序。 系统结构的总体设计 ⑴输入模块：提示用户输入数据，接收用户输入的数据，即马的起始位置，并判断该位置是否在棋盘内。若该起始位置在棋盘内，则接着执行下一模块的功能；若该起始位置不在棋盘内，则提示用户输入无效，并要求用户再次输入； ⑵初始化模块：初始化所有的数据结构中的数据； ⑶棋盘遍历模块：采用特定算法，按照马的行走规则对棋盘进行遍历，每次访问一个格子时，要测试该格子是否在棋盘范围内，保存马的访问顺序； ⑷位置测试模块：接收格子的x和y坐标，判断该格子是否在棋盘内，然后根据该格子是否在棋盘内返回不同的信号； ⑸输出模块：将棋盘遍历模块中保存下来的讯号进行输出，输出格式遵从棋 盘格式； ⑹总控模块：负责调用个处理模块，完成马踏棋盘问题的求解。 处理方式设计 针对问题和核心模块，采用深度优先遍历思想和回溯算法的非递归形式。 ⑴深度优先遍历的基本思想 深度优先遍历可以从任意顶点开始访问图的顶点，然后把该顶点标记为已访问。在每次迭代的时侯，该算法紧接着处理与当前顶点邻接的未访问顶点。如果有若干个这样的顶点，可以任意选择一个顶点。凡在实际应用中，选择哪一个邻接的未访问候选顶点主要是由表示图的数据结构决定的。 ⑵回溯算法的基本思想 回溯法是穷举查找技术的一个变种。它每次只构造解的一个分量，然后按照下面的方法来评估这个部分构造解。如果一个部分构造解可以进一步构造而不会违反问题的约束，我们就接受对解的下一个分量所做的第一个合法选择。如果无法对下一分量进行合法的选择，就不必对剩下的任何分量再做任何选择了。在这种情况下，该算法进行回溯，把部分构造解的最后一个分量替换为它的下一个选择。 详细设计 详细设计的主要任务是根据概要设计对每个模块的定义进行设计，以实现其功能算法和外部接口所要求的模块内部的数据结构和程序的逻辑结构。 详细设计的目标有两个：实现模块功能的算法要逻辑上正确和算法描述要简明易懂。设计主要采用的工具是程序流程图。 实验二：栈和队列及其应用 题目：马踏棋盘 班级：姓名：学号： 一、问题描述 设计一个国际象棋的马踏遍棋盘的演示程序。 二、基本要求 将马随机放在国际象棋的8*8的棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。 编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1,2，……，64依次填入一个8*8的方阵，输出之。 三、概要设计 1.定义头文件和预定义 #include top++; //栈指针指向第一个栈首 stack[top].i=xi; //将起始位置的横坐标进栈 stack[top].j=yi; //将起始位置的纵坐标进栈 stack[top].director=-1; //将起始位置的尝试方向赋初值 board[xi][yi]=top+1; //标记棋盘 x=stack[top].i; //将起始位置的横坐标赋给棋盘的横坐标 y=stack[top].j; //将起始位置的纵坐标赋给棋盘的纵坐标 if(TryPath(x,y)) //调用马儿探寻函数，如果马儿探寻整个棋盘 返回1否则返回0 Display(); //输出马儿的行走路径 else printf("无解"); } 3. 探寻路径函数模块 int TryPath(int i,int j) { int find,director,number,min;//定义几个临时变量 int i1,j1,h,k,s; //定义几个临时变量 int a[8],b1[8],b2[8],d[8];//定义几个临时数组 while(top>-1) //栈不空时循环 { for(h=0;h<8;h++) //用数组a[8]记录当前位置的下一个位置的可 行路径的条数 { number=0; i=stack[top].i+Htry1[h]; j=stack[top].j+Htry2[h]; b1[h]=i; b2[h]=j; if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8) //如果找到下一位置 { for(k=0;k<8;k++) { i1=b1[h]+Htry1[k]; 马踏棋盘的贪心算法实现 问题描述： 将马放到国际象棋8*8棋盘的某个方格上，马按照“马走日”的规则移动。为马寻找一条走遍棋盘每一格并且只经过一次的路径，并将数字1、2、3、、、、64依次填入到8*8 的方格中。 问题分析： 国际象棋中 "马"的移动规则叫做"马走日"。它下一步可移动的位置有8个，但是如果"马"位于棋盘的边界附近，它下一步可移动到的位置就不一定有8个了，因为要保证"马"每一步都走在棋盘中。 马踏棋盘的问题其实就是要将1，2，…，64填入到一个8*8的矩阵中，要求相邻的两个数按照"马"的移动规则放置在矩阵中。将矩阵填满并输出。这样在矩阵中从1，2…遍历到64就得到了马踏棋盘的行走路线。因此本题的最终目的是输出一个8*8的矩阵，在该矩阵中填有1，2…64这64个数字，相邻数字之间遵照"马走日"的规则。 假设最开始"马"位于棋盘的(0,0)的位置，接下来"马"有两处位置可走，即(1,2)和(2,1)。这时"马"是无法确定走2的位置最终是正确的，还是走3的位置最终是正确的。因此"马"只能任意先从一个路径走下去（例如从2的位置）。如果这条路是正确的，那当然是幸运的，如果不正确，则"马"要退回到第一步，继续从3的位置走下去。以后"马"走的每一步行走都遵循这个规则。这个过程就是一种深度搜索的过程，同时也是一种具有重复性操作的递归过程。 "马"的行走过程实际上就是一个深度探索的过程。"探索树"的根结点为"马"在棋盘中的初始位置（这里用4*4的棋盘示意）。接下来"马"有两种行走方式，于是根结点派生出两个分支。而再往下一步行走，根结点的两个孩子又能够分别派生出其他不同的"行走路线"分支，如此派生下去，就得到了"马"的所有可能的走步状态。探索树的叶子结点只可能有两种状态：一是该结点不能再派生出其他的"走步"分支了，也就是"马"走不通了；二是棋盘中的每个方格都被走到，即"马"踏遍棋盘。于是从该探索树的根结点到第二种情况的叶结点构成的路径就是马踏棋盘的行走过程。 贪心算法描述： 在此对上述方法进行改进。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法就是贪心算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。马踏棋盘实验报告
实验报告 马踏棋盘
马踏棋盘数据结构实践报告
马踏棋盘分析文档
数据结构 马踏棋盘 设计报告
数据结构课程设计报告_马踏棋盘
马踏棋盘c报告 数据结构课程设计
马踏棋盘课程设计实验报告
数据结构实验报告马踏棋盘
马踏棋盘
数据结构课程设计 马踏棋盘求全部解及演示程序
马踏棋盘c++课程设计
数据结构 马踏棋盘
马踏棋盘非递归算法
数据结构课程设计 马踏棋盘
马踏棋盘 正式作业
数据结构马踏棋盘
马踏棋盘贪心算法