数据结构第3章栈和队列.ppt

1. 栈（Stack） 第三章 栈和队列 2. 队列（Queue） 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 1 1. 定 义 3.1 3.1 栈栈 与线性表相同，仍为一对一( 1:1)关系。 用顺序栈顺序栈或链栈链栈存储均可，但以顺序栈更常见 只能在栈顶栈顶运算，且访问结点时依照后进先出 后进先出 （LIFO）或先进后出先进后出（FILO）的原则。 关键是编写入栈入栈和出栈出栈函数，具体实现依顺 序栈或链栈的存储结构有别而不同。 3. 存储结构 4. 运算规则 5. 实现方式 2. 逻辑结构 限定只能在表的一端一端进行插入和删除运算的 线性表。 即栈顶 基本操作有：建栈、判断栈满或栈空、入栈、出栈、读栈顶 元素值，等等。 2 栈栈 是仅在表尾进行插入、删除操作的线性表。 表尾(即 an 端)称为栈顶 top ; 表头(即 a1 端)称为栈底bottom 例如： 栈 S S= (a1 , a2 , a3 , .,an-1 , an ) 插入元素到栈顶的操作，称为入栈。 从栈顶删除最后一个元素的操作，称为出栈。 an称为栈顶元素a1称为栈底元素 想一想：若要从栈中取出a1，该如何操作？ 强调：强调：插入和删除都只能在表的一端（栈顶）进行！ 3 讨论1：栈是什么？它与一般线性表有什么不同？ 答：栈是一种特殊的线性表，它只能在表的一端（ 即栈顶）进行插入和删除运算。 与一般线性表的区别：仅在于运算规则运算规则不同。 一般线性表一般线性表 栈栈 逻辑结构：1:1 逻辑结构： 1:1 存储结构：顺序表、链表 存储结构：顺序栈、链栈 运算规则：随机存取随机存取 运算规则：后进先出后进先出(LIFO) “进”插入=压入=PUSH（an+1) “出”删除=弹出 =POP(an) 4 a1 a2 an 顺序栈S ai 顺序表和顺序栈的操作区别: 表头 表尾 低地址 高地址 写入：Si= ai 读出： e= Si 压入(PUSH)PUSH): : Stoptop+=an+1 弹出( POP)POP) : : e e=S=S-toptop 低地址 高地址 Si a1 a2 ai an 顺序表S an+1 以线性表 S= (a1 , a2 , . , an-1 , an )为例 栈底bottombottom 栈顶toptop 前提：一定要预设栈顶指针toptop 栈顶toptop 5 断点 讨论：为什么要设计栈？它有什么独特用途？ 调用函数或子程序非它莫属； 递归运算的有力工具； 用于保护现场和恢复现场； 简化了程序设计的问题。 例： 输入x10输入x50输入x2输入x3输入x4 输出sum 0 输出sum 0+x4 输出sum x4+x3 输出sum x4+x3 +x2 输出sumx4+x3 +x2+x1 void test(int scanf(x); if(x=0)sum=0; elsetest(sum)test(sum); sum+=x; printf(sum); 答： 6 例：写出下面C程序段的执行结果。 递归概念及算法实现 运行结果为： 5，120 long int fact(n) int n; long f; if(n1)f=n*fact(n-1); else f=1; return(f); main( )main( ) int n; long y; n=5; y=fact(n); printf(“%d,%ldn”,n,y); 此题为递归运算此题为递归运算! ! 7 编制递归算法要注意些什么？ 递归进行是有条件的。一般常把判断 语句加在递归语句以前。 递归的最底层应该有返回值，以供上 层递归的调用。否则死循环。 递归调用需要利用栈。 每次调用要把本次调用的参数和局 部变量保存在栈顶。每次从下一层调 用返回到上一层调用时，从栈顶恢复 本层调用的参数和局部变量的值。 参量的初始化应该在递归以前。 void test(int scanf(x); if(x=0)sum=0; else test(sum) test(sum); sum+= x; printf(sum); 一个直接或间接调用自身的函数被称为一个直接或间接调用自身的函数被称为 是递归（是递归（recursionrecursion）的。的。 什么叫递归？ 8 例1 一个栈的输入序列为1,2,3，若在入栈的过程中 允许出栈，则可能得到的出栈序列是什么？ 答： 可以通过穷举所有可能性来求解： 1入1出， 2入2出，3入3出， 即123； 1入1出， 2、3入，3、2出， 即132； 1、2入，2出， 3入3出， 即231； 1、2入，2、1出，3入3出， 即213； 1、2、3入，3、2、1出， 即321； 合计有5种可能性。 9 例2：一个栈的输入序列是12345，若在入栈的过 程中允许出栈，则栈的输出序列43512可能实现吗 ？12345的输出呢？ 43512不可能实现，主要是其中的12顺序不能实现 ； 12345的输出可以实现，每压入一数便立即弹出即 可。 答： 10 例3 ： 设依次进入一个栈的元素序列为c，a，b，d，则 可得到出栈的元素序列是： ）a，b，c，d ）c，d，a，b ）b，c，d，a ）a，c，d，b A）、D）可以， B）、C）不行。 讨论：有无通用的判别原则？ 有！若输入序列是 ,PjPkPi (PjM)上溢 else stop+=e; Push (B); Push (C); Push (D); top top top top 低地址L Push (A); 高地址M B C D 13 顺序栈出栈操作例如从栈中取出B B D C B A top top D C A B D C B A topD C B A top 低地址L 高地址M D 核心语句： pop ( ); 顺序栈出栈函数pop() status pop( ) if(top=L) 下溢 else e=s-top; return(e); pop ( ); printf( Pop () ); 14 链栈的入栈操作和出栈操 作 (1) 链栈的构造方式以头指针为栈顶，在头指针处插入或删除. Node *st, *p; int m=sizeof(Node); 栈顶 栈底 栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈 st st a1 a2 an-1 an nextdata 链栈中每个结点由两个域构成： data域和next域，其定义为： typedef Struct SNode SElemType data; Struct SNode *next; Node; 15 由此可以看出：一个链栈由其栈顶指针唯一指定 设stst指向栈顶元素，则 st st = NULL 表示栈空 1) 链栈不必设头结点，因为栈顶（表头）操作频繁； 链栈一般不会出现栈满情况，除非没有空间导致malloc分 配失败。 1) 链栈的入栈、出栈操作就是栈顶的插入与删除操作，修改 指针即可完成。 采用链栈存储方式的优点是，可使多个栈共享空间；当栈 中元素个数变化较大，且存在多个栈的情况下，链栈是栈 的首选存储方式。 几点说明: 16 例1： 数制转换（十转N） 设计思路：用栈暂存低位值 例2：表达式求值 设计思路：用栈暂存运算符 例3 ：括号匹配的检验 设计思路：用栈暂存左括号 例4：汉诺（Hanoi）塔 设计思路：用栈实现递归调用 栈的应用举例栈的应用举例 17 例2 表达式求值 ( 这是栈应用的典型例子, 见P48 ) 这里，表达式求值的算法是 “算符优先法”。 例如：编写算法，用栈实现表达式3*（7 2 ）求值。 一个算术表达式是由 操作数（x，y，z）和 运算符（* ，/， + ，-，（，），# ）组成. 教材P48给出了算符之间的优先级 表达式的 起止符号 (1) 表达式求值必须满足算术四则运算规则： a. 从左算到右 b. 先乘除，后加减 c. 先括号内，后括号外 18 (2) (2) 算法思想：算法思想： 1）首先置操作数栈操作数栈OPNDOPND为空栈，表达式的起始符# #为运算符栈 运算符栈 OPTROPTR的栈底元素； 2）依次读入表达式中的每个字符， 若运算符是#或栈顶是#，结束计算，返回OPNDOPND栈顶值。 if（是操作数） 则PUSH（ OPNDOPND，操作数）； if（是运算符） 则与OPTROPTR栈顶元素进行比较，按优先级 (规定详见P48）进行操作； 为了实现算符优先算法，可以设定两个工作栈， OPNDOPND存放操作数或运算结果， OPTROPTR存放运算符号。 3）直到整个表达式求值完毕（当前读入的字符和OPTROPTR 栈的栈顶元素均为# # ） if 运算符栈顶元素，则压入OPTROPTR栈。 19 表达式求值过程的描述： OPTROPNDINPUTOPERATE 3*(7-2)#Push(opnd,3) # *(7-2)#3#Push(optr,*) #,*3(7-2)#Push(optr,() #,*,(37-2)#Push(opnd,7) #,*,(3,7-2)#Push(optr,-) #,*,(,3,72)#Push(opnd,2) #,*,(,3,7,2)#Operate(7-2) #,*,(3,5)#Pop(optr) #,*3,5#Operate(3*5) #15#GetTop(opnd) 3*（7 2 ） 20 1. 栈（Stack） 第三章 栈和队列 2. 队列（Queue） 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 21 1. 定 义 3.2 队列 与线性表相同，仍为一对一关系。 顺序队或链队，以循环顺序队更常见。 只能在队首和队尾运算，且访问结点时依照 先进先出（FIFO）的原则。 关键是掌握入队和出队操作，具体实现依顺 序队或链队的不同而不同。 3. 存储结构 4. 运算规则 5. 实现方式 2. 逻辑结构 只能在表的一端进行插入运算，在表的另一 端进行删除运算的线性表。 基本操作：入队或出队，建空队列，判队空或队满等操作。 尾部插 入 22 队列 （Queue）是仅在表尾进行插入操作，在表头进行删除操 作的线性表。它是一种先进先出（）的线性表。 例如：队列 Q= (a1 , a2 , a3 , .,an-1 , an ) 在队尾插入元素称为入队入队；在队首删除元素称为出队出队。 队首队尾 问：为什么要设计队列？它有什么独特用途？ 1. 离散事件的模拟（模拟事件发生的先后顺序）； 2. 操作系统中的作业调度（一个CPU执行多个作业）； 3. 简化程序设计。 答： 例如 CPU芯片 中的指令译码 队列 23 队的队的实现方式实现方式是本节重点：是本节重点： 关键是掌握入队和出队操作，具体实现依存储结构 （链队或顺序队）的不同而不同。 1. 1. 链队列链队列 2. 2. 顺序队顺序队(特别是循环顺序队) 队的抽象数据类型定义(教材P54-55）： ADT Queue 数据对象：D= 数据关系：R= 基本操作： ADT Queue 建队、入队或出队、判队 空或队满等，教材罗列了 6种基本操作。 24 链队列类型定义： typedef struct QueuePtr front ; /队首指针 QueuePtr rear ; /队尾指针 LinkQueue; 结点类型定义： typedef Struct QNode QElemType data; /元素 Struct QNode *next; /指向下一结点的指针 Qnode , * QueuePtr ; 关于整个链队的 总体描述 链队中任一 结点的结构 1. 1. 链队列链队列 因简单而提前 介绍 25 链队示意图 讨论： 空链队的特征？ Q (队尾)(队首) front a1a2a3 rear p front rear 怎样实现链队的入队和出队操作？ 链队会满吗？ front=rear 一般不会，因为删除时有free动作。除非内存不足！ 入队（尾部插入）：rear-next=S; rear=S; 出队（头部删除）：front-next=p-next; 完整操作函数 见教材P59 S D 26 采用动态分配空间的形式 顺序队类型定义： 建队核心语句： q . base=(QElemType *)malloc(sizeof (QElemType ） * QUEUE_MAXSIZE); /分配空间 关于整个顺序 队的总体描述 #define QUEUE-MAXSIZE 100 /最大队列长度 typedef struct QElemType *base; /队列的基址 int front; /队首指针 int rear; /队尾指针 SqQueue 顺序队中结点的结构是QElemType, 此处略。 27 顺序队示意图 Q (队尾) (队首) front a1 a2 a3 data a4 0 . . . . . . . 99 rear 队列会满吗？ 极易装满！因为数组通 常有长度限制，而其前 端空间无法释放。 空队列的特征？ 约定：front=rear 队尾后地址 入队(尾部插入)：Qrear=e; rear+; 出队(头部删除)：e=Qfront; front+; 讨论： 假溢假溢 出出 有 缺 陷 怎样实现入队和出队 操作？核心语句如下: bas e e 28 问：什么叫“假溢出” ？如何解决？ 答：在顺序队中，当尾指针已经到了数组的上界 ，不能再有入队操作，但其实数组中还有空位置 ，这就叫“假溢出”。 解决假溢出的途径 采用循环队列 29 a3 a2 a1 0 1 2 3 N-1 rear front 循环队列（臆造）循环队列（臆造）顺序队列顺序队列 a3 a2 a1 front rear 0 1 2 3 . . N-1 新问题：在循环队列中，空队特征是front=rear；队满时也会有 front=rear；判决条件将出现二义性！ 解决方案有三： 使用一个计数器记录队列中元素个数（即队列长度）； 加设标志位，删除时置1,插入时置0,则可识别当前front=rear属于何种情况 人为浪费一个单元，则队满特征可改为front=(rear+1)%N； 30 队空条件 : front = rear (初始化时：front = rear ) 队满条件：