数据结构—马踏棋盘

目 录

1 前言...........................................................................................................................................................1

2 需求分析...................................................................................................................................................1

2.1 任务和要求....................................................................................................................................1

2.2 运行环境........................................................................................................................................1

2.3 开发工具........................................................................................................................................1

3 分析和设计...............................................................................................................................................1

3.1 系统分析及设计思路....................................................................................................................1

参考文献....................................................................................................................................................18

致 谢...........................................................................................................................................................18

1 前言

编写一个 C 语言程序，作为国际象棋中的马踏遍棋盘的演示程序。在这里，我

们用一个 main 函数通过调用其他一些分功能函数来实现求并且输出马踏遍棋盘的行

走路线。

2 需求分析

2.1 任务和要求

将马随机放在国际象棋的 8×8 棋盘的某个方格中，马按照走棋的规则进行移动。

每个方格只进入一次，走遍棋盘的全部 64 个方格。编写算法，求出马的行走路线，

C 语言

3 分析和设计

3.1 系统分析及设计思路

根据需求分析可知，我们所设计的程序要达到让马从任意一起点出发都不重复

地遍历所有的 8×8 棋格的功能。按照需求，并考虑到程序的可读性，我们按顺序共

设计了以下六大模块：

(1) 定义头文件和宏定义模块：这是 C 程序必不可少的一个部分，通过头文件

来调用程序所需库函数，而通过宏定义进行宏替换。

(2) 数据类型定义模块：该模块定义了全局数据结构，它们的作用域为从定义

开始到本源文件结束，以便于让后面很多函数都可以用到它们，而不必再重新定义。

探寻路径函数和输出路径函数达到预期效果。

(6) 主程序模块：主要是完成棋盘初始化，输入，调用等任务进而来完成马踏

棋盘问题。

另外，一般来说，当马位于（i,j）时，可以走下列 8 个位置之一：

（i-2,j+1) (i-1,j+2) (i+1,j+2) (i+2,j+1)

(i+2,j-1) (i+1,j-2) (i-1,j-2) (i-2,j-1) 这 8 个可能的位置可以用两个一维数组

存放，利用一维数组表示马在棋盘内新位置。但是，如果 (x,y)靠近棋盘的边缘，上

述位置可能超出棋盘范围，成为不允许的位置。

3.2 主要数据结构及算法

（1) 定义头文件和宏定义

#include<stdio.h>

#define MAXSIZE 100

#define N 8

{

int i;

int j;

int director;

}stack[MAXSIZE];

int top=-1; 这里是定义栈类型，其中 i 是横坐标，j 是纵坐标，director 是存

(3) 探寻路径函数

方向进行探寻。

(4) 输出路径函数

（5） 起始坐标函数

N

Y

N

Y

开始

i<N

J<N