数据结构课程设计任务书马踏棋盘：陈晨

课程设计(论文)任务书软件学院软件工程专业2009 - 5班一、课程设计(论文)题目数据结构课程设计(A)二、课程设计(论文)工作自2010 年12月27日起至2010 年12月31 日止。

三、课程设计(论文) 地点: 软件学院机房四、课程设计(论文)内容要求：1．本课程设计的目的（1）使学生熟练掌握抽象数据类型的组织和定义；（2）使学生熟练掌握数据类型的定义和实现；（3）培养学生组织和分析数据的能力；（4）培养学生分析和应用基于不同数据结构的算法的能力；（5）提高学生的科技论文写作能力。

2．基本要求：每位同学在以下题目中任选一题（在方框中打勾），独立完成课程设计：□马踏棋盘：参见《数据结构题集》P98。

3．课程设计论文编写要求（1）要按照书稿的规格打印誊写课设报告；（2）报告分为封面、任务书（本文档）、正文、课程设计体会和参考文献四部分；学生签名：年月日课程设计(论文)评审意见（1）题目分析（20分）：优（）、良（）、中（）、一般（）、差（）；（2）流程分析（30分）：优（）、良（）、中（）、一般（）、差（）；（3）数据定义（30分）：优（）、良（）、中（）、一般（）、差（）；（4）代码编写（10分）：优（）、良（）、中（）、一般（）、差（）；（5）创新能力（10分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性、设计态度及考勤是否降等级：是（）、否（）评阅人：职称：讲师年月日正文一、数据结构定义1.抽象数据类型本设计中用到的数据结构ADT定义如下：ADT Stack{数据对象：D={ ai | ai∈ElemSet，i=1，2，……，n，n≥0} 数据关系：R1={ <ai-1,ai> | ai-1,ai∈D，i=1，2，……，n } 约定an端为栈顶，a1端为栈底。

InitStack(&S)操作结果：构建一个空栈S。

StackEmpty(S)初始条件：栈S已存在。

操作结果：若栈S为空栈，则返回TURE,否则FALSE。

Push(&S，e)初始条件：栈S已存在。

操作结果：插入元素e为新的栈顶元素。

Pop（&S，&e）初始条件：栈S已存在且非空。

操作结果：删除S的栈顶元素，并用e返回其值。

}ADT Stack2.存储结构定义数据存储结构的C语言定义如下：位置存储方式typedef struct qipange {int num; //记录该格是路径中的第几步int row; //该格的横坐标int col; //该格的纵坐标int di[8]; // 记录该格的下一步（8个方向）是否走过，走过为1否则为0 }qipange;栈的存储方式typedef struct sqstack { //定义栈qipange *base; //栈底指针qipange *top; //栈顶指针int stacksize; //栈容量} sqstack;sqstack s,sp;3.基本操作数据结构的基本操作实现如下：对栈进行操作的主要函数解释如下：int initstack(sqstack &s) //栈的初始化，构造一个空栈sbool stackempty(sqstack &s) //判断栈是否为空，若为空，返回0void push(sqstack &s,qipange &q) //插入元素q为栈s中新的栈顶元素void pop(sqstack &s,qipange &q) //删除栈顶元素，用q返回其值int count(int r,int c) //count函数用以计算并返回下一步某方向可行路线的总数定义：typedef struct qipange {int num; //记录该格是路径中的第几步int row; //该格的横坐标int col; //该格的纵坐标int di[8]; // 记录该格的下一步（8个方向）是否走过，走过为1否则为0}qipange;typedef struct sqstack { //定义栈qipange *base; //栈底指针qipange *top; //栈顶指针int stacksize; //栈容量} sqstack;全局变量定义：int qipan[20][20]; //棋盘方阵，存放各点走的次序int r,c,i,j,total,n,max; //r,c分别表示横纵坐标；i，j计数；total 进入路径栈的元素个数；n是单向格数（用户输入）；max是总格数int dir[8][2]={{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}}; //定义8个方向的操作int sign[20][20]; //标记该格是否已走过，是为1，否为0二、解题过程1.问题分解该问题主要应实现以下功能：能够实现一个国际象棋的马踏棋盘的演示过程将马随机放在国际象棋n×n的棋盘的某个方格中，马按走棋规则进行移动。

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

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

需求分析以数组下标形式输入，i表示横坐标，j表示纵坐标。

以棋盘形式输出，没一格打印马走的步数，这种方式比较直观程序所能达到的功能：让马从任一起点出发都能够遍历整个n*n的棋盘测试数据，包括正确的输入及输出结果和含有错误的输入及输出结果。

数据可以任定，只要y<=n你就可以了正确的输入结果为一个2维数组，每个元素的值表示马行走的第几步。

若输入有错，则显示相应提示信息，要求用户重新输入数据，直到输入正确位置2.模块结构系统主要由4个模块组成，分别是：①求各点权值的模块②检验坐标值(i,j)是否在棋盘内模块③输出各个函数的模块④主算法函数，踏遍棋盘的算法的模块模块之间的结构如下：各模块的实现步骤为按照顺时针顺序，每次产生一个新的路点，并验证此路点的可用性，需要考虑的问题包括是否超出棋盘和此点已经走过与否。

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

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

实现#include<stdio.h>#include<stdlib.h>int qipan[20][20]; //棋盘方阵，存放各点走的次序int r,c,i,j,total,n,max; //r,c分别表示横纵坐标；i，j计数；total 进入路径栈的元素个数；n是单向格数（用户输入）；max是总格数typedef struct qipange {int num; //记录该格是路径中的第几步int row; //该格的横坐标int col; //该格的纵坐标int di[8]; // 记录该格的下一步（8个方向）是否走过，走过为1否则为0}qipange;qipange q,p;int dir[8][2]={{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}}; //定义8个方向的操作int sign[20][20]; //标记该格是否已走过，是为1，否为0typedef struct sqstack { //定义栈qipange *base; //栈底指针qipange *top; //栈顶指针int stacksize; //栈容量} sqstack;sqstack s,sp;int initstack(sqstack &s){//构造一个空栈ss.base=(qipange*)malloc(max*sizeof(qipange)); s.top=s.base;//栈为空时栈底、栈顶指针指向一处s.stacksize=max;return 1;} // initstackbool stackempty(sqstack &s){//判断栈是否为空if(s.top==s.base)return 0;else return 1;} // stackemptyvoid push(sqstack &s,qipange &q) {//插入元素为新的栈顶元素*s.top=q;s.top++;} // pushvoid pop(sqstack &s,qipange &q){//删除栈顶元素，用q返回其值s.top--;q=*s.top;}//popint count(int r,int c) //count函数用以计算并返回下一步某方向可行路线的总数{int di_n=0,k,e,f;for(k=0;k<8;k++){e=r+dir[k][0];//改变横坐标f=c+dir[k][1];//改变纵坐标if(e>-1&&e<n&&f>-1&&f<n&&!sign[e][f]){di_n++;}}return di_n; //返回下一步某方向可行路线的总数}//主函数int main(){printf("请输入n*n型棋盘的单向格数n:");scanf("%d",&n);max=n*n;int nextr,nextc,min,nr,nc; //nextr和nextc分别记录选中的最少可通方向的下一格横纵坐标//min记录当前下一格的最少可通方向。

total=0; //入栈数个数初值为0for(i=0;i<n;i++)for(j=0;j<n;j++){ sign[20][20]=0; } //棋盘格初标志为0。

if(initstack(s))//空栈构造成功，则输入起始坐标{ printf("请输入起点坐标(x,y)（0~n）:");scanf("%d,%d",&r,&c);if(r<0||r>n||c<0||c>n)//坐标越界，给出提示信息，并重新输入{ printf("过界请重新输入\n");scanf("%d,%d",&r,&c);}}while(total<max) //入栈数个数不超过总格数{if(r>-1&&r<n&&c>-1&&c<n&&!sign[r][c]) //未过界且未曾走过的点，压入栈{q.row=r; //棋盘格结构体存储行坐标q.col=c; //棋盘格结构体存储列坐标push(s,q); //当前点压入栈sign[r][c]=1; //标记为已走过total++; //入栈数加一nextr=r;nextc=c;min=9;} //iffor(i=0;i<8;i++) //搜索拥有最少可通方向的下一格{nr=r+dir[i][0];nc=c+dir[i][1];if(nr>-1&&nr<n&&nc>-1&&nc<n&&!sign[nr][nc]) //若该点的下一步可继续往下走，则改变行列数{if(count(nr,nc)<min){nextr=nr;nextc=nc;min=count(nr,nc);}}}//forif(total==max) break; //入栈数满总格数，跳出循环if(nextr!=r) //行列数已改，棋子已移动{ r=nextr;c=nextc;}else //若棋子不能移动则应回到上一步{ pop(s,q);sign[r][c]=0;total--;pop(s,q);r=q.row; //上一步格子弹出，取坐标后再压入栈c=q.col;push(s,q);}//elseif (!stackempty(s))//栈为空，无路径{ printf("没有通路"); printf("\n");break; }}while(stackempty(s)) //栈不为空{s.top--;q=*s.top;r=q.row;c=q.col;qipan[r][c]=max--; // 逆序弹出棋盘格结构体，qipan数组记录其路径序号}printf("**************************** 马踏棋盘************************* *****");printf("\n");for(i=0;i<n;i++){ for(j=0;j<n;j++){printf("%d ",qipan[i][j]); //输出方阵其值为棋子走各点的顺序printf("\t");}printf("\n");}printf("**************************** 程序结束************************* *****");printf("\n");//system("pause");return 0;}三、实验结果1.实验数据运行环境：windows7+Microsoft Visual Studio 2008编辑语言：C++语言1）输入n*n型棋盘方阵单向格数n及马走的起始坐标，结果如下2）若输入的起始坐标越界，则给出提示信息，并重新输入，如图所示：3）若方阵太小或起始坐标不当导致马无路可走，则提示没有通路，如图所示：四、实验小结1.数据结构使用小结通过本次实验的编写，能够掌握栈的性质以及它的应用。