《第3单元线性数据结构（二）》由会员分享，可在线阅读，更多相关《第3单元线性数据结构（二）（53页珍藏版）》请在金锄头文库上搜索。
1、 1/53 第 3单元 线性数据结构（二） 和队列 (46) 和数组 (55) 2/53 和队列 一、栈的逻辑结构和运算 念 1) 只允许在同一端进行插入和删除操作的特殊线性表。 2) 允许进行插入和删除操作的一端称为栈顶，另一端为栈底； 3) 栈底固定，而栈顶浮动； 4) 特点：后进先出（ 5) 空栈 :元素个数为零的栈。 3/53 2. 栈的基本运算 置栈为空； 判断栈是否为空； x) 进栈 x 出栈 取栈顶元素 顺序栈 : 采用顺序存储结构的栈 链栈 : 采用链式存储结构的栈 4/53 出栈序列 操作序列 1 2 3 s x s x s x 1 3 2 s x s s x x 2 1 3
2、 s s x x s x 2 3 1 s s x s x x 3 2 1 s s s x x x 例 1 有三个元素的进栈序列是 1， 2， 3。写出可能的出栈序列。 5/53 1) 栈顶指针 用来指出栈顶元素所在的位置 2) 栈空条件： 3) 栈满条件： 4) 上溢 栈满后再进行入栈操作 ,产生上溢。 5) 下溢 栈已空 ,再执行出栈操作，产生下溢。 6/53 二、栈的存储结构之一 :顺序栈 1) 采用顺序存储结构的栈 2) 实现 : 使用一维数组 3) 栈顶位置随进栈和出栈而变化。 4) #n /*下标从 0开始 */ 7/53 栈操作举例 a n 栈底 栈顶 . 1 A B C 2. (
3、空栈 ) (A、 B、 A B 3. ( 4. A B C D E F 栈满 ） 8/53 算法 1 进栈算法 判断栈满否， 若满，显示溢出信息，停止执行 否则，执行 ； 栈顶指针 加 1)； 在 x。 9/53 算法 1栈算法程序 x） = 1） 栈上溢 ！ n”） ; 1） ; +； /* 栈指针加 1 */ x ； /* 元素 */ 10/53 算法 1栈算法 判断栈是否为空； 若空，输出下溢信息，并停止执行； 否则，执行 弹出（删除）栈顶元素； 栈顶指针 减 1)。 返回栈顶元素 11/53 算法 1栈算法程序 ） x; = 栈下溢 n”); ); x = - ； x ； 12/53
4、5) 两栈共享一个栈空间 两栈共享：两个栈底分别设在两端，栈顶指针 间分界线不定。 a. b. c. 0 空栈 1、栈 2均有元素 满 13/53 二、栈的存储结构之二 :链栈 1. 顺序栈的问题 1) 最多实现 2个栈的共享 2) 不能用于最大空间事先不知的情况 解决方法 : 链栈 14/53 链栈存储结构 2. 链栈存储结构的 ; 链栈空： 链栈满 : t = * 申请结点失败 15/53 链栈示意图 a1 a2 底 顶 . 16/53 算法 1进栈操作算法 申请一个链栈结点 , 若 t=链满 ; 否则 ,执行 在 并将 t。 17/53 算法 1进栈操作程序 x) t; t=( ); (
5、t = = 栈已满 n”); ); t- x; t- t; 18/53 算法 1出栈操作算法 若链栈空，输出栈溢出信息； 否则，执行 。 删除 使 指向被删除结点的后继结点 释放被删除结点的存储空间 返回栈顶元素 19/53 算法 1出栈操作程序 ) p; x; = 栈下溢 n”）； ); p= x = p - p) ; x; 20/53 三、队列 1. 队列概念 1) 只允许在表的一端进行删除操作，在表的另一端进行插入的特殊线性表。 2) 队尾 (进行插入操作的一端 3) 队头 (进行删除操作的一端 4) 特点：先进先出（ a n 入队 插入 出队 删除 21/53 2、队列的操作 清空队列
6、 判断队列是否为空 x) 入队 (插入 ) 出队 (删除 ) 取队头元素 22/53 四、队列的顺序存储 1. 定义空队列 : 用一维数组 #n 1, 1; 头指针 ; 尾指针 ; 空队列： 满队列： 23/53 约定： 总是指向队头元素的前一个位置； 总是指向队尾元素的位置 结果： 对任何元素，操作都一样 出队 : 入队 : 1 ； ; x = x; a n 24/53 举例：顺序队列的入队、出队操作 1）空队列 2） A、 B、 C、 D、 3） A、 B、 E B C D E 队时， 出队时， 25/53 4） F、 G、 5） D、 E、 F、 G、 现假“溢出” E F G H 26/53 3. 假溢出 假溢出 队列是空的情况下出现的溢出。 解决方法 1) 整个队列左移 ,费时 2) 队列的首尾相连 目的 队列中真正没有空位置时，才产生溢出。 27/53 4、 循环队列 队头指针移动 ) )% 等价于： (= = 0 ; ; 队尾指针移动
