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

安徽工程大学 信息 10 课程设计马踏棋盘的求解及演示设计摘要数据构造是计算机科学与技术专业的一门核心专业根底课程，是一门理论性强、思维抽象、难度较大的课程。我认为学习数据构造的最终目的是为了获得求解问题的力量。对于现实世界中的问题，我们应当能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据构造来表示，然后设计一个解此数学模型的算法，再进展编程调试，最终获得问题的解答。数据构造课程设计是计算机科学技术专业集中实践性环节之一，是学习完数据构造课程后进展的一次全面的综合练习。开设本课程设计实践的主要目的就是要到达理论与实际应用相结合，提高学生的动手力量，完成计算机应用力量的培育；本课程设计主要解决马踏棋盘的问题，找出踏遍棋盘的多种路径，并实现动态要是过程。马踏棋盘问题，实际上是图论中的哈密顿通路问题，是 典 型 的NP 问 题,求解的问题与算法设计有很大关系，假照实行穷举搜寻的话，很简洁陷入海量搜寻的状态，消耗巨大的时间，使问题几乎不行解，因此马在棋盘上遍历承受算法当中的深度优先算法和启发式贪心算法，用栈来存储遍历过程，通过对栈的使用实现对全部路径的搜寻。在调试过程觉察，启发式贪心算法，针对于马踏棋盘问题有着极大的好处，就是无论从棋盘上哪个点开头，找到一条遍历完棋盘的通路是不需要回溯的，也就节约了大量的时间，而摸干脆的操作对于每个点都也只有 168 步，所以求出全部路径在 不到一秒的时间内完成。关键词：马踏棋盘；骑士周游；哈密顿通路;NP-完全问题；贪心算法；回溯法；10目 录马踏棋盘的求解及演示设计1目 录2第一章 引言3其次章 需求分析42.1 问题描述42.2 根本要求42.3 具体需求42.4 开发环境4第三章 概要设计53.1 系统概述53.2 系统描述63.3 规律设计6第四章 具体设计74.1 功能模块设计74.2 数据构造设计74.3 算法设计9第五章 调试与分析135.1 调试分析13第六章 系统试用说明146.1 系统试用说明14第七章 总结与体会14参考文献15第一章 引言本课程设计主要争论马踏棋盘的问题，即骑士周游问题，是将马随机放在国际象棋的 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 2023 ,MyEclipse 10.5运行环境：Windows XP/Vista/7/8第三章 概要设计3.1 系统概述马踏棋盘演示系统3.11 系统流程图求解多条路径自动演示路径3.12 主函数 main的执行流程求解多条路径子系统：自动演示路径子系统开头输入起始点N推断合法性Y开头遍历(找出一条路径) tour(Postion)打印找到的路径fprint寻找下一步next_Path(Postion)While(hasMNorePath)Y查找其他路径other_PathPostion打印全部路径/开 始 移 动domoving(Postion)/ 尝 试 下 一 步 的 移 动extAccessible;递归调用完毕tour ( nextPatharrayPos);3.2 系统描述完毕通过 VS2023 完成的查找多条路径的子系统，通过java 来实现马踏棋盘的动态演示子系统。在查找多条路径的子系统中，通过启发式贪心算法，将某点的下一步最少通往其它落 脚点，将该点确定为最正确落点。每次只走下一步通向其他点最少的点。用栈记录探寻的过程， 将走过的点标记为 1，摸索而没有走的点标记为 0.最终通过查找出栈标志为 0 的点来查找其他路径。在动态显示模块式通过java 的线程机制是先的自动动画演示。3.3 规律设计抽象数据类型棋盘上某点的位置坐标构造体Postion 把个方向摸索的增量位置数组 direct8棋盘某点通向其他点的可到达数的二位数组 access88 链栈用来记录可到达下一位置坐标的数组 ：nextPath8;用来记录整个遍历过程的数组： tourpos64;第四章 具体设计4.1 功能模块设计4.1.2 创立模块本模块创立棋盘，以及棋盘上每一点的可到达数，一个向8 个方向摸索的增量数组。以及记录整个遍历流程的链栈。选择或设计数据构造的存储构造，实现存储构造的根本运算、设计的模块构成、各模块的简要说明、流程图、调用关系表等。在这个过程中，要综合考虑系统功能，使得系统构造清楚、合理、简洁和易于调试，抽象数据类型的实现尽可能做到数据封装，根本操作的规格说明尽可能明确具体。具体设计的结果是对数据构造和根本操作作出进一步的求精，写出数据存储构造的类型定义，写出函数形式的算法框架。4.1.3 操作模块实现对棋盘的周游，并找到多条路径4.1.4 显示模块将找到的全部路径显示在屏幕上，并统计找到的路径数。4.1.5 自动演示模块通过Java 的 Applet 和线程机制，实现对找到的路径进展动态演示。4.2 数据构造设计Postion4.2.1 数据设计typedef structint x; int y;Postion;定义把个方向摸索的增量位置数组定义棋盘上某点的位置坐标构造体81726354Postion 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 Postion p; int flag; DataType; 定义一个链栈：typedef struct node /定义结点构造DataType data;struct node *next;StackNode,*PStackNode;/ typedef struct /定义一个栈PStackNode top;LinkStack,*PLinkStack;用来记录可到达下一位置坐标的数组 ：Postion nextPath8;用来记录整个遍历过程的数组： Postion tourpos64;4.3 算法设计开头查找下一条路径： 流程图：略：算法描述：算法：voidnext_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)/推断测试位置是否在棋盘内nextPatharrayPos=testPos ;/由测试位置给出正确X,Y坐标accessibility arrayPos = access testPos.xtestPos.y; /利用对应的X,Y坐标得出相应的可到达的路径总数if (accessibility arrayPos > 0 )说明格子已经被占据arrayPos + ;/查找空格子完毕/ accessibility arrayPos = 0/ 完毕for循环,查找完毕countAccessibility = arrayPos ;/统计可到达数if (countAccessibility > 0 )sortAll;arrayPos = -1 ;/应考察每一方格的可到达性。使用数组accessibility 表示可到达数,并当马踏棋盘时，程序动态修正剩余格子的可到达数。accessibility arrayPos = 0 说明格子已经被占据。2.使用冒泡法来查询最小数。void sortAll /冒泡排序法.冒泡排序的根本概念是：依次比较相邻的两个数，将大数放在前面，小数3./3、向下一步移动，将当前要走的结点入栈，标记为1，其他可到达但没有走的点入栈，标记为0假设当前坐标走过，那么它可以到达的其它点的可到达数应当-1 最终将该点的可到达数更为0void domoving(Postion P)for ( int i = 0 ; i < countAccessibility ; i + )DataType q;q.p=nextPathi; if(i=0)q.flag=1; elseq.flag=0;Push_LinkStack(S,q);access nextPathi.x nextPathi.y - ;/直到没有路径了access P.x P.y = 0 ;/当前位置置04、打印路径：打印 8×8 棋盘，在棋盘中显示马跳的步骤：放在后面。/保持稳定性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=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 of sortAllvoid fprint /输出路径int order88=0;/初始化for(int k=0;k<64;k+)ordertourposk.xtourposk.y=k;cout<<“n棋盘表示n“;cout<<“01234567n“ ;cout<<“+-+-+-+-+-+-+-+n“;for(int i=0;i<8;i+)printf(“);printf(“%2d“,i); for(int j=0;j<8;j+)printf(“| %2d “,orderij);printf(“|“);printf(“n“); if(i=7)printf(“+-+-+-+-+-+-+-+“);elseprintf(“+-+-+-+-+-+-+-+“);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 Ps169;while(!Empty_LinkStack(S) int flag=0;Pop_LinkStack(S,&Pscount);1if(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;i<count_next;i+)access tourpos63-i.xtourpos63-i.y=1; tourpos63-i.x=0;tourpos63-i.y=0;access tourpos63-count_next.xtourpos63-count_next.y=0; for(int j=count_next;j>0;j-)if(! tour_next( tourpos63-j,63-j)flag=1; break;if(flag!=1)coutpath+; fprint;count+;cout<<endl;cout<<“周游完毕共找到“<<coutpath+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;/repaint将调用paint方法画一帧图像count+;13if(recount>63)try final Frame from= new Frame; JOptionPane.showMessageDialog(from, “周游完成“); return;Threads.leep(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 的线程机制来实现动画演示程序，可对以说是一个不小的受获。对数据构造的应用上也得到很大的提升，前面做试验都是一些验证性的试验，只是把书上的代码输进去，检测它的正确性，和它的算法思想，而这次是在问题的前提下，来确定数据构造，在算法思想的前提下，来确定算法的使用，并依据各种可行的算法来确定最优的算法，即时空效率最高。并且在写出解决查找多种路径的算法后，很有成就感，由于在网上，这一问题只有求出一条路径的方法，也没有动态演示的，很不符合课程设计的要求，并且觉察，假设只找一条路径的话，要是算法用的敏捷，可以说没学数据构造之前也可解决，所以在找到全部路径的时候内心很喜悦，或许这就是编程的乐趣吧。本次数据构造课程设计确实收益匪浅。参考文献×××××××××××××××××××××××××××××××××××××××××××参考文献书写格式应符合 GB771487文后参考文献著录规章。常用参考文献编写工程和挨次规定如下：先安排中文(按姓氏笔划排序)，后安排英语或其他语种(按字母先后排列)；注释置于页脚，参考文献置于文末。参考文献只列出最主要的、且是公开发表的文献，非正式公开发表的资料不列。文献主要类型格式如下：期刊：序号 作者篇名J附录/ NP_compelte.cpp : 定义掌握台应用程序的入口点。/ NP_compelte.cpp : 定义掌握台应用程序的入口点。/#include “stdafx.h“ #include<iostream> using namespace std;#define Max 100typedef structint dx; int dy;direct_increment; direct_incrementdirect_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 accessibility8; int countAccessibility; typedef structint x; int y;Postion;static Postion nextPath8; static Postion tourpos64; static int arrayPos=0;static int ownAccessibility ;/当前棋子的可到达数static int countMoving=-1;bool success = false;/ typedef structPostion 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;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=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 of sortAll/ voidnext_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)/推断测试位置是否在棋盘内nextPatharrayPos=testPos ;/由测试位置给出正确X,Y坐标accessibility arrayPos = access testPos.xtestPos.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;elsereturn false;/ hasMoreAccessible方法完毕/ void nextAccessiblearrayPos + ;/ void domoving(Postion P)for ( int i = 0 ; i < countAccessibility ; i + )DataType q;q.p=nextPathi; if(i=0)q.flag=1; if(countAccessibility>1)q.flag=2; elseq.flag=0;Push_LinkStack(S,q);access nextPathi.x nextPathi.y - ;/直到没有路径了access P.x P.y = 0 ;/当前位置置0/ void undomoving(Postion P) /撤消移动操作for ( int i = 0 ; i < countAccessibility ; i + )access nextPathi.x nextPathi.y + ;access P.x P.y = ownAccessibility ;/ void tour(Postion P)countMoving + ;/假设64个格子都被走过，则返回if (countMoving = 63 ) tourpos countMoving .x= P.x ; tourpos countMoving .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 - ;/ void fprint /输出路径int order88=0;/初始化for(int k=0;k<64;k+)ordertourposk.xtourposk.y=k;cout<<“n棋盘表示n“;cout<<“01234567n“ ; cout<<“+-+-+-+-+-+-+-+n“;for(int i=0;i<8;i+)printf(“);2printf(“%2d“,i); for(int j=0;j<8;j+)printf(“| %2d “,orderij);printf(“|“);printf(“n“); if(i=7)printf(“+-+-+-+-+-+-+-+-+“);elseprintf(“+-+-+-+-+-+-+-+-+“);printf(“n“);printf(“);/