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

课程设计(论文)任务书 软件 学院软件工程专业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 | aiElemSet，i=1，2，n，n0数据关系：R1= | ai-1,aiD，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 di8; / 记录该格的下一步（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 di8; / 记录该格的下一步（8个方向）是否走过，走过为1否则为0 qipange;typedef struct sqstack /定义栈 qipange *base; /栈底指针 qipange *top; /栈顶指针 int stacksize; /栈容量 sqstack;全局变量定义：int qipan2020; /棋盘方阵，存放各点走的次序 int r,c,i,j,total,n,max; /r,c分别表示横纵坐标；i，j计数；total 进入路径栈的元素个数；n是单向格数（用户输入）；max是总格数 int dir82=-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1; /定义8个方向的操作int sign2020; /标记该格是否已走过，是为1，否为0二、 解题过程1. 问题分解该问题主要应实现以下功能：能够实现一个国际象棋的马踏棋盘的演示过程将马随机放在国际象棋nn的棋盘的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘全部的64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，3, .64一次填入一个nn的方阵输出之。需求分析以数组下标形式输入，i表示横坐标，j表示纵坐标。以棋盘形式输出，没一格打印马走的步数，这种方式比较直观程序所能达到的功能：让马从任一起点出发都能够遍历整个n*n的棋盘测试数据，包括正确的输入及输出结果和含有错误的输入及输出结果。数据可以任定，只要y=n你就可以了正确的输入结果为一个2维数组，每个元素的值表示马行走的第几步。若输入有错，则显示相应提示信息，要求用户重新输入数据，直到输入正确位置2. 模块结构系统主要由4个模块组成，分别是： 求各点权值的模块 检验坐标值(i,j)是否在棋盘内模块 输出各个函数的模块 主算法函数，踏遍棋盘的算法的模块模块之间的结构如下：3. 解题思路各模块的实现步骤为按照顺时针顺序，每次产生一个新的路点，并验证此路点的可用性，需要考虑的问题包括是否超出棋盘和此点已经走过与否。如新路点可用，则入栈，并执行下一步，每次按照上一路点的位置生成新路点。如一个路点的可扩展路点数为0，则走不下去了，进行回溯。实现#include#includeint qipan2020; /棋盘方阵，存放各点走的次序 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 di8; / 记录该格的下一步（8个方向）是否走过，走过为1否则为0 qipange;qipange q,p;int dir82=-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1; /定义8个方向的操作int sign2020; /标记该格是否已走过，是为1，否为0 typedef struct sqstack /定义栈 qipange *base; /栈底指针 qipange *top; /栈顶指针 int stacksize; /栈容量 sqstack; sqstack s,sp; int initstack(sqstack &s) /构造一个空栈s s.base=(qipange*)malloc(max*sizeof(qipange); s.top=s.base;/栈为空时栈底、栈顶指针指向一处 s.stacksize=max; return 1; / initstack bool stackempty(sqstack &s) /判断栈是否为空 if(s.top=s.base) return 0; else return 1; / stackempty void push(sqstack &s,qipange &q) /插入元素为新的栈顶元素 *s.top=q; s.top+; / push void pop(sqstack &s,qipange &q) /删除栈顶元素 ，用q返回其值 s.top-; q=*s.top; /pop int count(int r,int c) /count函数用以计算并返回下一步某方向可行路线的总数 int di_n=0,k,e,f; for(k=0;k-1&e-1&fn&!signef) 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; /入栈数个数初值为0 for(i=0;in;i+) for(j=0;jn;j+) sign2020=0; /棋盘格初标志为0。 if(initstack(s)/空栈构造成功，则输入起始坐标 printf(请输入起点坐标(x,y)（0n）:); scanf(%d,%d,&r,&c); if(rn|cn)/坐标越界，给出提示信息，并重新输入 printf(过界 请重新输入n); scanf(%d,%d,&r,&c); while(total-1&r-1&cn&!signrc) /未过界且未曾走过的点，压入栈 q.row=r; /棋盘格结构体存储行坐标 q.col=c; /棋盘格结构体存储列坐标 push(s,q); /当前点压入栈 signrc=1; /标记为已走过 total+; /入栈数加一 nextr=r; nextc=c; min=9; /if for(i=0;i-1&nr-1&ncn&!signnrnc) /若该点的下一步可继续往下走 ，则改变行列数 if(count(nr,nc)min) nextr=nr;nextc=nc;min=count(nr,nc); /for if(total=max) break; /入栈数满总格数，跳出循环 if(nextr!=r) /行列数已改，棋子已移动 r=nextr; c=nextc; else /若棋子不能移动 则应回到上一步 pop(s,q); signrc=0; total-; pop(s,q); r=q.row; /上一步格子弹出，取坐标后再压入栈 c=q.col; push(s,q); /else if (!stackempty(s)/栈为空，无路径 printf(没有通路); printf(n);break; while(stackempty(s) /栈不为空 s.top-; q=*s.top; r=q.row; c=q.col; qipanrc=max-; / 逆序弹出棋盘格结构体，qipan数组记录其路径序号 printf(* 马踏棋盘 *); printf(n); for(i=0;in;i+) for(j=0;jn;j+) printf(%d ,qipanij); /输出方阵 其值为棋子走各点的顺序 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. 数据结构使用小结通过本次实验的编写，能够掌握栈的性质以及它的应用。这次实验花了很多时间才完成，其实早完成了该程序的绝大部分功能，但在功能完善和检查修改方面又下了很大一番功夫，不过算法思想却没有改变。这个程序也让我头疼了好几次，就是输出结果时总是出现多多少少的错误，跟自己想象中的总有差距，还不时出现一些乱码。在编写过程中，我也参考了一些优化的算法，力求缩短程序运行时间，提高其效率。2. 需完善之处在该程序的编制过程中留下了一些思考的问题，就是马儿从一个起点位置开始探寻，最后马儿探寻成功的路径会不会不止一条，可能还有多条路径，由于时间实在有限没来得及去深究，但是这应该是值得思考的一个问题。20课程设计体会通过此次课程设计，刚开始看完题目的时候觉得有点不知从何下手的感觉，但是通过课本提示以及资料的查询，就感觉思路渐渐的清晰，通过这次课程设计，我也学会了很多东西。把自己平时所学的东西应用