数据结构与算法分析-2.ppt

内容提要 1 定义栈与队列抽象数据类型2 讨论栈与队列的顺序表示方法3 讨论栈与队列的链接表示方法 第三章栈与队列 第三章栈与队列3 1栈3 1 1栈抽象数据类型3 1 2栈的顺序表示3 1 3栈的链接表示3 3队列3 3 1队列抽象数据类型3 3 2队列的顺序表示3 3 3队列的链接表示 数据结构 DATASTRUCTURE 3 1栈 第三章栈与队列3 1栈3 1 1栈抽象数据类型3 1 2栈的顺序表示3 1 3栈的链接表示3 3队列3 3 1队列抽象数据类型3 3 2队列的顺序表示3 3 3队列的链接表示 栈的示意图S a1 a2 an 栈是限定插入和删除操作都在表的一端进行的线性表 若栈中无元素 则为空栈 允许插入和删除元素的一端称为栈顶 另一端称为栈底 S a1 a2 an 1 栈的定义 3 1 1栈抽象数据类型 第三章栈与队列3 1栈3 1 1栈抽象数据类型3 1 2栈的顺序表示3 1 3栈的链接表示3 3队列3 3 1队列抽象数据类型3 3 2队列的顺序表示3 3 3队列的链接表示 若给定栈S a1 a2 an 则称a1是栈底元素 an是栈顶元素 若元素a1 an依次进栈时 则出栈的顺序与进栈相反 即元素an必定最先出栈 然后an 1才能出栈 因此 栈是后进先出 LastInFirstOut LIFO 的线性数据结构 2 栈抽象数据类型 ADT3 1栈抽象数据类型ADTStack Data 零个或多个元素的线性序列 a1 a2 an 其最大允许长度为 axStackSize 对于它插入和删除运算都限制在同一端进行 并遵循LIFO原则 Operations Create 建立一个空栈 Destroy 撤消一个栈 IsEmpty 若栈空 则返回true 否则返回false IsFull 若栈满 则返回true 否则返回false Top x 返回栈顶元素 Push x 在栈中插入元素 Pop 从栈中删除栈顶元素 3 栈的C 模板抽象类 程序3 1栈的C 类constintMaxSize 50 templateclassStack public Stack Stack virtualvoidPush constT 3 1 2栈的顺序表示 第三章栈与队列3 1栈3 1 1栈抽象数据类型3 1 2栈的顺序表示3 1 3栈的链接表示3 3队列3 3 1队列抽象数据类型3 3 2队列的顺序表示3 3 3队列的链接表示 1 栈的顺序表示法 程序3 2顺序栈的C 类templateclassSeqStack publicStack public SeqStack intMaxSize SeqStack voidPush constT 2 顺序栈类 3 动态一维数组描述顺序栈类 templateclassSeqStack publicStack public private T s intMaxTop inttop 构造函数templateSeqStack SeqStack intMaxSize MaxTop MaxSize 1 s newT MaxSize top 1 析构函数SeqStack SeqStack intMaxSize delete s 4 在顺序存储表示下实现栈上定义的操作 1 进栈 压入 templatevoidSeqStack Push constT 在函数的实现中使用了一种断言assert 它是C 提供的一种功能 若断言语句的条件满足 则继续执行后面的语句 否则出错处理 终止程序执行 assert语句包括在assert h中 2 出栈 弹出 templatevoidSeqStack Pop assert IsEmpty top 3 取栈顶元素templateTSeqStack Top const assert IsEmpty returns top 3 1 3栈的链接表示 第三章栈与队列3 1栈3 1 1栈抽象数据类型3 1 2栈的顺序表示3 1 3栈的链接表示3 3队列3 3 1队列抽象数据类型3 3 2队列的顺序表示3 3 3队列的链接表示 1 栈的链接表示法 链式栈 链式栈的定义和操作的实现类似于单链表 请自行实现之 不带表头结点的单链表 3 2表达式计算 3 2 1表达式 表达式 由操作数 操作符和界限符组成 中缀表达式 操作符在两个操作数之间的表达式如 a b c d e前缀表达式 操作符放在两个操作数之前的表达式如 a bc de后缀表达式 操作符放在两个操作数之后的表达式 逆波兰表达式 如 abc de 表达式的优先级 表3 1操作符的优先级操作符优先级 7 6 5 4 3 2 1 3 2 2后缀表达式求值 后缀表达式中无括号 求值时无需考虑操作符的优先级 计算简便 故编译程序中常用 表3 2中缀表达式和其后缀表达式中缀表达式后缀表达式a b cab c a b cab c a b c d eabc d e a b c d eabc de 后缀表达式求值 1 从左往右顺序扫描后缀表达式 2 遇到操作数就进栈 3 遇到操作符就从栈中弹出两个操作数 并执行该操作符规定的运算 并将结果进栈 4 重复上述操作 直到表达式结束 弹出栈顶元素即为结果 表3 3后缀表达式的计算扫描项项类型操作栈6操作数6进栈64操作数4进栈462操作数2进栈246 操作符2 4出栈 执行4 2 结果2进栈26 操作符2 6出栈 执行6 2 结果3进栈33操作数3进栈332操作数2进栈233 操作符2 3出栈 执行3 2 结果6进栈63 操作符6 3出栈 执行3 6 结果9进栈9 栈底 例 模拟一个简单的计算器 假设该计算器可以接收浮点数据 但只进行 和 运算 为实现计算器 定义一个计算器类 它的私有数据成员是一个栈 用于存放操作数 计算器类声明如下 include SeqStack h include includeclassCalculator private SeqStackS voidPushOperand doubleop BOOLGetOperands double 成员函数的实现 voidCalculator PushOperand doubleop S Push op BOOLCalculator GetOperands double voidCalculator DoOperator charoper BOOLresult doubleoper1 oper2 result GetOperands oper1 oper2 if result switch oper case S Push oper2 oper1 break case S Push oper2 oper1 break case S Push oper2 oper1 break case if oper1 0 0 cerr Divideby0 endl Clear elseS Push oper2 oper1 break case S Push pow oper2 oper1 break elseClear voidCalculator Run charc doublenewop while cin c c switch c case case case case case DoOperator c break default cin putback c 将字符放回输入流cin newop PushOperand newop break if S IsEmpty cout S Top endl voidCalculator Clear S SetNull 上述类声明存在文件 postcal h 中计算器类的应用程序 include postcal h constintSIZE 20 voidmain CalculatorCal SIZE Cal Run 输入 642 32 结果 9 第三章栈与队列3 1栈3 1 1栈抽象数据类型3 1 2栈的顺序表示3 1 3栈的链接表示3 2表达式计算3 2 1表达式3 2 2后缀表达式求值3 2 3中缀 后缀3 3队列3 3 1队列抽象数据类型3 3 2队列的顺序表示3 3 3队列的链接表示 3 2 3中缀表达式转换为后缀表达式 转换步骤 1 从左到右扫描中缀表达式 遇到 转 6 2 遇到操作数直接输出 3 遇到 则连续出栈输出 直到遇到 为止 出栈但不输出 否则 4 若是其它操作符 则与栈顶的操作符比较优先级 若优先级小于栈顶的优先级 则连续出栈输出 直到大于等于结束 操作符进栈 5 转 1 6 输出栈中剩余操作符 除外 第三章栈与队列3 1栈3 1 1栈抽象数据类型3 1 2栈的顺序表示3 1 3栈的链接表示3 2表达式计算3 2 1表达式3 2 2后缀表达式求值3 2 3中缀 后缀3 3队列3 3 1队列抽象数据类型3 3 2队列的顺序表示3 3 3队列的链接表示 转换的关键 确定操作符的优先级优先级决定操作符是进栈或出栈 操作符在栈内外的优先级应该不同 以体现中缀表达式同优先级操作符从左到右的计算要求 的优先级在栈外最高 但进栈后应该比除 外的操作符低 便于括号内的其它操作符进栈 a b c d e abc de isp 栈内优先级icp 栈外优先级 操作符 icp07421isp01537 扫描项操作栈输出 进栈 aa直接输出 a icp isp 进栈 a icp isp 进栈 abb直接输出 ab icp isp 进栈 abcc直接输出 abc icp isp 进栈 abc dd直接出栈 abc d icp isp 进栈 abc dee直接出栈 abc de 输出栈中剩余操作符 出栈输出 abc de 中缀表达式转换为后缀表达式的算法 constintSIZE 20 voidInfixToPostfix SeqStacks SIZE charch y s Push while cin ch ch if IsDigit ch IsAlpha ch cout ch 操作数直接输出elseif ch 遇到 则连续出栈输出 直到遇到 为止for y s Top s Pop y y s Top s Pop cout y else for y s Top s Pop icp ch isp y y s Top s Pop cout y s Push y s Push ch while s IsEmpty 输出栈中剩余部分 y s Top s Pop if y cout y cout endl 输入 a b c d e O n 结果 abc de 3 3队列 第三章栈与队列3 1栈3 1 1栈抽象数据类型3 1 2栈的顺序表示3 1 3栈的链接表示3 3队列3 3 1队列抽象数据类型3 3 2队列的顺序表示3 3 3队列的链接表示 队列的示意图Q a1 a2 an 队列是限定在表的一端插入 在表的另一端删除的线性表 若队列中无元素 则为空队列 队尾 允许插入元素的一端队头 允许删除元素的另一端Q a1 a2 an 1 队列的定义 3 3 1队列抽象数据类型 第三章栈与队列3 1栈3 1 1栈抽象数据类型3 1 2栈的顺序表示3 1 3栈的链接表示3 3队列3 3 1队列抽象数据类型3 3 2队列的顺序表示3 3 3队列的链接表示 若给定队列Q a1 a2 an 则称a1是队头元素 an是队尾元素 元素a1 an依次入队 出队的顺序与入队相同 a1出队后 a2才能出队 因此又称队列为先进先出 FirstInFirstOut FIFO 的线性数据结构 2 队列抽象数据类型 ADT3 2队列抽象数据类型ADTQueue Data 零个或多个元素的线性序列 a1 a2 an 其最大允许长度为MaxQueueSize 它插入在一端进行 而删除在另一端进行 并遵循FIFO原则 Operations Create 建立一个空队列 Destroy 撤消一个队列 IsEmpty 若队列空 则返回true 否则返回false IsFull 若队列满 则返回true 否则返回false Front 返回队头元素 EnQueue x 在队列中插入元素 Dequeue 从队列中删除队头元素 3 队列的C 模板抽象类 程序3 5队列的C 类templateclassQueue public Queue Queue virtualvoidEnQueue constTx 0 virtualvoidDeQueue 0 virtualTFront 0 virtualboolIsEmpty const 0 virtualboolIsFull const 0 3 3 2队列的顺序表示 第三章栈与队列3 1栈3 1 1栈抽象数据类型3 1 2栈的顺序表示3 1 3栈的链接表示3 3队列3 3 1队列抽象数据类型3 3 2队列的顺序表示3 3 3队列的链接表示 1 队列的顺序表示法 从 d 可以看到 当再有元素需要入队时将产生 溢出 然而队列中尚有三个空元素单元 我们称这种现象为 假溢出 2 循环队列表示法把数组从逻辑上看成是一个头尾相连的环 实现循环队列操作 1 为使入队和出队实现循环 可以利用取余运算符 2 队头指针进一 front front 1 MaxSize 3 队尾指针进一 rear rear 1 MaxSize 4 空队列 当front rear时为空队列 5 满队列 当 rear 1 MaxSize front时为满队列 满队列时实际仍有一个元素的空间未使用 程序3 6循环队列templateclassSeqQueue publicQueue public SeqQueue intMaxQueSize SeqQueue delete q voidEnQueue constT 3 顺序队列类 3 动态一维数组描述顺序队列类 templateclassSeqQueue publicQueue public p