一．问题描述

设计一个国际象棋的马踏棋盘的演示程序。

基本要求：将马随机放在国际象棋 8×8 的棋盘 Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘全部的 64 个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字 1，2，3, ,64 一次填入一个 8×8 的方阵输出之。

二．实验目的

1、对数据结构基本理论和存储结构及算法设计有更加深入的理解；

2、了解栈的特性，以便在实际问题背景下灵活运用他们；

3、提高在实际设计操作中系统分析、结构确定、算法选择、数学建模和信息加工的能力。

三．程序设计

1.顺序栈的抽象数据类型定义：

ADT Stack{

数据对象：D={ai| ai∈（0，1， ，9），i=0,1，2， ，n，n≥0}

数据关系：R={< ai-1, ai >| ai-1, ai∈D,i=1,2， ，n}

} ADT Stack

2.本程序包含三个模块：

（1）主程序模块：

void main(){

定义变量；

接受命令；

处理命令；

退出；

}

（2）起始坐标函数模块——马儿在棋盘上的起始位置；

（3）探寻路径函数模块——马儿每个方向进行尝试，直到试完整个棋盘；

（4）输出路径函数模块——输出马儿行走的路径；

3.主要算法设计

主程序

马的初始位置是 否正确

是起始坐标函数

探寻路径函数

输出路径函数

结果

4.设计功能的分析和实现

（1）起始坐标函数 void InitLocation(int xi,int yi);

作用：将马的起始位置先送给栈，然后送给棋盘上的位置

（2） 探寻路径函数 int TryPath(int i,int j)

作用：用来寻找马在棋盘上的下个位置，如果没有找到，就回溯到上一个位置。

（3）输出路径函数 void Display()

作用：输出马在整个棋盘上的路径

四．调试报告

1.在调试的过程中出现的问题与解决方案

问题一：在刚开始写完程序后初次运行发现有较多错误。

原因：大多数为语法和字符错误，由于粗心大意造成的。虽然都是小错误，但在书写的过程中会无意搞错。

解决方法：根据提示的错误进行修改。直到“0 error（s），0 warning（s）”。这些错误在一定程度上说明对编写程序的不熟悉。

问题二：输入马的位置时，不能判断这个初始位置的合法性

原因：代码书写过程中未对马的位置进行限制

解决方案：对不合理的代码进行修改。对马在棋盘上的位置进行设定，并书写当马位置输入错误时的循环程序。

问题三：在未修改的程序中运行，出现运算时间很长的情况

原因：在程序的书写过程中，代码的书写不够简练，导致运行过慢

解决方案：在于同学互相沟通和交流的情况下，尽力简化代码，提升运行速度。虽然我尽力对程序进行简化，但运行速度依然不是很快。

2.对设计和编程的讨论与分析

（1）本次实验的主要目的是在于掌握和理解栈的特性和它的应用。在编制该程序中遇到了很多问题。首先，在开始刚编制程序的时候遇到的问题是，程序编译都通不过，主要在一些细节的问题上，还有在程序的返回值在刚开始时也没有正确返回。经过编译慢慢调试，编译都能通过，没有错误和警告。

（2）标记好马尝试的方向后，编译运行，但是运行结果却不符合程序所要求的结果，说明在算法上肯定有错误，检查发现，马儿走的坐标没有控制后，它的横纵坐标必须控制0到7之间，否则的话马儿就会踏出棋盘以外，这样输出的结果就不对。还有就是棋盘走过的位置要标记一下，以便下次走不重复走，当回溯的时候的记得把标记给清掉，这个地方有时候也很容易混淆。

五．源程序及实验结果

#include "stdafx.h"

#include<stdio.h>

#define MAXSIZE 100

#define N 8

int board[8][8]; //定义棋盘

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

/*存储马各个出口位置相对当前位置行下标的增量数组*/

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

/*存储马各个出口位置相对当前位置列下标的增量数组*/ struct Stack{ //定义栈类型

int i; //行坐标

int j; //列坐标

int director; //存储方向

}stack[MAXSIZE]; //定义一个栈数组

int top=-1; //栈指针

void InitLocation(int xi,int yi); //马儿在棋盘上的起始位置坐标

int TryPath(int i,int j); //马儿每个方向进行尝试，直到试完整个棋盘 void Display(); //输出马儿行走的路径

void InitLocation(int xi,int yi) //起始坐标函数

{

int x,y; //定义棋盘的横纵坐标变量

top++; //栈指针指向第一个栈首

stack[top].i=xi; //将起始位置的横坐标进栈

stack[top].j=yi; //将起始位置的纵坐标进栈

stack[top].director=-1; //将起始位置的尝试方向赋初值

board[xi][yi]=top+1; //标记棋盘

x=stack[top].i; //将起始位置的横坐标赋给棋盘的横坐标

y=stack[top].j; //将起始位置的纵坐标赋给棋盘的纵坐标

if(TryPath(x,y)) //调用马儿探寻函数，如果马儿探寻整个棋盘返回1否则返回0

Display(); //输出马儿的行走路径 …… 此处隐藏：2046字，全部文档内容请下载后查看。喜欢就下载吧 ……