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

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

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

3、溯的， 也就节省了大量的时间， 而试探性的操作对于每个 点都也只有 168 步，所以求出所有路径在 不到一秒的时间内完成。 关键词：马踏棋盘； 骑士周游；哈密顿通路 ;NP-完全问题；贪心算法；回溯法； 目录 马踏棋盘的求解及演示设计 1 目 录 2 第一章 引 言 3 第二章 需求分析 4 2.1 问题描述 4 2.2 基本要求 4 2.3 具体需求 4 2.4 开发环境 4 第三章 概要设计 5 3.1 系统概述 5 3.2 系统描述 6 3.3 逻辑设计 6 第四章 详细设计 7 4.1 功能模块设计 7 4.2 数据结构设计 7 4.3 算法设计 9 第五章 调试与分析 13 5.1

4、调试分析 13 第六章 系统试用说明 14 6.1 系统试用说明 14 第七章 总结与体会 14 参考文献 15 第一章 引 言 本课程设计主要研究马踏棋盘的问题， 即骑士周游问题， 是将马随机放在国 际象棋的 88 棋盘的某个方格中 ,“马”按照走棋规则进行移动， 要求每个方格 只进入一次 , 走遍棋盘上全部 64 个方格。 许多知名的数学家，如德莫弗 (De Moivre) 欧拉 (Euler) 与范德蒙德 (Vandermonde) 等人， 在过去的 200 年中都研究过这个问题， 今天从 数据结构的角度，解决这一问题。力求以最快的速度，即最高的效率来解决问题。 已知穷举 法是几乎不可能

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

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

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

8、 抽象数据类型 棋盘上某点的位置坐标结构体 Postion 把个方向试探的增量位置数组 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 数据设计 Postion 定义棋盘上某点的位置坐标结构体 typedef struct int x

10、; int y; Postion ; 定义把个方向试探的增量位置数组 8 1 7 2 6 3 5 4 3 Postion direct8=1,2,2,1,2,-1,1,-2 ，-1,-2,-2,-1,-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 ; typedef struct

11、定义一个以 某一棋盘上的点和标志的类型，作为栈的存储数据 DataType data; struct node *next; StackNode,* PStackNode; / typedef struct / 定义一个栈 PStackNode top; LinkStack ,* PLinkStack ; 用来记录可到达下一位置坐标的数组： Postion nextPath8; 用来记录整个遍历过程的数组： Postion tourpos64; 4.3 算法设计 开始 寻找下一条路径： 流程图：略： 算法描述： 应考察每一方格的可到达性。使用数组 accessibility 表示可达到数 ,并

12、当马 踏棋盘时， 程序动态修正剩余格子的可达到数。 accessibility arrayPos = 0 表明 格子已经被占据。 算法： void next_Path( Postion P) Postion testPos; for ( int i = 0 ; i 0 ) / accessibility arrayPos = 0 表明格子已经被占据 arrayPos + ; / 寻找空格子结束 / 2.使用冒泡法来查询最小数。 void sortAll () / 冒泡排序法 . 冒泡排序的基本概念是：依次比较相邻的两个数，将大数放在前面，小数放在后面。 / 保持稳定性 int temp; Po

13、stion temps; for ( int i = 0 ; i countAccessibility - 1 ; i + ) for ( int j = i + 1; j accessibility j ) temps=nextPathi; nextPathi=nextPathj; nextPathj=temps; temp = accessibility i ; accessibility i = accessibility j ; accessibility j = temp; /end of if / end of inner for / end of outer for / end

14、of sortAll 3./ 3、向下一步移动，将当前要走的结点入栈，标记为 1，其他可到达但没有走的点入栈，标记为 0 如果当前坐标走过，那么它可以到达的其它点的可到达数应该 -1 最后将该点的可到达数更新为 0 void domoving( Postion P) for ( int i = 0 ; i countAccessibility ; i + ) DataType q; q.p=nextPathi; if (i=0) Push LinkStack(S,q); access nextPathi.x nextPathi.y - ; / 直到没有路径了 access P.x P.y =

15、0 ; / 当前位置置 0 4 、打印路径：打印 8 8 棋盘，在棋盘中显示马跳的步骤： 10 void fprint() / 输出路径 int order88=0; / 初始化 for (int k=0;k64;k+) ordertourposk.xtourposk.y=k; cout n 棋盘表示 n ; cout 0 1 2 3 4 5 6 7n ; cout +n ; for (int i=0;i8;i+) printf( ); printf( %2d,i); for (int j=0;j8;j+) printf( | %2d ,orderij); printf( | ); print

16、f( 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()

17、/ 寻找其他路径 int count=0; int recount=0,coutpath=0,count next=0; DataType Ps169; while (!Empty_LinkStack(S) int flag=0; Pop_LinkStack(S, 11 if (Pscount.flag!=0) count_next+; if (Pscount.flag=0) access tourpos63-count_next.xtourpos63-count_next.y=1; tourpos63-count_next=Pscount.p; for (int i=0;i0;j-) if

18、(! tour_next( tourpos63-j,63-j) flag=1; break ; if (flag!=1) coutpath+; fprint(); count+; coutendl; cout 周游结束共找到 coutpath+1 条路径 endl; 动态演示：根据 JAVA线程机制，每隔 800毫秒动画演示 1 步。 public void run() / 启动线程后将自动调用 run ()方法，在 run ()方法内产生一个控制动画的循环 int delay = 800; while ( true ) count = 0; for (int i=0;i63) final F

19、rame from=new Frame(); JOptionPane. showMessageDialog (from, 周游完成 ); return ; try Thread. sleep (delay); catch (Exception e) 第五章 调试与分析 5.1 调试分析 经过对程序的编制， 调试和运行， 使我更好的掌握了栈基本性质和有关马的遍历问题 的解决方法， 熟悉了各种调用的数据类型， 在调试和运行过程中使我更加的了解和熟悉程序 运行的环境，提高了我对程序调试分析的能力和对错误的纠正能力。 5.1.1、 首先要检测贪心算法的可用性，先找出一条路径;检测输出的路径是否合法 5

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

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

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

23、最主要的、 且是公开发 表的文献，非正式公开发表的资料不列。 文献主要类型格式如下： 期刊： 序号 作者篇名 J 15 附录 / NP_compelte.cpp : 定义控制台应用程序的入口点 / / NP_compelte.cpp : 定义控制台应用程序的入口点。 / #include stdafx.h #include using namespace std; #define Max 100 typedef struct direct_increment direct increment direct_ay8=1,2,2,1,2,-1,-1,-2,-2,-1,1,-2,-1,2,-2,1;

24、 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 accessibility8; int countAccessibility; typedef struct int x; int y; Postion ; static Postion nextPath8; static Postion tourpos64; static int a

25、rrayPos=0; static int ownAccessibility ; / 当前棋子的可到达数 static int countMoving=-1; bool success = false ; / typedef struct Postion p; 16 int flag; DataType; typedef struct node / 定义结点结构 DataType data; struct node *next; StackNode,* PStackNode; / typedef struct / 定义一个栈 PStackNode top; LinkStack ,*PLinkS

26、tack; / / 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) r

27、eturn 0; p-data= x; 17 p-next= S-top; int Pop_LinkStack( PLinkStack S,DataType * x)/ 出栈函数 PStackNode p; if (Empty LinkStack( S) 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 / void Destroy_LinkStack

28、( PLinkStack * LS) / 销毁栈函数 PStackNode p,q; if (* LS) p=(* LS)-top; while (p) q=p; p=p-next; 18 delete (q); delete (* LS); *LS=NULL; return ; PLinkStack S=Init_LinkStack(); / bool checkPath( Postion P) / 判断测试位置是否在棋盘内 if ( P.x=0 else return false ; / / void sortAll () / 冒泡排序法 . 冒泡排序的基本概念是：依次比较相邻的两个数，将

29、大数放在前面，小数 放在后面。 / 保持稳定性 int temp; Postion temps; for ( int i = 0 ; i countAccessibility - 1 ; i + ) for ( int j = i + 1; j accessibility j ) temps=nextPathi; nextPathi=nextPathj; nextPathj=temps; temp = accessibility i ; accessibility i = accessibility j ; accessibility j = temp; /end of if / end of

30、 inner for / end of outer for 19 / end of sortAll / void next_Path( Postion P) Postion testPos; for ( int i = 0 ; i 0 )/ accessibility arrayPos = 0 表明格子已经被占据 arrayPos + ; / 寻找空格子结束 / 结束 for 循环 , 寻找结束 countAccessibility = arrayPos ;/ 统计可达到数 if (countAccessibility 0 ) arrayPos = -1 ; / bool hasMorePat

31、h() / arrayPos + 1 指向下一个可行的 if ( (arrayPos + 1 ) countAccessibility ) return true ; else return false ; / hasMoreAccessible() 方法结束 / void nextAccessible() 20 arrayPos + ; / void dom oving( Postion P) for ( int i = 0 ; i 1) q.flag=2; else q.flag=0; Push LinkStack(S,q); access nextPathi.x nextPathi.y

32、- ; / 直到没有路径了 access P.x P.y = 0 ; / 当前位置置 0 / void undomoving( Postion P) / 撤消移动操作 for ( int i = 0 ; i countAccessibility ; i + ) access P.x P.y = ownAccessibility ; / void tour( Postion P) countMoving + ; / 如果 64个格子都被走过，则返回 21 if (countMoving = 63 ) tourpos countMoving .x= P.x ; tourpos countMovin

33、g .y = P.y ; success = true ; countMoving - ; return next_Path( P); / 初试化 AccessibleSquares 对象，给 nextSquare 分配内存 while (hasMorePath() / 利用 AccessibleSquares() 对象调用 hasMoreAccessible() 成员函数 / 开始移动 domoving( P); / 调用 nextSquare.domoving() 函数 / 把这一步记录下来 tourpos countMoving .x= P.x ; tourpos countMoving .y = P.y ; / 尝试下一步的移动 nextAccessible(); tour ( nextPatharrayPos); / 如果 64个格子都被走过，则返回 if ( success ) countMoving - ; return ; countMoving - ; /