数据结构3栈和队列.ppt

第三章栈和队列 内容提要 本课主题 栈的表示与实现 栈的应用 队列的表示与实现 队列的应用教学目的 栈的数据类型定义 栈的顺序存储表示与实现 掌握栈的应用方法 理解栈的重要作用 掌握队列的类型定义 掌握链队列的表示与实现方法教学重点 顺序栈的表示与实现 栈与递归 顺序队列的表示与实现教学难点 栈的定义 栈与递归 栈的应用 顺序队列的表示与实现 3 1栈 栈的由来函数调用 中断的计算机实现 P56 3 1 1栈的概念 一 栈的定义栈 限定仅在表尾进行插入或删除操作的线性表 形象的例子 仓库物流 车辆进出只有一对铁轨 一个出口的火车站 建房 典型应用 函数调用 递归调用的实现 递归问题的非递归法求解 括号匹配 表达式求值 语句编译 迷宫问题求解 3 1 1栈的概念 栈的表尾称为栈顶 表头称为栈底 不含元素的空表称为空栈 栈的特点 栈的特点 后进先出 lastinfirstout LIFO 提问 向某栈输入了三个元素 已知元素输入的先后顺序是A B C 那么该栈的输出序列可能有哪些 反过来 如果输出序列是A B C呢 CBA ABC ACB BAC BCA 无CAB 3 1 2栈的抽象数据类型定义 ADTStack 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R ai D i 2 n 基本操作 InitStack S 构造一个空栈SDestroyStack S 栈S存在 则栈S被销毁ClearStack S 栈S存在 则清为空栈StackEmpty S 栈S存在 栈空则返回TRUE 否则返回FALSEStackLength S 栈S存在 则返回S的元素个数 即栈的长度GetTop S e 栈S存在且非空 则返回S的栈顶元素Push S e 插入元素e为新的栈顶元素 俗称推入操作或压入操作Pop S e 删除栈顶元素并用e返回其值 俗称弹出操作StackTraverse S visit 遍历栈S ADTStack 3 1 3顺序栈 栈的顺序存储及其实现 1 顺序栈 利用一组地址连续的存储单元依次存放从栈底到栈顶的所有数据元素 同时附设栈底指针和栈顶指针指示栈底元素和栈顶元素的位置 顺序栈的类C语言实现 2 顺序栈的类C语言实现 defineSTACK INIT SIZE100 注意P46页多出分号 defineSTACKINCREMENT10structSqStack ElemType base 栈底指针 指向栈底元素 也即数组基地址 ElemType top 栈顶指针 指向栈顶元素的下一个位置 有的书上表示的是当前栈顶元素的位置 便于判断栈空 栈满和计算表长intstacksize 栈当前可使用的最大容量 顺序栈的类C语言实现 栈底元素 base 栈顶元素 top 1 栈空判断条件 top base 或top base 0 栈满判断条件 top base stacksize 栈的长度 top base注意不同的课本上top的含义略有不同 导致判断条件也略有不同 初始化 StatusInitStack SqStack InitStack 插入 StatusPush SqStack Push 删除 StatusPop SqStack Pop 销毁 栈空 StatusDestroyStack SqStack StackEmpty 该函数可简化 获取栈顶元素 StatusGetTop SqStackS ElemType GetTop 3 1 4链栈 栈的链式存储及其实现 注意base指向链栈的头结点而非首元素 top指向尾结点 而非其 下一个 元素 栈空判断条件 base topbase next NULLtop next NULL错误 3 2栈的应用 数制转换 一 栈的应用之一 数制转换 P48 将十进制数转换成其它进制数的方法 66 8 8余28 8 1余0结果 66 10 102 81 8 0余1结论 后求出的余数先写 先求得的余数后写 符合栈的后入先出性质 故可用栈来实现数制转换 3 2栈的应用 行编辑程序 二 栈的应用之二 行编辑程序 P49 用户在终端输入字符不可能不出错 例如 用户在终端上输入whli ilr e s s 其中 为退格符 为退行符 则实际输入的数据应为while s 行编辑程序的功能 接受用户从终端输入的数据 并存入缓冲区 然后程序把缓冲区信息转换为正确的数据存入数据区 3 2栈的应用 表达式求值 三 栈的应用之三 括号匹配 P49 四 栈应用之四 表达式求值 P52 高级语言 如C 允许程序中含表达式 编译器应能分析表达式并求出结果 如 a 1 2 3 4 5 表达式的要素 运算符 操作数 优先级 界限符算法基本思想 1 算法需要两个栈 操作数栈和运算符栈 2 首先置操作数栈为空栈 表达式起始符 为运算符栈的栈底元素 3 依次读入表达式中每个字符 若是操作数则进操作数栈 若是运算符 则和运算符栈的栈顶运算符比较优先权并作相应操作 直至整个表达式求值完毕 3 2栈的应用 递归问题 五 栈应用子五 迷宫求解 P50 六 栈应用之六 递归问题的非递归算法递归 本章下一节 第六章中二叉树遍历的非递归算法 3 3栈与递归 递归问题举例 阶乘函数 数列递推函数 汉诺塔问题递归函数 直接或间接调用自己的函数 本质 根据小规模结论探讨大规模问题的解 注意 递归函数一定要有退出条件 其时间复杂度 空间复杂度的计算方法也很特殊 参见第一章 递归问题求解 利用递归函数很容易求解递归问题 如阶乘函数 利用栈可以实现递归问题的非递归算法 栈的一个重要用途就是在程序设计语言中通过非递归算法求解递归问题 递归的用途与栈 递归的用途 实现递归问题实现 非递归 问题 如顺序表 链表的处理 逻辑上链表可看作是首元素和剩下的元素组成的链表组成的 这是一个递归形式的定义 因此算法上就可以用递归函数实现 但效率不一定会提高 参见recursion cpp提问 该程序相当于实现了那种线性结构 如何通过递归函数实现load 函数 3 4队列 一 队列的定义 队列 只允许在表的一端插入元素 在另一端删除元素的线性表 形象的例子 日常生活中的排队 最早入队的最早离开 车辆进站 任务安排 进程管理 网络数据传输 离散事件模拟 3 4 1队列的概念 在队列中 允许插入的的一端叫队尾 允许删除的一端称为队头 队列的特点 先进先出 firstinfirstout FIFO 3 4 2队列的抽象数据类型定义 ADTQueue 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R ai D i 2 n 基本操作 InitQueue Q 构造一个空队列QDestroyqueue Q 队列Q存在则销毁QClearQueue Q 队列Q存在则将Q清为空队列QueueEmpty Q 队列Q为空队列则返回TRUE 否则返回FALSEQueueLength Q 队列Q存在 返回Q的元素个数 即队列的长度GetHead Q e Q为非空队列 用e返回Q的队头元素EnQueue Q e 队列Q存在 插入元素e为Q的队尾元素DeQueue Q e Q为非空队列 删除Q的队头元素 并用e返回其值QueueTraverse Q vivsit 遍历队列Q ADTQueue 3 4 3链队 队列的链式表示和实现 用链表表示的队列简称为链队列 链队列需要两个指针分别指向头结点和队尾 队列为空的判断条件 front rearfront next NULLrear next NULL 错误 链队列表示和实现 structQNode 定义数据元素类型 结点类型 QElemTypedata 元素的数据信息QNode next 后继元素的指针 structLinkQueue 定义队列类型 QNode front 队头指针 指向链队头结点 即首元素前驱结点QNode rear 队尾指针 指向队尾元素 初始化 StatusInitQueue LinkQueue 插入 StatusEnQueue LinkQueue 删除 略修改P62程序 StatusDeQueue LinkQueue 销毁 修改P62程序 StatusDestroyQueue LinkQueue 3 4 4循环队列 队列的顺序表示和实现 顺序队列 使用连续内存空间表示队列所存在的问题 顺序队列的问题和解决办法 改进办法 循环队列采用循环结构以节省空间 其中 实际存储位置 理论存储位置 MAXQSIZE少用一个元素空间 以便区分空队和满队 循环队列的类C语言实现 defineMAXQSIZE100 最大队列长度structSqQueue QElemType base 应当定义为静态数组结构base MAXQSIZE 可简化操作 P64 intfront 队头指针 游标 指向队头元素intrear 队尾指针 游标 指向队尾元素的下一个位置 循环队列的类C语言实现 队头元素 注意不是Q base 0 Q base front 队尾元素 注意不是Q base Q rear 1 更不是Q base Q rear Q base Q rear 1 MAXQSIZE MAXQSIZE 队空判断条件 front rear队满判断条件 rear 1 MAXQSIZE front rear 1 front MAXQSIZE 0表长 注意不是rear front rear front MAXQSIZE MAXQSIZE 注意 不同的课本上front rear的含义略有不同 会导致判断条件略有不同 初始化 StatusInitQueue SqQueue 插入 StatusEnQueue SqQueue 删除 StatusDeQueue SqQueue 获取队列长度 intQueueLength SqQueueQ return Q rear Q front MAXQSIZE MAXQSIZE StatusQueueEmpty SqQueueQ if Q rear Q front returnTRUE elsereturnFALSE 该函数可简化 3 4 5队列的应用 1 任务安排2 进程管理3 离散事件模拟4 二叉树的层次遍历算法 第六章 总结 1 栈的定义 特点 主要操作2 栈的顺序存储结构和链式存储结构3 栈与递归 栈的应用4 队列的定义 特点 主要操作5 队列的顺序存储结构 循环队列 和链式存储结构