栈和队列实验报告.doc

西西 安安 邮邮 电电 大大 学学 计算机学院 课课内内实实验验报报告告 实验名称实验名称 栈和队列的应用栈和队列的应用 专业名称专业名称 班班 级级 学生姓名学生姓名 学号 学号 8 8 位 位 指导教师指导教师 实验时间实验时间 一一 实验目的及实验环境实验目的及实验环境 1 实验目的实验目的 1 熟练使用栈和队列解决实际问题 熟练使用栈和队列解决实际问题 2 了解并掌握数据结构与算法的设计方法 具备初步的独立分析和设计能力 了解并掌握数据结构与算法的设计方法 具备初步的独立分析和设计能力 3 初步掌握软件开发过程的问题分析 系统设计 程序编码 测试等基本方法和技能 初步掌握软件开发过程的问题分析 系统设计 程序编码 测试等基本方法和技能 4 提高综合运用所学的理论知识和方法独立分析和解决问题的能力 提高综合运用所学的理论知识和方法独立分析和解决问题的能力 2 实验环境实验环境 Dev C 二二 实验内容实验内容 设计一个国际象棋的马踏棋盘的演示过程 基本要求 将马随机放在国际象棋的 8 8 棋盘 Board 8 8 的某个方格中 马按走棋规 则进行移动 要求每个方格只进行一次 走遍整个棋盘的全部 64 个方格 编制 非递归程序 求出马的行走路线 并按求出的行走路线 将数字 1 2 64 依次填入一个 8 8 的方阵 输出之 测试数据 可自行制定一个马的初始位置 i j 0 I j 7 三 方案设计三 方案设计 第第 1 步 实现提示步 实现提示 一般来说 当马位于位置 i j 时 可以走到下列 8 个位置之一 i 2 j 1 i 1 j 2 i 1 j 2 i 2 j 1 i 2 j 1 i 1 j 2 i 1 j 2 i 2 j 1 但是 如果 i j 靠近棋盘的边缘 上述有些位置可能要超出棋盘位置 成 为不允许的位置 8 个可能位置可以用一位数组 HTry1 0 7 和 HTry2 0 7 来 表示 0 1 2 3 4 5 6 7 2 11221 1 2 1221 1 2 2 1 位于 i j 的马可以走到新位置是在棋盘范围内的 i HTry1 h j HTry2 h 其中 h 0 7 第第 2 步 需求分析步 需求分析 1 输入的形式和输入值的范围 输入马的初始行坐标 X 和列坐标 Y X 和 Y 的范围都是 1 8 2 输出形式 以数组下表的形式输入 i 为行标 j 为列标 用空格符号隔开 以棋盘形式输出 每一格打印马走的步数 这种方式比较直观 3 程序所能达到的功能 让马从任意起点出发都能够遍历整个 8 8 的 棋盘 4 测试数据 包括正确输入及输出结果和含有错误的输入及其输出结 果 数据可以任定 只要 1 x y 8 就可以了 正确的输出结果为一个二维数组 每个元素的值表示马行走的第几 步 若输入有错 则程序会显示 输入有误 请重新输入 并且要求用户重新输入数据 直至输入正确为止 第第 3 步 算法设计思想 步 算法设计思想 1 输入马所在初始位置的坐标值 考虑到用户的输入习惯 此处 1 x y 8 2 将输入的初始值进栈 3 设置一个 while 循环 循环条件为 count 64 4 取出栈顶元素 5 定义 flag 标志变量的值 6 按照 SetRound 函数逆时针顺序优先原则 找栈顶元素周围未被占用 的 7 新位置 若存在该位置 则令 order 的值等于该新位置的坐标 并入 栈 8 否则弹出栈顶元素 9 再次回到第 步 while 循环进行判断 10 输出一个 8 8 的方阵 所示数字即为相应步骤 四 测试数据及运行结果四 测试数据及运行结果 1 正常测试数据 3 组 及运行结果 2 非正常测试数据 2 组 及运行结果 五 总结五 总结 1 实验过程中遇到的问题及解决办法 例如 记录编译时错误信息 根据实验过程中出现的编译错误信息分析出 错原因 并改正错误 2 对设计及调试过程的心得体会 马踏棋盘 作为一种经典的栈的应用例子 从大方面将 刚看到这名字就知道用栈来实现 但是 当你面对这个题目 打开编译器之后想写的时候 发现又不是那么容易 很多细节 需要认真的分析 比如结构体的定义 棋子因为是二维的 所以对于用来存储棋盘的横纵 坐标 需要用到两个变量 定义两整型变量 x y 刚开始只定义了这两个变量 后来发现如 果找到下一个位置 而下一个位置有很多个都是符合的 如何选取最优的呢 最有的有可 能是最先找到的 可找到后还得继续找下去 万一没有比他更优的 则要退回来 如果没 有变量 from 来记录前一位置最优位置 就无法找到之前的点 所以要多加一个变量 其外 就是程序的调试 调试确实需要很大的耐心 有时候只是你的大意而输错了字符或输入输 出格式不符合就会出现很多看起来不可思议很难发现的错误 这也说明了编程的时候一定 要认真有耐心六 附录 六 附录 源代码 请把源代码按照实验内容附到其后 include define MAXSIZE 100 define N 8 2 数据类型定义 数据类型定义 int board 8 8 定义棋盘定义棋盘 int Htry1 8 1 1 2 2 2 1 1 2 存储马各个出口位置相对当前位置行下标的增量数组存储马各个出口位置相对当前位置行下标的增量数组 int Htry2 8 2 2 1 1 1 2 2 1 存储马各个出口位置相对当前位置列下标的增量数组存储马各个出口位置相对当前位置列下标的增量数组 struct Stack 定义栈类型定义栈类型 int i 行坐标行坐标 int j 列坐标列坐标 int director 存储方向存储方向 stack MAXSIZE 定义一个栈数组定义一个栈数组 int top 1 栈指针栈指针 3 函数声明 函数声明 void InitLocation int xi int yi 马儿在棋盘上的起始位置坐标马儿在棋盘上的起始位置坐标 int TryPath int i int j 马儿每个方向进行尝试 直到试完整个棋盘马儿每个方向进行尝试 直到试完整个棋盘 void Display 输出马儿行走的路径输出马儿行走的路径 4 起始坐标函数模块 起始坐标函数模块 void InitLocation int xi int yi int x y 定义棋盘的横纵坐标变量定义棋盘的横纵坐标变量 top 栈指针指向第一个栈首栈指针指向第一个栈首 stack top i xi 将起始位置的横坐标进栈将起始位置的横坐标进栈 stack top j yi 将起始位置的纵坐标进栈将起始位置的纵坐标进栈 stack top director 1 将起始位置的尝试方向赋初值将起始位置的尝试方向赋初值 board xi yi top 1 标记棋盘标记棋盘 x stack top i 将起始位置的横坐标赋给棋盘的横坐标将起始位置的横坐标赋给棋盘的横坐标 y stack top j 将起始位置的纵坐标赋给棋盘的纵坐标将起始位置的纵坐标赋给棋盘的纵坐标 if TryPath x y 调用马儿探寻函数 如果马儿探寻整个棋盘返回调用马儿探寻函数 如果马儿探寻整个棋盘返回 1 否则否则 返回返回 0 Display 输出马儿的行走路径输出马儿的行走路径 else printf 无解无解 5 探寻路径函数模块 探寻路径函数模块 int TryPath int i int j int find director number min 定义几个临时变量定义几个临时变量 int i1 j1 h k s 定义几个临时变量定义几个临时变量 int a 8 b1 8 b2 8 d 8 定义几个临时数组定义几个临时数组 while top 1 栈不空时循环栈不空时循环 for h 0 h 0k 0 记录条数记录条数 a h number 将条数存入数组将条数存入数组 a 8 中中 for h 0 h 8 h 根据可行路径条数小到大按下表排序放入数组根据可行路径条数小到大按下表排序放入数组 d 8 中中 min 9 for k 0 ka k min a k d h k 将下表存入数组将下表存入数组 d 8 中中 s k a s 9 director stack top director if top 63 如果走完整个棋盘返回如果走完整个棋盘返回 1 return 1 find 0 表示没有找到下一个位置表示没有找到下一个位置 for h director 1 h 0 表示找到下一个位置表示找到下一个位置 break if find 1 如果找到下一个位置进栈如果找到下一个位置进栈 stack top director director 存储栈结点的方向存储栈结点的方向 top 栈指针前移进栈栈指针前移进栈 stack top i i stack top j j stack top director 1 重新初始化下一栈结点的尝试方向重新初始化下一栈结点的尝试方向 board i j top 1 标记棋盘标记棋盘 else 否则退栈否则退栈 board stack top i stack top j 0 清除棋盘的标记清除棋盘的标记 top 栈指针前移退栈栈指针前移退栈 return 0 6 输出路径函数模块 输出路径函数模块 void Display int i j for i 0 i N i for j 0 j N j printf t d board i j 输出马儿在棋盘上走过的路径输出马儿在棋盘上走过的路径 printf n n printf n 5 主程序模块 主程序模块 int main int i j int x