骑士游历数据库课程设计

存档资料 成绩： 华东交通大学理工学院课 程 设 计 报 告 书所属课程名称 数据结构 题 目 骑士游历 分 院 电 信 分 院 专业班级 电子商务1班 学号 123 学生姓名 何芳林 指导教师 吴军良 2012 年 6月 15 日 目录第一章 课程设计内容及要求2第二章 功能说明3第三章 详细设计43.1 创建43.2 操作53.3 显示5第四章 程序实现64.1 源码分析64.2 程序编译94.3 程序运行94.4 运行结果104.5 时间复杂度分析11第五章 课程设计心得12第六章参考文献（资料）13第一章 课程设计内容及要求在一个棋盘上（8行8列）放一个“马”，按“马走日字”的规则，马要走到棋盘上每一个格子，且每个格子只走一次。用回溯法深度优先搜索，若寻找到满足要求的解，则输出；否则推回上一层往下一个方向搜索。对于当前所在位置（x，y），依次枚举8个方向搜索，直到找到一组可行解为止。使用剪枝有2处：第一、使用Warnsdorffs rule，枚举当前解得时候优先选择下一步可行步数最少的方向；第二、若第一点中的方向存在不止一个，则优先选择离中心位置较远的方向；每次都从中心点开始出发，求出一条合法路径后再平移映射回待求路径。第二章 功能说明1创建。创建一个8行8列的棋盘。2. 操作。 输入骑士的初始位置，进行骑士游历操作。3. 显示。显示出游历结果。创建操作骑士游历实验过程显示创建棋盘进行游历显示游历结果图2-1 功能模块图第三章 详细设计3.1 创建创建一个8行8列的棋盘：#include int board88 = 0;int main(void) for(i = 0; i 8; i+) for(j = 0; j 8; j+) printf(%2d , boardij);putchar(n);return 0;3.2 操作输入骑士的初始位置，进行骑士游历操作：int i, j;printf(输入起始点：);int travel(int x, int y) int ktmove18 = -2, -1, 1, 2, 2, 1, -1, -2;int ktmove28 = 1, 2, 2, 1, -1, -2, -2, -1;3.3 显示显示出游历结果：int startx, starty;int i, j;printf(输入起始点：);scanf(%d %d, &startx, &starty);if(travel(startx, starty) printf(游历完成！n);else printf(游历失败！n);第四章 程序实现4.1 源码分析#include int board88 = 0;int main(void) int startx, starty;int i, j;printf(输入起始点：);scanf(%d %d, &startx, &starty);if(travel(startx, starty) printf(游历完成！n);else printf(游历失败！n);for(i = 0; i 8; i+) for(j = 0; j 8; j+) printf(%2d , boardij);putchar(n);return 0;int travel(int x, int y) / 对应骑士可走的八个方向int ktmove18 = -2, -1, 1, 2, 2, 1, -1, -2;int ktmove28 = 1, 2, 2, 1, -1, -2, -2, -1;/ 测试下一步的出路int nexti8 = 0;int nextj8 = 0;/ 记录出路的个数int exists8 = 0;int i, j, k, m, l;int tmpi, tmpj;int count, min, tmp;i = x;j = y;boardij = 1;for(m = 2; m = 64; m+) for(l = 0; l 8; l+)existsl = 0;l = 0;/ 试探八个方向for(k = 0; k 8; k+) tmpi = i + ktmove1k;tmpj = j + ktmove2k;/ 如果是边界了，不可走if(tmpi 0 | tmpj 7 | tmpj 7)continue;/ 如果这个方向可走，记录下来if(boardtmpitmpj = 0) nextil = tmpi;nextjl = tmpj;/ 可走的方向加一个l+;count = l;/ 如果可走的方向为0个，返回if(count = 0) return 0;else if(count = 1) / 只有一个可走的方向/ 所以直接是最少出路的方向min = 0;else / 找出下一个位置的出路数for(l = 0; l count; l+) for(k = 0; k 8; k+) tmpi = nextil + ktmove1k;tmpj = nextjl + ktmove2k;if(tmpi 0 | tmpj 7 | tmpj 7) continue;if(boardtmpitmpj = 0)existsl+;tmp = exists0;min = 0;/ 从可走的方向中寻找最少出路的方向for(l = 1; l count; l+) if(existsl tmp) tmp = existsl;min = l;/ 走最少出路的方向i = nextimin;j = nextjmin;boardij = m;return 1;4.2 程序编译图4-1 程序编译图4.3 程序运行使用visualC+进行调试成功，程序的运行如下图：图4-2 程序运行图4.4 运行结果程序运行结果如下：图4-3 程序结果图图4-4 程序结果图图4-5 程序结果图4.5 时间复杂度分析巡游子函数时间复杂度O(N)第五章 课程设计心得该程序本来采用递归函数，后来发现运行很慢，后来在小组同学的讨论下决定不用递归，通过参考不少程序才完成此次实验的，在实验的过程中加深了对回溯法的算法思想的理解。骑士巡游的实验研究，有对此不明白到对骑士巡游有了深入的认识。通过查询资料，了解了不同，各种各样求解骑士巡游的方法。在编写与调试程序的过程中，遇到了许多没有想到过的问题，通过一个个问题的解决，既熟悉了C语言与调试技术，又熟悉了骑士巡游的关键步骤。在与他人合作的过程中，体会到了合作的重要性。本次课程设计使我有了很大的收获。第六章参考文献（资料）1