数据结构马踏棋盘.doc

实验二:栈和队列及其应用
题目:马踏棋盘
班级: 姓名: 学号:
问题描述
设计一个国际象棋的马踏遍棋盘的演示程序。
基本要求
将马随机放在国际象棋的8*8的棋盘Board[8][8]的某个方格中,马按走棋规则进行移动。要求每个方格只进入一次,走遍棋盘上全部64个方格。编制非递归程序,求出马的行走路线,并按求出的行走路线,将数字1,2,……,64依次填入一个8*8的方阵,输出之。
概要设计
定义头文件和预定义
#include<>
#define MAXSIZE 100
#define N 8
起始坐标函数:void InitLocation(int xi,int yi);
探寻路径函数:int TryPath(int i,int j);
输出路径函数:void Display();
主程序:void main();
详细设计

void InitLocation(int xi,int yi); //马儿在棋盘上的起始位置坐标
int TryPath(int i,int j); //马儿每个方向进行尝试,直到试完整个棋盘
void Display(); //输出马儿行走的路径
2. 起始坐标函数模块
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(); //输出马儿的行走路径
else
printf("无解");
}
3. 探寻路径函数模块
int TryPath(int i,int j)
{
int find,director,number,min; //定义几个临时变量
int i1,j1,h,k,s; //定义几个临时变量
int a[8],b1[8],b2[8],d[8]; //定义几个临时数组
while(top>-1) //栈不空时循环
{
for(h=0;h<8;h++) //用数组a[8]记录当前位置的下一个位置的可行路径的条数
{
number=0;
i=stack[top].i+Htry1[h];
j=stack[top].j+Htry2[h];
b1[h]=i;
b2[h]=j;
if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8) //如果找到下一位置
{
for(k=0;k<8;k++)
{
i1=b1[h]+Htry1[k];
j1=b2[h]+Htry2[k];
if(