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

《《数据结构课件、代码》第3章栈和队列.ppt》由会员分享，可在线阅读，更多相关《《数据结构课件、代码》第3章栈和队列.ppt（79页珍藏版）》请在三一办公上搜索。

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

2、即最后进栈的元素。因此，栈又称为后进先出的线性表。简称为LIFO表。,栈的示意图,a1,a2,an,栈顶（表尾）,栈底,bottom,top,入栈push,出栈pop,栈在计算机中主要有两种基本的存储结构：顺序存储结构和链式存储结构。顺序存储的栈为顺序栈 链式存储的栈为链栈,栈的存储方式,1.2 顺序栈,栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。,顺序栈的类型定义,#define TRUE 1#define FALSE 0#define Stack_Size 50typedef struct StackElementTy

3、pe elemStack_Size;/*一维数组*/int top;/*用来存放栈顶元素的下标*/SeqStack;,top,空栈,top,top,top,top,top,a 进栈,b 进栈,a,a,b,a,b,c,d,e,e 进栈,a,b,c,d,e,f 进栈溢出,a,b,d,e,e 退栈,c,top,c 退栈,b 退栈,a,b,a,a 退栈,空栈,top,a,b,d,d 退栈,c,top,a,b,c,top,top,注意,顺序栈中元素用向量存放栈底位置是固定不变的，可设置在向量两端的任意一个端点栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶

4、位置,顺序栈的基本运算,（1）置栈空（初始化）（2）判栈空（3）判栈满（4）进栈操作（5）退栈操作（6）取栈顶元素,（1）置栈空（初始化）,void InitStack（SeqStack*S）/将顺序栈置空 S-top=-1;,(2)判栈空,int StackEmpty（SeqStack*S）/*判栈S为空栈时返回值为真，反之为假*/return S-top=-1;,（3）判栈满,int StackFull（SeqStack*S）/*判栈S为满时返回真，否则返回假*/return S-top=StackSize-1;,（4）进栈,进栈时，需要将S-top加1 注意：S-top=StackSiz

5、e-1表示栈满上溢现象-当栈满时，再做进栈运算产生空间溢出的现象。上溢是一种出错状态，应设法避免。void Push（SeqStack*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）取栈顶元素,DataType StackTop（S）if(StackEmpty(S)Error(Stack is empty);return S-dataS-top;,1

6、.4 链栈,链栈是采用链表作为存储结构实现的栈，是线性链表的特例。因为栈的插入和删除操作仅限制在表头位置进行，所以链表的表头指针就作为栈顶指针。,top为栈顶指针，始终指向当前栈顶元素结点。若top=NULL，则代表空栈。注意：链栈在使用完毕时，应该释放其空间。,typedef struct stacknode DataType data struct stacknode*next StackNode;StackNode*head=NULL;typedef struct StackNode*top;/栈顶指针 LinkStack;,链栈的基本运算,(1)置栈空(2)判栈空(3)进栈(4)退栈(

7、5)取栈顶元素,（1）置栈空,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-

8、top=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入栈，修改栈顶指针:top=p,an出栈，修改栈顶指针:top=top-next,链栈的入栈操作和出栈操作,（5）取栈顶元素,DataType StackTop(LinkStack*S)if(StackEmpty(S)Error(St

9、ack is empty.)return S-top-data;,注意,链栈中的结点是动态分配的，所以可以不考虑上溢，无须定义StackFull运算。,2.队列,2.1 队列的定义2.2 顺序队列2.3 链队列,队列是一种特殊的线性表，限定插入和删除操作分别在表的两端进行。a1 a2 ai an,2.1 队列的定义和基本运算,队列的性质,（1）允许删除的一端称为队头（Front）。（2）允许插入的一端称为队尾（Rear）。（3）当队列中没有元素时称为空队列。（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表,队列的进队和出队,front,rear,空队列

10、,front,rear,A进队,A,front,rear,B进队,A B,front,rear,C,D进队,A B C D,front,rear,A退队,B C D,front,rear,B退队,C D,front,rear,E,F,G进队,C D E F G,C D E F G,front,rear,H进队,溢出,队列的进队和出队原则,进队时队尾指针先进一 rear=rear+1，再将新元素按 rear 指示位置加入。出队时队头指针先进一 front=front+1，再将下标为 front 的元素取出。队满时再进队将溢出出错；队空时再出队将队空处理。解决办法之一：将队列元素存放数组首尾 相接

11、，形成循环(环形)队列。,队列在计算机中主要有两种基本的存储结构：顺序存储结构和链式存储结构。顺序存储的队列为顺序队列链式存储的队列为链队列,队列的存储方式,队列的基本运算,(1)初始化队列(2)判队空(3)判队满(4)入队(5)出队(6)取队首元素,2.2 顺序队列,2.2.1 顺序队列的定义2.2.2 顺序队列的基本运算2.2.3 循环队列,2.2.1 顺序队列的定义,队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表,顺序队列的表示,和顺序表一样，顺序队列用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，设置两个“指针”front和rear分别指示队

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

13、,2.2.3 循环队列,为充分利用向量空间，克服“假上溢”现象的方法：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。,入队操作时的尾指针运算:rear=(rear+1)%Maxsize出队操作时的头指针运算:front=(front+1)%Maxaize问题：在循环队列中，由于队空时有front=rear；队满时也有front=rear；因此我们无法通过front=rear来判断队列是“空”还是“满”。,循环队列示意图,循环队列的几种状态,循环队列队满和队空的描述方法,队空:,队满:,rear=front（?）,rear=front,循环队列边界条件处理,如何判断是“空”还是“满

14、”。解决这个问题的方法至少有三种：另设一布尔变量以区别队列的空和满；少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；使用一个计数器记录队列中元素的总数（即队列长度）。,顺序循环队列的类型定义,#define QueueSize 100/应根据具体情况定义该值typedef char DataType;/DataType的类型依赖于具体的应用typedef struct int front;/头指针，队非空时指向队头元素int rear;/尾指针，队非空时指向队尾元素的下一位置 int count;/计数器，记录队

15、中元素总数 DataType dataQueueSizeCirQueue;,顺序循环队列的基本运算,1.置队空2.判队空3.判队满4.入队5.出队6.取队头元素,置队空,void InitQueue(CirQueue*Q)Q-front=Q-rear=0;Q-count=0;/计数器置0,判队空,int QueueEmpty(CirQueue*Q)/队列无元素为空，属第三种方法 return Q-count=0;int QueueEmpty(CirQueue*Q)/属第二种方法 return Q-rear=Q-front;,判队满,int QueueFull(CirQueue*Q)return

16、 Q-count=QueueSize;/队中元素个数等于QueueSize时队满，属第三种方法int QueueFull(CirQueue*Q)return(Q-rear+1)%QueueSize=Q-front;/队中元素个数等于QueueSize时队满，属第二种方法,入队,void EnQueue(CirQueue*Q,DataType x)if(QueueFull(Q)Error(Queue overflow);/队满上溢Q-count+;/队列元素个数加1Q-dataQ-rear=x;/新元素插入队尾Q-rear=(Q-rear+1)%QueueSize;/循环意义下将尾指针加1,出队

17、,DataType DeQueue(CirQueue*Q)DataType temp;if(QueueEmpty(Q)Error(Queue underflow);/队空下溢temp=Q-dataQ-front;Q-count-;/队列元素个数减1Q-front=(Q-front+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

18、.3.2 链队列的基本运算,链队列的定义,队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。,队头在链头，队尾在链尾。,q.frontq.rear,q.frontq.rear,空队列,链队列的几种状态示意图,此时，front=rear,修改rear指针,修改头结点的指针域,链队列为空的特征：front=rear,链队列会满吗？,一般不会，因为删除时有free动作，除非内存不足！,修改rear指针,注意,增加指向链表上的最后一个结点的尾指针，便于在表尾做插入操作,和链栈类似，无须考虑判队满的运算及上溢。在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是

19、队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。以上讨论的是无头结点链队列的基本运算。和单链表类似，为了简化边界条件的处理，在队头结点前也可附加一个头结点，增加头结点的链队列的基本运算,定义链队列的存储结构,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.取

20、队头元素,（1）置空队,int InitQueue(LinkQueue*Q)/构造一个空队列*Q Q-front=(LQnode*)malloc(sizeof(LQnode);if(Q-front=NULL)return FALSE;/申请内存失败返回 Q-rear=Q-front;Q-front-next=NULL;return TRUE;/申请内存成功返回,（2）判队空,int QueueEmpty(LinkQueue*Q)return Q-front-next=NULL/*实际上只须判断队头指针是否为空即可*/,（3）入队,void EnQueue(LinkQueue*Q,DataTyp

21、e x)/将元素x插入链队列尾部QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode);/申请新结点 p-data=x;p-next=NULL;if(QueueEmpty(Q)Q-front-next=p;Q-rear=p;/将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”);

22、/下溢p=Q-front-next;/指向队头结点x=p-data;/保存队头结点的数据Q-front-next=p-next;/将队头结点从链上摘下if(Q-rear=p)/原队中只有一个结点，删去后队列变空，此时队头指针已为空 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 递归、非递归,当在

23、一个函数的运行期间调用另一个函数时,在运行该被调用函数之前,需先完成三项任务：,保存现场,保存本函数参数、返回地址等信息;为被调用函数的局部变量分配存储区传递参数;将控制转移到被调用函数的入口。,3.1 函数调用,从被调用函数返回调用函数之前,应该完成下列三项任务：,保存返回的计算结果(用函数名,引用参数)；释放被调函数的数据区,恢复调用函数现场;依照被保存的返回地址将控制转移到调用函数。,多个函数嵌套调用的规则,此时的内存管理实行“栈式管理”,后调用先返回！,例如：main()void a()void b()a();b();/main/a/b,main的数据区,函数a的数据区,函数b的数据区

24、,栈在函数调用中的作用,过程一,过程二,过程三,过程四,断点一,断点二,断点三,stack,数据结构-第3章 栈和队列,70,3.2 递归、非递归,递归的含义 函数、过程或者数据结构的内部又直接或者间接地由自身定义。适合于应用递归的场合规模较大的问题可以化解为规模较小的问题，且二者处理(或定义)的方式一致；当问题规模降低到一定程度时是可以直接求解的(终止条件)例1.阶乘 n!=1 n=0 n(n-1)!n0,数据结构-第3章 栈和队列,71,写递归算法应注意的问题,递归算法本身不可以作为独立的程序运行，需在其它的程序中设置调用初值，进行调用；递归算法应有出口(终止条件)例1.求n！,int F

25、actorial(int n)if(n=0)return(1);return n*Factorial(n-1);/Factorial,数据结构-第3章 栈和队列,72,递归算法的实现原理,1,2,3,-利用栈，栈中每个元素称为工作记录，分成三个部分：返回地址 实际参数表(变参和值参)局部变量-发生调用时，保护现场，即当前的工作记录入栈，然后 转入被调用的过程-一个调用结束时，恢复现场，即若栈不空，则退栈，从 退出的返回地址处继续执行下去,73,递归时系统工作原理示例,int Factorial(int n)L1:if(n=0)L2:return 1;L3:else return n*Facto

26、rial(n-1);L4:/Factorial void main(void)L0:N=Factorial(3);/main 返回地址 n Factorial N,L0 3/,L3 3/,L3 2/,L3 1/,1,1,2,6,数据结构-第3章 栈和队列,74,递归算法的用途,求解递归定义的数学函数在以递归方式定义的数据结构上的运算/操作可用递归方式描述的解决过程递归算法的特点递归算法简单明了，直观易懂时间效率低，空间开销大，算法不易优化,数据结构-第3章 栈和队列,75,递归转换为非递归的方法,1）采用迭代算法 递归从顶到底 迭代从底到顶 例：求n！int fact(int n)m=1;fo

27、r(i=1;i=n;i+)m=m*i;return m;/fact,数据结构-第3章 栈和队列,76,2）消除尾递归,例：顺序输出单链表中的结点数据void linklist_output(LNode*p);if(p)printf(p-data);linklist_output(p-next)/linklist_output,使用跳转语句：void linklist_output1(LNode*p)1:if(p)printf(p-data);p=p-next;goto 1/linklist_output1,使用循环语句：void linklist_output2(LNode*p)while(p

28、)printf(p-data);p=p-next;/linklist_output2,p,an,a 2,a1,数据结构-第3章 栈和队列,77,3)对递归算法改写通用方法（利用栈模拟递归）,如果是递归函数，需改写为递归过程 例：求n!void fact(int n,int 2:f=n*f/fact,InitStack(S);,Push(S,(2,n,f);n=n-1;goto 0;,if(!StackEmpty(S)(S.top-1)-f=f;/还原本层变参值 Pop(S,(rd,n,f);goto rd;,78,自设栈模拟系统工作栈,例：typedef struct int rd;int n;int f;SElemType;改写算法在程序开头增加栈的初始化语句改写递归调用语句 入栈处理；确定调用的参数值；转至调用的开始语句改写所有递归出口 退栈还原参数；转至返回地址处,S,rd n f,top,void fact(int n;int/fact,void fact(int n;int/fact,注：此时可确定栈中只 存放n值即可。typedef int SElemType;,