《数据结构课设马踏棋盘》由会员分享，可在线阅读，更多相关《数据结构课设马踏棋盘（8页珍藏版）》请在金锄头文库上搜索。
1、附件1:学 号：课程设计题目马踏棋盘学院计算机科学与技术专业计算机科学与技术班级姓名指导教师2011 年 7 月 4 日附件2:课程设计任务书学生姓名： 专业班级：班指导教师： 工作单位：计算机科学系题目：马踏棋盘初始条件：设计一个国际象棋的马踏遍棋盘的演示程序。将马随机放在国际象棋的8X 8棋盘Board88的某个方格中，马按走棋规则（见题集p98）进行移动。要求每个方格只进入一次，走边棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1,2,3, , ,64依次填入一个8X 8的方阵，输出之。测试用例见题集p98。要求完成的主要任务:（包括课程设计工作量及其
2、技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用 A4纸打印（书写），并应包含如下内容：1、问题描述简述题目要解决的问题是什么。2、设计存储结构设计、主要算法设计（用类C语言或用框图描述）、测试用例 设计；3、调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4、经验和体会（包括对算法改进的设想）5、附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出，6、设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩 均为0分。时间安排：1、第19周完成。2、 7月1日14： 00到计算中心检查程序、交课程设计
3、报告、源程序（CD 盘）。指导教师签名：系主任（或责任教师）签名:马踏棋盘1 问题描述设计一个国际象棋的马踏遍棋盘的演示程序。基本要求：将马随机放在国际象棋的8X8棋盘Board88的某个方格中，马按走棋 规则(见题集p98)进行移动。要求每个方格只进入一次，走边棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字 1,2,3, , ,64依次填入一个8X8的方阵，输出之。2 程序设计1 存储结构马位于方格(i , j )时有八个可能的移动位置。分别用两个一维数组 move10, 7、 move20, 7 来表示这八个位置的。 Board 用于存储走过方格所填入的
4、数字， 从 1 到 64.int HTry18=2,2,1,1,-1,-1,-2,-2,HTry28=1,-1,2,-2,2,-2,1,-1,，board88=0;2主要算法程序主要用到两个函数，n extpos与move next。分别用来计算可能的出口 个数和选择出口。int nextpos(int i,int j,int a8,int b8) / 函数 nextpos 计算位置( i ， j )出口个数int count=0,k,i1,j1;for(k=0;k7|i17|j10)continue;else if(boardi1j1!=0)continue;elseacount=move1
5、k;bcount=move2k; +count; return(count);函数 nextpos 用于计算( i ，j )可走的出口数，用 count 返回。先从当前位置 走到八个可能的位置中的一个， 若超出 8*8 边界则返回进行下一循环， 若已被填 入数字则也要返回进行下一循环。反之纪录这一可走出口的位置并将 count 加 1.int movenext(int *i,int *j,int a,int b) / 函数 movenext 在有多出口时，选择适当出口推进一步int temp,count=8,a18,b18,nexti_like8,nextj_like8, cur_row_li
6、ke,cur_col_like,k,t;for(k=0;knpos;k+) temp=nextpos(*i+nextik,*j+nextjk,a1,b1); if(tempcount)cur_row_like=*i+nextik;cur_col_like=*j+nextjk;count=temp;for(t=0;tcount;t+)nexti_liket=a1t;nextj_liket=b1t;*i=cur_row_like;*j=cur_col_like;for(k=0;kcount;k+)ak=nexti_likek;bk=nextj_likek;return count;程序中主要用的是
7、两个一维数组存放可能的移动位置， 每次在多个可走位置中 选择一个进行试探， 其余未曾试探过的可走位置存储起来， 以备在试探失败时 “回 溯”使用。3调试程序测试数据预期结果运行结果(3, 4)输入有效:结果正确(9,0)输入无效结果错误(-9,4)输入无效:无路径(10,12)输入无效无路径(a, 4)输入无效结果错误调试结果：经过测试发现出错，当输入的字符为非数字字符时，均会被默认输入为（0, 0）。原因在于，输入模块用两个整形数据接收用户的输入数据，当这两个数据不是数字字符时，系统会默认其为0。故为该模块代码增设两个字符变量以接收用户输 入的数据。在次测试，符合预期结果。当输入数据超过8之
8、后就会显示没有路径。 最后调试完了输出一个8*8的方阵，方阵中数字从1到64表示依次所走的每一 步。4体会根据问题描述可知，需要解决的问题并不复杂，整个问题只需要实现一个功 能那就是输出马按特定规则在棋盘上的遍历顺序。 但是为了实现该功能却需要好 的算法以减少时间空间复杂度。由于对象是棋盘我们自然想到把棋盘抽象成一个 二维数组，并且用两个一维数组存放（i, j）可能移动到的位子的行与列。主要 用到两个函数nextpos和movepos分别计算出口个数和选择一个出口走下一步。 每走一步都输出相应数字，从1到64,于每一步相对应。知道走完 8*8方格。 此程序主要用到回溯的思想，每次选一个出口，如
9、果最后路不通，可以通过前面 保存的位置进行回溯。其实马踏棋盘问题还可以采用栈或队来作为存储结构，另外非递归算法比递 归算法更简洁，复杂度也小一些。可以米用深度优先搜索来解决。 深度优先遍历 马的行走路径所构成的一颗解的空间树，马的行走路径实际上就是从这颗解空间 树的根节点到叶节点过程中经过的所有节点所组成的路径。此外这个程序稍作修改之后可以表示一个9*9的棋盘。经过这次数据结构课程设计，我们不仅及时巩固了算法及软件工程的知识， 并利用所学的知识解决了实际问题。 我的课设题目是马踏棋盘，最初拿到题目很 茫然，但是翻看了一下指导书之后有了个大致思路。大部分代码是自己编写的， 只有其中一个函数是查了
10、资料之后参考了一下的。上机运行程序时没有错误。老师验收时提了相关问题，我都一一作了回答，对运行结果老师问道1到64代表什么，可不可以改成9*9方格，对此我都做了回答。我觉得自己对此次实验完成 的还不错，达到了课设的目的。5运行结果输入（3,4）之后运行结果截屏如下:输入符合要求的初始位置，得到的结果正确C Prog rat* F 沁 IMibogE Visual Stuc o-, M y P rc； e ct s-.f d g d Deh u g 1d g d s. exeEnter thestaFt in9position ：3 4Asolution :3615643417382761543
11、5632&3318143762595&312629S36047501581932381352574&49225710454951224320123?S544412439611402342142Pressanykeytocont inue输入的初始位置不合理，结果显示没有路径Enter the start!ng posit ionco1：10 12 no solutionPress any key to cont inue本科生课程设计成绩评定表班级：姓名：学号:序号评分项目满分实得分1学习态度认真、遵守纪律102设计分析合理性103设计方案正确性、可行性、创造性204设计结果正确性405设计报告的规范性106设计验收10总得分/等级评语：注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、 及格（60-69分）、60分以下为不及格指导教师签名:201年 月 日
