1安徽工程大学信息10课程设计马踏棋盘的求解及演示设计摘要数据结构是计算机科学与技术专业的一门核心专业基础课程，是一门理论性强、思维抽象、难度较大的课程。我认为学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，我们应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。《数据结构》课程设计是计算机科学技术专业集中实践性环节之一，是学习完《数据结构》课程后进行的一次全面的综合练习。开设本课程设计实践的主要目的就是要达到理论与实际应用相结合，提高学生的动手能力，完成计算机应用能力的培养；本课程设计主要解决马踏棋盘的问题，找出踏遍棋盘的多种路径，并实现动态要是过程。马踏棋盘问题，实际上是图论中的哈密顿通路问题，是典型的NP问题,求解的问题与算法设计有很大关系，如果采取穷举搜索的话，很容易陷入海量搜索的状态，耗费巨大的时间，使问题几乎不可解，因此马在棋盘上遍历采用算法当中的深度优先算法和启发式贪心算法，用栈来存储遍历过程，通过对栈的使用实现对所有路径的搜索。在调试过程发现，启发式贪心算法，针对于马踏棋盘问题有着极大的好处，就是无论从棋盘上哪个点开始，找到一条遍历完棋盘的通路是不需要回溯的，也就节省了大量的时间，而试探性的操作对于每个点都也只有168步，所以求出所有路径在不到一秒的时间内完成。关键词：马踏棋盘；骑士周游；哈密顿通路;NP-完全问题；贪心算法；回溯法；2目录马踏棋盘的求解及演示设计..........................................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参考文献.........................................................153第一章引言本课程设计主要研究马踏棋盘的问题，即骑士周游问题，是将马随机放在国际象棋的8×8棋盘的某个方格中,“马”按照走棋规则进行移动，要求每个方格只进入一次,走遍棋盘上全部64个方格。许多知名的数学家，如德莫弗(DeMoivre)、欧拉(Euler)与范德蒙德(Vandermonde)等人，在过去的200年中都研究过这个问题，今天从数据结构的角度，解决这一问题。力求以最快的速度，即最高的效率来解决问题。已知穷举法是几乎不可能完成的，而与解决迷宫问题的回溯法，也要占用大量的时间，这里采用贪心算法来解决这一问题，并找出多有的遍历路径。4第二章需求分析2.1问题描述马随机放在国际象棋的8×8棋盘的某个方格中,“马”按照走棋规则...
