树结构综合版1——7数据结构ch3栈和队列.pptVIP

数 据 结 构 Data Structure 主讲人： 刘 玮 第三章 栈和队列 3.1 栈 3.1 栈 3.1 栈 1、顺序栈 1、顺序栈 1、顺序栈 2、链栈 2、链栈 顺序栈和链栈的比较 3.2 栈的应用 3.3 递归 3.3 递归 3.3 递归 3.3 递归 3.4 队列 3.4 队列 3.4 队列 1、链队列 1、链队列 1、链队列 1、链队列 1、链队列 2、线性队列 2、线性队列 3、循环队列 3、循环队列 3、循环队列 3、循环队列 循环队列和链队列的比较 本章小结 栈 逻辑结构：后进先出 抽象数据类型 物理结构：顺序栈，链栈 基本运算实现 栈空条件，栈满条件？（何时判断） 队列 逻辑结构：先进先出 抽象数据类型 物理结构：链队列，循环队列（顺序队列） 基本运算实现 队空条件，队满条件？（何时判断） 第三章 思考题 假设算术表达式中包含两种括号：圆括号“（”，“）”和方括号“[”，“]”，编写判别给定表达式中所含括号是否正确配对出现的算法。 已知有一个多项式Fn(X)，可递归定义如下： 试写出计算Fn(X)值的递归函数。当n=3时，参照P57页图3.7的方式分析递归函数的调用过程。 1）存储特点 利用地址连续的存储单元依次存放队列各元素。 设置两个指示器 front, rear 分别指示队头、队尾。 2）线性队列的表示 #define MAXQSIZE 100 typedef struct { QElemtyope *base; int front; int rear; }SqQueue; 存在问题：“假溢出”现象！ 解决方法：循环队列 C D E F front rear C D E F front rear G 1）存储特点 同线性队列 存储队列的数组被当作首尾相接的表处理。 队头、队尾指针加1时从 MaxSize -1直接进到0，可用C语言的取模(余数)运算实现。 补充： 出队:队头指针进1 front = (front + 1) % MaxSize; 入队:队尾指针进1 rear = (rear + 1) % MaxSize; 队列初始化：front=rear= 0; 队空条件： (rear + 1) % MaxSize == front ; front == rear ; front rear B A C D E F front rear 队满条件： rear 2）循环队列的表示 #define MAXQSIZE 100 typedef struct { QElemtyope *base; int front; int rear; }SqQueue; 3）基本操作的实现 ① 初始化（置空队） 算法 ② 入队（插入） 算法 ③ 出队（删除） 0 1 2 3 4 5 C D E F front rear 算法 时间性能: 相同，都是常数时间O(1)。 空间性能： 循环队列:必须预先确定一个固定的长度，所以有存储元素个数的限制和空间浪费问题。 链队列：没有队列满的问题，只有当内存没有可用空间时才会出现队列满，但是每个元素都需要一个指针域，产生结构性开销。 设置一个工作栈 工作栈stack 依次读入表达式中的每个字符 若是左括号（’(’,‘[’,’{’），则将其入栈； 若是右括号（‘）’，‘]’，‘}’）： 若工作栈stack为空栈，则错误返回； 若工作栈stack不为空： 若栈顶元素与当前字符不匹配则错误退出； 否则将栈顶元素出栈； 算法思想： 表达式读取完毕，若栈非空则错误退出； 3.2.3 迷宫求解 2 1 3 4 10 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 y x 算法思想： 3.2.4 表达式求值 表达式的组成： 操作数（operand）：常数、变量。 运算符（operator）: 算术运算符、关系运算符和逻辑运算符。 界限符（delimiter）：左右括弧和表达式结束符。 算术运算的规则： 先乘除后加减 先左后右 先括弧内后括弧外 例：4+2*3-10/5 =4+6-10/5 =10-10/5 =10-2 =8 在计算机中，表达式可以有三种不同的标识方法： 设 Exp = S1 + OP + S2 则称 OP + S1 + S2