骑士游历数据库课程设计.doc

存档资料 成绩：　

华东交通大学理工学院
课 程 设 计 报 告 书

所属课程名称 数据结构
题 目 　 骑士游历　　　　　　　　　 　　　
分 院 电 信 分 院 　　 　
专业班级 电子商务1班
学　　号 　 20100210460123　　　　 　　 　
学生姓名 　 何芳林　　　　 　　　
指导教师 吴军良 　　　

2012 年 6月 15 日
华东交通大学理工学院课程设计报告
目　录
第一章 课程设计内容及要求 2
第二章 功能说明 3
第三章 详细设计 4
3.1 创建 4
3.2 操作 5
3.3 显示 5
第四章 程序实现 6
4.1 源码分析 6
4.2 程序编译 9
4.3 程序运行 9
4.4 运行结果 10
4.5 时间复杂度分析 11
第五章 课程设计心得 12
第六章　参考文献（资料） 13

第一章 课程设计内容及要求

在一个棋盘上（8行8列）放一个“马”，按“马走日字”的规则，马要走到棋盘上每一个格子，且每个格子只走一次。
用回溯法深度优先搜索，若寻找到满足要求的解，则输出；否则推回上一层往下一个方向搜索。
对于当前所在位置（x，y），依次枚举8个方向搜索，直到找到一组可行解为止。使用剪枝有2处：
第一、使用Warnsdorff's rule，枚举当前解得时候优先选择下一步可行步数最少的方向；
第二、若第一点中的方向存在不止一个，则优先选择离中心位置较远的方向；每次都从中心点开始出发，求出一条合法路径后再平移映射回待求路径。

第二章 功能说明
1．创建。创建一个8行8列的棋盘。

2. 操作。 输入骑士的初始位置，进行骑士游历操作。

3. 显示。显示出游历结果。

创建
操作
骑士游历实验过程
显示
创建棋盘
进行游历
显示游历结果

图2-1 功能模块图

第三章 详细设计
3.1 创建
创建一个8行8列的棋盘：
#include <stdio.h>
int board[8][8] = {0};
int main(void) {
for(i = 0; i < 8; i++) {
for(j = 0; j < 8; j++) {
printf("%2d ", board[i][j]);
}
putchar('\n');
}
return 0;
}
3.2 操作
输入骑士的初始位置，进行骑士游历操作：
int i, j;
printf("输入起始点：");
int travel(int x, int y) {
int ktmove1[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int ktmove2[8] = {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 <stdio.h>
int board[8][8] = {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 ", board[i][j]);
}
putchar('\n');
}
return 0;
}
int travel(int x, int y) {
// 对应骑士可走的八个方向
int ktmove1[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int ktmove2[8] = {1, 2, 2, 1, -1, -2, -2, -1};
// 测试下一步的出路
int nexti[8] = {0};
int nextj[8] = {0};
// 记录出路的个数
int exists[8] = {0};
int i, j, k, m, l;
int tmpi, tmpj;
int count, min, tmp;
i = x;
j = y;
board[i][j] = 1;
for(m = 2; m <= 64; m++) {
for(l = 0; l < 8; l++)
exists[l] = 0;
l = 0;
// 试探八个方向
for(k = 0; k < 8; k++) {
tmpi = i + ktmove1[k];
tmpj = j + ktmove2[k];
// 如果是边界了，不可走
if(tmpi < 0 || tmpj < 0 || tmpi > 7 || tmpj > 7)
continue;
// 如果这个方向可走，记录下来
if(board[tmpi][tmpj] == 0) {
nexti[l] = tmpi;
nextj[l] = 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 = nexti[l] + ktmove1[k];
tmpj = nextj[l] + ktmove2[k];
if(tmpi < 0 || tmpj < 0 ||
tmpi > 7 || tmpj > 7) {
continue;
}
if(board[tmpi][tmpj] == 0)
exists[l]++;
}
}
tmp = exists[0];
min = 0;
// 从可走的方向中寻找最少出路的方向
for(l = 1; l < count; l++) {
if(exists[l] < tmp) {
tmp = exists[l];
min = l;
}
}
}
// 走最少出路的方向
i = nexti[min];
j = nextj[min];
board[i][j] = 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] 谢希仁. 计算机网络（第五版）[M]. 北京：电子工业出版社，2008年2月
[2] 胡小强 计算机网络[M] 北京：北京邮电大学出版社2005年1月
[3] 严蔚敏 数据结构（C语言版）[M]北京：人民邮电出版社2011年2月
[4] 李丽娟 C语言程序设计教程（第二版）[M] 北京：人民邮电出版社2009年3月

第 14 页 共 14 页