数据结构课程设计-马踏棋盘.doc

数据结构课程设计报告设计题目： 马踏棋盘院 系 计算机学院 年 级 11 级 学 生 xxxxxxx 学 号 xxxxxxxxx 指导教师 xxxxxxxxx 起止时间 9-6/9-13 2013年9月10日星期二目 录一、 课程设计目的 -3二、 需求分析-3三、程序源代码- 4四、调试分析-7五、问题总结-8六、参考资料-9 一、 课程设计目的(1) 熟练使用 C 语言编写程序，解决实际问题;(2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;(3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;(4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力; 二、 需求分析问题描述:将马随机放在国际象棋的 8X8 棋盘中的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部 64 个方格。编制递归程序，求出马的行走路线 ，并按求出的行走路线，将数字 1，2，64 依次填入 8X8 的方阵输出之。测试数据:由读者指定可自行指定一个马的初始位置。实现提示:每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”悔棋使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。背景介绍：国际象棋为许多令人着迷的娱乐提供了固定的框架，而这些框架常独立于游戏本身。其中的许多框架都基于骑士奇异的L型移动规则。一个经典的例子是骑士漫游问题。从十八世纪初开始，这个问题就引起了数学家和解密爱好者的注意。简单地说，这个问题要求从棋盘上任一个方格开始按规则移动骑士，使之成功的游历国际象棋棋盘的64个方格，且每个方格都接触且仅接触一次。可以用一种简便的方法表示问题的一个解，即将数字1，64按骑士到达的顺序依次放入棋盘的方格中。一种非常巧妙的解决骑士漫游地方法由J.C.Warnsdorff于1823年给出。他给出的规则是：骑士总是移向那些具有最少出口数且尚未到达的方格之一。其中出口数是指通向尚未到达方格的出口数量。在进一步的阅读之前，你可以尝试利用Warnsdorff规则手工构造出该问题的一个解。实习任务：编写一个程序来获得马踏棋盘即骑士漫游问题的一个解。您的程序需要达到下面的要求：棋盘的规模是8*8；对于任意给定的初始化位置进行试验，得到漫游问题的解；对每次实验，按照棋盘矩阵的方式，打印每个格被行径的顺序编号。技术提示：解决这类问题的关键是考虑数据在计算机中的存储表示。可能最自然的表示方法就是把棋盘存储在一个8*8的二维数组board中。以(x,y)为起点时骑士可能进行的八种移动。一般来说，位于(x,y)的骑士可能移动到以下方格之一：(x-2,y+1)、(x-1,y+2)、(x+1,y+2)、(x+2,y+1)、(x+2,y-1)、(x+1,y-2)、(x-1,y-2)、(x-2,y-1)。但请注意，如果(x,y)的位置离某一条边较近，有些可能的移动就会把骑士移到棋盘之外，而这当然是不允许的。骑士的八种可能的移动可以用一个数组MoveOffset方便地表示出来：MoveOffset0=(-2,1)MoveOffset1=(-1,2)MoveOffset2=(1,2)MoveOffset3=(2,1)MoveOffset4=(2,-1)MoveOffset5=(1,-2)MoveOffset6=(-1,-2)MoveOffset7=(-2,-1)于是，位于(x,y)的骑士可以移动到(x+MoveOffsetk.x, y+MoveOffsetk.y)，其中k是0到7之间的某个整数值，并且新方格必须仍位于棋盘上。扩展需求：可以考虑将结果图形化。(b)考察所有初始化的情况，测试是否都能够得到解。三、程序源代码#include#include#define MAXSIZE 100#define N 8int board88; /定义棋盘int Htry18=1,-1,-2,2,2,1,-1,-2; /*存储马各个出口位置相对当前位置行下标的增量数组*/int Htry28=2,-2,1,1,-1,-2,2,-1; /*存储马各个出口位置相对当前位置列下标的增量数组*/struct Stack /定义栈类型 int i; /行坐标int j; /列坐标 int director; /存储方向stackMAXSIZE; /定义一个栈数组int top=-1; /栈指针void InitLocation(int xi,int yi); /马在棋盘上的起始位置坐标int TryPath(int i,int j); /在每个方向进行尝试，直到试完整个棋盘void Display(); /输出行走的路径void InitLocation(int xi,int yi)int x,y; /定义棋盘的横纵坐标变量top+; /栈指针指向第一个栈首stacktop.i=xi; /将起始位置的横坐标进栈stacktop.j=yi; /将起始位置的纵坐标进栈stacktop.director=-1; /将起始位置的尝试方向赋初值boardxiyi=top+1; /标记棋盘x=stacktop.i; /将起始位置的横坐标赋给棋盘的横坐标y=stacktop.j; /将起始位置的纵坐标赋给棋盘的纵坐标if(TryPath(x,y) /调用马探寻函数，如果马探寻整个棋盘返回1否则返回0Display(); /输出马的行走路径else printf(无解); int TryPath(int i,int j)int find,director,number,min; /临时变量int i1,j1,h,k,s; /临时变量int a8,b18,b28,d8; /临时数组while(top-1) /栈不空时循环for(h=0;h=0&i=0&j8) /如果找到下一位置for(k=0;k=0&i1=0&j18) /如果找到下一位置 number+; /记录条数 ah=number; /将条数存入数组a8中 for(h=0;h8;h+) /根据可行路径条数小到大按下表排序放入数组d8中min=9; for(k=0;kak) min=ak; dh=k; /将下表存入数组d8中 s=k; as=9; director=stacktop.director; if(top=63) /若走完整个棋盘返回1return (1);find=0; /没有找到下一个位置for(h=director+1;h=0&i=0&j8) /如果找到下一位置find=1; /表示找到下一个位置break;if(find=1) /如果找到下一个位置进栈stacktop.director=director; /存储栈结点的方向 top+; /栈指针前移进栈stacktop.i=i;stacktop.j=j;stacktop.director=-1; /重新初始化下一栈结点的尝试方向boardij=top+1; /标记棋盘else /否则退栈boardstacktop.istacktop.j=0; /清除棋盘的标记top-; /栈指针前移退栈return (0); void Display()system(color 1e); int i,j; for(i=0;iN;i+)for(j=0;jn);printf(n);printf(欢迎进入骑士漫游小游戏! n);printf(n);int i,j;int x,y;for(i=0;iN;i+) /初始化棋盘 for(j=0;j.请输入初始位置坐标(x,y) 注:(1,1)-(8,8)n);printf(Input x = );scanf(%d,&x); /输入起始位置的横坐标printf(Input y = );scanf(%d,&y); /输入起始位置的纵坐标if(x=1&x=1&y=8)break;printf(n输入有误,请重新输入!nn);printf(骑士从第%d行，第%d列开始漫游:n,x,y);InitLocation(x-1,y-1); /调用起始坐标函数四、调试分析1. 开始界面2.输入坐标五、问题总结此次数据结构课程设计我组设计的是一个利用栈递归得到的马踏遍棋盘的演示程序，刚看题目时候觉得还比较困难，根本没一点思绪，但通过在网上查找相关资料，对这个问题才有了一定的思绪。在组员的分工合作中，我们终于把程序写出来了。在这个过程中，我收获颇多，不仅理论知识掌握的更牢，实际动手能力也