马踏棋盘数据结构.docx

《数据结构》课程设计报告课程设计题目:马踏棋盘姓名:张程浩院系:通信工程专业:信息安全年级:2011学号:11225104指导教师:任雪萍2012年11月26日(任雪萍编写)目录一、课程设计目的 3二、任务分析 3三、分析设计 3四、调试分析 5五、测试结果 5六、小结 6七、用户手册 6八、附录 6九、参考文献 8一、课程设计目的熟练使用C语言编写程序,强化模块设计理念;设计一个国际象棋马踏棋盘的演示程序。理解栈的特性“后进先出”和队列的特性“先进先出”。初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;二、任务分析(1)要求:在国际象棋8×8棋盘上面,按照国际象棋规则中马的行进规则,实现从任意初始位置,每个方格只进入一次,走遍棋盘上全部64个方格。编制程序,求出马的行走路线,并按求出的行走路线,将数字1,2,…,64依次填入一个8×8的方阵,并输出它的行走路线。(2)输入:任意一个起始位置;输出:无重复踏遍棋盘的结果,以数字1-64表示行走路线。三、分析设计需要处理的数据的逻辑结构:线性结构合适的存储结构:顺序储存设计好的数据类型:#defineBS 8 //棋盘大小typedefintStatus;intstep;intboard[8][8]={0};//定义棋盘intmayway[9]; //储存可能的路径intHtry1[8]={-2,-1,1,2,2,1,-1,-2},Htry2[8]={1,2,2,1,-1,-2,-2,-1}; /*存储马各个出口位置相对当前位置列下标的增量数组*/typedefstruct{ //位置存储表达方式 inti; //行坐标 intj; //列坐标 intfrom; //存储下一步所选方向}SElemType;typedefstruct{ SElemType *base; //在栈构造之前和销毁之后,base的值为NULL SElemType *top; //栈顶指针 int stacksize; //当前已经分配的储存空间,以元素为单位}Stack;StackPath;本程序包含模块:1、主程序模块:voidmain(){定义变量;接受命令;处理命令;退出;}输入的初始位置是否正确主程序模块起始坐标函数模块探寻路径函数模块结束输出路径函数模块块是否2、起始坐标函数模块——马儿在棋盘上的起始位置;3、探寻路径函数模块——马儿每个方向进行尝试,直到试完整个棋盘;4、输出路径函数模块——输出马儿行走的路径;各模块之间的调用关系:与功能对应的模块划分定义: //构造一个空栈SStatusInitStack(Stack&s); //若栈不空,则用e返回s的栈顶元素,返回OK;否则返回ERRORStatusGetTop(Stacks,SElemType&e); //插入元素e为新的栈顶元素StatusPush(Stack&s,SElemTypee); //若栈不空,则删除s的栈顶元素,并用e返回其值,并返回OK;否则返回ERRORStatusPop(Stack&s,SElemType&e); //从栈底到栈顶依次对栈中每个元素输出。StatusStackTraverse(Stacks); //若当前坐标在有效棋盘内返回OK;否则返回ERRORStatusInBoard(inti,intj);