数据结构与算法课件第4章.ppt

4.2 字典ADT 描述用于一个简单数据库的接口，称为字典。字典将定义 为一个ADT，它提供在数据库存储、查找和删除记录的功能。 常用操作： 记录检索(find)：通过比较关键码，返回匹配的记录。 插入记录(insert)：插入新记录。 删除记录(remove)：删除指定关键码的记录。 删除任意记录(removeAny)：删除任意一条（如最后一条）记录。 可实现字典的数据结构： 4.3 栈 栈：一种特殊的线性表。其插入与删除只在一端进行。 符合“先进后出，后进先出”的原则， 允许插入和删除的一端称为栈顶，不允许插入和删除的一端称为栈底。 通常用栈项指针top来指向栈项，用栈底指针bottom来指向栈底。 元素的插入称为压入或入栈，元素的删除称为弹出或退栈。 4.3.1 顺序栈 程序设计中，用一维数组作为栈的顺序存储空间。为使用方便，通常栈顶指针指向栈空间的高地址一端。 栈顶指针指向栈中第一个空闲位置。 栈的基本运算：1、入栈运算 2、退栈运算 3、读栈项元素。 4.3.2 链式栈 采用链式存储结构的栈。 通常用来收集计算机存储空间中所有空闲的存储结点，即可利用空间表。 4.3.3 顺序栈与链式栈的比较 1. 基本操作时间代价的比较 基本操作 时间代价 入栈运算 退栈运算 读栈项元素 顺序栈 链式栈 2. 存储空间利用的比较 4.3.4 递归的实现 栈的最广泛应用： 子程序调用时将有关子程序的必要信息压入到一个栈中 子程序调用结束后，再将信息从栈中弹出。 采用栈，递归调用（不是全部）可以用迭代来代替。 4. 4 队列 队列：符合“先进先出，后进后出”的原则，在一端进行插入，在另一端进行删除的线性表。 如消息映射队列。例：排队，自动流水线上装配部件。计算机操作系统利用队列管理多个用户程序：消息队列。 允许插入的一端称为队尾，用尾指针（rear）指向；允许删除的一端称为队首，用头指针(front)指向。 队尾插入元素称为入队操作，队首删除元素称为出队操作。 4.4.1 顺序队列 顺序队列实现上的困难： 1.要求队列中n个元素都存储在数组的前n个单元中。 （1）0号单元存储队尾元素。 删除元素的时间代价： Θ（1） 插入新元素的时间代价：Θ（n） （1）0号单元存储队首元素。 插入新元素的时间代价：Θ（1） 删除元素的时间代价： Θ（n） 2. 不要求队列中n个元素都必须存储在数组的前n个单元中。 删除元素的时间代价： Θ（1） 插入新元素的时间代价：Θ（1） 但如果队列不断地插入和删除元素后，整个队列向数组中编号较高的位置移动。 解决方法：循环队列 思考：一维数组中如何实现循环队列。 ？循环队列中如何区分队列空和队列满 例1：队列中只有一个元素，位于单元m。 front = m，rear ＝ m。 删除该元素，front = front+1=m+1=rear+1 队列空时，rear 比 front 小 1。 例2：循环队列如右示，只有一个 空闲单元m。 此时：front=m+1, rear=m-1 若插入一个新元素，则rear=rear+1=m 即队列满时，rear 比 front 小 1。 解决办法：1、设置标志区别队列空或满。2、以尾指针追上头指针作为队列满的条件。 3、记录元素的数量。 4.4.2 链式队列 4.4.3 顺序队列和链式队列的比较 表达式计算 　要求： 从左到右只需一次扫描表达式。 自动区分运算符和运算数。 自动根据运算符的优先级确定计算顺序。 表达式计算 　运算符和优先级： 低 ＋ － × / 高 ^ 特殊： ( ) ？ 如何判断山峰 利用栈实现表达式计算 　规则： 在表达式最后加一个结束符；将结束符;看作最低优先级。 设置两个栈：运算符栈，暂存表达式处理过程中的运算符。 运算数栈，暂存表达式处理过程中的运算数。 首先将结束符; 直接压入运算符栈. 将 ( 和 ）都看作低优先级运算符。 从左到右读入表达式中的符号，如果读出的是： 运算数，直接压入运算数栈，再读入下一个符号。 运算符，则： 读出的运算符的优先级大于运算符栈中栈顶运算符的优先级，且将读出的运算符压入运算符栈中，读下一个符号。 读出的运算符的优先级小于等于运算符栈中栈顶运算符的优先