第三章栈和队列-淮海工学院.ppt

课前导学 3.1 栈 3.2 栈的应用举例 * 3.3 栈与递归实现 3.4 队列;【学习目标】;【重点和难点】;引例;3.1 栈（stack）;2. 栈抽象数据类型的定义; StackLength(S) 初始条件：栈S已存在。 操作结果：返回S的元素个数，即栈的长度。 GetTop(S, e) 初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。 Push(S, e) 初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素。 Pop(S, e) 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。} ADT Stack ;3. 栈的存储结构（1）栈的数组表示 — 顺序栈; ;顺序栈的实现：一维数组s[M];顺序栈的存储;（2）栈的链接表示 — 链式栈;4. 栈的主要算法;(2) 顺序栈取栈顶元素算法;(3) 顺序栈出栈算法;(4) 将元素压入顺序栈算法;在一个程序中同时使用两个栈;(5) 将元素压入链式栈算法(同头部插入的单链表);(6)将元素弹出链式栈算法 ;3.2 栈的应用举例;2. 回文游戏：顺读与逆读字符串一样（不含空格）;3. 多进制输出：;4. 表达式求值;后缀表达式求值步骤： 1、读入表达式一个字符 2、若是操作数，压入栈，转4 3、若是运算符，从栈中弹出2个数，将运算结果再压入栈 4、若表达式输入完毕，栈顶即表达式值； 若表达式未输入完，转1 ;(1);* 3.3 栈与递归实现;递归调用执行情况如下：;利用栈和递归解决的几个经典问题 ;【 汉诺塔问题】;解决方法：;【迷宫问题】;【八皇后问题】;【背包问题】;2.4 队列 ( Queue );队列的进队和出队原则;队列的进队和出队示例 ; 1. 队列的抽象数据类型的定义 ADT Queue {数据对象：D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0}数据关系：R1＝{ a i-1,ai | ai-1, ai ∈D, i=2,...,n}约定其中a1 端为队列头，an 端为队列尾。基本操作： InitQueue(Q) 操作结果：构造一个空队列Q。; DestroyQueue(Q) 初始条件：队列Q已存在。 操作结果：队列Q被销毁，不再存在。 ClearQueue(Q) 初始条件：队列Q已存在。 操作结果：将Q清为空??列。QueueEmpty(Q) 初始条件：队列Q已存在。 操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。QueueLength(Q) 初始条件：队列Q已存在。 操作结果：返回Q的元素个数，即队列的长度。;GetHead(Q, e) 初始条件：Q为非空队列。 操作结果：用e返回Q的队头元素。EnQueue(Q, e) 初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。DeQueue(Q, e) 初始条件：Q为非空队列。 操作结果：删除Q的队头元素，并用e返回其值。} ADT Queue ;2. 队列的顺序存储结构 实现：用一维数组实现sq[M]; 队列的顺序存储结构表示——循环队列; 顺序存储队列的几种状态;存在问题 设数组维数为M，则： 当front=0,rear=M-1时，再有元素入队发生溢出——真溢出 当front?0,rear=M-1时，再有元素入队发生溢出——假溢出 解决方案 队首固定，每次出队剩余元素向下移动——浪费时间 循环队列 基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;;在顺序队列尾插入新元素算法;在顺序队列头删除旧元素算法;3. 队列的链式表示 — 链队列;队列的链式存储结构;几种链式队列的状态;Q.front;在链式队列尾插入新元素算法;在链式队列头删???旧元素算法 ;队列存放数组被当作首尾相接的表处理。 队头、队尾指针加1时从maxSize -1直接进到0，可用语言的取模(余数)运算实现。 队头指针进1: front = (front+1) % maxSize; 队尾指针进1: rear = (rear+1) % maxSize; 队列初始化：front = rear = 0; 队空条件：front == rear; 队满条件：(rear+1) % maxSize == front ;;本章小结