《【教学课件】第三章栈和队列.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第三章栈和队列.ppt（57页珍藏版）》请在三一办公上搜索。
1、第三章 栈和队列,学习要点理解栈和队列的基本概念和各种存储结构；掌握栈和队列的各种运算方法了解堆栈在递归运算中的应用,3.1 栈 栈的概念 使用数组创建栈使用链表创建栈,3.1.1 栈的概念,定义：栈(Stack)是限制在一端进行插入和删除运算的线性表。通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。,（a1,a2,.,an）,插入,删除,栈的特点后进先出(LIFO),栈顶：对栈进行操作的一端。栈顶指针：指示栈顶位置的指针。栈的长度：栈中元素的个数。假设栈S=(a1，a2，a3，,an)，则a1称为栈底元素，an为栈顶元素。插入的过程称为入栈，
2、删除的过程称为出栈。栈中元素的出栈入栈是按照后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。,(a)调用a函数,r进栈(c)调用c函数,t进栈(e)返回a函数,s退栈,(b)调用b函数,s进栈(d)返回b函数,t退栈(f)返回主程序,r退栈,栈在函数嵌套调用中的应用：,栈的基本操作InitStack(s)构造一个空栈SClearStack(s)将栈S清为空栈。EmptyStack(s)若栈S为空栈，返回TRUE，否则FALSELenStack(s)返回栈S中元素的个数，即栈的长度GetTop(s)取出S的栈顶元素的值Push(s,x)插入元素x为新的栈顶元素Pop(s,x)删除S的栈
3、顶元素，并返回其值,3.1.2 栈的顺序存储结构,顺序栈：是利用一块地址连续的存储单元来存放栈中的元素，同时要利用一个指示器top 来指示栈顶元素的位置。,typedef structElemtype skMaxsize；int top;seqstack;seqstack*s;s-sks-top/当前栈顶元素,栈的几种状态示意图,栈顶指针top,指向实际栈顶位置，初值为-1,top=-1,栈空，此时出栈，则下溢（underflow)top=M-1,栈满，此时入栈，则上溢（overflow),顺序栈的图示,1)进栈操作 进栈函数分为两个步骤：将栈顶的指针加1。将要存放的数据存放在指针所指向的数组
4、中。,1)进栈操作 int Push(seqstack*s,Elemtype x)if(s-top=Maxsize-1)printf(out of space!n);return(0);s-top+;s-sks-top=x;return(1);,2）出栈操作出栈操作也分为两个步骤：取出目前栈指针所指数组元素的内容。将栈指针的内容减1，即指向下一个栈元素。,2）出栈操作int Pop(seqstack*s,Elemtype*e)if(s-top=-1)printf(no element!n);return(0);*e=s-sks-top;s-top-;return(1);,3）其它几种操作seq
5、stack*InitStack()/创建空栈 seqstack*s;s=(seqstack*)malloc(sizeof(seqstack);if(!s)printf(“未完成空间分配!n);return(null);s-top=-1;return(s);,int EmptyStack(seqstack*s)/栈的判空操作 if（s-top=-1）s-top=Maxsize-1return(1);elsereturn(0);Elemtype GetTop(seqstack*s)/取栈顶元素 if(EmptyStack(s)return(0);elsereturn(s-sks-top);,注意：
6、对于顺序栈，入栈时，首先判栈是否满了，栈满的条件为：s-top=MAXSIZE-1，栈满时，不能入栈；否则出现空间溢出。出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作。合理初始化栈的方法：先为栈分配一个基本容量，然后在应用过程中，当栈的空间不够时再逐步扩大。,栈的链式存储结构，也称链栈，如图所示：,data next,S,栈顶,栈底,3.1.2 栈的链式存储结构,typedef struct nodeElemtype data;struct node*next;stacknode,*LinkStack;,链栈的存储结构:,top,1)进栈算法int PushLinkStack(LinkS
7、tack S,Elemtype x)LinkStack p;p=(LinkStack)malloc(sizeof(StackNode);if(!p)printf(分配不成功n);return(0);p-data=x;p-next=S-next;S-next=p;return(p);,S,x,2)出栈算法int PopLinkStack(LinkStack S,Elemtype*e)LinkStack p;if(S-next=null)printf(Not Existn);return(0);p=S-next;S-next=S-next-next;e=p-data;free(p);return(
8、1);,3.1.3 共享栈,常采用将两个栈底设在可用空间的两端。仅当两个栈顶相遇时，才产生上溢，即所有可用空间已用完。对每个栈可用的最大空间就可能大于整个可用空间的一半m/2。,有时，一个程序设计中，需要使用多个同一类型的栈，这时候可能会产生一个栈空间过小，容量发生溢出，而另一个栈空间过大，造成大量存储单元浪费的现象。为了充分利用各个栈的存储空间，这时可以采用多个栈共享存储单元，即给多个栈分配一个足够大的存储空间，实现多个栈存储空间的动态分配。,小结1 栈是限定仅能在栈顶一端进行插入、删除操 作的线性表；2 栈的元素具有后进先出的特点；3 栈顶元素的位置由一个称为栈顶指针的变量 指示，进栈、出
9、栈操作要修改栈顶指针；,3.2 栈的应用举例,结果：2 5 0 4,例1 数制转换,十进制N和其它进制数的转换是计算机实现计算的基本问题,其中一个简单算法基于下列原理:N=(N div d)10d+N mod d例如:(1348)10=283+582+08+4=(2504)8 N N div 8 N mod 81348 168 4 168 21021 252 02,计算时从低位到高位顺序产生八进制数的各个数位,显示时按从高位到低位的顺序输出,void Transform()S=InitStack();scanf(%d,利用栈“先进后出”的性质，把先产生的数位压入栈中，然后再从栈顶依次弹出即可,
10、3.3 栈与递归,什么是递归一个对象（事物）的组成包含了自身或者说对于一个对象的描述又用到了该对象本身的现象称为递归。递归是程序设计中一个很有用的工具，许多数学函数的定义和程序设计等许多领域中都用到了递归。,A()A();,A 直接调用自己,B间接调用自己,递归算法的编写1）将问题用递归的方式描述（定义）2）根据问题的递归描述（定义）编写递归算法问题的递归描述（定义）递归定义包括两项 基本项（终止项）：描述递归终止时问题的求解；递归项：将问题分解为与原问题性质相同，但规模较小的问题；例 阶乘函数n!=1*2*3*4*(n-1)*n n!递归定义n!=1 当 n=1 时n!=n(n-1)!当n
11、1 时,用(n-1)!定义n!,计算5的阶乘（5！=5X4X3X2X1）int f(int n)if(n=1)return(1);else return(n*f(n-1);,f(1),f(2),f(3),f(4),f(5),top,1 f(1)=1,2*f(1)f(2)=2*f(1),3*f(2)f(3)=3*f(2),4*f(3)f(4)=4*f(3),5*f(4)f(5)=5*f(4),例1 阶乘函数,void print(int w)int i;if(w!=0)print(w-1);for(i=1;i=w;+i)printf(“%3d,”,w);printf(“/n”);,运行结果：1，
12、2，2，3，3，3，,例2 递归的执行情况分析,递归调用执行情况如下：,print(w-1);for(i=1;i=w;+i)printf(“%3d,”,w);printf(“/n”);,3.4 队列 队列的概念 循环队列队列的顺序存储和实现3.4.3 队列的链式存储和实现,3.4.1 队列的概念,什么是队列?队列是限定仅能在一端进行删除，另一端进行插入的线性表。,允许删除的一端称为队头，允许插入的一端称为队尾队列的长度：队列中元素的个数,队列的特点先进先出(FIFO),队列的基本操作InitQueue(Q)将Q置为一个空队列QueueEmpty(Q)若Q为空队列返回TRUE，否则FALSEQu
13、eueLen(Q)返回队列Q中元素个数，即队的长度GetHead(Q)返回Q的队头元素EnQueue(Q,e)插入元素e为队Q的新队尾元素DeQueue(Q,e)删除Q的队头元素，并用e返回其值,3.4.2 队列的顺序存储和循环队列,用一个数组来实现队列的顺序存储队头指针front指向队头元素实际位置的前一个位置队尾指针rear指向队尾元素在队列中的实际位置,队列顺序结构的C语言描述：typedef structElemtype elemmaxsize;int front;int rear;SqQueue;SqQueue*Q;,实现：用一维数组实现elemM,J1,J2,J3,设两个指针fro
14、nt,rear,约定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=-1,空队列条件：front=rear入队列：elem+rear=x;出队列：x=elem+front;,24,56,（a)假溢出,(b)真溢出,rear,front,32,rear,front,15,42,61,存在问题设数组维数为M，则：当front=-1,rear=M-1时，再有元素入队发生溢出真溢出当front-1,rear=M-1时，再有元素入队发生溢出假溢出当rear指向数组的最后一个分量的时候，队列再也无法插入新元素，而这时常常还有大量的内存空间被闲置。,解决方案队首固定，每次出队
15、剩余元素向下移动浪费时间循环队列基本思想：把队列设想成环形，让elem0接在elemM-1之后，若rear+1=M,则令rear=0;实现：利用“模”运算入队：rear=(rear+1)%M;elemrear=x;出队：front=(front+1)%M;x=elemfront;队满、队空判定条件,队满、队空判定条件,front,rear,(c)队空,(b)队满,front,rear,front,rear,(a)一般情况,队空：front=rear队满：front=rear,解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间，约定队头指示的位置不存放元素：队空：front=rea
16、r 队满：(rear+1)%M=front,循环队列的基本操作算法,front,rear,（1）队头指针 front=(front+1)%M；等价于：if（front+1=M）front=0;else front=front+1;,（2）队尾指针rear=(rear+1)%M；等价于：if（rear+1=M）rear=0;else rear=rear+1;,循环队列在指针移动处理时与一般队列不同：,1）初始化队列 功能：对循环队列Q进行初始化，即将Q置为一个空队列；算法：,建一个空队列Q,front,rear,int InitQueue(SqQueue*Q)Q-font=0;Q-rear=0;
17、return OK;,2）入队操作 功能：将元素 x 插入队尾,元素 x 入队前,元素 x 入队后,Q-rear=(Q-rear+1)%Maxsize;Q-elemQ-rear=e;,入队算法：,int EnQueue(SqQueue*Q,ElemType e)if(Q-rear+1)%Maxsize=Q-front)return ERROR;Q-rear=(Q-rear+1)%Maxsize;Q-elemQ-rear=e;return OK;,2）出队操作 功能：删除队头元素,出队操作前,出队操作后,Q-front=(Q-front+1)%Maxsize;*e=Q-elemQ-front;,
18、int DeQueue(SqQueue*Q,ElemType*e)if(Q-front=Q-rear)return ERROR;Q-front=(Q-front+1)%Maxsize;*e=Q-elemQ-front;return OK;,出队算法：,打印队列算法：（数组打印）,void print1(SqQueue*Q)for(i=0;ielemi);printf(n);printf(“Q-front=,Q-front);printf(“Q-rear=,Q-rear);,打印队列算法：（循环队列打印）,void print2(SqQueue*Q)i=(Q-front+1)%Maxsize;w
19、hile(i!=Q-rear)printf(%d,Q-elemi);i=i+1;i=i%maxsize;printf(“Q-rear=,Q-rear);,空链队列,链队列图示,链队列,3.4.3 链队列-队列的链式表示与实现,链队列存储结构的C语言描述:,typedef struct QsNodeelemtype data;struct QsNode*next;Qsnode;typedef struct Qsnode*front;Qsnode*rear;LinkQueue;,1）队列初始化运算,int InitQueue(LinkQueue*Q)Q-front=(Qsnode*)malloc(
20、sizeof(Qsnode);if(!Q-front)return 0;Q-rear=Q-front;Q-front-next=NULL;return 1;,2）队列入队运算将结点加入到队列Q的尾端,int InQuene(LinkQueue*Q,elemtype e)Qsnode*p;p=(Qsnode*p)malloc(sizeof(Qsnode);if(p=NULL)return 0;p-data=e;Q-rear-next=p;Q-rear=p;Q-rear-next=NULL;return 1;,3）队列出队运算将队头元素删除,int DeQuene(LinkQueue*Q)Qsno
21、de*P;if(Q-front=Q-rear)return 0;p=Q-front-next;Q-front-next=p-next;if(Q-rear=p)Q-rear=Q-front;free(p);return 1;,当只有一个元素时，要修改尾指针,void print(LinkQueue*q)LinkQueue*p;p=q-front-next;while(p!=NULL)printf(%4d,p-data);p=p-next;,4）队列打印运算,1）解决计算机主机与外设不匹配的问题；2）解决由于多用户引起的资源竞争问题；,3）离散事件的模拟-模拟实际应用中的各种排队现象；4）用于处理
22、程序中具有先进先出特征的过程；,在操作系统课程中会讲到,队列的应用,返回目录,小结1 队列是限定仅能在表尾一端进行插入，表 头一端删除操作的线性表；2 队列中的元素具有先进先出的特点；3 队头、队尾元素的位置分别由称为队头指 针和队尾指针的变量指示；4 入队操作要修改队尾指针，出队操作要修 改队头指针；,习题1、设将整数1、2、3、4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问题：（1）若入栈次序为push(1)，pop()，push(2)，push(3)，pop()，pop()，push(4)，pop()，则出栈的数字序列为什么？（2）能否得到出栈序列423和
23、432？并说明为什么不能得到或如何得到。（3）请分析1、2、3、4的24种排列中，哪些序列可以通过相应的入出栈得到。3、循环队列的优点是什么？如何判断它的空和满？,4、设长度为n的链队列用单循环链表表示，若只设头指针，则怎样进行入队和出队操作；若只设尾指针呢？7、用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试设计置空队、判队空、判队满、出队、入队及取队头元素等六个基本操作。,9、指出下列程序段的功能是什么？(1)void demo1(seqstack*s)int I;arr64;n=0;while(!stackempty(s)arrn+=pos(s);for(I=0;n;I+)push(s,arrI);(2)void demo2(seqstack*s,int m)seqstack t;int i;initstack(t);while(!Stackempty(s)if(I=pop(s)!=m)push(t,I);While(!Stackempty(t)i=pop(t);push(s,I);,
