《数据结构、代码》第3章 栈和队列ppt课件

1、第3章 栈和队列张成文张成文北京邮电大学计算机学院北京邮电大学计算机学院概述两种特殊的线性表。逻辑构造和线性表一样。比起线性表其运算受限制，故又称它们为运算受限的线性表。栈和队列运用在各种程序设计中尤其栈的运用更广1. 栈1.1 栈的定义1.2 顺序栈1.3 链栈1.1 栈的定义 栈Stack是限制仅在表的一端进展插入 和删除运算的线性表。(1)通常称插入、删除的这一端为栈顶Top，另一端称为栈底Bottom。(2)当表中没有元素时称为空栈。(3)栈的插入操作被笼统地称为进栈或入栈，删除操作称为出栈或退栈。 每次进栈的元素都被放在原栈顶元素之上而成为每次进栈的元素都被放在原栈顶元素之上而成为新

2、的栈顶，而每次出栈的总是当前栈中新的栈顶，而每次出栈的总是当前栈中“最新的元最新的元素，即最后进栈的元素。因此，栈又称为后进先出的素，即最后进栈的元素。因此，栈又称为后进先出的线性表。简称为线性表。简称为LIFOLIFO表。表。栈的表示图a1a2an栈顶表尾栈底bottomtop入栈入栈pushpush出栈出栈pop 栈在计算机中主要有两种根本的存储栈在计算机中主要有两种根本的存储构造：顺序存储构造和链式存储构造。构造：顺序存储构造和链式存储构造。 顺序存储的栈为顺序栈顺序存储的栈为顺序栈 链式存储的栈为链栈链式存储的栈为链栈栈的存储方式1.2 顺序栈 栈的顺序存储构造简称为顺序栈,它是运算受

3、限的顺序表。顺序栈利用一组地址延续的存储单元依次存放自栈底到栈顶的数据元素。 顺序栈的类型定义#define TRUE 1#define FALSE 0#define Stack_Size 50 typedef struct StackElementType elemStack_Size; /* 一维数组*/ int top; /*用来存放栈顶元素的下标*/SeqStack; top空栈toptoptoptoptopa 进栈进栈b 进栈进栈aababcdee 进栈进栈abcdef 进栈溢出进栈溢出abdee 退栈退栈ctopc 退栈退栈b 退栈退栈abaa 退栈退栈空栈空栈topabdd 退栈

4、退栈ctopabctoptop 留意顺序栈中元素用向量存放栈底位置是固定不变的，可设置在向量两端的恣意一个端点栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top通常称top为栈顶指针来指示当前栈顶位置顺序栈的根本运算1 置栈空初始化2 判栈空3 判栈满4 进栈操作5 退栈操作6 取栈顶元素 1置栈空初始化 void InitStackSeqStack *S /将顺序栈置空 S-top=-1; (2) 判栈空 int StackEmptySeqStack *S /*判栈S为空栈时前往值为真，反之为假*/ return S-top=-1; 3判栈满 int StackFullSeqStack

5、 *S/*判栈S为满时前往真，否那么前往假*/ return S-top=StackSize-1; 4进栈进栈时，需求将S-top加1 留意： S-top=StackSize-1表示栈满上溢景象-当栈满时，再做进栈运算产生空间溢出的景象。 上溢是一种出错形状，应设法防止。 void PushSeqStack *S，DataType x if (StackFull(S) Error(“Stack overflow); /上溢，退出运转 S-data+S-top=x;/栈顶指针加1后将x入栈5退栈退栈时，需将S-top减1 留意： S-topdataS-top-;/栈顶元素前往后将栈顶指针减1 6

6、取栈顶元素 DataType StackTopS if(StackEmpty(S) Error(Stack is empty); return S-dataS-top; 1.4 链栈 链栈是采用链表作为存储构造实现的栈，是线性链栈是采用链表作为存储构造实现的栈，是线性链表的特例。由于栈的插入和删除操作仅限制在表头链表的特例。由于栈的插入和删除操作仅限制在表头位置进展，所以链表的表头指针就作为栈顶指针。位置进展，所以链表的表头指针就作为栈顶指针。 top top为栈顶指针，一直指向当前栈顶元素结点。为栈顶指针，一直指向当前栈顶元素结点。假设假设top=NULLtop=NULL，那么代表空栈。，那

7、么代表空栈。留意：链栈在运用终了时，应该释放其空间。留意：链栈在运用终了时，应该释放其空间。留意留意: 链栈中指针的方向是从栈顶指向栈底方向链栈中指针的方向是从栈顶指向栈底方向栈顶指针栈顶指针topa1 an-1 an typedef struct stacknode DataType data struct stacknode *next StackNode; StackNode *head=NULL; typedef struct StackNode *top; /栈顶指针 LinkStack;链栈的根本运算(1) 置栈空(2) 判栈空(3) 进栈(4) 退栈(5) 取栈顶元素1 置栈空

8、void InitStack(LinkStack *S) S-top=NULL; (2) 判栈空 int StackEmpty(LinkStack *S) return S-top=NULL; 3 进栈void Push(LinkStack *S,DataType x)/将元素x插入链栈头部 StackNode *p= (StackNode *)malloc(sizeof(StackNode); if(p=NULL) printf(“内存空间不够分配); exit(0);/return /强壮(Robust) p-data=x; p-next=S-top;/将新结点*p插入链栈头部 S-top

9、=p; 4 退栈 DataType Pop(LinkStack *S) DataType x; StackNode *p=S-top;/保管栈顶指针 if(StackEmpty(S) Error(Stack underflow.); /下溢 x=p-data; /保管栈顶结点数据 S-top=p-next; /将栈顶结点从链上摘下 free(p); return x; 将将x x入栈，修正栈顶入栈，修正栈顶指针指针:top=p:top=panan出栈，修正栈顶指出栈，修正栈顶指针针:top=top-next:top=top-next链栈的入栈操作和出栈操作5 取栈顶元素 DataType St

10、ackTop(LinkStack *S) if(StackEmpty(S) Error(Stack is empty.) return S-top-data; 留意 链栈中的结点是动态分配的，所以可以不思索上溢，无须定义StackFull运算。 2. 队列2.1 队列的定义2.2 顺序队列2.3 链队列 队列是一种特殊的线性表，限定插入和删除操作分别队列是一种特殊的线性表，限定插入和删除操作分别在表的两端进展。在表的两端进展。 a1 a2 ai an 队头 f队尾 r出队出队入队入队2.1 队列的定义和根本运算队列的性质1允许删除的一端称为队头Front。2允许插入的一端称为队尾Rear。3当

11、队列中没有元素时称为空队列。4队列亦称作先进先出First In First Out的线性表，简称为FIFO表队列的进队和出队 front rear空队列front rearA进队进队Afront rearB进队进队A Bfront rearC, D进队进队A B C Dfront rearA退队退队B C Dfront rearB退队退队C Dfront rearE,F,G进队进队C D E F GC D E F Gfront rearH进队进队,溢出溢出队列的进队和出队原那么n 进队时队尾指针先进一进队时队尾指针先进一 rear = rear + 1，n 再将新元素按再将新元素按 rear

12、 指示位置参与。指示位置参与。n 出队时队头指针先进一出队时队头指针先进一 front = front + 1，n 再将下标为再将下标为 front 的元素取出。的元素取出。n 队满时再进队将溢出出错；队满时再进队将溢出出错；n 队空时再出队将队空处置。队空时再出队将队空处置。n 处理方法之一：将队列元素存放数组首尾处理方法之一：将队列元素存放数组首尾n 相接，构成循环相接，构成循环(环形环形)队列。队列。 队列在计算机中主要有两种根本的存队列在计算机中主要有两种根本的存储构造：顺序存储构造和链式存储构造。储构造：顺序存储构造和链式存储构造。顺序存储的队列为顺序队列顺序存储的队列为顺序队列链式

13、存储的队列为链队列链式存储的队列为链队列队列的存储方式队列的根本运算(1)初始化队列(2)判队空(3)判队满(4)入队(5)出队(6)取队首元素2.2 顺序队列2.2.1 顺序队列的定义2.2.2 顺序队列的根本运算2.2.3 循环队列2.2.1 顺序队列的定义 队列的顺序存储构造称为顺序队列，顺序队列实践上是运算受限的顺序表 frontreara b c da b c d d e f d e f rear front rear 顺序队列的表示和顺序表一样，顺序队列用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，设置两个“指针front和rear分别指示队头元素和队尾

14、元素在向量空间中的位置，它们的初值在队列初始化时均应置为0。2.2.2 顺序队列的根本运算入队时：将新元素插入rear所指的位置，然后将rear加1。出队时：删去front所指的元素，然后将front加1并前往被删元素。 留意：当头尾指针相等时，队列为空。在非空队列里，队头指针一直指向队头元素，尾指针一直指向队尾元素的下一位置。 当Q-front= Q-rear 时,队列空。 当Q-rear+1MaxSize 时,队列满(即上溢出),但此时头指针指示的元素之前能够还有空单元,此景象称为假溢出;假设把这样的顺序构造想象为一个循环表, 插入时就可以利用这些空单元, 这样就构成循环队列。假上溢2.2

15、.3 循环队列为充分利用向量空间，抑制“假上溢景象的方法：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。入队操作时的尾指针运算入队操作时的尾指针运算: rear=(rear+1)%Maxsize出队操作时的头指针运算出队操作时的头指针运算: front=(front+1)%Maxaize问题：在循环队列中，由于队空时有问题：在循环队列中，由于队空时有front=rear；队满时也有；队满时也有front=rear；因；因此我们无法经过此我们无法经过front=rear来判别队列是来判别队列是“空还是空还是“满。满。循环队列表示图循环队列的几种形状循环队列的几种形状frontrea

16、r循环队列队满和队空的描画方法循环队列队满和队空的描画方法frontrear队空队空:队满队满:frontfrontrearrear rear=front?rear=front循环队列边境条件处置如何判别是“空还是“满。 处理这个问题的方法至少有三种： 另设一布尔变量以区别队列的空和满； 少用一个元素的空间。商定入队前，测试尾指针在循环意义下加1后能否等于头指针，假设相等那么以为队满留意：rear所指的单元一直为空；运用一个计数器记录队列中元素的总数即队列长度。顺序循环队列的类型定义#define QueueSize 100 /应根据详细情况定义该值typedef char DataType;

17、 /DataType的类型依赖于详细的运用typedef struct int front; /头指针，队非空时指向队头元素 int rear; /尾指针，队非空时指向队尾元素的下一位置 int count; /计数器，记录队中元素总数 DataType dataQueueSize CirQueue;顺序循环队列的根本运算1.置队空2.判队空3.判队满4.入队5.出队6.取队头元素 置队空置队空 void InitQueue(CirQueue *Q) Q-front=Q-rear=0; Q-count=0; /计数器置0 判队空判队空 int QueueEmpty(CirQueue *Q) /

18、队列无元素为空，属第三种方法 return Q-count=0; int QueueEmpty(CirQueue *Q) /属第二种方法 return Q-rear=Q-front; 判队满判队满int QueueFull(CirQueue *Q) return Q-count=QueueSize; /队中元素个数等于QueueSize时队满，属第三种方法int QueueFull(CirQueue *Q) return (Q-rear+1)%QueueSize=Q-front ; /队中元素个数等于QueueSize时队满，属第二种方法 入队入队void EnQueue(CirQueue *

19、Q,DataType x) if(QueueFull(Q) Error(Queue overflow); /队满上溢 Q-count +; /队列元素个数加1 Q-dataQ-rear=x; /新元素插入队尾 Q-rear=(Q-rear+1)%QueueSize; /循环意义下将尾指针加1 出队出队DataType DeQueue(CirQueue *Q) DataType temp; if(QueueEmpty(Q) Error(Queue underflow); /队空下溢 temp=Q-dataQ-front; Q-count-; /队列元素个数减1 Q-front=(Q-front+

20、1)%QueueSize; /*循环意义下的头指针加1*/ return temp; 取队头元素取队头元素DataType QueueFront(CirQueue *Q) if(QueueEmpty(Q) Error(Queue if empty.); return Q-dataQ-front; 2.3链队列2.3.1 链队列的定义2.3.2 链队列的根本运算2.3.1 链队列的定义 队列的链式存储构造简称为链队列。它是限制仅在表头删除和表尾插入的单链表。 队头在链头，队尾在链尾。队头在链头，队尾在链尾。a1anq.frontq.rearq.frontq.rear空队列空队列链队列的几种形状表

21、示图此时，front=rear修正rear指针修正头结点的指针域链队列为空的特征：链队列为空的特征：front=rear 链队列会满吗？链队列会满吗？普通不会，由于删除时有普通不会，由于删除时有freefree动作，除非内存缺乏！动作，除非内存缺乏！修正rear指针留意 添加指向链表上的最后一个结点的尾指针，便于在表尾做插入操作 和链栈类似，无须思索判队满的运算及上溢。在出队算法中，普通只需修正队头指针。但当原队中只需一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修正尾指针，且删去此结点后队列变空。以上讨论的是无头结点链队列的根本运算。和单链表类似，为了简化边境条件的处置，在队头结点前

22、也可附加一个头结点，添加头结点的链队列的根本运算定义链队列的存储构造typedef char DataType;typedef struct queuenode DataType data; struct queuenode *next;QueueNode;typedef struct QueueNode * front; QueueNode *rear; LinkQueue;2.3.2 链队列的根本运算1.置空队2.判队空3.入队4.出队5.取队头元素1 置空队int InitQueue( LinkQueue int InitQueue( LinkQueue * *Q )Q ) / /构造一

23、个空队列构造一个空队列 * *Q Q Q-front = (LQnode Q-front = (LQnode * *)malloc(sizeof(LQnode); )malloc(sizeof(LQnode); if( Q-front = NULL ) if( Q-front = NULL ) return FALSE; / return FALSE; /恳求内存失败前往恳求内存失败前往 Q-rear = Q-front; Q-rear = Q-front; Q-front- next = NULL; Q-front- next = NULL; return TRUE; / return TR

24、UE; /恳求内存胜利前往恳求内存胜利前往 2 判队空 int QueueEmpty(LinkQueue *Q)return Q- front- next =NULL&Q-rear-next=NULL;/*实践上只须判别队头指针能否为空即可*/3 入队void EnQueue(LinkQueue *Q,DataType x)/将元素x插入链队列尾部 QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode); /恳求新结点 p-data=x; p-next=NULL; if(QueueEmpty(Q) Q-front-next=p; Q-rear=p;

25、 /将x插入空队列 else /x插入非空队列的尾 Q-rear-next=p; /*p链到原队尾结点后 Q-rear=p; /队尾指针指向新的尾 4 出队DataType DeQueue (LinkQueue *Q) DataType x; QueueNode *p; if(QueueEmpty(Q) Error(“Queue underflow);/下溢 p=Q-front-next; /指向队头结点 x=p-data; /保管队头结点的数据 Q-front-next=p-next; /将队头结点从链上摘下 if(Q-rear=p)/原队中只需一个结点，删去后队列变空，此时队头指针已为空

26、Q-rear= Q-front; free(p); /释放被删队头结点 return x; /前往原队头数据 5 取队头元素 DataType QueueFront(LinkQueue *Q) if(QueueEmpty(Q) Error(Queue if empty.); return Q-front-next-data; 3. 栈的运用3.1 函数调用3.2 递归、非递归 当在一个函数的运转期间调用另一个函数时当在一个函数的运转期间调用另一个函数时, 在运转该被调用函数之前在运转该被调用函数之前, 需先完成三项义务：需先完成三项义务： 保管现场保管现场, 保管本函数参数、前往地址等信息保管

27、本函数参数、前往地址等信息; 为被调用函数的部分变量分配存储区传送参数为被调用函数的部分变量分配存储区传送参数; 将控制转移到被调用函数的入口。将控制转移到被调用函数的入口。3.1 函数调用 从被调用函数前往调用函数之前从被调用函数前往调用函数之前, 应该完成以下应该完成以下三项义务：三项义务：保管前往的计算结果保管前往的计算结果(用函数名用函数名,援用参数援用参数) ；释放被调函数的数据区释放被调函数的数据区, 恢复调用函数现场恢复调用函数现场 ;按照被保管的前往地址将控制转移到调用函数。按照被保管的前往地址将控制转移到调用函数。多个函数嵌套调用的规那么多个函数嵌套调用的规那么此时的内存管理

28、实行此时的内存管理实行“栈式管理栈式管理后调用先前往后调用先前往 ！例如：例如：main( ) void a( ) void b( ) a( ); b( ); /main / a / bmain的数据区函数a的数据区函数b的数据区 栈在函数调用中的作用过程一过程二过程三过程四断点三断点一断点二断点一断点二断点三stack调用子程序前往断点程序执行 数据构造-第3章 栈和队列703.2 递归、非递归递归的含义递归的含义 函数、过程或者数据构造的内部又直接或者间接函数、过程或者数据构造的内部又直接或者间接地由本身定义。地由本身定义。适宜于运用递归的场所适宜于运用递归的场所规模较大的问题可以化解为规

29、模较小的问题，且二者处规模较大的问题可以化解为规模较小的问题，且二者处置置(或定义或定义)的方式一致；的方式一致；当问题规模降低到一定程度时是可以直接求解的当问题规模降低到一定程度时是可以直接求解的(终止条终止条件件) 例例1. 阶乘阶乘 n!= 1 n=0 n(n-1)! n0数据构造-第3章 栈和队列71写递归算法应留意的问题写递归算法应留意的问题 递归算法本身不可以作为独立的程序运转，需在其它的程序中设置调用初值，进展调用； 递归算法应有出口(终止条件) 例1. 求n！int Factorial(int n) if (n=0) return(1); return n*Factorial(

30、n-1);/Factorial数据构造-第3章 栈和队列72递归算法的实现原理递归算法的实现原理123s123- 利用栈，栈中每个元素称为任务记录，分成三个部分： 前往地址 实践参数表(变参和值参) 部分变量- 发生调用时，维护现场，即当前的任务记录入栈，然后 转入被调用的过程- 一个调用终了时，恢复现场，即假设栈不空，那么退栈，从 退出的前往地址处继续执行下去73递归时系统任务原理例如递归时系统任务原理例如int Factorial( int n) L1: if ( n=0 ) L2: return 1; L3: else return n*Factorial(n-1); L4: /Fact

31、orial void main(void) L0: N=Factorial(3); /main 前往地址 n Factorial NL0 3 / / L3 3 /L3 2 /L3 1 / 1126数据构造-第3章 栈和队列74递归算法的用途递归算法的用途 求解递归定义的数学函数 在以递归方式定义的数据构造上的运算/操作 可用递归方式描画的处理过程 递归算法的特点 递归算法简单明了，直观易懂 时间效率低，空间开销大，算法不易优化数据构造-第3章 栈和队列75递归转换为非递归的方法递归转换为非递归的方法1采用迭代算法采用迭代算法 递归递归从顶究竟从顶究竟 迭代迭代从底到顶从底到顶 例：求例：求n！ int fact(int n) m=1; for ( i=1; idata); linklist_output(p-next) /linklist_output运用跳转语句：void linklist_output1(