《数据结构》
实验报告
课程名称： 《数据结构》
课程设计题目： 马踏棋盘
姓名： 柳煜颖
系别： 计算机
学号： 10051319
20##年10月13日
1.问题分析
问题描述：将马随机放在国际象棋的8X8棋盘的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线 ，并按求出的行走路线，将数字1，2，…，64依次填入8X8的方阵输出之。
*测试数据：由读者指定,可自行指定一个马的初始位置。
*实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。
2.课程设计报告内容
（1）概要设计
定义一张棋盘，定义一个栈保存马走的路径的点坐标和来自方向，用函数计算周围可走坐标，并检查正确性，当周围没有可走格子时退栈到最优位置，继续进行，然后将路径输出。
（2）详细设计
#include <stdio.h>
#include <stdlib.h>
typedef struct { //定义结构体
int x;//横坐标
int y;//纵坐标
int dir;//方向
}Snode;
typedef struct{
Snode *base, *top;
int length;
}SqStack;
char board[9][9] = {0};//数组归零
*/栈用来存放坐标/*
void InitStack(SqStack *S){
S->top=S->base = (Snode *)malloc(100 * sizeof(Snode));
S->length = 0;
return;
}//InitStack
void Push(SqStack *S, Snode e){
*(S->top++) = e;
S->length++;
return;
}//Push
void Pop(SqStack *S, Snode *e){
*e=*(--S->top);
S->length--;
return;
}//Pop
int check(Snode e, int i, int j){
if ((e.x + i > 0) && (e.x + i<9) && (e.y + j>0) && (e.y + j <9) && (board[e.x + i][ e.y + j] == 0))
return 1;
else return 0;
}//check检查八个方向
void doit(SqStack *S, Snode *e,int i, int j,int status){
e->dir=status+1;
Push(S, *e);
board[e->x][e->y] = S->length;
e->x += i; e->y += j; e->dir = 0;
return;
}//do it
void output(SqStack *S){
int i, j;
for (i = 1; i < 9; i++){
for (j = 1; j < 9; j++)
if (board[i][j] < 10) printf(" %d ", board[i][j]);
else printf("%d ", board[i][j]);
putchar(10);
}//循环
putchar(10);
}//output
void search(SqStack *S){
Snode e;
scanf("%d %d", &e.x, &e.y);
e.dir = 0;
while (S->length < 63){
switch (e.dir){
case 0:if (check(e,-2,-1)){
doit(S, &e, -2, -1,0);
break;
}
case 1:if (check(e,-2,1)){
doit(S, &e, -2, 1,1);
break;
}
case 2:if (check(e, -1, -2)){
doit(S, &e, -1, -2,2);
break;
}
case 3:if (check(e, -1, 2)){
doit(S, &e, -1, 2,3);
break;
}
case 4:if (check(e, 1, -2)){
doit(S, &e, 1, -2,4);
break;
}
case 5:if (check(e, 1, 2)){
doit(S, &e, 1, 2,5);
break;
}
case 6:if (check(e, 2, -1)){
doit(S, &e, 2, -1,6);
break;
}
case 7:if (check(e, 2, 1)){
doit(S, &e, 2,1,7);
break;
}
default:Pop(S, &e); board[e.x][e.y] = 0;
}
if (S->length == 63) board[e.x][e.y] = 64;
}
}//检查八个方向 如果存在 且为零 则走到该方向 并且停止上一步检查 开始重新检查
如果不为零或不存在 则检查下一方向 直到能走
*/主函数/*
int main()
{
SqStack *S;
S = (SqStack *)malloc(sizeof(SqStack));
InitStack(S);
search(S);
output(S);
}
（3）测试结果
3.个人小结
这是第二次写数据结构课程设计的代码，相对于第一次的生疏，这次已经能比较熟练地知晓题目应该如何编写的框架了，但具体实现的想法还是在网络中寻找了思路，然后写出了代码，一开始调试时一直出错，结果是自己在很多细节出现了错误，这导致了我一直无法运行起程序，后来在自习检查代码后发现了这一点，由此看出，数据结构编写程序不仅要对学习的只是能够灵活运用在编写代码的时候还要仔细仔细再仔细。
我要在以后的学习中注意以下几点：
1.认真上好专业课，多在实践中锻炼自己。
2.写程序要考虑周到，严密。
3.在做设计的时候要有信心，有耐心，不浮躁。
4.认真学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。
5.在课余时间多写程序，熟练掌握在调试程序过程中常见的错误，一边节约调试程序的时间。
第二篇：马踏棋盘实验报告单(含代码)
计算机学院
《数据结构》课程设计报告
课题名称： 马踏棋盘
课题负责人（学号/姓名）： 黎贵涛 110520121
同组成员名单（姓名）： 刘伟 110520131
林建彪 110520104
指导教师： 孔令寅
评阅成绩：
评阅意见：
提交报告时间：20##年12月9日
项目成员
一、【问题描述】
设计一个国际象棋的马踏棋盘的演示过程。
基本要求:
将马随机放在国际象棋的8*8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动，要求每个方格只进行一次，走遍整个棋盘的全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8*8的方阵，输出之。
测试数据：可自行制定一个马的初始位置（i，j），0<=I,j<=7。
二、【实验目的】
1、对数据结构基本理论和存储结构及算法设计有更深入的理解；
2、了解栈的特性，以便在实际问题背景下灵活运用他们；
3、提高在世纪设计操作中系统分析、结构确定、算法选择、数学建模和信息加工的能力。
三、【设计过程】
第1步：实现提示
一般来说，当马位于位置（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) （图-1）
但是，如果（i，j）靠近棋盘的边缘，上述有些位置可能要超出棋盘位置，成为不允许的位置。8个可能位置可以用一位数组HTry1[0…7]和HTry2[0…7]来表示：
0 1 2 3 4 5 6 7
（表-2）
位于（i，j）的马可以走到新位置是在棋盘范围内的（i+HTry1[h],j+HTry2[h]），其中h=0…7。
第2步：需求分析
（1） 输入的形式和输入值的范围：输入马的初始行坐标X和列坐标Y，X和Y的范围都是[1,8]。
（2） 输出形式：
以数组下表的形式输入，i为行标，j为列标，用空格符号隔开。
以棋盘形式输出，每一格打印马走的步数，这种方式比较直观
（3） 程序所能达到的功能：让马从任意起点出发都能够遍历整个8*8的棋盘。
（4） 测试数据，包括正确输入及输出结果和含有错误的输入及其输出结果。数据可以任定，只要1<=x,y<=8就可以了。
正确的输出结果为一个二维数组，每个元素的值表示马行走的第几步，若输入有错，则程序会显示：“输入有误！请重新输入……”并且要求用户重新输入数据，直至输入正确为止。
第3步，算法设计思想：
1、输入马所在初始位置的坐标值，考虑到用户的输入习惯，此处1<=x，y<=8；
2、将输入的初始值进栈；
3、设置一个while循环，循环条件为count<64；
4、取出栈顶元素；
5、定义flag标志变量的值；
6、按照setpossible函数顺时针顺序优先原则，找栈顶元素周围未被占用 的新位置。
7、若存在该位置，则令order的值等于该新位置的坐标，并入栈；
8、否则弹出栈顶元素；
9、再次回到第③步while循环进行判断；
10、输出一个8*8的方阵，所示数字即为相应步骤。
第4步，算法框图：
第5步，存储结构设计：
（1）、位置的存储表示方式
typedef struct
{
int x;
int y;
int from;
}Point;
（2）、栈的存储方式
#define STACKSIZE 70
#define STACKINCREASE 10
typedef struct Stack
{
Point *top;
Point *base;
int stacksize;
};
第6步，设计功能分析与实现
（1）、设定栈的抽象数据类型定义：
ADT Stack {
数据对象：D=｛ai | ai∈ElemSet,i=1,2,…,n,n≥0｝
数据关系：R1={<ai-1 , ai>|ai-1, ai∈D,i=2,…,n}
约定an端为栈顶，ai端为栈顶。
基本操作：
InitStack(&s)
操作结果：构造一个空栈s，
DestroyStack(&s)
初始条件：栈s已存在。
操作结果：栈s被销毁。
ClearStack(&s)
初始条件：栈s已存在。
操作结果：栈s清为空栈。
StackEmpty(&s)
初始条件：栈s已存在。
操作结果：若栈s为空栈，则返回OK，否则返回ERROR。
StackLength(s);
初始条件：栈s存在。
操作结果：返回s的元素个数，即栈的长度。
GetTop (s,&e);
初始条件：栈s已存在且非空。
操作结果：用e返回s的栈顶元素。
Push(&s,e)
初始条件：栈s已存在。
操作结果：插入元素e为新的栈顶元素。
DeleteTop(&s,&e)
初始条件：栈s存在且非空。
操作结果：删除栈顶元素，并用e返回。
GetDeep(s)
初始条件：栈s存在。
操作结果：返回一个int型的整数表示栈深。
stackTraverse(s,visit())
初始条件：栈s存在且非空。
操作结果：从栈底到栈顶依次对s的每个元素调用visit()。一旦visit()失败，则操作失败。
}ADT Stack
（2）、选取对该程序有用的函数。
1、InitStack(&s)
用于构建空栈实现相应的操作；
2、StackEmpty(&s)
用于判断空栈情况，已确保循环体能够准确实现；
3、GetTop (s,&e)
用于取放入栈的栈顶元素，实现把放入的横纵坐标按要求取出；
4、Push(&s,e)
用于将用户输入的横纵坐标放入栈；
5、DeleteTop(&s,&e)
用于实现将要求取出的元素取出；
6、GetDeep()
用于获取栈的深度；
7、DestroyStack()
用于销毁栈。
（3）、主要函数及算法说明。
1、函数：void setpossible(Point cur)
参数：Point cur
功能：找出当前位置下一步的八个位置，将其赋给g_round[8];
算法：接受参数传来的值，按顺时针次序加上
g_round[i].x={-2,-1,1,2,2,1,-1,-2};
g_round[i].y={1,2,2,1,-1,-2,-2,-1};
再根据getpossible函数来判断是否合法；若合法则返回OK,否则返回ERROR.
2、函数：Status getpossible(int i,Point &pt)
参数：int i,Point &pt
功能：将所在位置周围八个位置坐标赋予指针变量，并判断其合理性；
算法：用以下赋值语句
pt.x=g_round[i-1].x;
pt.y=g_round[i-1].y;
将现在周围8个指定位置赋予指针变量pt，并用
if(pt.x<0||pt.y<0||pt.x>7||pt.y>7)
条件语句判断其合理性，若合理则返回OK，否则返回ERROR.
3、语句：for(int i=cur.from+1;i<=8;i++)
{
if(getpossible(i,next)&&order[next.x][next.y]==0)
{
语句……
}
}
功能：按照顺时针优先规则，选出下一个可用的位置，通过if判断语句来判断所选的下一步是否可用，若可用，则使其进栈，否则运行下面一个语句。
4、语句：if(flag==NULL)
{
语句…..
while(j<p && GetDeep(herseVisit)>1)
{
语句…..
}
}
功能：如果当前位置不存在任何新路径，则根据while循环进行退栈，直至退到存在有最佳位置的坐标。但必须保证栈不为空。所以此出栈中设定了int GetDeep的基本操作，就是防止空栈还继续弹东西出来的情况发生。
四、【调试程序】
（1）、问题：语法错误
原因：首次运行语法错误比较多，一般都是由于粗心大意输入有误造成的，还有一些错误属于变量忘记定义之类的，经过认真一个一个调试后这类错误得以解决。下图为第一次运行时的错误
（2）、问题：运行后突然停止程序
原因：可能是输出不恰当
解决：此问题出现后，刚开始不知道为啥，看了很多遍程序就是找不出原由，于是后来请教同学，一起研究后无意中改了输出格式，将printf("%s,%2d ",'|',order[i][j]);改成了printf("%d,%f ",order[i][j],'|');竟然成功输出了。怀疑是%s使用得不恰当。
下图为修改前的运行结果：
（3）、问题：将上述问题解决后虽然不会出现程序突然终止的情况，但运行结果如下图，输出结果很乱；
原因：输出格式不符
解决：将printf("%d,%f ",order[i][j],'|');改成printf("| %2d ",order[i][j]);
(4)、 问题：上述问题都搞定后，输入初始坐标后按下Enter键后不会出现棋盘
原因：main()函数里flag写成int flage ；
解决： 将int flage改成flag
(5)、问题：上述问题都搞定后，输入初始坐标后按下Enter键后会出现棋盘，但是在棋盘上 会
出现0 0 0 0的情况，与需要的结果不符。
原因：regular.h 文件里面获得合理位置的边界位置判定，横坐标和纵坐标的范围少写了ps.x>7||ps.y<0。
解决：在regular.h文件里面添加横坐标和纵坐标的范围ps.x>7||ps.y<0
（6）、问题：上述问题都搞定后，输入初始坐标后按下Enter键后立即退出了
原因：main()函数里有scanf()，当用户输入初始坐标后，将这两个坐标赋予给&begin.x,&begin.y，结果当用户想用Enter键进行确认操作后，Enter本身是一个字符，而这个字符不符合循环要求，所以直接退出
解决：多加一个getchar()把Enter键给吸收掉，结果如下图：
五、【用户手册】
1、 运行程序，程序开始界面，如图所示：
2、输入初始值x, y，如输入（3, 7），如图所示：
3、因为（3, 7）在（1~8）的范围内，所以程序输出结果如下:
按（y/Y）后，程序将跳到输入初始值位置，如图所示：
按其他任意键后（如按（n/N）键），将退出程序，如图所示：
4、若输入的初始值没在（1~8）的范围内，如输入（7, 9），则将提示错误，并要求重新输入，如图所示：
按任意键后，程序将跳回输入初始值的位置，如图所示：
六、【实验总结与体会】
总结：马踏棋盘，作为一种经典的栈的应用例子，从大方面将，刚看到这名字就知道用栈来实现，但是，当你面对这个题目，打开编译器之后想写的时候，发现又不是那么容易，很多细节需要认真的分析，比如结构体的定义，棋子因为是二维的，所以对于用来存储棋盘的横纵坐标，需要用到两个变量，定义两整型变量x,y。刚开始只定义了这两个变量，后来发现如果找到下一个位置，而下一个位置有很多个都是符合的，如何选取最优的呢？最有的有可能是最先找到的，可找到后还得继续找下去，万一没有比他更优的，则要退回来，如果没有变量from来记录前一位置最优位置，就无法找到之前的点，所以要多加一个变量；其外就是程序的调试，调试确实需要很大的耐心，有时候只是你的大意而输错了字符或输入输出格式不符合就会出现很多看起来不可思议很难发现的错误，这也说明了编程的时候一定要认真有耐心。
体会：刚学习栈的时候，觉得并不太难，反正就是先进后出，可是到了实际运用的时候，才发现学到的理论知识要用到实际去还真是个问题，通过这次课程设计的实践，让我对栈有了更深入的理解，也发现一种理论再简单的知识，如果不实际运用一下，对于你的掌握肯定是不够的，因为实际运用中你要适当选取哪些是有用的，哪些不必用到的，而且当你很兴奋的写完代码后，会发现很多错误，当然一般是语法错误，如果你的逻辑没错的话，也有可能是你思想没错，但你的表达不妥当，这也会让你对程序的修改显得很无助；再次，世上没有完美的程序，如今社会上出现的各个软件每到一定的时候就会有升级版也正是这个原因，我承认自己这个程序存在很多漏洞和不足，但一个程序的优化可不是一朝一夕的事，只要求自己能完成基本任务就行了。
七、【参考文献】
《数据结构（C语言版）》--------严蔚敏、吴伟民 编著
《C语言设计（第三版）》--------谭浩强 著
《C语言课程设计（第2版）》-------梁旭、谷晓琳、黄明 编著
《C语言通用范例金典》-------柳盛，王国全，沈永林 编著
八、【程序清单】
1.文件horse.h
#ifndef __HORSE_H__
#define __HORSE_H__
#include<stdio.h>
#include<malloc.h>
#define OK 1
#define ERROR 0
#define STACKSIZE 70
#define STACKINCREASE 10
typedef int Status;
//位置的储存
typedef struct
{
int x;
int y;
int from;
}Point;
//栈的储存
typedef struct
{
Point *top;
Point *base;
int stacksize;
}Stack;
//建栈
Status Initstack(Stack &s)
{
s.base=(Point*)malloc(STACKSIZE*sizeof(Point));
if(s.base==NULL)return ERROR;
s.top=s.base;
s.stacksize=STACKSIZE;
return OK;
}
//向栈中插入元素e
Status Push(Stack &s,Point e)
{
if(s.top-s.base>=s.stacksize)
{
s.base=(Point*)realloc(s.base,
(s.stacksize+STACKINCREASE)*sizeof(Point));
if(s.base==NULL)return ERROR;
s.top=s.base+s.stacksize;
s.stacksize+=STACKINCREASE;
}
(*s.top).x=e.x;
(*s.top).y=e.y;
(*s.top).from=e.from;
s.top++;
return OK;
}
//栈不为空，则删除栈顶元素
Status DeleteTop(Stack &s,Point &e)
{
if(s.top==s.base)return ERROR;
s.top--;
e.x=(*s.top).x;
e.y=(*s.top).y;
e.from=(*s.top).from;
return OK;
}
//销毁栈
Status DestroyStack(Stack &s)
{
free(s.base);//free(s);
return OK;
}
//判断栈是否为空
Status StackEmpty(Stack s)
{
if(s.base==s.top)return OK;
else return ERROR;
}
//获得栈顶元素
Status GetTop(Stack s,Point &e)
{
if(s.base==s.top)return ERROR;
e.x=(*(s.top-1)).x;
e.y=(*(s.top-1)).y;
e.from=(*(s.top-1)).from;
return OK;
}
//获得栈的深度
int GetDeep(Stack s)
{
return s.top-s.base;
}
#endif
2.文件regular.h
#ifndef __REGULAR_H__
#define __REGULAR_H__
#include"horse.h"
Point h_possible[8]={0,0,0};
//查找所有可能的位置，并存入h_possible[8]中
void setPossible(Point con)
{
Point round[]=
{
{con.x-2,con.y+1,0},
{con.x-1,con.y+2,0},
{con.x+1,con.y+2,0},
{con.x+2,con.y+1,0},
{con.x+2,con.y-1,0},
{con.x+1,con.y-2,0},
{con.x-1,con.y-2,0},
{con.x-2,con.y-1,0}
};
for(int i=0;i<8;i++)
{
h_possible[i].x=round[i].x;
h_possible[i].y=round[i].y;
h_possible[i].from=round[i].from;
}
}
//取得合理的可能位置
Status getPossible(int i,Point &ps)
{
ps.x=h_possible[i-1].x;
ps.y=h_possible[i-1].y;
if(ps.x<0||ps.y>7||ps.x>7||ps.y<0)return ERROR;
else return OK;
}
#endif
3.主函数main.c
#include<stdio.h>
#include<stdlib.h>
#include"horse.h"
#include"regular.h"
void main()
{
int i,j,p;
int s=1;
char yn;
Stack horseVisit;
Point cur,next;
H1:while(s)
{
int order[8][8]={0};//是一个中间变量，用来记录当前位置
int count=0;
Point begin;
system("color 31");
printf("<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<马踏棋盘程序演示>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n");
printf("请输入马在棋盘上的任意初始位置x，y，根据用户习惯，其中x,y为（~8），例如（7）：");
scanf("%d%d",&begin.x,&begin.y);
printf("\n================================================================================\n");
begin.from=0;
while(begin.x>8||begin.y>8||begin.x<1||begin.y<1)
{
system("cls");
printf("<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<输入格式不对，请重新输入...>>>>>>>>>>>>>>>>>>>\n");
getchar();
getchar();
system("cls");
goto H1;
}
getchar();
begin.x--;//注意用户输入的坐标（~8），而储存是（~7），这里要自减
begin.y--;
Initstack(horseVisit);//创建空栈
Push(horseVisit,begin);//入栈，将用户输入的坐标存入栈中
count++;//计数器加
order[begin.x][begin.y]=count;
while(count<64)
{
GetTop(horseVisit,cur);//取栈顶元素存入cur中
setPossible(cur);//找出位置附近可能的八个位置
int flag=false;//标志
for(int i=cur.from+1;i<=8;i++)
{
//按照顺时针的顺序，选出下一个可走的新位置
if(getPossible(i,next)&&order[next.x][next.y]==0)//next是下一个位置，这里表示下一个位置未被占领
{
flag = true;//代表成功
count++;//位置可用，计数器加
order[next.x][next.y]=count;//在新的位置上显示当前步数
DeleteTop(horseVisit,cur);//删除栈顶元素，并将其放入cur中
//特别注意，这里不用GetTop(s,&e)是因为s不是引用，不能改变栈顶元素的值
//DeleteTop（&s,&e）可以通过修改e来更新栈顶元素的from值
cur.from = i;//八个可能位置中的第i个位置
Push(horseVisit,cur);//再把原来的栈顶元素重新入栈（这里i更新了）
next.from=0;//下一个位置的from归零
Push(horseVisit,next);//下一个合法位置入栈
break;//跳出
}
//重复循环
}
if(flag==NULL)
{
//如果当前位置周围没有可以走的位置，则退栈，直退到存在最佳位置的坐标
j=0;
if(begin.x==2&&begin.y==6)
p=4;//退步
else
p=5;//退步
while(j<p&&GetDeep(horseVisit)>1)
{
DeleteTop(horseVisit,cur);//退栈
order[cur.x][cur.y]=0;//该位置归零
count--;//计数器减
j++;
}
}
}
DestroyStack(horseVisit);//完成后销毁栈
printf("\n 棋盘演示\n");
printf(" 1 2 3 4 5 6 7 8\n");
printf(" +---+---+---+---+---+---+---+---+\n");
for(i=0;i<8;i++)
{
printf(" ");
printf("%2d",i+1);
for(j=0;j<8;j++)
{
printf("|%2d ",order[i][j]);
}
printf("|\n");
if(i==7)
printf(" +---+---+---+---+---+---+---+---+");
else
printf(" +---+---+---+---+---+---+---+---+");
printf("\n");
}
printf("你是否需要继续运行该程序（'Y'或'y'继续，按其他任意键退出：）");
scanf("%c",&yn);
printf("\n");
if(yn=='Y'||yn=='y')
{
s=1;
}
else
{
s=0;
system("cls");
printf("=========================谢谢使用===========================\n\n\n\n");
system("PAUSE");
}
system("cls");
}
}