c语言版数据库骑士游历

存档资料 成绩：

华东交通大学理工学院

课 程 设 计 报 告 书

所属课程名称 数据结构 题 目 骑士游历 分 院 电 信 分 院

专业班级 电子商务2班 学 号 学生姓名

指导教师 吴军良

2012 年 6月 15 日

目 录

目 录 ......................................................... 2 第1章 课程设计内容及要求 ..................................... 3

1.1课程设计的内容 .......................................... 3 1.2课程设计要求 ............................................ 3 第2章 程序设方法与分析 ....................................... 4

2.1程序设计方法 ............................................ 4 2.2程序详细分析 ............................................ 4

2.21创建棋盘 ............................................ 4 2.22分析骑士行走方法的实现 .............................. 4 2.3程序实现结构图 .......................................... 6 第3章 源程序代码 ............................................. 7 第4章 程序的测试与运行 ...................................... 10

4.1编译程序 ............................................... 10 4.2链接结果如图 ........................................... 12 4.3运行程序结果 ........................................... 13 第5章 课程设计心得 .......................................... 17 第6章 参考文献（资料） ...................................... 18

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

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

1.1课程设计的内容

在WINDOWS XP系统中，运行Visual C++ 6.0，在Visual C++ 6.0环境下，根据所学教材C语言版数据结构知识，运用C语言编写一个可以实现骑士游历的游戏程序。

1.2课程设计要求

（1）运行环境要求：

window xp 系统 Visual C++ 6.0环境 （2）骑士游历棋盘要求：

设计一个8行*8列共64格的棋盘。 （3）棋子走法要求：

放一个“马”，按“马走日字”的规则，马要走到棋盘上每一个格子，且每个格子只走一次。 （4）课程设计目的要求：

骑士游历问题是一个古老而著名的问题，它最初是由大数学家Euler提出的。我们通过在window xp系统中，Visual C++ 6.0环境下，根据数据结构所学知识运用C语言编写一个8行*8列64格，满足“马走日字”的规则的骑士游历游戏来巩固数据结构知识，对理论知识加以实践，加深对知识的理解与运用。

第 3 页 共 18 页

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

第2章 程序设方法与分析

2.1程序设计方法

2.11 用回溯法深度优先搜索，若寻找到满足要求的解，则输出；否则推回上一层往下一个方向搜索。

2.12 对于当前所在位置（x，y），依次枚举8个方向搜索，直到找到一组可行解为止。使用剪枝有2处：

（1）使用Warnsdorff's rule，枚举当前解得时候优先选择下一步可行步数最少的方向。

（2）若第一点中的方向存在不止一个，则优先选择离中心位置较远的方向；每次都从中心点开始出发，求出一条合法路径后再平移映射回待求路径。

2.2程序详细分析 2.21创建棋盘

在Visual C++ 6.0环境下运用c语言的for循环语句创写一个8行8列的棋盘。

#include int board[8][8] = {0}; for(i = 0; i < 8; i++) for(j = 0; j < 8; j++)

2.22分析骑士行走方法的实现

（1）设计骑士骑士可走的八个方向

int ktmove1[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; int ktmove2[8] = {1, 2, 2, 1, -1, -2, -2, -1};

第 4 页 共 18 页

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

（2）测试骑士下一步的行走路线 int nexti[8] = {0}; int nextj[8] = {0};

（3）试探八个方向

for(k = 0; k < 8; k++) tmpi = i + ktmove1[k]; tmpj = j + ktmove2[k];

（4）如果骑士处于边界了，则不可以行走

if(tmpi < 0 || tmpj < 0 || tmpi > 7 || tmpj > 7) continue;

（5） 如果这个方向骑士可以行走，则记录下来，在可走的方向加一个 if(board[tmpi][tmpj] == 0) nexti[l] = tmpi; nextj[l] = tmpj; l++;

count = l;

（6）如果可走的方向为0个，返回 if(count == 0) return 0;

else if(count == 1)

骑士能够走最少的路线的方向 i = nexti[min]; j = nextj[min]; board[i][j] = m;

第 5 页 共 18 页

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

2.3程序实现结构图

图2-3

程序结构图

创建棋盘 骑士实现骑士行走规则 游历运行程序

第 6 页 共 18 页

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

第3章 源程序代码

#include int board[8][8] = {0}; int main(void) {

int beginx, beginy; int i, j;

printf(\：\

scanf(\if(travel(beginx, beginy)) {

printf(\！\\n\} else {

printf(\！\\n\}

for(i = 0; i < 8; i++) {

for(j = 0; j < 8; j++) {

printf(\}

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;

第 7 页 共 18 页

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

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;

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];

第 8 页 共 18 页

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

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; }

第 9 页 共 18 页

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

第4章 程序的测试与运行

4.1编译程序

(1)如图4-1-1：

图：4-1-1

(2)发现两个错误如图4-1-2：

图：4-1-2

第 10 页 共 18 页

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

(3)分析程序 发现没有定义beginx,beginy如图4-1-3：

图：4-1-3

（4）修改程序如图4-1-4：

图 4-1 -4

第 11 页 共 18 页

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

（5）重新编译，编译结果如下图4-1-5：

图4-1-5

4.2链接结果如图：

图4-2-1

第 12 页 共 18 页

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

4.3运行程序结果

（1）输入起点为（1，1）的程序结果图如下：

图4-3-1

（2）输入起点为（2，5）的程序结果如下：

图 4-3-2

（3）输入起点为（3，5）的程序结果如下：

第 13 页 共 18 页

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

图4-3-3

（4）输入起点为（4，6）的程序结果如下：

图4-3-4

（5）输入起点为（5，7）的程序结果如下：

第 14 页 共 18 页

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

图4-3-5

（6）输入起点为（8，6）的程序结果如下：

图4-3- 6

（7）输入起点为（5，9）的程序结果如下：

第 15 页 共 18 页

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

图4-3-7

（8）输入起点为（6，10）的程序结果如下：

图4-3-8

第 16 页 共 18 页

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

第5章 课程设计心得

通过这次数据结构课程设计的学习，我学到了许多知识，尤其是在运用c语言编写骑士游历游戏程序中通过解决问题，让我的实践能力得到了提高，让我明白理论还是要靠实践才能更好的加以理解。

在编写程序中我运用了数据结构里的回溯法深度优先搜索，寻找足要求的解，若寻找到满足要求的解则输出；否则推回上一层往下一个方向搜索。同时 定义函数x，y,对于当前所在位置（x，y），依次枚举8个方向搜索，直到找到一组可行解为止。使用剪枝有2处：使用Warnsdorff's rule，枚举当前解得时候优先选择下一步可行步数最少的方向。若第一点中的方向存在不止一个，则优先选择离中心位置较远的方向；每次都从中心点开始出发，求出一条合法路径后再平移映射回待求路径。在老师的帮助下我解决了一些细节问题和一些关于回溯法上面的问题。 在两周的数据结构课程设计的学习中，在老师的帮助下和与同学之间的互相学习下明白理论结合实际操作才更有助于我们的学习，通过这次的学习，我对数据结构的知识有了更深的了解，对C语言知识也得到了巩固。

第 17 页 共 18 页

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

第6章 参考文献（资料）

[1] 谢希仁. 计算机网络（第五版）[M]. 北京：电子工业出版社，2008年2月 [2] 胡小强 计算机网络[M] 北京：北京邮电大学出版社2005年1月

[3] 严蔚敏 数据库结构（C语言版）[M]. 北京：人民邮电出版社2011年2月

第 18 页 共 18 页

本文来源：https://www.bwwdw.com/article/lk5r.html