骑士游历、骑士巡游(C语言)课程设计.doc

存档资料 成绩： 华东交通大学理工学院课 程 设 计 报 告 书所属课程名称 数据结构 题 目 骑士游历 分 院 专业班级 学号 学生姓名 黄锦辉 指导教师 2012 年 6月 15 日 目 录第1章 课程设计内容及要求1第2章 功能的说明与实现22.1 程序功能模块22.2 程序功能模块图2第3章 程序功能的具体实现33.1 主函数main()的执行流程33.2 系统测试与调试3第4章 源代码6第5章 课程设计心得9第6章 参考文献10 华东交通大学理工学院 第1 章 课程设计内容及要求 运行程序设置一个8行8列的棋盘，在国际象棋的原则下，任意的输入一个存在的点，这个被视为骑士（马）的初始位置，让马通过这个点走完棋盘上的每一个点，并且不重复。在对已经走过的路线里，采用标志矩阵进行记录。标志矩阵的引入利用了数据的线性存储。这个称为骑士游历算法。 本课程设计所采用的计算机语言是C语言，所使用的软件是使用比较普遍的Microsoft Visual C+ 软件。第2章 功能的说明与实现 2.1 程序功能模块 总共分为三个模块，分别是创建棋盘模块，位置设置模块和显示结果模块 1.创建棋盘模块：此时我们使用矩阵设计一个模拟的棋盘。其关键代码如下：int f1111 ; /*定义一个矩阵来模拟棋盘*/int adjm121121; /*于上述棋盘，标志矩阵*/void creatadjm(void) /*创建标志矩阵函数声明*/void mark(int,int,int,int); /*将标志矩阵相应位置置1*/void travel(int,int); /*巡游函数声明*/int n,m; /*定义矩阵大小及标志矩阵的大小*/ 2.位置设置模块：输入任意一个在8行8列棋盘中的一个点，其格式表示为：m n （m表示行，n表示列）。 3.显示结果模块：将起始位置设定好了，将在这个模拟棋盘中用数字显示马走过的每一步。2.2 程序功能模块图总共有三个模块，如下图所示：骑士游历创建棋盘显示结果位置设置创建矩阵进行游历显示结果 图2.21第3章 程序功能的具体实现3.1 主函数main()的执行流程1.运行了主函数main()之后，马上执行了菜单，输入了行列数， 在这里我们采用的是8行8列的棋盘2.执行流程图，如下所示 是 否 再 是 否 次 运 行 输入模拟棋盘行列数判断棋盘输入起点位置判断棋子输出结果结束开始图3.113.2 系统测试与调试1.程序代码的输入和运行 新建C文件并输入代码到工作界面当中，仔细检查，运行代码，如下图所示，图3.2-1表示程序的输入和运行，图3.2-2表示运行出错：图3.21图3.222.程序代码的调试 经过老师和同学的讨论，自己上网查阅资料，修改了程序出错的地方，是由于自己的粗心，忘记写入标点符号，这才导致了错误，然后又仔细的检查了一遍程序，程序运行成功，没有错误了。图3.2-33 程序的显示结果 在命令窗口中输入了棋子的不同起点，运行都成功了。如下图所示：图3.2-4 以（2，3）为起点图3.2-5 以（4，5）为起点图3.2-6 以（6，6）为起点第4章 源代码#include int f1111 ; /*定义一个矩阵来模拟棋盘*/int adjm121121;/*标志矩阵，即对于上述棋盘，依次进行编号*/void creatadjm(void); /*创建标志矩阵函数声明*/void mark(int,int,int,int); /*将标志矩阵相应位置置1*/void travel(int,int); /*巡游函数声明*/int n,m; /*定义矩阵大小及标志矩阵的大小*/*主函数*/int main() int i,j,k,l; printf(Please input size of the chessboard: ); /*输入矩阵的大小值*/scanf(%d,&n); m=n*n; creatadjm(); /*创建标志矩阵*/puts(The sign matrix is:); for(i=1;i=m;i+) /*打印输出标志矩阵*/ for(j=1;j0)|(j0) /*对骑士位置的判断*/ for(i=1;i=n;i+) /*棋盘矩阵初始化*/ for(j=1;j=n;j+) fij=0; k=0; /*所跳步数计数*/ travel(l,k); /*从i,j出发开始巡游*/ puts(The travel steps are:); for(i=1;i=n;i+) /*巡游完成后输出巡游过程*/ for(j=1;j=n;j+) printf(%4d,fij); printf(n); printf(Please input the knights position (i,j): );/*为再次巡游输入起始位置*/ scanf(%d %d,&i,&j); l=(i-1)*n+j; puts(n Press any key to quit. );getchar(); return 0;/*创建标志矩阵子函数*/void creatadjm() int i,j; for(i=1;i=n;i+) /*巡游矩阵初始化*/ for(j=1;j=n;j+) fij=0; for(i=1;i=m;i+) /*标志矩阵初始化*/ for(j=1;j=m;j+) adjmij=0; for(i=1;i=n;i+) for(j=1;j=n;j+) if(fij=0) /*对所有符合条件的标志矩阵种元素置1*/ fij=1; if(i+2=n)&(j+1=n) mark(i,j,i+2,j+1); if(i+2=1) mark(i,j,i+2,j-1); if(i-2=1)&(j+1=1)&(j-1=1) mark(i,j,i-2,j-1); if(j+2=n)&(i+1=n) mark(i,j,i+1,j+2); if(j+2=1) mark(i,j,i-1,j+2); if(j-2=1)&(i+1=1)&(i-1=1) mark(i,j,i-1,j-2); return;/*巡游子函数*/void travel(int p,int r) int i,j,q; for(i=1;i=n;i+) for(j=1;jr) fij=0; /*棋盘矩阵的置r时，置0*/ r=r+1; /*跳步计数加1*/ i=(p-1)/n)+1; /*还原棋盘矩阵的横坐标*/ j=(p-1)%n)+1; /*还原棋盘矩阵的纵坐标*/ fij=r; /*将fij做为第r跳步的目的地*/ for(q=1;q=m;q+) /*从所有可能的情况出发，开始进行试探式巡游*/ i=(q-1)/n)+1; j=(q-1)%n)+1; if(adjmpq=1)&(fij=0) travel(q,r); /*递归调用自身*/ return;/*赋值子函数*/void mark(int i1,int j1,int i2,int j2) adjm(i1-1)*n+j1(i2-1)*n+j2=1; adjm(i2-1)*n+j2(i1-1)*n+j1=1; return; 第5章 课程设计心得 通过两个星期对骑士游历这个程序的分析，我对C语言这门课程有了进一步的巩固，对我们现在学的数据结构（C语言版）的知识有了一个很好的回顾和掌握，我的在这个过程中我也知道自己能力的不足，在面对问题的时候更应该要请教老师和同学，自己也可以动手查阅资料。