数据结构和算法马踏棋盘.doc

计科系数据结构课程设计报告PAGE 1 -合肥学院计算机科学与技术系课程设计报告2012～2013学年第2学期课程 数据结构与算法课程设计名称马踏棋盘学生姓名学号专业班级指导教师2013 年6月目 录 TOC \o 1-3 \h \z \u HYPERLINK \l _Toc359482967 数据结构课程设计报告————马踏棋盘 PAGEREF _Toc359482967 \h - 2 - HYPERLINK \l _Toc359482969 问题描述 PAGEREF _Toc359482969 \h - 2 - HYPERLINK \l _Toc359482970 1、问题分析与定义 PAGEREF _Toc359482970 \h - 2 - HYPERLINK \l _Toc359482971 2、数据结构的选择和概要设计 PAGEREF _Toc359482971 \h - 3 - HYPERLINK \l _Toc359482972 数据结构的选择 PAGEREF _Toc359482972 \h - 3 - HYPERLINK \l _Toc359482973 概要设计 PAGEREF _Toc359482973 \h - 3 - HYPERLINK \l _Toc359482974 3、详细设计和编码 PAGEREF _Toc359482974 \h - 4 - HYPERLINK \l _Toc359482975 4、上机调试过程 PAGEREF _Toc359482975 \h - 6 - HYPERLINK \l _Toc359482976 5、测试结果及分析 PAGEREF _Toc359482976 \h - 7 - HYPERLINK \l _Toc359482977 6、用户使用说明 PAGEREF _Toc359482977 \h - 9 - HYPERLINK \l _Toc359482978 7、参考文献 PAGEREF _Toc359482978 \h - 9 -附录 HYPERLINK \l _Toc359482980 源程序 PAGEREF _Toc359482980 \h - 10 -数据结构课程设计报告————马踏棋盘题目：【问题描述】设计一个国际象棋的马踏遍棋盘的演示程序。要求：将马随机放在国际象棋的8×8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出之。1、问题分析与定义走棋规则：马走3×2格对角线，简单的说就是走L形棋盘如图所示，将马放在棋盘中的任意一个位置，按照马的走棋规则，我们能够发现，如果没有其他棋子的影响，它最多有8个出口，最少有2个出口。?012345670??8?1???1?7???2??2???H????3?6???3??4??5?4???5????????6????????7????????马所在位置及其出口算法核心思想：本程序的核心算法是“贪心算法”。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。2、数据结构的选择和概要设计数据结构的选择栈：本程序可以利用栈的知识来解决，当然，栈也包括链栈和顺序栈，由于本程序数据有限，并且顺序栈较链栈简单，所以该程序最终选择使用顺序栈来解决。贪心算法：在算法中采用逐步构造最优解。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出就不可再更改。概要设计Ⅰ、主程序模块：void main(){定义变量；接受命令；处理命令；退出；}Ⅱ、起始坐标函数模块——马儿在棋盘上的起始位置；Ⅲ、探寻路径函数模块——马儿每个方向进行尝试，直到试完整个棋盘；Ⅳ、输出路径函数模块——输出马儿行走的路径； 流程图如下：主程序模块主程序模块 输入的初始位置是否正确 否 是 起始坐标函数模块