《数据结构(清华版)》3第三章 栈和队列.ppt_第1页
《数据结构(清华版)》3第三章 栈和队列.ppt_第2页
《数据结构(清华版)》3第三章 栈和队列.ppt_第3页
《数据结构(清华版)》3第三章 栈和队列.ppt_第4页
《数据结构(清华版)》3第三章 栈和队列.ppt_第5页
已阅读5页,还剩43页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第三章栈和队列 栈和队列是两种特殊的线性表 是操作受限的线性表 称限定性DS3 1栈 stack 栈的定义和特点定义 限定仅在表尾进行插入或删除操作的线性表 表尾 栈顶 表头 栈底 不含元素的空表称空栈特点 先进后出 FILO 或后进先出 LIFO 栈的存储结构顺序栈实现 一维数组s M 栈顶指针top 指向实际栈顶后的空位置 初值为0 进栈 A 出栈 栈满 B C D E F 设数组维数为Mtop 0 栈空 此时出栈 则下溢 underflow top M 栈满 此时入栈 则上溢 overflow 栈空 入栈算法 出栈算法 在一个程序中同时使用两个栈 链栈 结点定义 入栈算法 出栈算法 typedefstructnode intdata structnode link JD 栈的应用过程的嵌套调用 例递归的执行情况分析 递归过程及其实现递归 函数直接或间接的调用自身叫 实现 建立递归工作栈 voidprint intw inti if w 0 print w 1 for i 1 i w i printf 3d w printf n Ch3 10 c 运行结果 1 2 2 3 3 3 递归调用执行情况如下 TowerofHanoi问题问题描述 有A B C三个塔座 A上套有n个直径不同的圆盘 按直径从小到大叠放 形如宝塔 编号1 2 3 n 要求将n个圆盘从A移到C 叠放顺序不变 移动过程中遵循下列原则 每次只能移一个圆盘圆盘可在三个塔座上任意移动任何时刻 每个塔座上不能将大盘压到小盘上 解决方法 n 1时 直接把圆盘从A移到Cn 1时 先把上面n 1个圆盘从A移到B 然后将n号盘从A移到C 再将n 1个盘从B移到C 即把求解n个圆盘的Hanoi问题转化为求解n 1个圆盘的Hanoi问题 依次类推 直至转化成只有一个圆盘的Hanoi问题算法 执行情况 递归工作栈保存内容 形参n x y z和返回地址返回地址用行编号表示 main intm printf Inputnumberofdisks scanf d 8 9 main intm printf Inputthenumberofdisksscanf d 8 9 main intm printf Inputthenumberofdisksscanf d 8 9 main intm printf Inputthenumberofdisksscanf d 8 9 回文游戏 顺读与逆读字符串一样 不含空格 1 读入字符串2 去掉空格 原串 3 压入栈4 原串字符与出栈字符依次比较若不等 非回文若直到栈空都相等 回文 多进制输出 字符串 madamimadam 表达式求值 中缀表达式后缀表达式 RPN a b cab c a b cabc a b c d eabc d e 中缀表达式 操作数栈和运算符栈 例计算2 4 3 6 后缀表达式求值步骤 1 读入表达式一个字符2 若是操作数 压入栈 转43 若是运算符 从栈中弹出2个数 将运算结果再压入栈4 若表达式输入完毕 栈顶即表达式值 若表达式未输入完 转1 例计算4 3 5 后缀表达式 435 地图四染色问题 1 2 2 3 4 1 4 3 3 4 2 3 1 紫色2 黄色3 红色4 绿色 3 2队列队列的定义及特点定义 队列是限定只能在表的一端进行插入 在表的另一端进行删除的线性表队尾 rear 允许插入的一端队头 front 允许删除的一端队列特点 先进先出 FIFO 双端队列 链队列结点定义 typedefstructnode intdata structnode link JD 设队首 队尾指针front和rear front指向头结点 rear指向队尾 入队算法 出队算法 队列的顺序存储结构实现 用一维数组实现sq M J1 J2 J3 设两个指针front rear 约定 rear指示队尾元素 front指示队头元素前一位置初值front rear 1 空队列条件 front rear入队列 sq rear x 出队列 x sq front 存在问题设数组维数为M 则 当front 1 rear M 1时 再有元素入队发生溢出 真溢出当front 1 rear M 1时 再有元素入队发生溢出 假溢出解决方案队首固定 每次出队剩余元素向下移动 浪费时间循环队列基本思想 把队列设想成环形 让sq 0 接在sq M 1 之后 若rear 1 M 则令rear 0 实现 利用 模 运算入队 rear rear 1 M sq rear x 出队 front front 1 M x sq front 队满 队空判定条件 队空 front rear队满 front rear 解决方案 1 另外设一个标志以区别队空 队满2 少用一个元素空间 队空 front rear队满 rear 1 M front 入队算法 出队算法 队列应用举例划分子集问题问题描述 已知集合A a1 a2 an 及集合上的关系R ai aj ai aj A i j 其中 ai aj 表示ai与aj间存在冲突关系 要求将A划分成互不相交的子集A1 A2 Ak k n 使任何子集中的元素均无冲突关系 同时要求分子集个数尽可能少 例A 1 2 3 4 5 6 7 8 9 R 2 8 9 4 2 9 2 1 2 5 6 2 5 9 5 6 5 4 7 5 7 6 3 7 6 3 可行的子集划分为 A1 1 3 4 8 A2 2 7 A3 5 A4 6 9 算法思想 利用循环筛选 从第一个元素开始 凡与第一个元素无冲突的元素划归一组 再将剩下的元素重新找出互不冲突的划归第二组 直到所有元素进组所用数据结构冲突关系矩阵r i j 1 i j有冲突r i j 0 i j无冲突循环队列cq n 数组result n 存放每个元素分组号工作数组newr n 工作过程初始状态 A中元素放于cq中 result和newr数组清零 组号group 1第一个元素出队 将r矩阵中第一行 1 拷入newr中对应位置 这样 凡与第一个元素有冲突的元素在newr中对应位置处均为 1 下一个元素出队若其在newr中对应位置为 1 有冲突 重新插入cq队尾 参加下一次分组若其在newr中对应位置为 0 无冲突 可划归本组 再将r矩阵中该元素对应行中的 1 拷入newr中如此反复 直到9个元素依次出队 由newr中为 0 的单元对应的元素构成第1组 将组号group值 1 写入result对应单元中令group 2 newr清零 对cq中元素重复上述操作 直到cq中front rear 即队空 运算结束 算法描述 R 2 8 9 4 2 9 2 1 2 5 6 2 5 9 5 6 5 4 7 5 7 6 3 7 6 3 算法描述 cq R 2 8 9 4 2 9 2 1 2 5 6 2 5 9 5 6 5 4 7 5 7 6 3 7 6 3 算法描述 cq R 2 8 9 4 2 9 2 1 2 5 6 2 5 9 5 6 5 4 7 5 7 6 3 7 6 3 算法描述 cq R 2 8 9 4 2 9 2 1 2 5 6 2 5 9 5 6 5 4 7 5 7 6 3 7 6 3 算法描述 cq R 2 8 9 4 2 9 2 1 2 5 6 2 5 9 5 6 5 4 7 5 7 6 3 7 6 3 算法描述 cq R 2 8 9 4 2 9 2 1 2 5 6 2 5 9 5 6 5 4 7 5 7 6 3 7 6 3 算法描述 cq R 2 8 9 4 2 9 2 1 2 5 6 2 5 9 5 6 5 4 7 5 7 6 3 7 6 3 算法描述 cq R 2 8 9 4 2 9 2 1 2 5 6 2 5 9 5 6 5 4 7 5 7 6 3 7 6 3 算法描述 cq R 2 8 9 4 2 9 2 1 2 5 6 2 5 9 5 6 5 4 7 5 7 6 3 7 6 3 算法描述 cq R 2 8 9 4 2 9 2 1 2 5 6 2 5 9 5 6 5 4 7 5 7 6 3 7 6 3 算法描述 cq R 2 8 9 4 2 9 2 1 2 5 6 2 5 9 5 6 5 4 7 5 7 6 3 7 6 3 算法描述 cq R 2 8 9 4 2 9 2 1 2 5 6 2 5 9 5 6 5 4 7 5 7 6 3 7 6 3 算法描述 cq R 2 8 9 4 2 9 2 1 2 5 6 2 5 9 5 6 5 4 7 5 7 6 3 7 6 3 算法描述 cq R 2 8 9 4 2 9 2 1 2 5 6 2 5 9 5 6 5 4 7 5 7 6 3 7 6 3 算法描述 cq R 2 8 9 4 2 9 2 1 2 5 6 2 5 9 5 6 5 4 7 5 7 6 3 7 6 3 算法描述 cq R 2 8 9 4 2 9 2 1 2 5 6 2 5 9 5 6 5 4 7 5 7 6 3 7 6 3 算法描述 cq R 2 8 9 4 2 9 2 1 2 5 6 2 5 9 5 6 5 4 7 5 7 6 3 7 6 3 算法描述 cq R 2 8 9 4 2 9 2 1 2 5 6 2 5 9 5 6 5 4 7 5 7 6

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论