数据结构课程设计马踏棋盘求全部解及演示程序

1、安徽工程大学 信息10课程设计马踏棋盘的求解及演示设计摘 要数据结构是计算机科学与技术专业的一门核心专业基础课程，是一门理论性强、思维抽象、难度较大的课程。我认为学习数据结构的最终目的是为了获得求 解问题的能力。对于现实世界中的问题，我们应该能从中抽象出一个适当的数学 模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。数据结构课程设计是计算机科学技术专业集中实践性环节之一， 是学习完数据结构课程后进行 的一次全面的综合练习。开设本课程设计实践的主要目的就是要达到理论与实际 应用相结合，提高学生的动手能力，完成计算机应用能力的

2、培养；本课程设计主 要解决马踏棋盘的问题，找出踏遍棋盘的多种路径，并实现动态要是过程。马踏棋盘问题，实际上是图论中的哈密顿通路问题，是 典型的np问 题,求解的问题与算法设计有很大关系，如果采取穷举搜索的话，很容易 陷入海量搜索的状态，耗费巨大的时间，使问题几乎不可解，因此马在棋盘上遍 历采用算法当中的深度优先算法和 启发式贪心算法，用栈来存储遍历过程，通过 对栈的使用实现对所有路径的搜索。 在调试过程发现，启发式贪心算法，针对于 马踏棋盘问题有着极大的好处，就是无论从棋盘上哪个点开始，找到一条遍历完 棋盘的通路是不需要回溯的，也就节省了大量的时间，而试探性的操作对于每个 点都也只有168步，

3、所以求出所有路径在 不到一秒的时间内完成。关键词：马踏棋盘；骑士周游；哈密顿通路；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系统试用说明第七章总结与体会错误！未定义书签 错误！未定义书签 错误！未定义书签 错误！未定义书签 错误！未定义书签 错误！未定义书签 错误！未定义书签 错误！未定义书签 错误！未定义书签 错误

4、！未定义书签 错误！未定义书签 错误！未定义书签 错误！未定义书签 错误！未定义书签 错误！未定义书签 错误！未定义书签 错误！未定义书签 错误！未定义书签 错误！未定义书签 错误！未定义书签 错误！未定义书签 错误！未定义书签参考文献3第一章引 言本课程设计主要研究马踏棋盘的问题， 即骑士周游问题，是将马随机放在国际象棋的8x8棋盘的某个方格中，“马”按照走棋规则进行移动，要求每个方格只进入一次,走遍棋盘上全部64个方格。许多知名的数学家，如德莫弗 (de moivre)、欧拉(euler)与范德蒙德(vandermonde)等人，在过去的200年中都研究过这个问题， 今天从数据结构的角度，

5、解决这一问题。力求以最快的速度，即最高的效率来解决问题。已知穷举法是几乎不可能完成的， 而与解决迷宫问题的回溯法， 也要占用大量的时间， 这里采用贪心 算法来解决这一问题，并找出多有的遍历路径。4第二章需求分析2.1问题描述马随机放在国际象棋的8x8棋盘的某个方格中，“马”按照走棋规则 进行移动，要求每个方格只进入一次，走遍棋盘上全部64个方格。设计一个国际 象棋的马踏遍棋盘的演示程序。2.2基本要求设计合适的数据结构，编制递归以及非递归程序，求出马的行走路线,并按求 出的马的行走路线,将路线1,2, , ,64依次填入一个8x 8的方阵,输出之，若有 多种走法，则能将全部的输出。必须要能够将

6、踏遍棋盘的过程显示在计算机屏幕 上。要求：(1) 描述设计所涉及的数据模型，设计高效的数据结构完成总体设计，搭好框架，确定人机对话的界面(要求界面上能动态体现出演示的过程)，实现功能；(2) 界面友好，函数功能要划分好(3) 要有算法设计的流程图(4) 程序要加必要的注释(5) 要提供程序测试方案2.3具体需求1、首先要找到马踏棋盘棋盘的多条路径。2 、实现马踏棋盘的动态演示过程。3 、优化算法，提高算法效率，以递归与非递归的方式实现2.4开发环境开发环境：win dows 8辅助工具：visual studio 2012 ,myeclipse 10.5运行环境：win dows xp/vis

7、ta/7/8第三章概要设计3.1系统概述3.12 主函数main()的执行流程求解多条路径子系统：自动演示路径子系统开始3.2系统描述通过vs2012完成的寻找多条路径的子系统，通过java来实现马踏棋盘的动态演示子系统。在寻找多条路径的子系统中，通过启发式贪心算法，将某点的下一步最少通往其它落 脚点，将该点确定为最佳落点。每次只走下一步通向其他点最少的点。用栈记录探寻的过程，将走过的点标记为1，试探而没有走的点标记为 0.最后通过寻找出栈标志为0的点来寻找其他路径。在动态显示模块式通过java的线程机制是先的自动动画演示。3.3逻辑设计抽象数据类型棋盘上某点的位置坐标结构体posti on把

8、个方向试探的增量位置数组direct8棋盘某点通向其他点的可到达数的二位数组access88链栈用来记录可到达下一位置坐标的数组：nextpath8;用来记录整个遍历过程的数组：tourpos64;第四章详细设计4.1功能模块设计4.1.2创建模块本模块创建棋盘，以及棋盘上每一点的可到达数，一个向8个方向试探的增量数组。以及记录整个遍历流程的链栈。选择或设计数据结构的存储结构，实现存储结构的基本运算、设计的模块构 成、各模块的简要说明、流程图、调用关系表等。在这个过程中，要综合考虑系 统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可 能做到数据封装，基本操作的规格说明尽可

9、能明确具体。 详细设计的结果是对数 据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数 形式的算法框架。4.1.3操作模块实现对棋盘的周游，并找到多条路径4.1.4显示模块将找到的所有路径显示在屏幕上，并统计找到的路径数。4.1.5自动演示模块通过java的applet和线程机制，实现对找到的路径进行动态演示4.2数据结构设计4.2.1数据设计posti on定义棋盘上某点的位置坐标结构体typedef structint x;int y; postion ;定义把个方向试探的增量位置数组jqk-00l-qiira-qg-q,-1,-2,-2,-1,-1,2,-2,1;po

10、stion direct8=1,2,2,1,2,-1,1,-2定义棋盘某点通向其他点的可到达数的二位数组int access88 = 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 datatype data; struct node *n ext; stacknode,* pstacknode;/typ

11、edef struct / 定义一个栈pstacknode top; linkstack ,* plinkstack ;用来记录可到达下一位置坐标的数组：postion nextpath8;用来记录整个遍历过程的数组：postion tourpos64;4.3算法设计开始寻找下一条路径: 流程图：略：算法描述：应考察每一方格的可到达性。使用数组accessibility 表示可达到数,并当马踏棋盘时，程序动态修正剩余格子的可达到数。accessibility arraypos = 0表明 格子已经被占据。算法：void next_path( postion p)|postion testpos

12、;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)/判断测试位置是否在棋盘内nextpatharraypos=testpos ;/由测试位置给岀正确x,丫坐标accessibility arraypos = access testpos.xtestpos.y;/ 利用对应/结束for循环,寻找结束countaccessibility = arraypos ;/ 统计可达到

13、数的x,y坐标得岀相应的可到达的路径总数if(accessibility arraypos > 0 )/ accessibility arraypos = 0表明格子已经被占据arraypos + ;/寻找空格子结束/2.使用冒泡法来查询最小数。void sortall () |/冒泡排序法.冒泡排序的基本概念是：依次比较相邻的两个数，将大数放在前面，小数放在后面。/保持稳定性int temp;postion temps;for ( int i = 0 ; i < countaccessibility - 1 ; i + )for ( int j = i + 1; j < c

14、ountaccessibility ; j + )if ( accessibility i > accessibility j )temps=n extpathi;n extpathi=nextpathj;n extpathj=temps;temp = accessibility i ;accessibility i = accessibility j ;accessibility j = temp;/end of if/ end of inner for/ end of outer for / end of sortall3./3、向下一步移动，将当前要走的结点入栈，标记为 1其他可到

15、达但没有走的点入栈，标记为 0 如果当前坐标走过，那么它可以到达的其它点的可到达数应该-1最后将该点的可到达数更新为0void domoving( postion p)for ( int i = 0 ; i < countaccessibility ; i + ) ,datatype q;q.p=n extpathi;if (i=0)push li nkstack(s,q);access n extpathi.x n extpathi.y -;/直到没有路径了accessp.x p.y = 0 ;/ 当前位置置 04、打印路径：打印8x8棋盘，在棋盘中显示马跳的步骤:void fprin

16、t()/输出路径int order88=0;ii-初始化for (int k=0;k<64;k+)ordertourposk.xtourposk.y=k;cout« "n棋盘表示n"cout<< "01234567n"coutvv"+-+-+-+-+-+-+-+-+n"for (int i=0;i<8;i+)pri ntf(" " );pri ntf("%2d",i);for (int j=0;j<8;j+)printf("| %2d "

17、; ,orderij);pri ntf("|");pri ntf("n");if (i=7)pri ntf("+");elsepri ntf("+");printf("n");pri ntf(" " );5、寻找其他路径：算法描述:将栈中存储的路径岀栈，判断标记是否为 0,并累计标记为1的个数count next，即走过的 步数，方便撤销走过的步骤，根据 count_next来撤销走过的步骤，先将在 access叩 撤销，即还原 为1,将当前为flag为0的复制到下一步的to

18、urpos数组中，之后将tourpos后面的步骤还原为 0,再结束后，在寻找下一条路径，若找不到，则继续岀栈，向前回溯。void other path()/寻找其他路径int count=0;int recount=0,coutpath=0,count next=0;datatype ps169;while (!empty_linkstack(s) int flag=0;pop_li nkstack(s,&pscou nt);if (pscount.flag!=o)cou nt_n ext+;if(pscou nt.flag=0)access tourpos63-cou nt_n ex

19、t.xtourpos63-cou nt_n ext.y=1;tourpos63-cou nt_n ext=pscou nt.p;for (int i=0;i<count_next;i+)access tourpos63-i.xtourpos63-i.y=1;tourpos63-i.x=0;tourpos63-i.y=0;access tourpos63-cou nt n ext.xtourpos63-cou nt n ext.y=o; for (int j=count_next;j>0;j-)if (! tour_next( tourpos63-j,63-j)flag=1;brea

20、k;if (flag!=1)coutpath+;fprin t();cou nt+;cout«e ndl;coutvv "周游结束共找到"vvcoutpath+1 << "条路径"<<endl;动态演示：根据java线程机制，每隔800毫秒动画演示1步。public void run() /启动线程后将自动调用run ()方法，在run ()方法内产生一个控制动画的循环 int delay = 800;while (true )count = 0;for (int i=0;i<64;i+)repaint();/re

21、paint()将调用 paint()方法画一帧图像count +;if (recount >63) final frame from= new frame();joptionpane. showmessagedialog (from,"周游完成”); return ;try thread.sleep (delay);catch (excepti on e) 第五章调试与分析5.1调试分析经过对程序的编制，调试和运行，使我更好的掌握了栈基本性质和有关马的遍历问题 的解决方法，熟悉了各种调用的数据类型， 在调试和运行过程中使我更加的了解和熟悉程序 运行的环境，提高了我对程序调试分析

22、的能力和对错误的纠正能力。5.1.1、首先要检测贪心算法的可用性，先找出一条路径；检测输出的路径是否合法5.1.2、完成一条路径的输出之后，进行栈的检查，检查栈中存储的元素是否正确能否满足回溯的标准，经过检测栈的合法性才能对栈中元素进行操作，最后就是，实现对其他路径的寻找,并统计路径的条数。第六章系统试用说明6.1系统试用说明系统提示用户输入测试坐标， 输入坐标应满足 必须为整数，且大于等于0,小于8两 点之间以空格隔开。及满足在棋盘上点的的要求。测试数据：0 0 ； 1 0； 7 7，2 3第七章总结与体会通过本次课程设计掌握了关于数据结构的很多内容如算法的设计，栈的使用，对图的深度优先遍历

23、算法有了更深入的了解， 对于马踏棋盘这一问题，有了 独到研究和见解，让学习的理论与实际应用相结合， 提高了我的动手能力，以及 独立解决问题的能力，如使用 java来动态演示马踏棋盘的步骤，本来学习 java 是对于用于动画的线程机制就没有深入了解， 经过这次的课程设计，在网上查阅 资料，在几天内，我学会了如何使用 java的线程机制来实现动画演示程序，可 对以说是一个不小的受获。对数据结构的应用上也得到很大的提升， 前面做实验 都是一些验证性的实验，只是把书上的代码输进去，检测它的正确性，和它的算 法思想，而这次是在问题的前提下，来确定数据结构，在算法思想的前提下，来 确定算法的使用，并根据各

24、种可行的算法来确定最优的算法，即时空效率最高。 并且在写出解决查找多种路径的算法后， 很有成就感，因为在网上，这一问题只 有求出一条路径的方法，也没有动态演示的，很不符合课程设计的要求，并且发 现，如果只找一条路径的话，要是算法用的灵活，可以说没学数据结构之前也可 解决，所以在找到所有路径的时候内心很喜悦， 大概这就是编程的乐趣吧。本次 数据结构课程设计确实收益匪浅。参考文献xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx参考文献书写格式应符合gb7714-87文后参考文献著录规则。常用参考 文献编写项目和顺序规定如下：先安排中文（按姓氏笔划排序），后安排

25、英语（或其他语种）（按字母先后排列）;注释置于页脚，参考文献置于文末。参考文献只列出最主要的、且是公开发 表的文献，非正式公开发表的资料不列。文献主要类型格式如下：期刊：序号作者篇名j.17附录/ np_compelte.cpp :定义控制台应用程序的入口点/ np_compelte.cpp :定义控制台应用程序的入口点。/#i nclude "stdafx.h" #include <iostream> using namespacestd; #defi ne max100typedef struct direct_ in creme nt direct_ in

26、 creme ntdirect_ay8=1,2,2,1,2,-1,-1,-2,-2,-1,1,-2,-1,2,-2,1;int access88 = 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;int countaccessibility;typedef structint x;int y; postion ;staticpostion nextpa

27、th8;staticpostion tourpos64;staticint arraypos=0;staticint own accessibility ;/当前棋子的可到达数static int cou ntmov in g=-1;bool success = false ;/typedef struct postion p;int flag; datatype;typedef structnode /定义结点结构datatype data; struct node *n ext; stacknode,* pstacknode;/typedef struct / 定义一个栈pstacknod

28、e top; linkstack ,*plinkstack;/plinkstack init_linkstack() / 初始化函数 一plinkstack s;s=( plinkstack ) new( linkstack );if (s)s->top->n ext=nullreturn (s);j/bool empty_linkstack( plinkstack s) 判断栈空函数return ( s>top= null;/int push_linkstack( plinkstack s, datatype x) / 入栈函数 一pstacknode p;p= new (

29、 stacknode);if (!p)return 0;p->data= x;p>n ext= s>top;int pop_linkstack( plinkstack s,datatype * x) / 岀栈函数pstacknode p;if (empty linkstack( s)p=s>top;s>top= s>top->n ext;delete (p);return 1;/int gettop_linkstack( plinkstack s, datatype *x) 取栈顶元素if (empty linkstack( s)return 0;el

30、se/void destroy_linkstack(plinkstack * ls) / 销毁栈函数pstacknode p,q;if (* ls)p=(* ls)->top;while (p)q=p;p=p->n ext;delete (q);delete (* ls);*ls=nullreturn ;plinkstack s=init_linkstack();/bool checkpath( postion p)/判断测试位置是否在棋盘内if (p.x>=0&&p.x<8&&p.y>=0&&p.y<8) r

31、eturn true ;elsereturn 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=n extpathi;n extpathi=next

32、pathj;n extpathj=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(posti on p)postion testpos;for ( int i = 0 ; i < 8 ; i+ )/有八种到达的情况testpos.x =p.x + direct ay i .dx;/ 得岀 x,y坐标的测试

33、位置testpos.y =p.y + direct_ay i .dy;if (checkpath(testpos)/判断测试位置是否在棋盘内nextpatharraypos=testpos ;/由测试位置给岀正确x,丫坐标accessibility arraypos = access testpos.xtestpos.y;/ 利用对应的x,y坐标得岀相应的可到达的路径总数if (accessibility arraypos > 0 )/ accessibility arraypos = 0表明格子已经被占据arraypos + ;/寻找空格子结束/结束for循环,寻找结束countacc

34、essibility = arraypos ;/ 统计可达到数if (countaccessibility > 0 )arraypos = -1 ;/bool hasmorepath()/ arraypos + 1指向下一个可行的if ( (arraypos + 1 ) < countaccessibility)return true ;elsereturn false ; / hasmoreaccessible()方法结束/void nextaccessible()arraypos + ;/void domioving( postion p)for ( int i = 0 ; i

35、 < countaccessibility ; i + )datatype q;q.p=n extpathi;if (i=0) q.flag=1;if (countaccessibility>1)q.flag=2; elseq.flag=0;push li nkstack(s,q);access n extpathi.x n extpathi.y -; =/直到没有路径了accessp.x p.y = 0 ;/ 当前位置置 0/void undomoving( postion p)/撤消移动操作for ( int i = 0 ; i < countaccessibility

36、; i + )accessp.x p.y = own accessibility ;/void tour( postion p)cou ntmov ing + ;/如果64个格子都被走过，则返回if (countmoving = 63 ) tourpos cou ntmov ing .x=p.x ;tourpos cou ntmov ing .y =p.y ;success =true ;cou ntmov ing -;returnnext_path( p);/初试化 accessiblesquares 对象，给nextsquare分配内存while (hasmorepath()/ 利用 ac

37、cessiblesquares() 对象调用 hasmoreaccessible() 成员函数/开始移动domoving( p); / 调用 nextsquare.domoving()函数/把这一步记录下来tourpos cou ntmov ing .x=p.x ;tourpos cou ntmov ing .y =p.y ;/尝试下一步的移动n extaccessible();tour ( n extpatharraypos);/如果64个格子都被走过，则返回if ( success ) cou ntmov ing -;return ;cou ntmov ing -;/void fprint

38、()/输出路径int order88=0;/-初始化for (int k=0;k<64;k+)ordertourposk.xtourposk.y=k;cout<< "n棋盘表示 n"cout«"0123 45 67n"cout«"for (int i=0;i<8;i+)printf("");pri ntf("%2d",i);for (int j=0;j<8;j+)printf("| %2d " ,orderij);pri ntf(&qu

39、ot;|");pri ntf("n");if (i=7)pri ntf(i!-+ " );elsepri ntf(i!+-+-+-+-+-+-+-+ " );pri ntf("n");printf("");/bool tour_next(postion p int j) _postion testpos;int count =0;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)/判断测试位置是否在棋盘内if ( access testpos.xtestpos.y!=o)/ 利用对应的 x,y坐标得岀相应的可