骑士游历数据库课程设计

存档资料成绩：华东交通大学理工学院课程设计报告书所属课程名称数据结构题目骑士游历分院电信分院专业班级电子商务1班学号20100210460123学生姓名何芳林指导教师吴军良2012年6月15日目录第一章课程设计内容及要求....................3第二章功能说明..............................4第三章详细设计..............................53.1创建...................................53.2操作...................................53.3显示...................................5第四章程序实现..............................74.1源码分析...............................74.2程序编译...............................94.3程序运行..............................104.4运行结果..............................104.5时间复杂度分析.........................12第五章课程设计心得.........................13第六章参考文献（资料）.....................14华东交通大学理工学院课程设计报告第3页共14页第一章课程设计内容及要求在一个棋盘上（8行8列）放一个“马”，按“马走日字”的规则，马要走到棋盘上每一个格子，且每个格子只走一次。用回溯法深度优先搜索，若寻找到满足要求的解，则输出；否则推回上一层往下一个方向搜索。对于当前所在位置（x，y），依次枚举8个方向搜索，直到找到一组可行解为止。使用剪枝有2处：第一、使用Warnsdorff'srule，枚举当前解得时候优先选择下一步可行步数最少的方向；第二、若第一点中的方向存在不止一个，则优先选择离中心位置较远的方向；每次都从中心点开始出发，求出一条合法路径后再平移映射回待求路径。华东交通大学理工学院课程设计报告第4页共14页第二章功能说明1．创建。创建一个8行8列的棋盘。2.操作。输入骑士的初始位置，进行骑士游历操作。3.显示。显示出游历结果。图2-1功能模块图创建操作骑士游历实验过程显示创建棋盘进行游历显示游历结果华东交通大学理工学院课程设计报告第5页共14页第三章详细设计3.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;}3.2操作输入骑士的初始位置，进行骑士游历操作：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};3.3显示显示出游历结果：intstartx,starty;inti,j;printf(输入起始点：);scanf(%d%d,&startx,&starty);if(travel(startx,starty)){printf(游历完成！\n);华东交通大学理工学院课程设计报告第6页共14页}else{printf(游历失败！\n);}华东交通大学理工学院课程设计报告第7页共14页第四章程序实现4.1源码分析#includestdio.hintboard[8][8]={0};intmain(void){intstartx,starty;inti,j;printf(输入起始点：);scanf(%d%d,&startx,&starty);if(travel(startx,starty)){printf(游历完成！\n);}else{printf(游历失败！\n);}for(i=0;i8;i++){for(j=0;j8;j++){printf(%2d,board[i][j]);}putchar('\n');}return0;}inttravel(intx,inty){//对应骑士可走的八个方向intktmove1[8]={-2,-1,1,2,2,1,-1,-2};intktmove2[8]={1,2,2,1,-1,-2,-2,-1};//测试下一步的出路intnexti[8]={0};intnextj[8]={0};//记录出路的个数intexists[8]={0};inti,j,k,m,l;华东交通大学理工学院课程设计报告第8页共14页inttmpi,tmpj;intcount,min,tmp;i=x;j=y;board[i][j]=1;for(m=2;m=64;m++){for(l=0;l8;l++)exists[l]=0;l=0;//试探八个方向for(k=0;k8;k++){tmpi=i+ktmove1[k];tmpj=j+ktmove2[k];//如果是边界了，不可走if(tmpi0||tmpj0||tmpi7||tmpj7)continue;//如果这个方向可走，记录下来if(board[tmpi][tmpj]==0){nexti[l]=tmpi;nextj[l]=tmpj;//可走的方向加一个l++;}}count=l;//如果可走的方向为0个，返回if(count==0){return0;}elseif(count==1){//只有一个可走的方向//所以直接是最少出路的方向min=0;}else{//找出下一个位置的出路数for(l=0;lcount;l++){for(k=0;k8;k++){华东交通大学理工学院课程设计报告第9页共14页tmpi=nexti[l]+ktmove1[k];tmpj=nextj[l]+ktmove2[k];if(tmpi0||tmpj0||tmpi7||tmpj7){continue;}if(board[tmpi][tmpj]==0)exists[l]++;}}tmp=exists[0];min=0;//从可走的方向中寻找最少出路的方向for(l=1;lcount;l++){if(exists[l]tmp){tmp=exists[l];min=l;}}}//走最少出路的方向i=nexti[min];j=nextj[min];board[i][j]=m;}return1;}4.2程序编译图4-1程序编译图华东交通大学理工学院课程设计报告第10页共14页4.3程序运行使用visualC++进行调试成功，程序的运行如下图：图4-2程序运行图4.4运行结果程序运行结果如下：华东交通大学理工学院课程设计报告第11页共14页图4-3程序结果图图4-4程序结果图华东交通大学理工学院课程设计报告第12页共14页图4-5程序结果图4.5时间复杂度分析巡游子函数时间复杂度O(N)华东交通大学理工学院课程设计报告第13页共14页第五章课程设计心得该程序本来采用递归函数，后来发现运行很慢，后来在小组同学的讨论下决定不用递归，通过参考不少程序才完成此次实验的，在实验的过程中加深了对回溯法的算法思想的理解。骑士巡游的实验研究，有对此不明白到对骑士巡游有了深入的认识。通过查询资料，了解了不同，各种各样求解骑士巡游的方法。在编写与调试程序的过程中，遇到了许多没有想到过的问题，通过一个个问题的解决，既熟悉了C语言与调试技术，又熟悉了骑士巡游的关键步骤。在与他人合作的过程中，体会到了合作的重要性。本次课程设计使我有了很大的收获。华东交通大学理工学院课程设计报告第14页共14页第六章参考文献（资料）[1]谢希仁.计算机网络（第五版）[M].北京：电子工业出版社，2008年2月[2]胡小强计算机网络[M]北京：北京邮电大学出版社2005年1月[3]严蔚敏数据结构（C语言版）[M]北京：人民邮电出版社2011年2月[4]李丽娟C语言程序设计教程（第二版）[M]北京：人民邮电出版社2009年3月