数据结构课程设计骑士游历问题

存档资料成绩：华东交通大学理工学院课程设计报告书所属课程名称数据结构题目骑士游历分院电信分院专业班级11电商2班学号20110210460227学生姓名罗湾湾指导教师吴军良2013年7月5日目录第一章课程设计内容及要求..........................................................................3第二章课程设计的设计分析与功能模块..................................................12.1设计分析............................................................................................1(1)设计目的........................................................................................1(2)任务分析..........................................................................................11.要求.........................................................................................................12.输入........................................................................................................12.2程序功能模块图.................................................................................1第三章流程图设计的具体实现....................................................................33.1马踏遍棋盘流程图...............................................................................33.2系统测试与调试...................................................................................5第四章源代码程序设计............................................................................94.1详细设计.............................................................................................9创建...............................................................................................................9操作...............................................................................................................9显示...............................................................................................................94.2源代码..............................................................................................10第五章课程设计心得............................................................................13第六章参考文献..............................................................................14第七章致谢..........................................................................................15第一章课程设计内容及要求骑士游历问题是一个古老而著名的问题,问题的描述是:在8×8格的国际象棋棋盘上,象棋马能否从某个格子出发按照“马跳日”的规则跳遍所有64个格子最后再回到出发的那个格子。国际象棋中的马,英语为knight,恰好又意指中世纪西方世界的“骑士”,因此,这个问题又被称为“骑士游历。在一个棋盘上（8行8列）放一个“马”，按“马走日字”的规则，马要走到棋盘上每一个格子，且每个格子只走一次。用回溯法深度优先搜索，若寻找到满足要求的解，则输出；否则推回上一层往下一个方向搜索。对于当前所在位置（x，y），依次枚举8个方向搜索，直到找到一组可行解为止。使用剪枝有2处：第一、使用Warnsdorff'srule，枚举当前解得时候优先选择下一步可行步数最少的方向；第二、若第一点中的方向存在不止一个，则优先选择离中心位置较远的方向；每次都从中心点开始出发，求出一条合法路径后再平移映射回待求路径。华东交通大学理工学院第1页第二章课程设计的设计分析与功能模块2.1设计分析(1)设计目的1.熟练使用C语言编写程序，强化模块设计理念。2.设计一个国际象棋马踏棋盘的演示程序。3.理解栈的特性“后进先出”和队列的特性“先进先出”。4.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。(2)任务分析1.要求在国际象棋8×8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。编制程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，并输出它的行走路线。2.输入任意一个起始位置；输出：无重复踏遍棋盘的结果，以数字1-64表示行走路线。2.2程序功能模块图各模块之间的调用关系，如图所示：华东交通大学理工学院第2页华东交通大学理工学院第3页第三章流程图设计的具体实现3.1马踏遍棋盘流程图华东交通大学理工学院第4页开始Inti、ji=0iNBoard[i][j]=0i++输入棋子起始位置判断棋子是否出棋盘MultiplexFor循环从这个位置开始结束华东交通大学理工学院第5页3.2系统测试与调试1.程序代码的输入和运行新建C文件并输入代码到工作界面当中，仔细检查，运行代码，如下图所示，图3.2-1表示程序的输入和运行，图3.2—1图3.2—22.程序代码的调试经过请教老师和同学们的帮助，还有自己的多次调试，终于修改好了程序代码，运行后准确无误，如图3.2-3所示：图3.2-33程序的显示结果在命令窗口中输入了棋子的不同起点，运行都成功了。如下图华东交通大学理工学院第6页所示：图3.2-4以（1，1）为起点图3.2-5以（0，5）为起点华东交通大学理工学院第7页图3.2-6以（2，0）为起点图3.2-6以（4，0）为起点华东交通大学理工学院第8页图3.2-6以（0，3）为起点华东交通大学理工学院第9页第四章源代码程序设计4.1详细设计创建创建一个8行8列的棋盘：#includestdio.hintboard[8][8]={0};intmain(void){for(i=0;i8;i++){for(j=0;j8;j++){printf(%2d,board[i][j]);}putchar('\n');}return0;}操作输入骑士的初始位置，进行骑士游历操作：inti,j;printf(输入起始点：);inttravel(intx,inty){intktmove1[8]={-2,-1,1,2,2,1,-1,-2};intktmove2[8]={1,2,2,1,-1,-2,-2,-1};显示显示出游历结果：intstartx,starty;inti,j;printf(输入起始点：);华东交通大学理工学院第10页scanf(%d%d,&startx,&starty);if(travel(startx,starty)){printf(游历完成！\n);}else{printf(游历失败！\n);}4.2源代码#includestdio.h#defineN5#defineNSQUAREN*NintHorseTry(inti,intx,inty,inth[N+1][N+1]);staticinta[9]={0,2,1,-1,-2,-2,-1,1,2};staticintb[9]={0,1,2,2,1,-1,-2,-2,-1};main(){inti,j,flag,x,y;staticinth[N+1][N+1]={0};printf(Inputtheinitialpositionx,y:);scanf(%d,%d,&x,&y);h[x][y]=1;flag=HorseTry(2,x,y,h);if(flag)华东交通大学理工学院第11页{printf(Output:\n);for(i=1;i=N;i++){for(j=1;j=N;j++){printf(%5d,h[i][j]);}printf(\n);}}else{printf(Nosolution!\n);}}intHorseTry(inti,intx,inty,inth[N+1][N+1]){intu,v,flag,count=0;do{count++;flag=0;u=x+a[count];v=y+b[count];if((u=1&&u=N)&&(v=1&&v=N)&&h[u][v]==0){h[u][v]=i;if(iNSQUARE){flag=HorseTry(i+1,u,v,h);if(!flag)h[u][v]=0;华东交通大学理工学院第12页}else{flag=1;}}}while(!flag&&count8);returnflag;}华东交通大学理工学院第13页第五章课程设计心得通过两个星期对骑士游历这个程序的分析，我对C语言这门课程有了进一步的巩固，对我们现在学的《数据结构（C语言版）》的知识有了一个很好的回顾和掌握，我的在这个过程中我也知道自己能力的不足，在面对问题的时候更应该要请教老师和同学，自己也可以动手查阅资料。我们不单是要提高自己的理论能力，还要多去实践，这样我们就能够更好的提高自己。课程设计是我们专业课程知识综合应用的实践训练，是我们迈向社会，从事职业工作前一个必不少的过程．”千里之行始于足下”，通过这次课程设计，我深深体会到这句千古名言的真正含义．我今天认真的进行课程设计，学会脚踏实地迈开这一步，就是为明天能稳健地在社会大潮中奔跑打下坚实的基础．在这次设计过程中，体现出自己单独设计的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，从中发现自己平时学习的不足和薄弱环节，从而加以弥补。华东交通大学理工学院第14页第六章参考文献[1]谢希仁.计算机网络（第五版）[M].北京：电子工业出版社，2008年2月[2]胡小强计算机网络[M]北京：北京邮电大学出版社2005年1月[3]严蔚敏李冬梅吴伟民数据结构（C语言版）[M]人民邮电出版社，2011年2月[4]李丽娟C语言程序设计教程（第二版）[M]北京：人民邮电出版社2009年3月［