两种存储结构比较（线性表）：.pptVIP

第三章 栈与队列 两种重要的，限定操作的线性结构。 §3.1 栈 栈的例子：操作系统中中断现场的保留等。 一、定义：限定只能在表尾进行插入或删除操作的线性表。 修改原则：后进先出（LIFO） 练习： 设进栈顺序为1、2、3、4，请说出以下的出栈顺序是否可能？ A、1 2 3 4 B、4 3 1 2 C、2 1 4 3 D、3 2 1 4 E、3 4 2 1 F、3 4 1 2 二、栈的基本操作 进栈、出栈、清空、求栈顶元素…… 接下来学习线索： 存储方式：顺序，链式 行为特征 应用实例 三、栈的顺序存储结构 数组定义栈：stack[max] 进栈： 出栈： 四、栈的链式存储结构 规定：top指向栈顶元素地址 基本操作： 判断空栈 进栈 出栈 利用链式存储结构存储栈，可解决栈的致命错误——上溢 五、栈的应用 1、递归调用 一个子程序调用自身，称为递归调用。 例：阶乘的计算 五、栈的应用 2、计算表达式 （1）由计算规则得算符优先关系表 3+5*3 3+5+5 θ1：先来的算符 θ2：后来的算符 （2）原理 两工作栈：一个算符栈，一个操作数栈 a.读取到操作数，直接入操作数栈 b.读取到运算符，取运算符栈栈顶元素与该算符比较优先级： “”：读取符号入运算符栈； “”：运算符栈出一元素，操作数栈出两元素， 运算后，结果放回操作数栈； “=”：运算符栈出一元素，与之相抵消。 （2）原理 算法结束标志：运算符栈为空，操作数栈有一元素，即为结果。 上机： 输入一包含“(”和“)”的字符串，检测括号是否匹配（其中括号中能嵌套括号），并输出括号是否匹配的信息（匹配、缺少左括号、缺少右括号）； 分析： gets(fun) while (fun[i]!=’\0’) {if (fun[i]==’(‘)：入栈； if (fun[i]==‘)’)： if 栈空：错，缺左边，return； else 出栈； i=i+1; } 如栈空 对！！！ 否则 错，缺少右边 §3.2 队列 队列的例子：排队等。 一、定义：限定只能在表的一端进行插入，在表的另一端进行删除的线性表。 修改原则：先进先出（FIFO） 二、队列的基本操作 进队、出队、清空、求队头元素…… 接下来学习线索： 存储方式：链式，顺序 行为特征 三、队列的链式存储结构 需设两个指针： front：头结点地址 rear：队尾结点地址 基本操作： rear=front； front-link=NULL; 基本操作： 四、队列的顺序存储结构 数组定义队列：queue[max] 四、队列的顺序存储结构 假溢出的问题：用循环队列来解决 下一个rear计算公式：rear=（rear+1）mod max 练习： 设循环队列容量为70（序号0~69），现经过一系列的入队和出队后，问下列情况下循环队列中各有几个元素？ （1）front=14，rear=21 （2）front=23，rear=12 §3.3两种存储结构比较（线性表）： 顺序存储（数组）： 思想简单，静态管理，定位方便；但会有溢出问题，有时会有大量冗余，系统开销大。 链式存储（链表）： 操作方便，无冗余，解决溢出问题。 两个限定操作、用途广泛的线性表： 堆栈：LIFO 队列：FIFO 练习: 设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次入栈，如果出栈顺序为s2,s3,s4,s6,s5,s1，栈的容量至少为（ ）。 A. 2 B. 3 C. 5 D. 6 设有一栈已有a1,a2,a3三个元素,栈顶为a3,a4正等待入栈,则以下序列是不可能的出栈序列是( )。 A. a3,a1,a4,a2 B. a3,a2,a4,a1 C. a3,a4,a2,a1 D. a4,a3,a2,a1 (