c++课件栈和队列.ppt

栈栈的应用队列队列的应用 第三章栈和队列 栈和队列是两种特殊的线性表 是操作受限的线性表 称限定性DS 3 1栈 stack 1 栈的定义和特点定义 限定仅在表尾进行插入或删除操作的线性表 通常称插入 删除的这一端 即表尾为栈顶 Top 另一端表头为栈底 Base 不含元素的空表称空栈 特点 先进后出 FILO 或后进先出 LIFO 2 栈的存储结构 1 顺序栈由于栈是运算受限的线性表 因此线性表的存储结构对栈也适应 栈的顺序存储结构简称为顺序栈 可用数组来实现顺序栈 因为栈底位置是固定不变的 所以可以将栈底位置设置在数组的两端的任何一个端点 栈顶位置是随着进栈和退栈操作而变化的 故需用一个变量top来指示当前栈顶的位置 通常称top为栈顶指针 栈顶指针top 指向实际栈顶后的空位置 进栈 A 出栈 栈满 B C D E F 栈空 设栈的初始容量为Stacksizetop base 栈空 此时出栈则下溢 underflow top base Stacksize 栈满 此时入栈则上溢 overflow 顺序栈的存储 顺序存储栈的结点类型的定义 defineSTACK INIT SIZE100 存储空间初始分配量 defineSTACKINCREMENT10 存储空间分配增量typedefstruct SElemType base 栈底指针SElemType top 栈顶指针intstacksize 当前已分配的存储空间 sqStack 顺序栈入栈算法 Push sqStack 在一个程序中同时使用两个栈 顺序栈出栈算法StatusPop sqStack 例1 多进制输出 例1的解法 nndiv8nmod81591971923202 voidconversion 教材48页initstack s 构造空栈 见教材47页scanf n while n push s n 8 入栈n n 8 while Stackempty s 判断是否为空栈 见教材46页 pop s e 出栈 e为出栈元素printf d e 例2 假设以I和O分别表示入栈和出栈 栈的初态和终栈均为空 入栈和出栈的操作序列可表示为仅由I和O组成的序列 下列所示的序列中 不合法的是 A IOIIOIOOB IOOIOIIOC IIOOIOIOD IIIOOIOO B 例3 一个栈的入栈序列为a b c d e 则出栈的不可能序列为 A edcbaB decbaC dceabD abcde C 例4 设有一顺序栈S 元素s1 s2 s3 s4 s5 s6依次入栈 如果6个元素出栈的顺序是s2 s4 s3 s6 s5 s1 则栈的容量至少应该是 A 2B 3C 5D 6 B 2 栈的存储结构 2 链栈 链栈无栈满问题 空间可扩充插入与删除仅在栈顶处执行链栈的栈顶在链头适合于多栈操作 结点定义 typedefintdatatype typedefstructnode datatypedata structnode link JD 入栈算法 出栈算法 回文游戏 顺读与逆读字符串一样 不含空格 1 读入字符串2 去掉空格 原串 3 压入栈4 原串字符与出栈字符依次比较若不等 非回文若直到栈空都相等 回文 字符串 madamimadam 3 栈的应用 表达式求值 前提规则见教材52 53页 读一个字符 如为操作数 直接入到操作数栈 否则即为运算符 需判断 1 如当前运算符高于栈顶运算符 入到运算符栈 2 如当前运算符低于栈顶运算符 栈顶运算符出栈 同时操作数栈出栈两个数与运算符计算 并将结果入栈 并输出到队列 当前运算符再与栈顶运算符比较 3 如当前运算符等于栈顶运算符 且栈顶运算符为 当前运算符为 则脱去括号继续读下一字符 4 如当前运算符等于栈顶运算符 且栈顶运算符为 当前运算符也为 则表达式求值完毕 表达式求值的处理规则 运算符的优先级 当前运算符 栈顶运算符 设两个栈 操作数栈OPND和运算符栈OPTR 例 计算 2 4 3 6 参考书54页例3 7 2 过程的嵌套调用 4 栈的递归和嵌套应用 递归过程及其实现递归 函数直接或间接的调用自身叫 实现 建立递归工作栈 补充 递归的种类1 直接递归 directrecursion 在子程序中直接调用本身 就称为直接递归 2 间接递归 在子程序中调用了另外的子程序 再从另外子程序中调用原来的子程序 则称为间接递归 补充 递归程序和非递归程序的比较 例递归的执行情况分析 voidwrite intw inti if w 0 write w 1 for i 1 i w i printf 3d w printf n 运行结果 1 2 2 3 3 3 递归调用执行情况如下 地图四染色问题 1 2 2 3 4 1 4 3 3 4 2 3 1 紫色2 黄色3 红色4 绿色 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和返回地址返回地址用行编号表示 Hanoi txt main intm printf Inputthenumberofdisks scanf d voidhanoi intn charx chary charz if n 1 move 1 x z 将第1号盘子从A移到C上else hanoi n 1 x z y 将n 1个盘子从A移到B上 借助于Cmove n x z 将第n号盘子从A移到C上hanoi n 1 y x z 将剩下的n 1个盘子从B移到C上 借助于A voidmove inth charc charf printf d c c n h c f 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 0 空队列条件 front rear入队列 sq rear x 出队列 x sq front 存在问题设数组维数为M 则 当front 0 rear M时 再有元素入队发生溢出 真溢出当front 0 rear M时 再有元素入队发生溢出 假溢出解决方案队首固定 每次出队剩余元素向下移动 浪费时间循环队列基本思想 把队列设想成环形 让sq 0 接在sq M 1 之后 若rear 1 M 则令rear 0 实现 利用 模 运算入队 sq rear x rear rear 1 M 出队 x sq front front front 1 M 队满 队空判定条件 队空 front rear队满 front rear 解决方案 1 另外设一个标志以区别队空 队满2 队列中留一个空位 队空 front rear队满 rear 1 M front 入队算法 voiden cycque intsq intfront intrear intx if rear 1 M front 对满printf overflow else sq rear x rear rear 1 M 尾指针后移 出队算法 intdl cycque intsq intfront intrear int q if front rear 对空return 0 返回出队失败标志else q sq front 存储出队元素front front 1 M 头指针后移一位return 1 返回出队成功标志 例5 在具有n个单元的循环队列中 队满时共有 个元素 n 1 例6 若用单链表来表示队列 则应该选用 带尾指针的循环链表带头指针的循环链表C 带尾指针的非循环链表D 带头指针的非循环链表 A 队列应用举例划分子集问题问题描述 已知集合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