数据结构3剖析.ppt

第三章 栈和队列 重点 栈和队列的抽象数据类型的定义 栈和队列的基本操作算法和复杂性分析 栈的递归实现原理、递归算法执行过程中栈的变化状态 利用栈编写递归程序 栈和队列的区别 递归算法和非递归算法的转换过程 学习应用栈和队列中的基本操作解决实际问题 第三章 栈和队列 难点 栈和队列的基本操作算法和复杂性 栈的递归实现原理、递归算法执行过程中栈的变化状态 利用栈编写递归程序 递归算法和非递归算法的转换过程 应用栈和队列中的基本操作解决实际问题 第三章 栈和队列 学习要点 理解栈的逻辑结构定义及特点 掌握栈的顺序存储结构的描述 重点掌握顺序栈上的基本运算 掌握栈的链式存储结构 掌握描述链栈结构的方法 掌握链栈上的基本运算 了解栈的广泛应用 理解队列的逻辑结构定义及特点 掌握顺序队列存储结构及其描述方法 掌握顺序队列上的基本运算 第三章 栈和队列 理解栈和队列中“上溢”和“下溢”的概念 理解顺序队列出现“假上溢”的原因及其解决方案 掌握循环顺序队列的结构 重点掌握循环队列的基本运算 理解循环顺序队列消除“假上溢”的方法理解队列“满”和“空”的含义 掌握顺序队列和循环队列判断“满”和“空”的条件 掌握队列的链式存储结构及其描述方法 掌握队列的链队列的基本运算 了解队列的广泛应用 第三章 栈和队列 通常称栈和队列是限定插入和删除只能在表的“端点”进行的线性表 3.1 栈 抽象数据类型栈的定义 栈（stack）是限定在表尾一端进行插入或删除操作的线性表。在栈中，允许插入和删除操作的一端称为栈顶（top），而另一端称为栈底（base）。不含元素的栈称为空栈 在栈的运算中，栈的插入操作称为进栈或入栈，栈的删除操作称为退栈或出栈。根据栈的定义，每一次进栈的元素都在原栈顶元素之上，并成为新的栈顶元素；每一次出栈的元素总是当前的栈顶元素，因此最后进栈的元素总是最先出栈，所以栈也称为后进先出（Last In First Out）线性表，简称为LIFO表。或先进后出FILO表, （ First In Last Out） 3.1 栈 3.1 栈 基本操作 InitStack(S) 操作结果：构造一个空栈 S。 DestroyStack(S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。 StackEmpty(S) 初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALSE StackLength(S) 初始条件：栈 S 已存在。 操作结果：返回 S 的元素个数，即栈的长度 3.1 栈 GetTop(S, e) 初始条件：栈 S 已存在且非空。 操作结果：用 e 返回 S 的栈顶元素。 3.1 栈 Push(S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。 3.1 栈 Pop(S, e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值 3.1 栈 StackTravers(S, visit( )) 初始条件：栈 S 已存在且非空。 操作结果：从栈底到栈顶依次对栈S的每个元素调用函数visit( )。一旦visit( )失败，则操作失败 3.1 栈 栈的表示和实现 顺序栈 类似于线性表的顺序映象实现，指向表尾的指针top可以作为栈顶指针 3.1 栈 3.1 栈 3.1 栈 3.1 栈 3.1 栈 链栈 3.1 栈 3.1 栈 3.1 栈 3.1 栈 3.1 栈 栈的两种存储结构的差别与一般的线性表的两种存储结构的差别是相同的。 栈的后进先出的固有特性，在计算机程序的开发过程中，其应用是非常广的，只要用编程语言来写程序，就会用到栈 3.2 栈的应用举例 数制转换 算法基于原理： N = (N / d)×d + N % d 3.2 栈的应用举例 3.2 栈的应用举例 括号匹配的检验 假设在表达式中( [ ] ( ) ) 或[ ( [ ] [ ] ) ]等为正确的格式 [ ( ] )或( [ ( ) )或 ( ( ) ] )均为不正确的格式 则 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述 3.2 栈的应用举例 3.2 栈的应用举例 3.2 栈的应用举例 3.2 栈的应用举例 行编辑程序问题 如何实现“每接受一个字符即存入存储器” ，这样并不恰当 在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正 合理的作法 设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区; 并假设“#”为退格符，“@”为退行符 3.2 栈的应用举例 3.2 栈的应用举例 3.2 栈的应用举例