马踏棋盘课程设计实验报告

《数据结构》课程设计报告课程名称：《数据结构》课程设计课程设计题目：姓名：院系：专业：年级：学号：指导教师：2011年月日目录1、程序设计的目的2、设计题目3、分析4、设计思想5、算法6、测试结果7、调试分析8、小结1、课程设计的目的1、熟练使用C++语言编写程序，解决实际问题；2、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；3、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；4、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；5、学习并熟悉栈的有关操作；6、利用栈实现实际问题；2、设计题目【马踏棋盘】*问题描述：将马随机放在国际象棋的8X8棋盘Bo阿rd[0..7,0..7]的某个方格中，马按走棋规则进行移动。

要求每个方格上只进入一次，走遍棋盘上全部64个方格。

编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入8X8的方阵输出之。

*测试数据：由读者指定,可自行指定一个马的初始位置。

*实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。

并探讨每次选择位置的“最佳策略”，以减少回溯的次数。

3、分析确定输入值的范围，输入马的初始行坐标X和Y，X和Y的范围都是1到8之间。

程序的功能是输出马走的步骤，要使马从任一起点出发，通过程序能找到下一个地点，然后遍历整个棋盘。

每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。

并探讨每次选择位置的“最佳策略”，以减少回溯的次数。

输出时可以用二维数组。

4、设计思想输入马初始位置的坐标。

将初始位置进栈，经过一个while循环，取出符合条件的栈顶元素。

利用函数，找出栈顶元素周围未被占用的新位置，如果有，新位置入栈；否则弹出栈顶元素。

四，实验内容与步骤
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
int x;
int y; //棋盘上的坐标
}Coordinate;
int chessboard[8][8];; //棋盘
int curstep; //马跳的步骤序号
Coordinate fangxiang[8]= //马可走的方向
桂林电子科技大学
数学与计算科学学院综合性、设计性实验报告
实验室：06406实验日期：2015年05月29日
院（系）
信息与计算科学系
年级、专业、班
1300710226
姓名
庞文正
成绩
课程
名称
数据结构实验
实验项目
名 称
马踏棋盘问题
指导
教师
教师
评语
教师签名：
年 月 日
一 ，实验目的
加深对图的理解，培养解决实际问题的编程能力。根据数据对象的特性，学会数据组织的方
19（4，4）
20（5，4）
11（1，3）
12（2，3）
13（3，3）
14（4，3）
15（5，3）
6（1，2）
7（2，2）
8（3，2）
9（4，2）
10（5，2）
1（1，1）
2（2，1）
3（3，1）
பைடு நூலகம்4（4，1）
5（5，1）
综合起来，马踏棋盘问题就可以转化为图的遍历问题。
三，使用仪器，材料
XP系统电脑一台，vc++软件！
{
printf("输入数值越界，请重新输入！\n");

一、实习背景马踏棋盘问题是一个经典的算法问题，也是数据结构课程中的一个重要实验。

通过对马踏棋盘问题的研究和实现，可以加深对栈和队列这两种抽象数据类型的理解，提高算法设计能力和编程能力。

本次实习旨在通过编程实现马踏棋盘问题，并分析其算法的复杂度和优化策略。

二、实习目的1. 理解马踏棋盘问题的背景和意义；2. 掌握栈和队列的应用，以及它们在解决实际问题中的作用；3. 提高算法设计能力和编程能力；4. 分析马踏棋盘问题的算法复杂度，并尝试优化算法。

三、实习内容1. 马踏棋盘问题介绍马踏棋盘问题是指在8x8的国际象棋棋盘上，将一匹马随机放在棋盘上的一个位置，然后按照国际象棋的走法，即“日”字形移动，使得马能够走遍棋盘上的所有方格。

要求使用非递归的方式实现。

2. 栈和队列的应用在解决马踏棋盘问题时，我们可以使用栈来存储马走过的路径，使用队列来实现广度优先搜索（BFS）策略，以寻找马的所有可能走法。

3. 算法实现（1）初始化棋盘和路径栈首先，我们需要初始化一个8x8的二维数组来表示棋盘，并将起始位置设置为（0，0）。

同时，创建一个栈来存储马走过的路径。

（2）定义马的移动规则根据国际象棋的规则，马可以走到以下八个位置之一：（-2，-1），（-2，1），（-1，-2），（-1，2），（1，-2），（1，2），（2，-1），（2，1）在实现时，我们需要判断这些位置是否在棋盘范围内，以及是否已经走过。

（3）广度优先搜索使用队列来实现广度优先搜索策略，从起始位置开始，按照BFS的顺序，依次尝试马的所有可能走法。

每走一步，就将新的位置压入栈中，并更新队列。

（4）输出结果当队列中所有位置都尝试过一遍后，栈中的路径即为马的行走路线。

按照路径输出棋盘上的数字，即可得到最终结果。

4. 算法优化为了提高算法的效率，我们可以考虑以下优化策略：（1）使用邻接矩阵来表示棋盘，减少重复计算；（2）在遍历队列时，优先考虑距离起始位置较近的位置；（3）在遍历过程中，避免重复访问已经访问过的位置。

马踏棋盘一目的1、巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解。

2、掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）。

3、提高利用计算机分析解决综合性实际问题的基本能力。

4、加强对基础知识的运用，做到学以致用。

5、二需求分析1、从键盘输入马起始的横坐标x和纵坐标y，其范围都是0-7。

2、马按走棋规则进行移动，要求每个方格只进入一次，走遍棋盘上全部64个方格。

3、一般说来，当马位于位置（i,j）时，可以走到下列8个位置之一（ x-2,y+1）,(x-1,y+2),(x+1,y+2),(x+2,y+1),(x+2,y-1)(x+1,y-2),(x-1,y-2),(x-2,y-1)4、求出马的行走路线，将数字1到64依次填入一个8X8的方阵，输出到文本中（文本中能清楚看到方阵）。

输出的形式；（1）以数组下标形式输入，代表起始位置，i表示行标，j表示列标。

（2）以棋盘形式输出，每一格打印马走的步数，这种方式比较直观。

3、程序所能达到的功能；（1）让马从任一起点出发都能够历遍整个8×8的棋盘。

（2）能寻找多条不同的行走路径。

4．测试数据，包括正确的输入及输出结果和含有错误的输入及其输出结果。

数据可以任定，只要 0<=X<7&&0<=Y<7 就可以了。

正确的输出结果为一个2维数组，每个元素的值表示马行走的第几步。

若输入有错，程序会显示“输入错误，请重新输入:”并且要求用户重新输入数据，直至输入正确为止。

三概要设计initstack(s) //构建一个空栈。

push(s,e) //在栈顶插入新的元素。

pop（s,e）//将栈顶元素弹出。

settop(s, e) //将e设为栈顶元素。

gettop(s, e)//将栈顶元素取出。

stackempty(s) //判断栈是否为空check(int x,int y)//判断点(x,y)是否在棋盘内weighting()//求棋盘中每一点的权值四详细设计1、名称详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详棋盘点的结构类型定义typedef struct{int x;该点的横坐标int y;该点的纵坐标int z;}elemtype;栈的类型定义typedef struct SNode{elemtype data;struct SNode *next;}SNode,*Linkstack;栈的初始化操作int initstack(Linkstack &s){s=(Linkstack)malloc(sizeof(SNode));if(!s){printf("初始化失败！");return 0;}s->next=NULL;return 1;}入栈操作int push(Linkstack &s,elemtype e){Linkstack p;p=(Linkstack)malloc(sizeof(SNode));if(!p) return 0;p->next=s->next;s->next=p;p->data=e;return 1;}出栈操作int pop(Linkstack &s,elemtype &e) {Linkstack p=s->next;if(p==NULL) return 0;s->next=p->next;e=p->data;free(p);return 1;}取栈顶元素操作gettop(Linkstack &s,elemtype &e) {Linkstack p=s->next;if(p==NULL) return 0;e=p->data;return 1;}判断栈是否为空操作int stackempty(Linkstack s){int flag=0;if(s->next==NULL)flag=1;return flag;}设为栈顶元素操作int settop(Linkstack &s,elemtype e) {if(s->next!=NULL){s->next->data=e;return 1;}else return 0;}void setmap(){int i,j,k,m,d1,d2,x1,x2,y1,y2,l1,l2; for(i=0;i<N;i++)//for 1{for(j=0;j<N;j++)//for 2{for(k=0;k<8;k++)map[i][j][k]=k;//默认8个方向顺时针赋值for(k=0;k<8;k++)//for 3 与 for 4 两个循环对方向索引按点的权值升序排列，不能到达的方向排在最后{for(m=k+1;m<8;m++) //for 4{d1=map[i][j][k];x1=i+HTry1[d1];y1=j+HTry2[d1];d2=map[i][j][m];x2=i+HTry1[d2];y2=j+HTry2[d2];l1=check(x1,y1);l2=check(x2,y2);if((l1==0&&l2)||(l1&&l2&&(weight[x1][y1]>weight[x2][y2]))){map[i][j][k]=d2;map[i][j][m]=d1; //交换两个方向值,按权值递增排列,不可到达的目标点(超出棋盘)的方向放在最后面}//end if}//end for 4}//end for 3}//end for 2}//end for 1}//end setmap()void path(int xx, int yy){ int c[N*N]={0},h[N*N]={0};Linkstack a;elemtype ptemp;elemtype pop_temp,get_temp;elemtype p,dest_p; //当前点和目标点int step=0,x,y,s,k=1,l=1,d =0;char ch;p.x = xx; p.y = yy;p.z = 0;//初始化出发点board[xx][yy]=1;initstack(a);push(a,p); //起始点的坐标和首选方向入栈while(1){if (step==63){output(a);exit(1);}if(stackempty(a)) break;gettop(a,p);x=p.x; y=p.y; d=p.z;if(d>=8)//该点所有方向已走完，退栈{board[x][y]=0; //抹去痕迹step--; //步数减一pop(a,pop_temp); //退栈gettop(a,get_temp); //取当前栈顶元素ptemp.x=get_temp.x;ptemp.y=get_temp.y;ptemp.z=get_temp.z+1;settop(a,ptemp); //更改方向gettop(a,p);} //end if (d>=8)if(d<8)//方向未走完{s=map[x][y][d];//map[x][y][0]未必是(x,y)点的HTry[0]方向,而是到该点可到的权值最小的点的方向即HTry[map[x][y][0]dest_p.x=x+HTry1[s];dest_p.y=y+HTry2[s];if(check(dest_p.x,dest_p.y)&&board[dest_p.x][dest_p.y]==0)//目标点在棋盘内且未被走过,则将目标点入栈同时标记当前点为已走过{h[step]=step;board[x][y]=1;step++;//步数加一dest_p.z=0;push(a,dest_p);//存入目标点,方向栈初始}else//目标点已被走过或目标点不在棋盘内,换方向{ //printf(" 进行");ptemp.x=p.x;ptemp.y=p.y;ptemp.z=d+1;//取下一个方向 settop(a,ptemp);//切换方向// gettop(a,p);//gettop(a,p);//x=p.x; y=p.y; d=p.z;检测重新将d赋值//printf("%d %d %d",x,y,d);}} //enf if(d<8)//printf("步数%d\n ",step);} //end while(1)}void output(Linkstack a){ Linkstack b;int c[8][8]={0},i,j,k=N*N,l=1,x,y;initstack(b);elemtype e;while(!stackempty(a)){pop(a,e);c[e.x][e.y]=k;k--;push(b,e);}gettop(b,e);x=e.x;y=e.y;printf("起始坐标:(%d,%d)\n",x,y);while(!stackempty(b)){ pop(b,e);printf("(%d,%d)",e.x,e.y);push(a,e);}printf("棋盘表示为：\n");for(i=0;i<8;i++){for(j=0;j<8;j++){printf("%2d",c[i][j]);printf(" ");if(j==7) printf("\n");}}}五调试分析1、设计gettop函数时误将栈顶元素取出，原因是多加了一条s->next=p->next语句，造成不应有的错误2、写settop(s)函数时，忘记了s仅为头结点误将e赋值给了s->data,而实际上应为s->next->data=e;由此造成的错误极难发现，这也进一步说明了基础知识的重要。

马踏棋盘实习报告题目：设计一个国际象棋的马踏遍棋盘的演示程序班级：姓名：学号：完成日期：一．需求分析将马随机放在m*n棋盘Board[m][n]的某个方格中，马按国际象棋行棋的规则进行移动。

要求每个方格只行走一次，走遍棋盘上全部m*n个方格。

编写非递归程序，求出马的行走路线，并按求出的行走路线，将数字1, 2, . m*n依次填入-一个m*n的方阵中。

程序要求：在国际象棋8×8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。

编制程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，并输出它的行走路线。

输入：任意一个起始位置；输出：无重复踏遍棋盘的结果，以数字1-64表示行走路线。

二．概要设计棋盘可用二维数组表示，马踏棋盘问题可采用回溯法解题。

当马位于棋盘某-位置时，它有唯一坐标，根据国际象棋的规则，它 6 7有8个方向可跳，对每一方向逐探测，从中选择可行方向继续行棋，每一行棋坐标借助栈记录。

若8个方向均不可行则借助栈回溯，在前一位置选择下一可行方向继续行棋，直至跳足m*n步，此时成功的走步记录在栈中。

或不断回湖直至栈空失败。

关于栈的抽象数据类型定义:否则返回ERRORPushStack( &s,SElemType e);操作结果：插入元素e为新的栈顶元素PopStack (&s,SElemType &e);操作结果：若栈不空，则删除s的栈顶元素，并用e返回其值，并返回OK；否则返回ERROR本程序包含以下模块：主程序模块：void main(){定义变量；接受命令；处理命令；退出；}起始坐标函数模块——马儿在棋盘上的起始位置；搜索路径函数模块——马儿每个方向进行尝试，直到试完整个棋盘；输出路径函数模块——输出马儿行走的路径模块调用关系：函数调用关系：三．详细设计#define OK 1#define TRUE 1#define ERROR 0#define FALSE 0#define M 8#define N 8int direction[2][9]={{0,-2,-1,1,2,2,1,-1,-2},{0,1,2,2,1,-1,-2,-2,-1}}; //增量数组int pow[M][N];int check[M][N],next[M][N]; //创建棋盘，初始为0struct Element //数据域{int x,y; //x行,y列int d; //下一步的方向};typedef struct LStack //链栈}*PLStack;typedef struct check //定义棋盘内点的坐标{int x;int y;}Check;/*************栈函数****************/ int InitStack(PLStack &S)//构造空栈{S=NULL;return OK;}int StackEmpty(PLStack S)//判断栈是否为空{if(S==NULL)return OK;elsereturn FALSE;}int Push(PLStack &S, Element e)//元素入栈PLStack p;p=(PLStack)malloc(sizeof(LStack));p->data=e;p->next=S;S=p;return OK;}int Pop(PLStack &S,Element &e) //元素出栈{PLStack p;if(!StackEmpty(S)){e=S->data;p=S;S=S->next;free(p);return OK;}/********贪心权值函数********/void Printf(int p[M][N]){ //打印权值数组for(int i=0;i<M;i++){for(int j=0;j<N;j++)printf(" %2d ",p[i][j]);printf("\n");}}void InitWeight(){ //创建权值数组并初始化每个位置的权值for(int i=0;i<M;i++)for(int j=0;j<N;j++)pow[i][j]=0;for(int i=0;i<M;i++){for(int j=0;j<N;j++){for(int dir=1;dir<=8;dir++){int x1=i+direction[0][dir];int y1=j+direction[1][dir];if(x1>=0&&x1<=7&&y1>=0&&y1<=7)pow[i][j]++;}}}}void SetWeight(int x,int y) { //位置（x,y）设置为被占用时，修改权值数组,被占用时为9pow[x][y]=9;for(int dir=1;dir<=8;dir++){int x1=x+direction[0][dir];int y1=y+direction[1][dir];if(x1>=0&&x1<=7&&y1>=0&&y1<=7&& pow[x1][y1]!=9)pow[x1][y1]--;}}void UnSetWeight(int x,int y){ //位置（x,y）设置为未占用时，修改权值数组for(int dir=1;dir<=8;dir++){ int x1=x+direction[0][dir];struct Element t,data;int pow_min=9;for(int dir=1;dir<=8;dir++){ //探测下一步可走的方向int x1=x+direction[0][dir];int y1=y+direction[1][dir];if(x1>=0&&x1<=7&&y1>=0&&y1<=7&& pow[x1][y1]!=9){if(pow_min>pow[x1][y1])//找出下一步位置中权值最小的{pow_min=pow[x1][y1];t.d=dir; //上一步的方向t.x=x1;t.y=y1;}}}data.x=x; //入栈data.y=y;data.d=t.d;Push(H,data);x=t.x; //坐标更新y=t.y;i++; //步数增加}PLStack H;InitStack(H);Check start;printf("请输入起始坐标x y：");scanf("%d%d",&start.x,&start.y);Step(start,H);Printf(check);return 0;}四．调试分析1.刚开始的时候并没有采用贪心算法，时间复杂度很大，探测量也很大。

个人自我介绍简单大方
很抱歉，但我无法为您提供____字的自我介绍。

以下是一个简洁而大方的自我介绍示例，供您参考：
大家好，我叫[姓名]。

很高兴有机会向大家介绍一下自己。

我出生并长大在[所在地]，是一个勤奋、积极向上的人。

在学业方面，我于[毕业时间]从[学校名称]获得了[学位/专业]学位。

在大学期间，我通过自我努力和课外学习，取得了良好的学术成绩，并参与了一些学生组织和社团活动。

这些经历不仅培养了我的团队合作和领导能力，也加强了我的沟通和组织能力。

在工作方面，我有[工作年限]年的相关工作经验。

我曾在[公司/组织名称]担任[职位]，负责[工作职责]。

在这期间，我不断努力提升自己的专业知识和技能，以适应快速发展的工作环境。

我善于分析问题并找出解决方案，能够有效地与团队合作并承担责任，这些都为我赢得了同事和上级的认可。

除了工作，我也积极参与志愿者活动，希望能为社区和弱势群体做一点贡献。

我相信，通过奉献和关心他人，我们可以建立一个更加和谐和温暖的社会。

在个人生活中，我喜欢阅读、旅行和运动。

阅读扩展了我的视野，旅行让我能够体验不同的文化和风景，而运动则让我保持健康和积极的精神状态。

此外，我也很喜欢与家人和朋友相处，分享彼此的喜怒哀乐。

总的来说，我是一个热情、乐观、有责任心的人。

我相信勤奋和坚持可以取得成功，而真诚和善良可以赢得他人的信任和支持。

我希望能够在您的团队中发挥我的才能，并与大家一同成长和进步。

这就是我简单的自我介绍，谢谢大家！。

马踏棋盘问题摘要：马踏棋盘就是在国际象棋8X8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。

理解栈的“后进先出”的特性以及学会使用回溯。

关键字：马踏棋盘、递归、栈、回溯1．引言马踏棋盘就是在国际象棋8X8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。

编制程序，求出马的行走路线，并按求出的行走路线，将数字1，2….64依次填入一个8X8的方阵，并输出它的行走路线。

输入：任意一个起始位置；输出：无重复踏遍棋盘的结果，以数字1-64表示行走路线。

2．需求分析（1）需要输出一个8X8的棋盘，可以采用二维数组的方法实现。

（2）输入马的起始位置，必须保证输入的数字在规定范围内，即0<=X<=7,0<=Y<=7。

（3）保证马能走遍整个棋盘，并且不重复。

（4）在棋盘上输出马的行走路线,标记好数字1、2、3直到64。

3．数据结构设计采用栈数组为存储结构。

#define maxsize 100struct{int i;int j;int director;}stack[maxsize];4．算法设计4.1 马的起始坐标void location(int x,int y) //马的位置坐标的初始化{top++;stack[top].i=x; //起始位置的横坐标进栈stack[top].j=y; //起始位置的竖坐标进栈stack[top].director=-1;a[x][y]=top+1; //标记棋盘Try(x,y); //探寻的马的行走路线}4.2 路径探寻函数void Try(int i,int j){ int count,find,min,director;int i1,j1,h,k,s;intb[8]={-2,-2,-1,1,2,2,1,-1},c[8]={1,-1,-2,-2,-1,1,2,2};//存储马各个出口相对当前位置行、列坐标的增量数组int b2[8],b1[8];for(h=0;h<=7;h++)//用数组b1[8]记录当前位置的下一个位置的可行路径的条数{ count=0;i=stack[top].i+c[h];j=stack[top].j+b[h];if(i>=0&&i<=7&&j>=0&&j<=7&&a[i][j]==0)//如果找到下一个位置{for(k=0;k<=7;k++){i1=i+c[k];j1=j+b[k];if(i1>=0&&i1<=7&&j1>=0&&j1<=7&&a[i1][j1]==0) //如果找到下一个位置count++; //记录条数}b1[h]=count; //将条数存入b1[8]中}}for(h=0;h<=7;h++)//根据可行路径条数的大小，从小到大排序，并放入数组b2[8]中{min=9;for(k=0;k<=7;k++)if(min>b1[k]){min=b1[k];b2[h]=k;s=k;}b1[s]=9;}find=0;director=stack[top].director;for(h=director+1;h<=7;h++)//向8个方向进行寻找{i=stack[top].i+c[b2[h]];j=stack[top].j+b[b2[h]];if(i>=0&&i<=7&&j>=0&&j<=7&&a[i][j]==0){stack[top].director=h; //存储栈的寻找方向top++; //进栈stack[top].i=i;stack[top].j=j;stack[top].director=-1;//重新初始化下一栈的方向a[i][j]=top+1;find=1; //找到下一位置break;}}if(find!=1){a[stack[top].i][stack[top].j]=0; //清除棋盘的标记top--; //退栈}if(top<63)Try(i,j); //递归}4.3输出函数void display(){int i,j;for(i=0;i<=7;i++){ for(j=0;j<=7;j++)printf("\t%d ",a[i][j]); //输出马的行走路线printf("\n\n");}printf("\n");}5.程序实现5.1 主函数void main(){int i,j,x,y;for(i=0;i<=7;i++) //棋盘的初始化for(j=0;j<=7;j++)a[i][j]=0;printf("输入X Y (0=<X<=7,0=<Y<=7)\n");scanf("%d%d",&x,&y);if(x>=0&&x<=7&&y>=0&&y<=7)//判断输入的起始位子是否正确{location(x,y);display();}else printf("错误\n");}5.2运行结果（1）当输入不符合要求时（2）正确输入时5.3 算法分析（1）马的起始坐标一开始先建立一个栈数组，里面包括横坐标和竖坐标还有方向。

2.4题马踏棋盘题目：设计一个国际象棋的马踏棋盘的演示程序班级：：学号：完成日期：一．需求分析（1）输入的形式和输入值的围：输入马的初始行坐标X和列坐标Y，X和Y的围都是[1,8]。

（2）输出形式：以数组下表的形式输入，i为行标，j为列标，用空格符号隔开。

以棋盘形式输出，每一格打印马走的步数，这种方式比较直观（3）程序所能达到的功能：让马从任意起点出发都能够遍历整个8*8的棋盘。

（4）测试数据，包括正确输入及输出结果和含有错误的输入及其输出结果。

数据可以任定，只要1<=x,y<=8就可以了。

正确的输出结果为一个二维数组，每个元素的值表示马行走的第几步，若输入有错，则程序会显示：“输入有误！请重新输入……”并且要求用户重新输入数据，直至输入正确为止。

二．概要设计（1）、位置的存储表示方式（2） typedef struct {int x;int y;int from;}Point;（2）、栈的存储方式#define STACKSIZE 70#define STACKINCREASE 10typedef struct Stack {Point *top;Point *base;int stacksize;};（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为空栈，则返回TRUE，否则返回FALSE。

马踏棋盘课程设计实验报告《数据结构》课程设计实验报告课程名称: 《数据结构》课程设计课程设计题目: 马踏棋盘姓名: 邱可昉院系: 计算机学院专业: 计算机科学与技术班级: 10052313 学号: 10051319 指导老师: 王立波2012年5月18日1目录1.课程设计的目的...............................................................3 2.问题分析........................................................................3 3.课程设计报告内容 (3)(1)概要设计 (3)(2)详细设计 (3)(3)测试结果 (5)(4)程序清单...............................................................6 4.个人小结 (10)21.课程设计的目的《数据结构》是计算机软件的一门基础课程，计算机科学各领域及有关的应用软件都要用到各种类型的数据结构。

学好数据结构对掌握实际编程能力是很有帮助的。

为了学好《数据结构》，必须编写一些在特定数据结构上的算法，通过上机调试，才能更好地掌握各种数据结构及其特点，同时提高解决计算机应用实际问题的能力。

2.问题分析*问题描述:将马随机放在国际象棋的8X8棋盘Bo阿rd[0..7,0..7]的某个方格中，马按走棋规则进行移动。

要求每个方格上只进入一次，走遍棋盘上全部64个方格。

编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入8X8的方阵输出之。

*测试数据:由读者指定,可自行指定一个马的初始位置。

*实现提示:每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。

并探讨每次选择位置的“最佳策略”，以减少回溯的次数。

中南民族大学数据结构课程设计报告姓名：康宇年级： 2010学号： 10061014专业：计算机科学与技术指导老师：宋中山2013年4月15日实习报告：2.4题 马踏棋盘题目：设计一个国际象棋的马踏棋盘的演示程序班级：计科一班 姓名：康宇 学号：10061014 完成日期：2013.4.15 一、需求分析1、国际象棋的马踏棋盘的功能是：将马随机放在国际象棋的N*N 棋盘board[N][N]的某个方格中，马按走棋规则进行移动。

要求每个方格只进一次，走遍棋盘上全部N*N 个方格。

编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1,2，...,N*N 依次填入一个N*N 的方阵，输出之。

2、测试数据：N 由读者指定。

马开始的位置也有读者指定（x,y ）,1<=x<=N,1<=y<=N.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 标记栈指针。

用户在输入了期盼的规格和起始坐标后，程序通过八个方向的探寻，123456输出第一个符合要求的棋盘，棋盘上显示了马每一步的位置，每一个位置只踏了一次，且踏遍棋盘。

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];用来标记棋盘。

数据结构课程设计实习报告题目：马踏棋盘（实习题 2.4 ）班级：计算机科学与技术2004 班学031010151552010号：姓游尾妹名：日期:二OO五年七月八日指导老师：李杨老师源程序结构1． 定义函数caculate （） 计算各点的权值dirctions （） 求出各点的最佳方向序列，即优先向权值小的方向，以使运行速度加快 check （int i,int j ） 检查（ i,j ）是否在棋盘内print （） 输出路径走过的序号2． 程序步骤简介（1） 计算各点的权值，方向（2） 用户输入行数和列数（3） 寻找点的八个可走方向，若所有方向都已走过，则退回前一步，并将此步 抹去，使前一步的方向发生变化。

（ 4） 确定下一步该走的方向，依次走完全部点（5） 记录每一步（6） 当步数已满时输出，根据需要可输出一条或多条路径3． 源程序描述#include "stdio.h" #define N 8int w=0; /* 第几条可走路径 */int way1[8]={-2,-1,1,2, 2, 1,-1,-2};int way2[8]={ 1,2, 2,1,-1,-2,-2,-1}; /*在( i,j )位置处的 8 个可能走的位置 */ int ch[N*N]={0}; /*走过的相应的点的赋值 */int a[N*N+1][3]={0}; /* 路径所经过点的记录 */int dir[N][N][8];/* ( i,j )点的八个可能走的方向 */ int st=1; /* 走过的步数 *//* 每个点的权值 *//* 计算各点的权值 */ 求出各点的最佳方向序列，即优先向权值小的方向 /* 输出路径走过的序号 */ /* /*检查（i,j ）是否在棋盘内*/ 计算各点的权值，将权值存在 weight[i][j] 中*//*int i,j,k;for(i=1;i<=N;i++)for(j=1;j<=N;j++) for(k=0;k<N;k++)char c='y'; int weight[N][N]; void caculate(); voiddirctions(); voidprint(); intcheck(int i,int j);void caculate() { */int x,y;x=i+way1[k];y=j+way2[k]; /* 下一步走的点 */if(x>=1&&x<=N&&y>=1&&y<=N)weight[i-1][j-1]++; /*权值 */ }}int check(int i,int j) /*检查 (i,j) 是否在棋盘内，在返回 1，不在返回 {if(i<1||i>8||j<1||j>8)return 0;return 1;}void directions() /* 求出各点的最佳方向序列，即优先向权值小的方向 {int i,j,k,m,n1,n2,x1,y1,x2,y2,way_1,way_2; for(i=0;i<N;i++)0*/ */ for(j=0;j<N;j++){ for(k=0;k<8;k++)dir[i][j][k]=k; for(k=0;k<8;k++) for(m=k+1;m<8;m++) { way_1=dir[i][j][k]; x1=i+way1[way_1];y1=j+way2[way_1];way_2=dir[i][j][m]; x2=i+way1[way_2];y2=j+way2[way_2];n1=check(x1+1,y1+1); n2=check(x2+1,y2+1);{/* 对每个方向考察看有没有更好的*//*k 方向时的下一个点 *//*m 方向时的下一个点 *//*判断 n1,n2 是否在棋盘内*/if(( n1==0 && n2)||( n1 && n2&&weight[x1][y1]>weight[x2][y2])) 到，而 m 方向可达到 */ || /*都可达到，但 m 方向权值小 *//*k 方向不可达 { dir[i][j][k]=way_2;dir[i][j][m]=w ay_1; 即权值小的一步) *//* 交换两个方向值，将 k 走更好的一步棋 }}void print() /* 输出路径走过的序号 */ {int x,y;printf("\n - %d answer --- \n",++w); for(x=1;x<N+1;x++) /*输出是第 w 条路径的序号 */printf("\n");printf("\n");}printf("\nPress n to quit ,press any other key to continue.\n"); c=getchar(); /* 询问是否继 续输出结果 */}main(){int x,y,way,way0; caculate();directions();printf("Please enter the row and column of the starting point.\n");scanf("%d,%d",&a[1][0],&a[1][1]); /* 输入行数和列数 */getchar();y=a[st][1];ch[(x-1)*N+y-1]=0; /* 将这一点被走过的痕迹抹去 */a[st][0]=a[st][1]=a[st][2]=0;a[st-1][2]++; /* 将上一次走的点走的方向发生变化 */st--; /* 步数减一 */}else /* 此点的八个方向未全走过，应走此方向 */{way0=a[st][2];a[st][2]++; /* 确定下次应走的方向 */ x=a[st][0];y=a[st][1]; way=dir[x-1][y-1][way0];x=a[st][0]+way1[way];y=a[st][1]+way2[way]; /* 确定按这次的方向走应走到的 x,y 坐标 */ if(x<1||y<1||x>N||y>N||ch[(x-1)*N+y-1]!=0)continue; /* 此点不满足要求 */ a[st][0]=x; a[st][1]=y;a[st][2]=0; if(st==N*N){ p rint(); /* 标记这一点*//* 步数已满 *//* 输出结果 */if(c=='n')break; a[st][0]=a[st][1]=a[st][2]=0;a[st-1][2]++;}}}}二、 程序运行结果 for(y=1;y<N+1;y++)printf("%2d ",ch[(x-1)*N+y-1]); x=a[1][0],y=a[1][1];ch[(x-1)*N+y-1]=1; while(1){if(a[1][2]>=8)break; if(a[st][2]>=8) { x=a[st][0]; /*在 ch 数组中对相应点赋值，即输出时用到的各点的顺序号/* 出发点的八个方向都已走过，表示所有的方法均已找出 此点的八个方向都已走过，应该退回到上一次走的点 */ */ */ ch[(x-1)*N+y-1]=++st; /* 走到这一点 */ch[(x-1)*N+y-1]=0;例如：输入数值为2，3 时，并且要求输入第2条路径（只按回车键即可）Please enter the row and column of the starting point.2，3---- 1 answer --2 29 54 15 12 31 56 1753 14 1 30 55 16 11 3228 3 52 13 64 61 18 5751 46 63 60 39 58 33 104 27 50 45 62 37 40 1949 24 47 38 59 44 9 3426 5 22 43 36 7 20 4123 48 25 6 21 42 35 8Press n to quit ,press any other key to continue.---- 2 answer --2 29 54 15 12 31 60 1753 14 1 30 55 16 11 3228 3 52 13 64 61 18 5951 46 63 56 39 58 33 104 27 50 45 62 37 40 1949 24 47 38 57 44 9 3426 5 22 43 36 7 20 4123 48 25 6 21 42 35 8Press n to quit ,press any other key to continue.。

数据结构课程设计-马踏棋盘目录1 前言 (1)2 需求分析 (1)2.1 任务和要求 (1)2.2 运行环境 (1)2.3 开发工具 (1)3 分析和设计 (1)3.1 系统分析及设计思路 (1)3.2 主要数据结构及算法 (2)3.3 函数流程图 (2)4 具体代码实现 (10)5 课程设计总结 (17)5.1 程序运行结果 (17)5.2 设计结论 (17)参考文献 (20)致谢 (20)1 前言编写一个C语言程序，作为国际象棋中的马踏遍棋盘的演示程序。

在这里，我们用一个main函数通过调用其他一些分功能函数来实现求并且输出马踏遍棋盘的行走路线。

2 需求分析2.1 任务和要求将马随机放在国际象棋的8×8棋盘的某个方格中，马按照走棋的规则进行移动。

每个方格只进入一次，走遍棋盘的全部64个方格。

编写算法，求出马的行走路线，并按求出的行走路线，将1,2,…,64依次填入一个8×8的方阵，并输出。

要求：画出算法的流程图，分析算法的时间复杂度。

2.2 运行环境（1）WINDOWS2000/XP系统（2）Visual C++ 6.0编译环境或TC编译环境2.3 开发工具C语言3 分析和设计3.1 系统分析及设计思路根据需求分析可知，我们所设计的程序要达到让马从任意一起点出发都不重复地遍历所有的8×8棋格的功能。

按照需求，并考虑到程序的可读性，我们按顺序共设计了以下六大模块：(1)定义头文件和宏定义模块：这是C程序必不可少的一个部分，通过头文件来调用程序所需库函数，而通过宏定义进行宏替换。

(2) 数据类型定义模块：该模块定义了全局数据结构，它们的作用域为从定义开始到本源文件结束，以便于让后面很多函数都可以用到它们，而不必再重新定义。

(3) 探寻路径函数模块：按照马的行走规则对棋盘进行遍历，寻找马的行走路径，每次仅访问一个棋格，保证每个棋格都访问到且每个棋格仅访问一次。

(4) 输出路径函数模块：对探寻路径函数模块中保存下来的顺序进行输出，输出格式按照棋盘8×8的方阵格式。

生 容 易 下 手 ，容 易 通 过 对 已学 理 论 举 一 反 三 ，进 行 求 解 。 传 统 的马 踏 棋 盘 问题 采 用 的 回 溯 法 或 者 贪 心 法 求 解 ， 学 生 学 完 了数 据 结 构 课 程 ，用 此 类 方 法 求 解 仍 具 有 一 定 难 度 。 就 其 原 因 ， 学 生 对 数 据 结构 的 理 论 知 识 不 能 灵 活 运 用 以及 相
总第 １ ４卷 １ ７期 ５ ２１ ０ ２年 ９月
大 众 科 技
Ｐ ｕａｒ ｉｎ ｅ ＆ Ｔｅ ｈ ｏｏ ｙ ｏｐ ｌ ｅ ｃ Ｓｃ ｃ ｎ ｌｇ
Ｖｏ ． ４ Ｎ０ ９ Ｌ１ ．
Ｓｅ ｔ ｐｅｍｂ ｒ ２ １ ｅ ０ ２
马踏 棋 盘
一 个 数 据 结构 综 合 实验 案 例 新解
知从 何 下 手 ，产 生 畏 难 心 理 ，会 打 击 学 生解 决 问题 的 自信 心 ；
而 案 例 过 于 简 单 ， 则 达 不 到 综 合 实验 要 求 ，起 不 到锻 炼 学 生 的 目的 。一 个 合 适 的 综 合 实 验 案 例 ，应 该具 有 以 下几 个 特 点 ：
课程打 下坚 实的基础 。然而 ， 数据 结构也是一门理论性很强 的课程 ，理论 知识抽象 、概 念多 、算法 多而杂 ，学 生不好理 解 ，设 计程序无 从下手 。很 多学生反 映这 门课 “ 难懂 、不好 用 ”。学生不通 过实践很难对其 理论有深入 理解和应用 。因
Ａｂ ｔ ａ ｔ Ｉ ｈ ｓｐ ｐ ｒ ｔ ｅｐ ｏ ｌｍ ｆ ｏ ｓ ｒ ｖ ｌ ｇ ｏ ｈ ｓ ｂ ａｄ ｗａ ｎ ｒ ｄ ｃ ｄ ｉ ｔ ａ ａ ｓ ｕ ｔ ｒ ｘ ｅ ｍｅ ｔ ｅ ｃ ｉ ｇ ａ ｎ ｓ ｒ ｃ ： ｎ ｔ ｉ ａ ｅ ， ｈ ｒ ｂ ｅ ｏ ｒ ｅｔａ ｅｉ ｎ ｃ ｅ ｓ ｏ ｒ ｓｉ ｔｏ ｕ ｅ ｎ ｏ ｄ ｔ ｔ ｃ ｕ ｅｅ ｐ ｒ ｈ ｎ ｒ ｉ ｎ ａ ｈ ｎ ｓａ ｔ

马踏棋盘c++课程设计1．问题描述设计一个国际象棋的马踏棋盘的演示程序2．需求分析(1)将马随即放在国际象棋的8×8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。

要求每个方格只进入一次，走遍棋盘上全部64个方格。

(2)编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1,2,……,64依次填入一个8×8的方阵，输出之。

(3)程序执行命令为：1)输入起始方格坐标(X,Y)2)求解第一组路径并显示,按Q键退出系统，按其他任意键求解并显示下一组路径。

(4)测试数据:(0,0),(1,2)3概要设计3.1[程序设计思路].按照顺时针顺序，每次产生一个新的路点，并验证此路点的可用性，需要考虑的问题包括是否超出棋盘和此点已经走过与否。

如新路点可用，则入栈，并执行下一步，每次按照上一路点的位置生成新路点。

如一个路点的可扩展路点数为0，则走不下去了，进行回溯。

3.2[存储结构设计]8个可能位置可以用两个一维数组表示：数组1： 0 1 2 3 4 5 6 7-2 -1 1 1221-1 -2数组2：0 1 2 3 4 5 6 71 2 2 1 -1 -2 -2 -1位于（i,j）的马可以走到的新位置是在棋盘范围内的（I+数组1[h],j+数组2[h]）,其中h=0，1，…7。

每次在多个可走位置中选择其中一个进行试探，其中未曾试探过的可走位置用适当栈结构妥善管理，也备试探失败时的“回溯”（悔棋）使用，即用栈结构存储试探的路径来进行路径试探操作。

3.3[主要算法设计]3.3.1栈类的定义和接口:templateclass MyStack{private:Type *bottom; // 元素存放的动态数组int size,ptr; // 堆栈大小和当前栈顶元素索引inline int extent(){…}; //当栈满时,自动扩充public://构造函数MyStack() {bottom=new Type[BASESIZE];ptr=-1;size=BASESIZE;};//用默认大小初始化MyStack(int i) {bottom=new Type[i];ptr=-1;size=i;}; //用指定大小初始化//析构函数~MyStack(){if(bottom!=NULL) delete []bottom;};//清栈inline void clear(){…};//判栈空inline bool IsEmpty(){…};//入栈int push(Type e);//出栈int pop(Type &e);//获得栈顶元素int top(Type &e);//直接修改栈定元素int settop(Type e);// 用callback函数对栈从栈底向上遍历void traverse(void callback(Type *),Type *); };3.3.2本程序的结构1)主程序模块:void main(){初始化；向屏幕输出输入提示；接受输入起始坐标(X,Y)；输出第一组解的路径和回溯情况；while(1){接受命令；处理命令{if(命令==退出)退出；其他命令{输出下一组解的路径及回溯情况；}}}异常处理{}；正常退出；}2)路径求解模块---求解所有可行的路径3)可行路径求解的核心算法:bool Result(int start_x, int start_y, int board[][8]){初始化路径栈sPath;初始化方向栈sDir;初始化当前步数序号和当前方向step = 1, d = 0将点(start_x,start_y)入路径栈,将该点方向d入方向栈；while(1){将当前的路径栈中点出栈并保存，将该点方向出栈并保存；//为上一次的目标点和目标方向if(方向=>8){ 抹去该点痕迹；步数序号-1；调用MyStack的traverse函数演示退栈情况；退栈；方向栈中的方向++；continue;}if(方向<8)//方向未走完{if(目标点在棋盘内且未被走过){ 记录序号，目标点入栈，目标点方向初始为0入栈；continue;}else(目标点已被走过或目标点不在棋盘内){方向++；continue;//继续}}//enf if(d<8)if (步数序号已满){向屏幕输出路径if（查看下一路径）{回退一步；方向++；continue;}}} //end while(1)}3.4[测试用例设计]依次输入（0，0）（1，2）4详细设计4.1堆栈类MyStack参见文件base 中MyStack模板类的定义和实现。

1：实验题目：马踏棋盘，2：实验目的：队列和栈的操作练习：3：实验具体内容：设计一个国际象棋的马踏遍棋盘的演示程序。

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

要求每个方格只进入一次，走遍棋盘上全部64个方格。

编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1,2,…,64依次填入一个8x8的方阵，输出之。

矚慫润厲钐瘗睞枥庑赖賃軔。

4：数据结构算法思想：数据结构：简单的结构体和相关数组；算法思想：a :首先定义一个8*8的数组用于存放马的跳步过程；定义方向结点；b :获得马的第一个踩入点，调用findway()函数，该函数的while()语句将获得下一个要踩入的结点坐标，该过程调用pathnum()函数（注解：该函数给出了可踩入的所有结点各自的路径数目）; 在findway()中，选择的要进入的下一个结点就是在pathway()中找到的结点（注解：该结点是可跳入的所有结的中路径最少的一个）；聞創沟燴鐺險爱氇谴净祸測。

c : 在每步踩入前，将该结点的下标和踩入的次序做记录并输出；d : 读取最后一个结点的相关信息；5：模块划分：6：详细设计及运行结果：A：定义一个8*8的数组，用于存放每次踩入的结点位置；B：获取第一个踩入点；C：调用findway()函数Findway() 函数功能介绍：定义一个结点类型数组，用于存放8个下一步可踩入结点的信息；期间调用pathnum() 函数，该函数功能是记录所有下一个可踩入结点的可执行路径数目）；选择下一个结点中路径最少的结点为下一个踩入的结点；在进入下一个踩入点前，先保存该结点的信息并输出，然后依次寻找下一个结点；残骛楼諍锩瀨濟溆塹籟婭骒。

D：寻找最后一个结点，并赋给相应信息；运行结果如下：7：调试情况，设计技巧和相关方法：A : 该开始想着利用栈的数据结构，记录回溯的相关信息，后来查资料发现如果每次入结点路径最少的那个结点，根本不会产生回溯的过程，后来就省去了栈队列的应用；酽锕极額閉镇桧猪訣锥顧荭。

马踏棋盘课程设计摘要一、课程目标知识目标：使学生掌握“马踏棋盘”问题中的基本算法原理，理解程序设计的顺序、选择和循环结构，掌握利用算法解决实际问题的方法。

技能目标：培养学生运用所学算法知识解决“马踏棋盘”问题的能力，提高学生的逻辑思维和编程技能，使其能独立编写并优化程序代码。

情感态度价值观目标：激发学生对计算机科学的兴趣，培养他们面对问题积极思考、勇于挑战的精神，增强团队协作意识，认识到合作解决问题的重要性。

课程性质：本课程以算法与程序设计为核心，结合实际操作，注重培养学生的动手能力和解决问题的能力。

学生特点：五年级学生已具备一定的逻辑思维能力和计算机操作技能，对新鲜事物充满好奇心，但需进一步引导和培养。

教学要求：结合学生特点，采用任务驱动教学法，引导学生自主探究、合作学习，实现课程目标。

将目标分解为具体学习成果，如：学生能独立编写“马踏棋盘”程序，并在课堂上展示和分享成果，以便进行教学评估。

二、教学内容本课程以《信息技术》教材中“算法与程序设计”章节为基础，结合“马踏棋盘”问题进行教学。

具体内容包括：1. 算法原理：介绍“马踏棋盘”问题的背景和基本算法原理，如贪心算法、回溯算法等。

2. 程序设计结构：回顾顺序、选择和循环结构，引导学生运用这些结构编写程序解决“马踏棋盘”问题。

3. 编程实践：指导学生使用编程软件（如Scratch或Python等）进行“马踏棋盘”程序编写和调试。

4. 算法优化：探讨优化算法的方法，如剪枝策略，提高程序的效率和性能。

教学大纲安排如下：第一课时：导入“马踏棋盘”问题，介绍算法原理，让学生了解课程目标。

第二课时：复习程序设计结构，引导学生思考如何运用这些结构解决问题。

第三课时：分组讨论，每组制定解决方案，开始编写程序。

第四课时：展示学生成果，互相评价，教师点评和指导，优化算法。

第五课时：总结课程，让学生分享学习心得，巩固所学知识。

教学内容与教材紧密关联，注重实践操作，旨在提高学生的编程能力和问题解决能力。