数据结构课程设计报告.doc

合肥学院计算机科学与技术系课程设计报告2013 ～2014 学年第(二) 学期课程 数据结构与算法 课程设计名称 马拦过河卒问题学生姓名 王雪梅学号 1104013042专业班级 11 级计本（班）指导教师 何立新、檀明2013 年 6 月合肥学院数据结构与算法设计报告目 录课程设计目的内容概要关键词正文1、问题分析和任务2、 数据结构的选择和概要设计3、 详细设计和编码4、 上机调试5、 测试结果及其分析6、 用户使用说明7、 参考文献8、 附录心得体会鸣谢 课程设计目的:“数据结构与算法”精品课程建设组根据“数据结构与算法”课程教学大纲的要求，精心选择了一批课程设计题目，要求学生选择其中的题目，通过独立解决这些问题，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用，按“课、程设计教学大纲”的要求完成“数据结构与算法课程设计报告”使学生深刻理、解、牢固掌握数据结构和算法设计技术，提高分析和解决实际问题的能力在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练内容概要: 棋盘上 A 点有一个过河卒，需要走到目标 B 点。

卒行走的规则：可以向下、或者向右同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点因此称之为“马拦过河卒” 棋盘用坐标表示，A 点(0, 0)、B 点(n, m)(n, m 为不超过 13 的整数)，同样马的位置坐标是需要给出的要求计算出卒从 A 点能够到达 B 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步关键词:马过河,递归法,回溯法,数组…….正文:一、问题分析和任务定义图 1-1 坐标轴A 点有一个过河卒，需要走到目标 B 点卒行走的规则：可以向下、或者向右同时在棋盘上的任一点有一个对方的马（如上图 1-1 的 C 点），该马所在的点和所有跳跃一步可达的点称为方马的控制点例如上图 C 点上的马可以控制 9 个点（图中的 P1，P2...P8 和 C）卒不能通过对方的控制点棋盘用坐标表示，A 点（0，0）、B 点（n, m）(n,m 为不超过 13 的整数，并由键盘输入)，同样马 的位置坐标是需要给出的（约定：C≠A，同时 C≠B）现在要求你计算出卒从 A 点能够到达 B 点的路径的条数做一个表，记录马可以攻击的位置，主要要包括马本身的位置；然后从（0，0）开始每次递归（x+1,y）和（x，y+1） ，如何(x==n1&&y==n2)说明走到位置了，那么 k++（路径数） ；如果大于边界和等于马可以攻击的位置就 return，这样就可以了。

不说考虑速度关系，我们可以加一个过程，即坐标一旦超出目标就 return二、数据结构的选择和概要设计做一个表，记录马可以攻击的位置，主要要包括马本身的位置；然后从（0，0）开始每次递归（x+1,y）和（x，y+1） ，如何(x==n1&&y==n2)说明走到位置了，那么 k++（路径数） ；如果大于边界和等于马可以攻击的位置就return，这样就可以了不说考虑速度关系，我们可以加一个剪枝过程，即坐标一旦超出目标就 return图 1-2 坐标轴三、详细设计和编码1、卒行走的规则：可以向下、或者向右2、计算马的控制点 按照题意，对方的马所在的点和所有跳跃一步可达的点称为对方马的控制点，卒不能通过对方马的控制点在卒出发之前，必须计算对方马的所有控制点显然，若（0，0）或（n,m）为控制点，则输出路径数为 03、假设马的位置是固定不动的，并不是卒走一步马走一步所以从这去计算路径数使用递归的方法，记录马可以攻击的位置if(c=0) //马不能在 x 坐标最边缘的点{if(d+2=0) a[c-1][d-2]=0; //查看马是否能够攻击到}if(c+1=0) a[c+1][d-2]=0; //查看马是否能够攻击到} if(c-2>=0) //马不能在 y 坐标为 1 的点{if(d-1>=0) a[c-2][d-1]=0;if(d+1=0) a[c+2][d-1]=0;if(d+1=0) //马不能在 x 坐标最边缘的点{if(d+2=0) a[c-1][d-2]=0;}if(c+1=0) a[c+1][d-2]=0;}if(c-2>=0) //马不能在 y 坐标为 1 的点{if(d-1>=0) a[c-2][d-1]=0;if(d+1=0) a[c+2][d-1]=0;if(d+1<=Y) a[c+2][d+1]=0;}fun(0,0);printf("路径的条数为:");printf("%d\n",k);printf("是否继续？0--退出\n");scanf("%d",&s);if(s==0) break;}return 0;}心得体会:本次的数据结构课程设计针对具体的实际项目来进行问题分析，数据结构的选择和概要设计，详细设计，测试分析等具体的步骤流程走下来，从中我收获了很多 经过一周的课程设计，有很多的心得体会。

首先，在编写函数之前仔细的将本次课程设计的题目看懂，其次，根据题目要求考虑用数据结构中的那个知识点来实现题目的要求此次，我的课程设计题目比较简单，很容易理解，但是一开始还是把题目要达到的结果想错了，后来经过一个同学的提点发现自己错了将题目理解后，虽然不能用栈的思想来解决这个为题，但是用其他的数据结构思想既简单又容易理解在此次过程中，我发现了一些自己的不足：拿来一个题目，对于问题理解的有些不全面与偏差，直到在网上查询后在正确知道了问题的根本所在；发现我编的程序，太乱没有条理性，当我有不会的问题打算询问同学时，说我编的太乱，所以必须慢慢改正，使程序具有科学性、条理性通过这次课程设计，我深刻认识到算法在程序设计中的重要性，发现一个程序设计就是算法与数据结构的结合体，在一个完整的程序中总是由若干个函数构成的，这些相应的函数体现了算法的基本思想通过完成整个程序设计，对栈的使用掌握的更加熟练，加深了对数据结构的理解和认识同时，由于我以前对于函数的递归调用掌握的不太熟练，通过此程序的完成，更进一步的了解了函数的递归调用 此次课程设计，获得了很多宝贵的经验，特别是怎样将理论与实践相结合，把书本上的内容应用到我的程序中。

怎样使各个子函数实施其详细功能，特别是各个子函数之间的调用，一定要相当清晰达到相互协调的作用，其实，我的程序相比较简单，函数调用主要是递归调用 总之，通过这次课程设计，我对于将课本上的知识运用到实际生活中的整个过程深有体会了，不像之前对知识单纯的停留在课本及考试的要求上对于我们学过的知识，我们要尽量深入而透彻地去理解以及渗透，因为，在我看来，只有充分的了解渗透才能更好的将课本所学的知识运用到实验和生活中去这次课程设计，我受益匪浅鸣谢：在此对指导老师和各位同学的帮助致以衷心的感谢。