马踏棋盘数据结构报告.docxVIP

《数据结构》课程设计报告课程设计题目：马踏棋盘姓名：张程浩院系：通信工程专业：信息安全年级：2011学号导教师：任雪萍2012年11月26日(任雪萍编写)目录一、课程设计目的熟练使用C语言编写程序，强化模块设计理念；设计一个国际象棋马踏棋盘的演示程序。理解栈的特性“后进先出” 和队列的特性“先进先出”。初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；二、任务分析（1）要求：在国际象棋8×8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。编制程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，并输出它的行走路线。（2）输入：任意一个起始位置；输出：无重复踏遍棋盘的结果，以数字1-64表示行走路线。三、分析设计需要处理的数据的逻辑结构：线性结构合适的存储结构：顺序储存设计好的数据类型：#define BS8//棋盘大小typedef int Status;int step; int board[8][8]={0}; //定义棋盘 int mayway[9];//储存可能的路径 int Htry1[8]={-2,-1,1,2,2,1,-1,-2},Htry2[8]={1,2,2,1,-1,-2,-2,-1};/*存储马各个出口位置相对当前位置列下标的增量数组*/typedef struct {//位置存储表达方式int i;//行坐标int j;//列坐标int from; //存储下一步所选方向}SElemType;typedef struct {SElemType*base;//在栈构造之前和销毁之后，base的值为NULLSElemType*top;//栈顶指针intstacksize;//当前已经分配的储存空间，以元素为单位}Stack;Stack Path;本程序包含模块：1、主程序模块：void main(){定义变量；接受命令；处理命令；退出；}2、起始坐标函数模块——马儿在棋盘上的起始位置；3、探寻路径函数模块——马儿每个方向进行尝试，直到试完整个棋盘；4、输出路径函数模块——输出马儿行走的路径； 各模块之间的调用关系：与功能对应的模块划分定义：//构造一个空栈SStatus InitStack(Stack s);//若栈不空，则用e返回s的栈顶元素，返回OK；否则返回ERRORStatus GetTop(Stack s,SElemType e);//插入元素e为新的栈顶元素Status Push(Stack s,SElemType e);//若栈不空，则删除s的栈顶元素，并用e返回其值，并返回OK；否则返回ERRORStatus Pop(Stack s,SElemType e);//从栈底到栈顶依次对栈中每个元素输出。Status StackTraverse(Stack s);//若当前坐标在有效棋盘内返回OK；否则返回ERRORStatus InBoard(int i,int j);//贪心法判断下一步的可能选位置，并把可选的最佳位置依次存入mayway，并返回OK；//若找不到位置返回ERRORStatus TryPath(SElemType s, int mayway[]);Status NextPath(SElemType cur,int mayway[]);函数调用关系：四、调试分析1、调试中的问题（1）调试问题：本程序设计过程中采用多文件组件工程的方式进行。在头文件中定义了全局变量，解决方案：将全局变量定义为staic型变量。或者在声明中使用extern关键字（2）调试问题：虽然编译都能通过，但是运行时却出错，程序不能终止，只有通过人工方式结束程序，可能是在某些地方出现了无限死循环了，马儿回溯的时候，下一次又有可能走那个方向，这样就出现了死循环。解决方案：标记马儿选择的方向director。在结点结构设计上加入director（3）调试问题：在调试过程中，对变量的监视发现栈顶元素中director无法更新，我原本的程序代码设计是cur.director=k解决方案：(Path.top-1)-from=k;//保存下一步所选最佳路径下标（4）调试问题：当走到边界时，有可走的路，但是程序却回溯了。解决方案：for (int k = 1+direction; k 9, k = mayway[0] ; k++)//向所得的方向进行探寻五、测试结果六、小结通过本次实验的编写，能够掌握栈的性质以及它的应用。这个程序也让我头疼了几次，就是运行速度很慢，要等很久才能输出结果，这样的话很占内存资源，而且CPU的使用记录也很高，主要是它需要的运算太多，