数据结构课程设计报告
姓 名： 康宇
年 级： 2010
学 号：专 业：计算机科学与技术
指导老师： 宋中山
2013年4月15日
马踏棋盘
一、需求分析
1、国际象棋的马踏棋盘的功能是：
将马随机放在国际象棋的N*N棋盘board[N][N]的某个方格中，马按走棋规则进行移动。要求每个方格只进一次，走遍棋盘上全部N*N个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1,2，...,N*N依次填入一个N*N的方阵，输出之。
2、测试数据：
N由读者指定。马开始的位置也有读者指定（x,y）,1
3、实现提示：
下图显示了N为6，马位于方格（3,3），8个可能的移动位置。一般来说，马位于位置（x，y）时，可以走到下列8个位置之一。但是，如果（x,y）靠近棋盘的边缘，上述有些位置可能超出棋盘范围，成为不允许的位置。8个可能的位置可以用两个一维数组hi[0...7],hj[0...7]来表示：
1
2
3
4
5
6
二、概要设计
为实现上述程序功能，应用栈Stack[Max*Max]来表示棋盘的行和列。定义棋盘的规格N,马在下一步可以走的8个位置，hi[0...7],hj[0...7],用数组board[Max][Max]来标记棋盘，top标记栈指针。用户在输入了期盼的规格和起始坐标后，程序通过八个方向的探寻，输出第一个符合要求的棋盘，棋盘上显示了马每一步的位置，每一个位置只踏了一次，且踏遍棋盘。
1、元素类型(栈)：
struct Stack
{
int i; //行坐标
int j; //列坐标
} stack[Max][ Max];
2、建立三个全局位置数组：
int hi[8]={-2,-1,1,2,2,1,-1,-2};
int hj[8]={1,2,2,1,-1,-2,-2,-1};
用来存放下一个可能位置的横纵坐标；
int board[Max][Max];
用来标记棋盘。
3、本程序包括4个模块
1）主程序：
Void main()
{
While(1)
{
Input棋盘规格N;
Input起始位置的x；
Input起始位置的x；
If(起始位置在棋盘之内)
Break;
}
调用栈函数InitLocation(x-1,y-1)；
}
2）判断是否踏遍棋盘函数
bool Find(int i,int j)
{ while(栈不空) { if(踏遍了棋盘) { return true; } for(k=0;k
} 把各路径数按从小到大顺序排列 for(k=0;k
3) 输出函数
void Print()
{
for(i=0;i
{
for(j=0;j
{
printf("%4d",board[i][j]);
}
printf("\n");
}
}
4） 初始化栈函数
void InitLocation(int i,int j)
{
初始化栈；
If(找到了踏遍棋盘的路)
调用输出函数Print();
}
三、详细设计
#include
#define Max 20
int hi[8]={-2,-1,1,2,2,1,-1,-2};
int hj[8]={1,2,2,1,-1,-2,-2,-1};
int N;
int board[Max][Max];//标记棋盘
int top=0;//标记栈指针
struct Stack
{
int i;
int j;
}stack[Max*Max];
bool Find(int i,int j)//是否能踏遍棋盘
{
//find标记是否找到下一个位置，number标记8个位置的路径数，min标记最少的路径 int find,number,min;
int xi,yj,k,m;
int a[8],b[8];//a[]标记各位置的路径数，b[]标记由小到大的路径数对应的下标 while(top>-1)
{
if(top==N*N-1)//踏遍了棋盘
{
return true;
}
for(k=0;k
{
number=0;
i=stack[top].i+hi[k];
j=stack[top].j+hj[k];
if(board[i][j]==0&&i>=0&&i=0&&j
{
for(m=0;m
{
xi=i+hi[m];
yj=j+hj[m];
if(board[xi][yj]==0&&xi>=0&&xi=0&&yj
number++;
}
a[k]=number;
}
}
for(k=0;k
{
min=9;
for(m=0;m
{
if(a[m]
{
min=a[m];
b[k]=m;
}
}
a[b[k]]=9;
}
find=0;
for(k=0;k
{
i=stack[top].i+hi[b[k]];
j=stack[top].j+hj[b[k]];
if(board[i][j]==0&&i>=0&&i=0&&j
{
find=1;
break;
}
}
if(find)//下一步有路可走
{
top++;
stack[top].i=i;
stack[top].j=j;
board[i][j]=top+1;
}
else//下一个位置无路
{
board[stack[top].i][stack[top].j]=0;//清除棋盘的标记
top--;//倒退一步
}
}
return false;
}
void Print()//输出棋盘
{
int i,j;
for(i=0;i
{
for(j=0;j
{
printf("%4d",board[i][j]);
}
printf("\n");
}
printf("\n");
}
void InitLocation(int i,int j)//初始化栈并判断输出
{
stack[top].i=i;
stack[top].j=j;
board[i][j]=top+1;
if(Find(i,j))
Print();
}
int main()
{
int x,y;
int i,j;
printf("Input N (N*N棋盘) :");
scanf("%d",&N);
for(i=0;i
for(j=0;j
board[i][j]=0;
while(1)
{
printf("Input x (1
scanf("%d",&x);
printf("Input y (1
scanf("%d",&y);
if(x>=1&&x=1&&y
break;
printf("Your input is wrong!!!\n");
}
printf("begin with %d row, %d rol on board:\n\n",x,y);
InitLocation(x-1,y-1);
return 0;
}
四、调试分析
1.本次作业比较简单，只有一个核心算法，即求下一步该怎么走，以及是否有路可走，所以总的调试比较顺利。在调试Find算法时，遇到两个问题：一是没有考虑到马的这一步失败后的回溯，另一个是避免重复以前走过的路。
2.本程序模块简洁，在main()函数里得到充分体现；
3.用户可灵活控制棋盘的规模大小以及马踏的起始位置，本程序具有一定的通用性。
五、用户手册
1.本程序运行环境为Windows操作系统，执行文件为：mata.exe
2.进入演示程序后显示的界面：
六、测试结果
数据结构课程设计报告
姓 名： 康宇
年 级： 2010
学 号：专 业：计算机科学与技术
指导老师： 宋中山
2013年4月15日
马踏棋盘
一、需求分析
1、国际象棋的马踏棋盘的功能是：
将马随机放在国际象棋的N*N棋盘board[N][N]的某个方格中，马按走棋规则进行移动。要求每个方格只进一次，走遍棋盘上全部N*N个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1,2，...,N*N依次填入一个N*N的方阵，输出之。
2、测试数据：
N由读者指定。马开始的位置也有读者指定（x,y）,1
3、实现提示：
下图显示了N为6，马位于方格（3,3），8个可能的移动位置。一般来说，马位于位置（x，y）时，可以走到下列8个位置之一。但是，如果（x,y）靠近棋盘的边缘，上述有些位置可能超出棋盘范围，成为不允许的位置。8个可能的位置可以用两个一维数组hi[0...7],hj[0...7]来表示：
1
2
3
4
5
6
二、概要设计
为实现上述程序功能，应用栈Stack[Max*Max]来表示棋盘的行和列。定义棋盘的规格N,马在下一步可以走的8个位置，hi[0...7],hj[0...7],用数组board[Max][Max]来标记棋盘，top标记栈指针。用户在输入了期盼的规格和起始坐标后，程序通过八个方向的探寻，输出第一个符合要求的棋盘，棋盘上显示了马每一步的位置，每一个位置只踏了一次，且踏遍棋盘。
1、元素类型(栈)：
struct Stack
{
int i; //行坐标
int j; //列坐标
} stack[Max][ Max];
2、建立三个全局位置数组：
int hi[8]={-2,-1,1,2,2,1,-1,-2};
int hj[8]={1,2,2,1,-1,-2,-2,-1};
用来存放下一个可能位置的横纵坐标；
int board[Max][Max];
用来标记棋盘。
3、本程序包括4个模块
1）主程序：
Void main()
{
While(1)
{
Input棋盘规格N;
Input起始位置的x；
Input起始位置的x；
If(起始位置在棋盘之内)
Break;
}
调用栈函数InitLocation(x-1,y-1)；
}
2）判断是否踏遍棋盘函数
bool Find(int i,int j)
{ while(栈不空) { if(踏遍了棋盘) { return true; } for(k=0;k
} 把各路径数按从小到大顺序排列 for(k=0;k
3) 输出函数
void Print()
{
for(i=0;i
{
for(j=0;j
{
printf("%4d",board[i][j]);
}
printf("\n");
}
}
4） 初始化栈函数
void InitLocation(int i,int j)
{
初始化栈；
If(找到了踏遍棋盘的路)
调用输出函数Print();
}
三、详细设计
#include
#define Max 20
int hi[8]={-2,-1,1,2,2,1,-1,-2};
int hj[8]={1,2,2,1,-1,-2,-2,-1};
int N;
int board[Max][Max];//标记棋盘
int top=0;//标记栈指针
struct Stack
{
int i;
int j;
}stack[Max*Max];
bool Find(int i,int j)//是否能踏遍棋盘
{
//find标记是否找到下一个位置，number标记8个位置的路径数，min标记最少的路径 int find,number,min;
int xi,yj,k,m;
int a[8],b[8];//a[]标记各位置的路径数，b[]标记由小到大的路径数对应的下标 while(top>-1)
{
if(top==N*N-1)//踏遍了棋盘
{
return true;
}
for(k=0;k
{
number=0;
i=stack[top].i+hi[k];
j=stack[top].j+hj[k];
if(board[i][j]==0&&i>=0&&i=0&&j
{
for(m=0;m
{
xi=i+hi[m];
yj=j+hj[m];
if(board[xi][yj]==0&&xi>=0&&xi=0&&yj
number++;
}
a[k]=number;
}
}
for(k=0;k
{
min=9;
for(m=0;m
{
if(a[m]
{
min=a[m];
b[k]=m;
}
}
a[b[k]]=9;
}
find=0;
for(k=0;k
{
i=stack[top].i+hi[b[k]];
j=stack[top].j+hj[b[k]];
if(board[i][j]==0&&i>=0&&i=0&&j
{
find=1;
break;
}
}
if(find)//下一步有路可走
{
top++;
stack[top].i=i;
stack[top].j=j;
board[i][j]=top+1;
}
else//下一个位置无路
{
board[stack[top].i][stack[top].j]=0;//清除棋盘的标记
top--;//倒退一步
}
}
return false;
}
void Print()//输出棋盘
{
int i,j;
for(i=0;i
{
for(j=0;j
{
printf("%4d",board[i][j]);
}
printf("\n");
}
printf("\n");
}
void InitLocation(int i,int j)//初始化栈并判断输出
{
stack[top].i=i;
stack[top].j=j;
board[i][j]=top+1;
if(Find(i,j))
Print();
}
int main()
{
int x,y;
int i,j;
printf("Input N (N*N棋盘) :");
scanf("%d",&N);
for(i=0;i
for(j=0;j
board[i][j]=0;
while(1)
{
printf("Input x (1
scanf("%d",&x);
printf("Input y (1
scanf("%d",&y);
if(x>=1&&x=1&&y
break;
printf("Your input is wrong!!!\n");
}
printf("begin with %d row, %d rol on board:\n\n",x,y);
InitLocation(x-1,y-1);
return 0;
}
四、调试分析
1.本次作业比较简单，只有一个核心算法，即求下一步该怎么走，以及是否有路可走，所以总的调试比较顺利。在调试Find算法时，遇到两个问题：一是没有考虑到马的这一步失败后的回溯，另一个是避免重复以前走过的路。
2.本程序模块简洁，在main()函数里得到充分体现；
3.用户可灵活控制棋盘的规模大小以及马踏的起始位置，本程序具有一定的通用性。
五、用户手册
1.本程序运行环境为Windows操作系统，执行文件为：mata.exe
2.进入演示程序后显示的界面：
六、测试结果