《数据结构课设》由会员分享，可在线阅读，更多相关《数据结构课设（18页珍藏版）》请在金锄头文库上搜索。
1、马踏棋盘的建立1. 课程设计的目的本课程设计是为了配合数据结构课程的开设，通过设计一完整的程序，使学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并用TC上机调试的基本方法。马踏棋盘就是将马随机放在国际象棋的8*8棋盘某个方格中，马按走棋规则进行移动，要求每个方格只进行一次，走遍整个棋盘的全 部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将 数字1, 2,，64依次填入一个8*8的方阵，输出之。2. 设计方案论证2.1设计思路(1) 根据需求分析可知，我们所设计的程序要达到让马从任意一起点出发都 不重复地遍历所有的8X 8棋格的功能。按照需求，并考虑到程序的
2、可读性，我 们按顺序共设计了以下六大模块：定义头文件和宏定义模块：这是C程序必不可少的一个部分，通过头文件 来调用程序所需库函数，而通过宏定义进行宏替换。数据类型定义模块：该模块定义了全局数据结构，它们的作用域为从定义 开始到本源文件结束，以便于让后面很多函数都可以用到它们， 而不必再重新定 义。探寻路径函数模块：按照马的行走规则对棋盘进行遍历， 寻找马的行走路 径，每次仅访问一个棋格，保证每个棋格都访问到且每个棋格仅访问一次。 输出路径函数模块：对探寻路径函数模块中保存下来的顺序进行输出，输出格式按照棋盘8X8的方阵格式。 起始坐标函数模块：将马的起始位置坐标与棋盘坐标联系起来， 通过调用
3、探寻路径函数和输出路径函数达到预期效果。 主程序模块：主要是完成棋盘初始化，输入，调用等任务进而来完成马踏 棋盘问题。另外，一般来说，当马位于(i,j)时，可以走下列8个位置之一：(i-2,j+1) (i-1,j+2) (i+1,j+2) (i+2,j+1)(i+2,j-1) (i+1,j-2) (i-1,j-2) (i-2,j-1) 这8个可能的位置可以用两个一维数组存放，利 用一维数组表示马在棋盘内新位置。但是，如果(x,y)靠近棋盘的边缘，上述位置可能超出棋盘范围，成为不允许的位置。2.2设计方法(1) 整体框架设计1)定义头文件和宏定义#in clude#i nclude con io
4、.h#in cludestdlib.h#define M 82)数据类型定义定义棋盘数组：int board88；定义结构体数组，如下：typedef struct directint r,c,path numdir这里r表示棋盘的行数，c表示棋盘的列数，path num用来标志可走方向 数。3 )探寻路径函数Findway()Findway()函数功能介绍：定义一个结点类型数组，用于存放8个下一步可踩入结点的信息；其中通过一个 while循环来对各个方向进行探寻，并通过一个for循环语句寻找当前位置的八个方向中的可走方向数最少的方向作为新的方向，期间调用pathnum()函数，该函数功能是记
5、录所有下一个可踩入结点的可执行路径 数目)；选择下一个结点中路径最少的结点为下一个踩入的结点；在进入下一个 踩入点前，先保存该结点的信息并输出，然后依次寻找下一个结点；4)主函数在main()函数中，我们先输入马在棋盘上的一个初始位置(这里表示坐标的两个数必须在大于等于0并且小于等于7)，然后通过调用Findway()函数，可以以三维坐标的形式输出每次马所走的位置的横纵坐标和此时的序号数，此时 boardij数组已经记下了马所走的路径，最后通过一个for循环语句将马走的 路径以棋盘的形式输出。就解决了整个马踏棋盘（2）主要流程图如图1所示输出路径模块流程图如图2所示(3) 功能模块化分析通过对
6、问题描述的分析，可知马踏棋盘问题所要求实现的功能大致由三个部 分组成：1) 接收用户输入的马的起始位置；2) 从起始位置开始在棋盘上标记马按问题描述中的行走规则访问棋盘中每 个格子的顺序；3)输出棋盘上标记的访问顺序。(4) 设计基本步骤：1 )定义一个8*8的数组，用于存放每次踩入的结点位置；2 )获取第一个踩入点；3 )调用findway()函数Findway()函数功能介绍：定义一个结点类型数组，用于存放8个下一步可踩入结点的信息；期间调用pathnum()函数，该函数功能是记录所有下一个可踩 入结点的可执行路径数目)；选择下一个结点中路径最少的结点为下一个踩入的 结点；在进入下一个踩入
7、点前，先保存该结点的信息并输出，然后依次寻找下一 个结点；4 )寻找最后一个结点，并赋给相应信息；3. 设计结果与分析(1) 先对程序进行调试，打开 Microsoft Visual C+ 6.0，输入函数，并进行执 行，确保函数正确。最后对系统进行测试(2) 经测试成功后截取部分图片：在该操作界面中，用户将看到“ in put the start posiitio n，such 3,4 the row and col must be between 0 and 7” 的提示。如图 3 所示。当输入坐标（8, 8）再输入（7, 9）时，用户可以看到“the position is in ava
8、ilable,please in put aga in:” 的提示，如图 4 所示。11Vos it ionsiich as 3,4 the iejvj And col nust be betueen 0 ard 7 :pt he position is pt he posit ion isinualiabLe Aplease input again-7,9 inualiable ,please input acrairi -5是输入溺 0,7, 2? 肆2.滋 7他P?6,&1?仰 11 U23 競 3 If327 E8 4750 丄 5&39483161554613 1G41306110
9、们 28 1E 135*5,543H,551,3,&4L242L552 卜冲MUtput661.4,43 4鹭53 2*5,&3the path of tilt cheae?-422?621144output4丄乎 2.0.B曲丄9inusIiflhI_plBast input AgaiP：?- invdlLftblr Apli!ciytr Lipul i2tCl 0图5.程序结果图输入坐标为(0，0)时结果如图6所示：所以用户应根据自己的需求在允许的范围内将数字填入。下图(4,5 )时的结果图6.程序结果图输入坐标为（1, 2）时结果如图7所示:b&tue&ri Q &ndl 7 input
10、 th ctAFt pociticnctich ac 3,4 the kou And co 1 muct be 1,2 outputthe pc it ten 鼻n戒 th nunh of th pocition,57,3,66,5,77,7,8S,6 2亦風26,3,36*S464,E1,2,10,02a340.4 6亠!.6,122,% 140.6.141,4,IS0,2,2230,2311.24叫3251,2,327,G,335,1.347,2,3S616r43叫442,3453,2,524,3,536,E,E4a.6 就4L0t62 叫13 loutut the path af the
11、c*t2631625别59142717241415264?86235245605728丄3231861485146胡4244?225356411225193437S04749如3633532213873011203563110阳81,0,170,7.27E,2f375,4M72,5f5710”弊 2P&,24,7,2?E.4JE ?,6,394,1,491,7,5S7 匚已7,1,28S,7,405,5B盼题图7.程序结果图4. 设计体会经过这几天的课程设计，我的课程设计已经接近尾声，在此期间，我已经基 本完成了简单的赫夫曼树输出系统， 经过我的不懈努力，同学们的热情帮助，老 师的悉心指导，赫
12、夫曼树输出系统基本功能基本实现，测试运行也基本正常。在课程设计的初期阶段，我知道做任何事没有准备和计划是不行的。 所以对 本学期的知识进行了复习，对不能解决的问题进行了梳理，基本有了制作课设的 能力，然后课程设计开始了。在课程设计的过程中，我非常深刻的认识到自己在数据结构方面的薄弱和不 足，明白了课程设计不是一两天的事，是需要平时在上课时认真听讲，仔细笔记， 还需要自己利用课余时间去图书馆查阅有关图书， 增长知识，以及用电脑浏览相 关网页来一点一滴得积累知识。这样面对课程设计才能应对自如。5. 参考文献1 .王红梅数据结构清华大学出版社 20122 .周海英，数据结构与算法设计（第二版）国防工
13、业出版社 20123 .何钦铭数据结构课程设计浙江大学出版社20124 .ISBN数据结构与算法实验教程高等教育出版社2012.严蔚敏数据结构及应用算法教程清华大学出版社2011.许卓群等著数据结构与算法高等教育出版社20137 .严蔚敏、吴伟民数据结构习题集（c语言版）清华大学出版社 20128 .滕国文.数据结构课程设计.北京：清华大学出版社.2010.099 .苏仕华 等编著. 数据结构课程设计.北京:机械工业出版社.2005.0510 .李春葆.数据结构（C语言版）习题与解析.北京：清华大学出版 社.2002.04源代码：#in clude#i nclude con io.h#i ncludestdlib.h#in clude #
