《数据结构和算法设计-第章 栈和队列lhf.pptx》由会员分享，可在线阅读，更多相关《数据结构和算法设计-第章 栈和队列lhf.pptx（70页珍藏版）》请在金锄头文库上搜索。
1、第三章栈和队列 3 1栈3 2栈的应用举例3 3栈与递归3 4队列 3 1栈 3 1 1栈的概念一 什么是栈 栈是限定仅能在表尾一端进行插入 删除操作的线性表 a1 a2 ai 1 ai ai 1 an 插入 删除 能进行插入和删除的一端称为栈顶 另一端称为栈底 称插入操作为进栈 删除操作为出栈 进栈出栈操作只能在栈顶进行 3 1栈 栈的特点后进先出 第一个进栈的元素在栈底最后一个进栈的元素在栈顶第一个出栈的元素为栈顶元素最后一个出栈的元素为栈底元素 3 1栈 二 栈的基本操作1 初始化操作InitStack S 功能 构造一个空栈S 2 销毁栈操作DestroyStack S 功能 销毁一个
2、已存在的栈 3 置空栈操作ClearStack S 功能 将栈S置为空栈 4 取栈顶元素操作GetTop S e 功能 取栈顶元素 并用e返回 3 1栈 二 栈的基本操作5 进栈操作Push S e 功能 元素e进栈 6 退栈操作Pop S e 功能 栈顶元素退栈 并用e返回 7 判空操作StackEmpty S 功能 若栈S为空 则返回True 否则 栈不空返回False 3 1栈 3 1 2栈的顺序存储和实现 一 栈的顺序存储结构 defineSTACK INIT SIZE100 栈存储空间的初始分配量 defineSTACKINCREMENT10 空间的分配增量typedefstruct
3、 ElemType base 栈空间基址ElemType top 栈顶指针intstacksize 当前分配的栈空间大小 SqStack 3 1栈 3 1 2栈的顺序存储和实现 顺序栈的图示 S stacksizeS topS base 100 约定栈顶指针指向栈顶元素的下一个位置 3 1栈 3 1 2栈的顺序存储和实现 top base 空栈 BCDE进栈 EDC出栈 称为 栈满 空栈top base栈满top base stacksize 无可分配空间 3 1栈 不可扩充栈的操作 栈空 栈顶指针top 指向实际栈顶后的空位置 初值为base 进栈 A 栈满 B C D E 设数组大小为Mt
4、op M 栈满 此时入栈 则上溢 overflow 栈空 top base 栈空 此时出栈 则下溢 underflow 出栈 3 1栈 可扩充栈的操作 栈顶指针top 指向实际栈顶后的下一个位置 初值为top base 进栈 A 出栈 栈当前空间不足 需扩充 B C D E 设栈的初始分配量为Stacksize STACK INIT SIZE 若top Stacksize 栈满 此时入栈 则需扩充栈空间 每次扩充STACK INCREMENT 若无可利用的存储空间 则上溢 overflow 栈空 若top base 栈空 此时出栈 则下溢 underflow base 栈空 top 3 1栈
5、二 顺序栈基本操作的算法1 初始化操作InitStack SqStack S 参数 S是存放栈的结构变量功能 建一个空栈S 100 3 1栈 初始化操作算法StatusInitStack SqStack InitStack 2 销毁栈操作DestroyStack SqStack S 功能 销毁一个已存在的栈 100 3 1栈 StatusDetroyStack SqStack DetroyStack 销毁操作算法 3 1栈 3 置空栈操作ClearStack SqStack S 功能 将栈S置为空栈 3 1栈 StatusClearStack SqStack ClearStack 置空操作算法
6、 3 1栈 an 4 取栈顶元素操作GetTop SqStackS ElemType e 功能 取栈顶元素 并用e返回 3 1栈 StatusGetTop SqStackS ElemType GetTop 取栈顶元素操作算法 3 1栈 5 进栈操作Push SqStack S ElemTypee 功能 元素e进栈 3 1栈 进栈操作算法StatusPush SqStack Push 3 1栈 6 出栈操作Pop SqStack S ElemType e 功能 栈顶元素退栈 并用e返回 3 1栈 StatusPop SqStack Pop 出栈操作算法 3 1栈 栈的链式存储结构 也称链栈 栈顶
7、 栈底 在前面学习了线性链表的插入 删除操作算法 不难写出链式栈初始化 进栈 出栈等操作的算法 3 1 3栈的链式存储和实现 3 1栈 小结1 栈是限定仅能在表尾一端进行插入 删除操作的线性表2 栈的元素具有后进先出的特点3 栈顶元素的位置由一个称为栈顶指针的变量指示 进栈和出栈操作都要修改栈顶指针 3 1栈 3 2栈的应用举例 数制转换 例如 1348 10 2504 8 其运算过程如下 NNdiv8Nmod8134816841682102125202 计算顺序 输出顺序 计算时从低位到高位顺序产生八进制数的各个数位 输出显示时按从高位到低位的顺序输出 数制转换算法 voidconversi
8、on 对于输入的任意一个非负十进制整数 打印输出与其等值的八进制数InitStack S 建空栈scanf d N 输入一个非负十进制整数while N N不等于零循环Push S N 8 N 8第一个余数进栈N N 8 整除运算 while StackEmpty S Pop S e printf d e 输出存放在栈中的八制数位DestroyStack S erorrinbook conversion 设立一个输入缓冲区 用以接受用户输入的一行字符 然后逐行存入用户数据区 并假设 为退格符 为退行符 在用户输入一行的过程中 允许用户输入出差错 并在发现有误时可以及时更正 合理的作法是 行编辑
9、过程分析 则实际有效的是下列两行 while s putchar s 假设从终端接受了这样两行字符 whli ilr e s s outcha putchar s while ch EOF 从终端接收下一个字符 ClearStack S 重置S为空栈if ch EOF ch getchar 为下一行准备 while ch EOF EOF为全文结束符 将从栈底到栈顶的栈内字符传送至调用过程的数据区 1 问题的提出从键盘一次性输入一串算术表达式 给出计算结果 栈的应用举例 表达式求值 3 2栈的应用举例 2 表达式的构成操作数 运算符 界符 1 2 3 4 常数 3 2栈的应用举例 3 表达式的求
10、值 例 5 6 1 2 4按照四则运算法则 上述表达式的计算过程为 5 6 1 2 4 5 6 3 4 5 18 4 23 4 19 4 算符优先关系表表达式中任何相邻运算符 1 2的优先关系有 1 2 1的优先级高于 2 注 1 2是相邻算符 1在左 2在右 3 2栈的应用举例 5 算符优先算法 从左向右扫描表达式 遇操作数 保存 遇运算符号 j 与前面的刚扫描过的运算符 i比较 若 i j则说明 i是已扫描的运算符中优先级最高者 可进行运算若 i j则说明括号内的式子已计算完 需要消去括号 5 6 1 2 6 后面也许有优先级更高的算符 后保存的算符优先级高 用两个栈分别保存扫描过程中遇到
11、的操作数和运算符 3 2栈的应用举例 在算符优先算法中 建立了两个工作栈 一个是OPTR栈 用以保存运算符 一个是OPND栈 用以保存操作数或运算结果 算法的基本思想是 1 首先置操作数栈为空栈 表达式起始符 为运算符栈的栈底元素 2 依次读入表达式中每个字符 若是操作数 则进OPND栈 若是运算符 则与OPTR栈的栈顶运算符比较优先级之后作相应操作 直至整个表达式求值完毕 即OPTR栈的栈顶元素和当前读入的字符均为 3 2栈的应用举例 17Oct 表达式求值示意 5 6 1 2 4 5 6 1 2 3 18 23 4 19 5 读入表达式过程 6 1 2 4 19 1 2 3 6 3 18
12、5 18 23 23 4 19 3 2栈的应用举例 算法描述operandTypeEvaluateExpression 算术表达式求值的算符优先算法 设OPTR和OPND分别为运算符栈和运算数栈 OP为运算符 界限符集合 InitStack OPTR Push OPTR InitStack OPND c getchar while c GetTop OPTR if In c OP In c OP 判断c是否为运算符 Push OPND c c getchar 不是运算符则进栈else 3 2栈的应用举例 switch Precede GetTop OPTR c 判定OPTR的栈顶运算符 1与读
13、入的运算符 2 即c 间的优先关系case 新输入的算符c优先级低 即栈顶算符优先权高 出栈并将运算结果入栈OPNDPop OPTR theta Pop OPND b Pop OPND a Push OPND Operate a theta b 进行二元运算a bbreak switch whilereturnGetTop OPND EvaluateExpression 3 2栈的应用举例 递归是很有用的工具 在数学和程序设计等许多领域中都会用到 递归定义 简单说 一个用自己定义自己的概念 称为递归定义 函数的递归调用 就是函数实现中存在自己调用自己的情况 任何一个递归程序都可以通过非递归来程
14、序实现 只是递归程序代码简洁 可读性好 3 3栈与递归 课堂练习 1 向一个栈顶指针为top的链栈中插入一个p所指的结点时 其操作步骤为 b a top next p b p next top next top next p c p next top top p d p next top top top next 2 对于栈操作数据的原则是 b a 先进先出b 后进先出c 后进后出d 部分顺序3 若已知一个栈的入栈序列是1 2 3 n 其输出序列为p1 p2 p3 pn 若pn n 则pi是 d a ib n ic n i 1d 不确定3 若已知一个栈的入栈序列是1 2 3 n 其输出序列为p
15、1 p2 p3 pn 若p1 n 则pi是 c a ib n ic n i 1d 不确定 3 4 1队列的概念一 什么是队列 队列是限定仅能在表头进行删除 表尾进行插入的线性表 a1 a2 ai 1 ai ai 1 an 插入 删除 能进行插入的一端称为队尾 能进行删除的一端称为队头 称插入操作为入队 删除操作为出队 3 4队列 a1a2a3an 队头 队尾 出队列 队列的示意图 队列的特点 先进先出 第一个入队的元素在队头最后一个入队的元素在队尾第一个出队的元素为队头元素最后一个出队的元素为队尾元素 入队列 3 4队列 二 队列的基本操作1 初始化操作InitQueue Q 功能 构造一个空
16、队列Q 2 销毁操作DestroyQueue Q 功能 销毁已存在队列Q 3 置空操作ClearQueue Q 功能 将队列Q置为空队列 4 出队操作DeQueue Q e 功能 删除Q的队头元素 5 取队头元素操作GetHead Q e 功能 取队头元素 并用e返回 3 4队列 二 队列的基本操作6 入队操作EnQueue Q e 功能 将元素e插入Q的队尾 7 判空操作QueueEmpty Q 功能 若队列Q为空 则返回True 否则返回False 3 4队列 3 4 2循环队列 队列的顺序存储和实现一 队列的顺序存储结构 defineMAXSIZE100 最大队列长度typedefstruct ElemType base 初始化时分配存储空间的基址intfront 队头指针 指向队头元素intrear 队尾指针 指向队尾元素的下一个位置 SqQueue 队头 队尾指针是用整型实现的 3 4队列 a 空队列 b J1 J2和J3相继入队列 c J1和J2相继出队 d J4 J5和J6相继入队之后 J3出队 Q front Q rear均为整数用箭头指示只是为了直观 3 4队列 3
