数据结构试验指导书V2.0.doc

V V 2 02 0 数据结构与算法数据结构与算法 实验指导书实验指导书 编写 编写 陆绍飞陆绍飞 校核 校核 湖南大学软件学院湖南大学软件学院 20112011 年年 9 9 月月 目目 录录 实验教学大纲实验教学大纲 1 1 一 课程所占的学时 学分及实验课所占学时 学分 1 二 实验适用专业 1 三 实验的任务 性质和目的 1 四 实验的基本理论 1 五 实验方式与基本要求 2 六 实验项目的设置与内容提要 2 七 考核方式与评分办法 3 实验项目实验项目 1 1 三元组三元组 ADTADT 4 4 实验项目实验项目 2 2 复数四则运算复数四则运算 6 6 实验项目实验项目 3 3 基本线性表运算基本线性表运算 8 8 实验项目实验项目 4 4 基本线性表就地逆置基本线性表就地逆置 1313 实验项目实验项目 5 5 数数制制转换转换 1515 实验项目实验项目 6 6 回文判断回文判断 1717 实验项目实验项目 7 7 算术表达式求值演示算术表达式求值演示 1919 实验项目实验项目 8 8 迷宫问题迷宫问题 2222 实验项目实验项目 9 9 树与二叉树树与二叉树 2727 实验项目实验项目 1010 图遍历演示图遍历演示 3030 实验项目实验项目 1111 二叉排序树二叉排序树 3333 实验项目实验项目 1212 内部排序算法比较内部排序算法比较 3535 实验项目实验项目 1313 哈希表设计哈希表设计 3636 实验项目实验项目 1414 约瑟夫环约瑟夫环 3737 实验项目实验项目 1515 停车场管理停车场管理 3838 实验项目实验项目 1616 旅游导游系统旅游导游系统 3939 实验教学大纲实验教学大纲 课程名称 课程名称 数据结构与算法 课程编号 课程编号 本大纲主笔人 李睿本大纲主笔人 李睿 陆绍飞修改陆绍飞修改 一 课程所占的学时 学分及实验课所占学时 学分一 课程所占的学时 学分及实验课所占学时 学分 总学时 80 总学分 4 实验课时 48 实验学分 1 二 实验适用专业 二 实验适用专业 软件工程 计算机专业 通信 信息类本科学生 三 实验的任务 性质和目的三 实验的任务 性质和目的 数据结构与算法是一门技术性与实践性很强的课程 实验的设置十分重要 为了帮助 学生更好地学习本课程 理解和掌握算法设计所需的技术 为整个专业学习打好基础 通 过要求完成对一些典型问题的分析及其实现的各环节 使学生掌握所用到的一些技术 扩 充知识面 通过实验内容的训练 突出构造性思维训练的特征 提高学生组织数据与进行 编写大型程序能力 同时 上机实习是对学生的一种全面综合的训练 是与课堂听讲 自学和练习相辅相 成的必不可少的一个教学环节 实习题中的问题比平时的习题复杂得多 也更接近实际 实习着眼于原理与应用的结合点 使学生学会把书上学到的知识解决实际问题 培养软件 工程所需要的动手能力 另一方面 能使书本知识变 活 起到深化理解和灵活掌握教学 内容的目的 平时的练习较偏重于如何编写功能单一的 小 算法 而实习题是软件设计的 综合训练 包括问题分析 总体结构设计 用户界面设计 程序设计基本技能和技巧 多 人合作 以至一整套软件工作规范的训练和科学作风的培养 此外 还有很重要的一点是 机器是比任何教师都严厉的检查者 四 实验的基本理论四 实验的基本理论 数据结构与算法 是计算机专业一门重要的专业技术基础课程 本课程较系统地介绍 了软件设计中常用的数据结构以及相应的存储结构和实现算法 介绍了常用的多种查找和 排序技术 并对进行性能分析和比较 内容非常丰富 本课程的学习将为后续课程的学习 以及软件设计水平的提高打下良好的基础 数据结构与算法课程是计算机专业的一门核心 的关键性课程 为了使学生熟练掌握并运用所学知识 本实验安排了 16 个主实习单元 除实习 1 2 作为预备练习之外 其它各单元的训练重点在于基本的数据结构 而不强调面面俱到 各 实习单元与教科书的各章只具有粗略的对应关系 一个实习题常常涉及几部分教学内容 每个实习题采取统一的格式 由问题描述问题描述 基本要求基本要求 测试数据测试数据 实现提示实现提示和选做内选做内 容容等 5 个部分组成 问题描述问题描述旨在为读者建立问题提出的背景环境 指明问题 是什么 基本要求基本要求则对问题进一步求精 划出问题的边界 指出具体的参量或前提条件 并规 定该题的最低限度要求 测试数据测试数据部分旨在为检查学生上机作业提供方便 在完成实习题时应自己设计完整和 严格的测试方案 当数据输入量较大时 提倡以文件形式向程序提供输入数据 实现提示实现提示对实现中的难点及其解法思路等问题作了简要提示 选做内容选做内容向那些尚有余力的读者提出了更严峻的挑战 同时也能开拓其他读者的思路 在完成基本要求时就力求避免就事论事的不良思想方法 尽可能寻求具有普遍意义的解法 使得程序结构合理 容易修改扩充 五 实验方式与基本要求五 实验方式与基本要求 为了培养一个软件工作者所应具备的科学工作的方法和作风 实验过程要求按以下 5 个步骤进行 1 问题分析和任务定义 2 数据类型和系统设计 3 编码实现和静态检查 4 上机准备和上机调试 5 总结和整理实习报告 六 实验项目的设置与内容提要六 实验项目的设置与内容提要 序号实验项目 实验 学时 每组 人数 实验 类型 实验 要求 内 容 提 要 1 抽象数据类型 三元组 ADT 复数四则运算 41综合 必修 实现创建一个三元组 实现其基本操作 设计实现抽象数据类型 复数 2 线性表 基本线性表运算 线 性表的逆置 41综合 必修 实现基本线性表的创建 求基本线性表的长度 在基本线性表中查找某个数据元素 在某个位 置插入一个新数据元素 在某个线性表中删除 某个数据元素等操作 分别以不同存储结构实现线性表的就地逆 置 3 栈 队列与递归算法设计 数 制转换问题 回文判断 41设计 必修 将十进制数 N 转换为其它 d 进制数 判断依次读入的一个以 为结束符的字母 序列 是否为形如 序列 1 Elem e2 Elem e3 public Triple Elem v1 Elem v2 Elem v3 e1 v1 e2 v2 e3 v3 Elem Get i 初始条件 三元组已经存在 1 i 3 操作结果 返回三元组的第 i 个分量 Bool put i e 初始条件 三元组已经存在 1 i 3 操作结果 将三元组的第 i 个分量赋值为 e 成功返回 true 否则返回 false Elem GetMax 初始条件 三元组已经存在 操作结果 返回三元组中最大分量值 e Elem GetMin 初始条件 三元组已经存在 操作结果 返回三元组中最小分量值 e void Output 初始条件 三元组已经存在 操作结果 输出三元组中所有分量值 测试数据测试数据 由学生任意指定 选作内容选作内容 实现两个三元组的对应分量相加或相减 给三元组的各分量同乘一个比例因子 销毁 三元组等操作 实验项目实验项目 2 2 复数四则运算复数四则运算 2 12 1 实验目的实验目的 本次实验与实验项目 1 为同一类型实验 主要目的是在于帮助读者进一步熟悉抽象数 据类型的表示和实现方法 抽象数据类型需要借助固有数据类型来表示和实现 即利用高 级程序设计语言中已经存在的数据类型来说明新的结构 用已经实现的操作来组合新的操 作 具体实现细节依赖于所用语言的功能 2 22 2 实验内容实验内容 问题描述问题描述 设计实现一个可进行复数运算的演示程序 基本要求基本要求 实现下列六种基本运算 1 由输入的实部和虚部生成一个复数 2 两个复数求和 3 两个复数求差 4 两个复数求积 5 从已知复数中分离出实部 6 从已知复数中分离出虚部 运算结果以相应的复数或实数的表示形式显示 算法描述算法描述 该算法中 Elem 为 float 或 double 类型 template class Complex Private Elem reality Elem falsehood public Triple Elem r Elem f reality r falsehood f Complex operate const complex Elem falsehood 初始条件 复数已经存在 操作结果 返回复数的虚部 void Output 初始条件 复数已经存在 操作结果 以复数形式输出复数到屏幕上 测试数据测试数据 由学生依据软件工程的测试技术自己确定 注意测试边界数据 如复数 0 实现提示实现提示 定义复数为两个相互之间存在次序关系的实数构成抽象数据类型 利用实数的操作来 实现复数的操作 选作内容选作内容 实现复数的其他运算 如 两个复数相除 求共轭 实验项目实验项目 3 3 基本线性表运算基本线性表运算 3 13 1 实验目的实验目的 1 掌握基本线性表顺序存储的类型定义及 C 语言实现 2 掌握基本线性表链式存储的类型定义及 C 语言实现 3 掌握基本线性表顺序存储结构中的各种基本操作 4 掌握基本线性表链式存储结构中的各种基本操作 3 23 2 实验内容实验内容 问题描述问题描述 基本线性表经常进行的运算操作有创建基本线性表 求基本线性表的长度 在基本线 性表中查找某个数据元素 在某个位置插入一个新数据元素 在某个线性表中删除某个数 据元素以及基本线性表的输出等操作 试编程实现基本线性表的这些基本运算 基本要求基本要求 实现基本线性表的基本运算可以采用链式存储方式实现 也可以采用顺序存储的方式实 现 在此给出这两种存储方式的实现方法 学生可任选其一进行具体实现 算法描述算法描述 1 顺序存储方式 templet class AList public List private int maxSize int listSize int fence Elem listArray public 线性表创建操作实现 AList int size DefaultListSize maxSize size listSize fence 0 listArray new Elem maxSize AList delete listArray void clear delete listArray listSize fence 0 listArray new Elem maxSize bool insert const Elem bool append const Elem bool remove Elem void setStart fence 0 void setEnd fence listSize void prev if fence 0 fence void next if fence 0 for int i listSize i fence i listArray i listArray i 1 listArray fence item listSize return true 在线性表末尾追加数据操作实现 templet bool AList append const Elem listArray listSize item return true 线性表中删除操作实现 templet bool AList remove Elem it listArray fence for int i fence i listSize 1 i listArray i listArray i 1 listSize return true 线性表中查找操作实现 templet bool AList bool find Elem k Elem it for L setStart L getValue it L next if K it return true found it return false K not found 2 链式存储方式 template class LList public List private Link head Link tail Link fence int leftcnt rightcnt 基本线性表的创建操作实现 void init fence head tail new Link leftcnt rightcnt 0 init void removeall while head null fence head head head next delete fence removeall public LList int size DefaultListSize init LList removeall void clear removeall init bool insert const Elem bool append const Elem bool remove Elem void setStart fence head rightcnt leftcnt leftcnt 0 setStart void setEnd fence tail leftcnt rightcnt rightcnt 0 setEnd void prev void next if fence tail fence fence next rightcnt leftcnt next int leftLength const return leftcnt int rightLength const return rightcnt bool setPos int Pos bool getValue Elem it fence next element return true getValue void print const 基本线性表插入操作的实现 template bool LList insert const Elem if tail fence tail fence next rightcnt return true 基本线性表末尾追加数据操作的实现 template bool LList append const Elem rightcnt return true 基本线性表删除操作的实现 template bool LList remove Elem it fence next element Link Itemp fence next fence next Itemp next if tail Itemp tail fence delete Itemp rightcnt return true template void LList prev Link temp head if fence head return while temp next fence temp temp next fence temp leftcnt rightcnt template bool LList setPos int pos if pos rightcnt leftcnt return false setStart for int i 0 i pos i next return true template void LList print const Linl temp head cout while temp fence cout next element next while cout next NULL cout next element next while cout n 测试数据测试数据 由学生依据软件工程的测试技术自己确定 注意测试边界数据 实验提示实验提示 1 基本线性表是数据结构中最简单 最常用的数据类型 它是学习其他数据结构类型 的基础 因此 虽然基本线性表相对较为简单 但其各种运算内容较多 只有熟练 掌握和理解基本线性表的基本内涵才能在解决实际问题的过程中准确运用 2 基本线性表的表示与存储是基本线性表进行各种运算的基础 所以 基本线性表中 各个数据元素之间的逻辑和存储关系必须要在各种运算中准确体现 不能有任何的 思路混淆 也不能有任何的不确定性 选作内容选作内容 两个线性表的并 交 差等运算的实现 实验项目实验项目 4 4 基本线性表就地逆置基本线性表就地逆置 4 14 1 实验目的实验目的 进一步掌握基本线性表的各种操作 深入理解线性表的存储方式 4 24 2 实验内容实验内容 问题描述问题描述 基本线性表就地逆置是指在基本线性表现有空间的基础上 将基本线性表中的数据元 素交换位置排列 排列完之后 新的顺序序列与原来的顺序序列刚好相反 如原来顺序序 列 abcdef 就地逆置后的新顺序序列为 fedcba 根据基本线性表的链式和顺序两 种存储结构分别完成 1 顺序结构的就地逆置 2 链式结构的就地逆置 基本要求基本要求 充分理解题目要求 在对基本线性表逆置时 必须是在基本线性表原有空间的基 础上进行 不能借助临时变量所生成的临时空间 也不能借助其他形式的临时空间 且算法时间复杂度要求为 O n 算法描述算法描述 针对两种存储结构的基本线性表实现就地逆置的方法有多种 每种存储结构的实现方法 选择一种讲解 1 顺序结构基本线性表就地逆置 首先 创建一个包含若干个结点的基本线性表 由于在基本线性表的顺序存储结构中 数据元素的个数往往会少于所申请的存储单元数 因此 可以利用空闲存储单元中的某一 个单元为中间单元 将基本线性表中前后对应位置上的数据元素交换位置 具体方法是将 基本线性表的第 1 个数据元素和最后一个数据元素交换位置 第 2 个数据元素和倒数第 2 个数据元素交换位置 依次类推 直到所有元素都交换了位置 则就地逆置的过程就 完成了 算法简单描述如下 template void Alist reverlist int i for i 0 i listSize 2 i listArray listSize 1 listArray i 将第 listSize 1 号单元作为中间存储单元 listArray i listArray listSize i 1 listArray listSize i 1 listArray listSize 1 思考 当基本队列满时应该如何处理 2 链式存储结构就地逆置 为清楚对比基本线性表在逆置前后的变化 链式基本线性表的逆置过程可分为 4 个步 骤进行 a 创建包含若干个结点的链式基本线性表 利用 for 循环 从键盘上随机输入结点 的个数和每个结点的数据域的值 b 输出创建成功的链式基本线性表 从表头到表尾逐个输出链表中所有结点的值 c 逆置链式基本线性表 设链式基本线性表有一个头结点 将链式基本线性表断开 成两部分 第一部分为只有头结点 第二部分为所有含有数据元素的结点 从第 二部分中依次取出结点插入到第一部分的头结点后 将第二部分所有结点插入到 第一部分后 就完成了链式基本线性表的逆置 思考 问什么 d 输出逆置后的链式基本线性表 核心算法简单描述如下 template void class LList reverlist Link p q p head next head next NULL 链式线性表分为两部分 while p NULL q p p p next q next head next head next q 测试数据测试数据 由学生依据软件工程的测试技术自己确定 注意测试边界数据 如对空线性表进行逆 置 以及当顺序线性表表满时进行逆置 实现提示实现提示 1 基本线性表的输入和输出可以有不同的形式 但是基本线性表的特征不会改 变 不管在实际问题中要求用何种形式对基本线性表进行输入和输出 首先 必须确定基本线性表用何种存储方式更为便利 2 在确定其存储结构之后 该选用何种解决方案更容易编程实现 更能有效地 组织数据 也是在编程之前应该考虑的事情 选作内容选作内容 无 实验项目实验项目 5 5 数制转换数制转换 5 15 1 实验目的实验目的 仅仅认识到栈是一种特殊的线性表是远远不够的 本次实习的目的在于使读者深入了 解栈的特征 以便在实际问题背景下灵活运用它们 同时还将巩固这种结构的构造方法 接触较复杂问题的递归算法设计 5 25 2 实验内容实验内容 问题描述问题描述 十进制 N 和其它进制数的转换是计算机实现计算的基本问题 其解决方法很多 其中一 个简单算法基于下列原理 N n div d d n mod d 其中 div 为整除运算 mod 为求余运算 例如 1348 10 2504 8 其运算过程如下 n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 从中我们可以看出 最先产生的余数 4 是转换结果的最低位 这正好符合栈的特性即 后进先出的特性 所以可以用顺序栈来模拟这个过程 试编程实现将 10 进制数转换 成 N 进制数 基本要求基本要求 对于键盘输入的任意一个非负的十进制整数 打印输出与其等值的八进制数 由 于上述的计算过程是从低位到高位顺序产生的八进制数的各个数位 而打印输出 一 般来说应从高位到地位进行 恰好和计算过程相反 因此可以先将计算过程中得到的 八进制数的各位进栈 待相对应的八进制数的各位均产生以后 再使其按顺序出栈 并打印输出 即得到了与输入的十进制数相对应的八进制数 算法描述算法描述 算法思想如下 当 N 0 时重复 1 2 1 若 N 0 则将 N r 压入栈 s 中 执行 2 若 N 0 将栈 s 的内容依次出栈 算 法结束 2 用 N r 代替 N 具体描述如下 void conversion Stack s scanf n while n s push n 8 n n 8 while s pop e printf d e 测试数据测试数据 由学生依据软件工程的测试技术自己确定 注意测试边界数据 实现提示实现提示 无 选作内容选作内容 无 实验项目实验项目 6 6 回文判断回文判断 6 16 1 实验目的实验目的 本次实习的目的在于进一步使读者深入了解栈和队列的特征 以便在实际问题背景下 灵活运用它们 同时还将巩固这两种结构的构造方法 接触较复杂问题的递归算法设计 6 26 2 实验内容实验内容 问题描述问题描述 试写一个算法 判断依次读入的一个以 为结束符的字母序列 是否为形如 序 列 1 Stack s new Stack while c getchar EOF 字符串输入没有结束 q Enqueue c s Push c while s pop e return true 测试数据测试数据 由学生依据软件工程的测试技术自己确定 注意测试边界数据 如序列 1 和序列 2 均 为空串 实现提示实现提示 利用队列的先进先出 FIFO 和栈的后进先出 LIFO 特点 将字符串中字符分别进行 入栈和入队操作 字符串输入结束后将队列和栈中字符依次取出 判断取出的一对字符是 否相同 选作内容选作内容 无 实验项目实验项目 7 7 算术表达式求值演示算术表达式求值演示 7 17 1 实验目的实验目的 本次实习的目的在于进一步使读者深入了解栈和队列的特征 以便在实际问题背景下 灵活运用它们 同时还将巩固这两种结构的构造方法 接触较复杂问题的递归算法设计 7 27 2 实验内容实验内容 问题描述问题描述 表达式求值是实现程序设计语言的基本问题之一 也是栈的应用的一个典型例子 设计一个程序 演示用算符优先法对算术表达式求值的过程 基本要求基本要求 以字符序列的形式从终端输入语法正确的 不含变量的整数表达式 按照算符优 先关系 实现对算术四则混合运算表达式的求值 并演示求值过程中运算符栈 运算 数栈 输入字符和主要操作的变化过程 算法描述算法描述 达式作为一个满足表达式语法规则的串存储 如表达式 3 2 4 2 2 3 5 它 的的求值过程为 自左向右扫描表达式 当扫描到 3 2 时不能马上计算 因为后面可能还 有更高的运算 正确的处理过程是 需要两个栈 对象栈 s1 和算符栈 s2 当自左至右扫描 表达式的每一个字符时 若当前字符是运算对象 入对象栈 是运算符时 若这个运算符 比栈顶运算符高则入栈 继续向后处理 若这个运算符比栈顶运算符低则从对象栈出栈两 个运算量 从算符栈出栈一个运算符进行运算 并将其运算结果入对象栈 继续处理当前 字符 直到遇到结束符 根据运算规则 左括号 在栈外时它的级别最高 而进栈后它的级别则最低了 乘方运算的结合性是自右向左 所以 它的栈外级别高于栈内 就是说有的运算符栈内栈 外的级别是不同的 当遇到右括号 时 一直需要对运算符栈出栈 并且做相应的运算 直到遇到栈顶为左括号 时 将其出栈 因此右括号 级别最低但它是不入栈的 对象栈初始化为空 为了使表达式中的第一个运算符入栈 算符栈中预设一个最低级的运 算符 根据以上分析 每个运算符栈内 栈外的级别如下 算符 栈内级别 栈外级别 4 3 2 1 0 5 0 0 运算规则如下 设两个运算符 1 2 a 1 b 2 c 1 2 1 优先权高于 2 可以运算 算法简单描述如下 设置两个栈 分别存放操作数和运算符 输入操作数时 一定不会运算 运算过程实际就是运算符号比较的过程 OpendType EvaluateExpression 表达式求值 Stack OPTR OPTR Push Stack OPND c getchar while c c getchar else OPTR topValue OPTRType it switch Precede it c case OPTR Pop t OPND Pop b OPND Pop a OPND Push Operate a t b break switch if while OPND topValue a EvaluateExpression 测试数据测试数据 3 7 2 8 1 2 3 4 88 1 5 1024 4 8 1024 4 8 20 2 6 2 3 3 3 8 9 9 2 6 2 3 6 6 6 实现提示实现提示 1 设置运算符栈和运算数栈辅助分析算符优先关系 2 在读入表达式的字符序列的同时 完成运算符和运算数 整数 的识别处理 以 及相应的运算 3 在识别出运算数的同时 要将其字符序列形式转换成整数形式 4 在程序的适当位置输出运算符栈 运算数栈 输入字符和主要操作的内容 选作内容选作内容 1 扩充运算符集 如增加乘方 单目减 赋值等运算 2 运算量可以是变量 3 运算量可以是实数类型 4 计算器的功能和仿真界面 实验项目实验项目 8 8 迷宫问题迷宫问题 8 18 1 实验目的实验目的 本次实习的目的在于进一步使读者深入了解栈和队列的特征 以便在实际问题背景下 灵活运用它们 同时还将巩固这两种结构的构造方法 接触较复杂问题的递归算法设计 8 28 2 实验内容实验内容 问题描述问题描述 以一个 m n 的长方阵表示迷宫 0 和 1 分别表示迷宫中的通路和障碍 设计一个程序 对任意设定的迷宫 求出一条从入口到出口的通路 或得出没有通路的结论 基本要求基本要求 首先实现一个以链表作为存储结构的栈类型 然后编写一个求解迷宫的非递归程序 求得的通路以三元组 i j d 的形式输出 其中 i j 指示迷宫的一个坐标 d 表示走到 下一坐标的方向 如 对于下列数据的迷宫 输出的一条通路为 1 1 1 1 2 2 2 2 2 3 2 3 3 1 2 算法描述算法描述 这是实验心理学中的一个经典问题 心理学家把一只老鼠从一个无顶盖的大盒子的入 口处赶进迷宫 迷宫中设置很多隔壁 对前进方向形成了多处障碍 心理学家在迷宫的唯 一出口处放置了一块奶酪 吸引老鼠在迷宫中寻找通路以到达出口 求解思想 回溯法是一种不断试探且及时纠正错误的搜索方法 下面的求解过程采用 回溯法 从入口出发 按某一方向向前探索 若能走通 未走过的 即某处可以到达 则 到达新点 否则试探下一方向 若所有的方向均没有通路 则沿原路返回前一点 换下一 个方向再继续试探 直到所有可能的通路都探索到 或找到一条通路 或无路可走又返回 到入口点 在求解过程中 为了保证在到达某一点后不能向前继续行走 无路 时 能正确返回 前一点以便继续从下一个方向向前试探 则需要用一个栈保存所能够到达的每一点的下标 及从该点前进的方向 需要解决的四个问题 1 表示迷宫的数据结构 设迷宫为 m 行 n 列 利用 maze m n 来表示一个迷宫 maze i j 0 或 1 其中 0 表 示通路 1 表示不通 当从某点向下试探时 中间点有 8 个方向可以试探 见图 3 4 而四个角点有 3 个方向 其它边缘点有 5 个方向 为使问题简单化我们用 maze m 2 n 2 来表示迷宫 而迷宫的四周的值全部为 1 这样做使问题简单了 每 个点的试探方向全部为 8 不用再判断当前点的试探方向有几个 同时与迷宫周围是 墙壁这一实际问题相一致 如图 8 1 表示的迷宫是一个 6 8 的迷宫 入口坐标为 1 1 出口坐标为 m n 入口 1 1 0123456789 01111111111 11011101111 21101011111 31010000011 41011101111 51100110001 61011001101 71111111111 出口 6 8 图 8 1 用 maze m 2 n 2 表示的迷宫 迷宫的定义如下 define m 6 迷宫的实际行 define n 8 迷宫的实际列 int maze m 2 n 2 2 试探方向 在上述表示迷宫的情况下 每个点有 8 个方向去试探 如当前点的坐标 x y 与其相 邻的 8 个点的坐标都可根据与该点的相邻方位而得到 如图 8 2 所示 因为出口在 m n 因此试探顺序规定为 从当前位置向前试探的方向为从正东沿顺时针方向进行 为了简化 问题 方便的求出新点的坐标 将从正东开始沿顺时针进行的这 8 个方向的坐标增量放在 一个结构数组 move 8 中 在 move 数组中 每个元素有两个域组成 x 横坐标增量 y 纵坐标增量 move 数组如图 8 3 所示 Move 数组定义如下 typedef struct int x y item item move 8 这样对 move 的设计会很方便地求出从某点 x y 按某一方向 v 0 v 5 8 2 5 7 0 5 6 0 4 5 1 top 3 6 03 6 3 3 5 03 5 0 3 4 03 4 0 3 3 03 3 0 2 2 12 2 1 1 1 11 1 1 出栈 求出下一个要试探的方向 d while 还有剩余试探方向时 if d 方向可走 则 x y d 入栈 求新点坐标 i j 将新点 i j 切换为当前点 x y if x n 结束 else 重置 d 0 else d 算法如下 int path maze move int maze m n item move 8 SeqStack s datetype temp int x y d i j temp x 1 temp y 1 temp d 1 s Push temp while s Empty s Pop temp x temp x y temp y d temp d 1 while d 8 i x move d x j y move d y if maze i j 0 temp x y d s Push temp x i y j maze x y 1 if x m 迷宫有路 else d 0 else d while ddata ch createbintree createbintree 2 用前序 中序两种不同的方法进行遍历 这两种遍历可分别用递归方式和非递 归方式实现 其递归方式相当简捷 在此只给出中序遍历的非递归算法 template void BinaryTree PreOrder stack BinTreeNode st BinTreeNode p root do while p NULL cout data st Push p p p leftChild if St length 0 st pop p p p rightChild while p NULL st length 0 3 交换二叉树中所有结点的左 右子树 交换过程中 同样需要借助一个指针栈来实现 最先交换二叉树中树根结点的左 右子树 然后再在其左 右子树中分别递归调用该函数 直到所有的结点的左 右 子树都完成交换为止 4 用前序 中序两种不同的方法进行遍历交换左 右子树之后的二叉树 其实现过程 同 2 测试数据测试数据 ABC DE G F 其中 表示空格字符 则输出结果为 先序 ABCDEGF 中序 CBEGDFA 实现提示实现提示 树是较基本线性表和特殊线性表稍微复杂一点的数据结构 它的复杂性体现在数据元素 的输入和输出形式上更为多样 由于数据元素之间的关系稍微较线性表复杂 因此在数据 的组织形式和输入形式的表达上一定要吻合 否则很容易创建出不符合要求的树 选作内容选作内容 采用非递归算法实现二叉树遍历 9 2 29 2 2 打印二叉树结构打印二叉树结构 问题描述问题描述 按凹入表形式横向打印二叉树结构 即二叉树的根在屏幕的最左边 二叉树的左子树 在屏幕的下边 二叉树的右子树在屏幕的上边 例如 图 9 1 一个图 测试数据测试数据 由学生依据软件工程的测试技术自己确定 注意测试边界数据 如空二叉树 实现提示实现提示 1 利用 RDL 遍历方法 2 利用结点的深度控制横向位置 实验项目实验项目 1010 图遍历演示图遍历演示 10 110 1 实验目的实验目的 1 掌握图的邻接矩阵 邻接表 十字链表等不同存储形式的表示方法 2 掌握图的两种不同遍历方法的基本思想并能编程实现 3 掌握构造最小生成树的两种算法 即 Prim 算法和 Kruscal 算法的思想 并 能编程实现 4 能够灵活运用图的相关算法解决相应的实际问题 10 210 2 实验内容实验内容 问题描述问题描述 很多涉及图上操作的算法都以图的遍历操作为基础 试写一个程序 演示在连通 的无向图上访问全部结点的操作 基本要求基本要求 以邻接多重表为存储结构 实现连通无向图的深度优先遍历和广度优先遍历 以用 户指定的结点为起点 分别输出每种遍历下结点访问序列和相应生成树的边集 算法描述算法描述 从已给的连通图中某一顶点出发 沿着一些边访遍图中所有的顶点 且使每个顶 点仅被访问一次 就叫做图的遍历 Graph Traversal 图中可能存在回路 且图 的任一顶点都可能与其它顶点相通 在访问完某个顶点之后可能会沿着某些边又回到 了曾经访问过的顶点 为了避免重复访问 可设置一个标志顶点是否被访问过的辅助 数组 visited 它的初始状态为 0 在图的遍历过程中 一旦某一个顶点 i 被访 问 就立即让 visited i 为 1 防止它被多次访问 DFS 在访问图中某一起始顶点 v 后 由 v 出发 访问它的任一邻接顶点 w1 再 从 w1 出发 访问与 w1 邻 接但还没有访问过的顶点 w2 然后再从 w2 出发 进行 类似的访问 如此进行下去 直至到达所有的邻接顶点都被访问过的顶点 u 为止 接着 退回一步 退到前一次刚访问过的顶点 看是否还有其它没有被访问的邻接顶 点 如果有 则访问此顶点 之后再从此顶点出发 进行与前述类似的访问 如果没 有 就再退回一步进行搜索 重复上述过程 直到连通图中所有顶点都被访问过为止 图的深度优先搜索算法描述如下 void Graph DFS visited new int n 创建数组 visited for int i 0 i n i visited i 0 访问标记数组 visited 初始化 for int i 0 i n i if visited i 0 DFS i visited delete visited 释放 visited viod Graph DFS const int v int visited cout GetValue v 访问顶点 v visited v 1 顶点 v 作访问标记 int w GetFirstNeighbor v 取 v 的第一个邻接顶点 w while w 1 若邻接顶点 w 存在 if visited w DFS w visited 若顶点 w 未访问过 递归访问顶点 w w GetNextNeighbor v w 取顶点 v 的排在 w 后面的下一个邻接顶点 使用广度优先搜索在访问了起始顶点 v 之后 由 v 出发 依次访问 v 的各个未 曾被访问过的邻接顶点 w1 w2 wt 然后再顺序访问 w1 w2 wt 的所有还未被 访问过的邻接顶点 再从这些访问过的顶点出发 再访问它们的所有还未被访问过的 邻接顶点 如此做下去 直到图中所有顶点都被访问到为止 广度优先搜索是一种分层的搜索过程 每向前走一步可能访问一批顶点 不像深 度优先搜索那样有往回退的情况 因此 广度优先搜索不是一个递归的过程 其算法 也不是递归的 为了实现逐层访问 算法中使用了一个队列 以记忆正在访问的这一层和上一层 的顶点 以便于向下一层访问 与深度优先搜索过程一样 为避免重复访问 需要一 个辅助数组 visited 给被访问过的顶点加标记 图的广度优先搜索算法描述如下 void Graph BFS const int v visited new int NumCertices 创建 visited for int i 0 i NumVertices i visited i 0 visited 初始化 cout GetValue v visited v 1 Queue q q EnQueue v 访问 v 进队列 while q IsEmpty 队空搜索结束 v q DeQueue 不空 出队列 int w GetFirstNeighbor v 取顶点 v 的第一个邻接顶点 w while w 1 若邻接顶点 w 存在 if visited w 若该邻接顶点未访问过 cout GetValue w 访问 visited w 1 q EnQueue w 进队 w GetNextNeighbor v w 取顶点 v 的排在 w 后面的下一邻接顶点 重复检测 v 的所有邻接顶点 delete visited 测试数据测试数据 对下图进行遍历 给出遍历后的结果 图 10 1 一个无向图 G1 实现提示实现提示 设图的结点不超过 30 个 每个结点用一个编号表示 如果一个图有 n 个结点 则它们编 号分别为 1 2 3 n 通过输入图的全部边输入一个图 每条边为一个数对 可 以对边的输入顺序作出某种限制 注意 生成树的边是有向边 不能颠倒顺序 选作内容选作内容 1 借助于栈类型 用非递归算法实现深度优先遍历 2 以邻接表为存储结构 建立深度优先生成树和广度优先生成树 V1 V2V3 V4V5V6V7 V8 实验项目实验项目 1111 二叉排序树二叉排序树 11 111 1 实验目的实验目的 掌握树表查找中二叉排序树查找 平衡二叉树查找的查找思想 并能用高级语言实现 11 211 2 实验内容实验内容 问题描述问题描述 从键盘读入一组数据 建立二叉排序树并对其进行查找 遍历 格式化打印等有 关操作 基本要求基本要求 建立二叉排序树并对其进行查找 包括成功和不成功两种情况 并给出查找长度 实现动态查找表的三种基本功能 查找 插入和删除 算法描述算法描述 算法的关键过程实际上就是二叉排序树的插入 删除和查找三个过程 创建可以 归结到插入操作中 首先分析二叉排序树的插入运算 由于二叉排序树中所有结点都有一个大小关系 因此 每个结点必须在二叉排序树中寻找合适位置 创建二叉排序树就是从一棵空二 叉排序树开始进行插入操作 第一步就是创建一个根结点 第二步就是将其它结点插 入到二叉排序树合适的位置 插入算法描叙如下 inserthelp BinNode subroot const Elem if EEComp lt val subroot val subroot setLeft inserthelp subroot left val else subroot setRight inserthelp subroot right val Return subtree with node inserted return subroot 查找是关键字不断比较的过程 第一次比较是与二叉排序树的根结点比较 如果比根 结点小则在左子树中继续查找 如果比根结点大则在右子树中继续查找 如果与根结点相 等则查找成功 算法描述如下 template bool BST findHelp BinNode subroot constKey else if KEComp lt K subroot val return findHelp subroot left K e else if KEComp gt K subroot val return findHelp subroot rightt K e else e subroot val return true 二叉排序树中的删除操作稍有复杂 删除操作应遵循如下原则 a 删除结点所断开的链要重新接起来 b 删除链接后仍是 BST c 重新链接后树的高度不增加 删除采取方法是 1 被删结点为叶子 只需将双亲结点的相应指针置为空 2 被删结点无右子树 拿左孩子结点顶替它的位置 3 被删结点无左子树 拿右孩子结点顶替它的位置 4 被删结点左右子树都有 在右子树中找中序遍历第一个结点 用它的值填补 到被删结点 然后再来删这个结点 5 结点删除是一个递归的过程 算法描述如下 template BinTreeNode BST deletemin BinTreeNode subroot BinTreeNode return subroot right else subroot SetLeft deletemin subroot left min template BinTreeNode BST removehelp BinTreeNode subroot constKey else if KEComp lt K subroot val subroot setLeft removehelp subroot left K t else if KEComp gt K subroot val subroot setRight removehelp subroot right K t else BinTreeNode temp t subroot if subroot left NULL subroot subroot right else if subroot right NULL subroot subroot left else subroot setRight deletemin subroot right temp Elem te subroo val subroot setVal temp val temp setVal te t temp r