DS03-栈和队列.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,栈（,Stack）,栈的应用,队列（,Queue）,队列的应用,第三章 栈和队列,定义,3.1 栈,与线性表相同，仍为一对一(1:1)关系,。,用,顺序栈,或,链栈,存储均可，但以顺序栈更常见,只能在,栈顶,运算，且访问结点时依照,后进先出,（,LIFO）,或,先进后出,（,FILO）,的原则。,关键是编写,入栈,和,出栈,函数，具体实现依顺序栈或链栈的存储结构有别而不同。,存储结构,运算规则,实现方式,逻辑结构,限定只能在表的,一端,进行插入和删除运算的线性表。,基本操作,建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值，等等。,栈,是仅在,表尾,进行插入、删除操作的线性表。,表尾,(,即,a,n,端),称为,栈顶,/,top;,表头,(,即,a,1,端),称为,栈底,/,base,例如：栈,S,=(a,1,a,2 ,a,3 ,.,a,n-1 ,a,n,),插入元素到栈顶的操作，称为,入,栈,。,从栈顶删除最后一个元素的操作，称为,出栈,。,a,n,称为栈顶元素,a,1,称为栈底元素,强调：,插入和删除都只能在表的一端（栈顶）进行！,栈的,基本操作,ClearStack,(S),：,清除栈,S,中的所有元素,InitStack,(S),：,构造一个空栈,S,StackEmpty,(S),：,判断栈,S,是否为空，若为空，则返回,true,；,否则返回,false,GetTop,(S),：,返回,S,的栈顶元素，但不移动栈顶指针,Push(S,x),：,插入元素,x,为新的栈顶元素（入栈操作),Pop(S)：,删除,S,的栈顶元素并返回其值（出栈操作）,顺序栈的存储结构和操作的实现,顺序栈:,是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。,在,C,语言中，预设一个数组的最大空间,栈底设置在0下标端，栈顶随着插入和删除元素而变化，用一个整型变量,top,来指示栈顶的位置,。,a,1,a,2,a,n,顺序栈,S,a,i,0,n,栈底,栈顶,top,压入(,PUSH),:,S,top,+,=,a,n+1,弹出(,POP),:,e,=S,-,top,顺序栈存储结构的描述：,#,define,Maxsize,100,/*,设顺序栈的最大长度为100，可依实现情况而修改*/,typedef int datatype,;,typedef struct,datatype,stack,Maxsize,;,int,top；,/*,栈顶指针*/,SeqStack,；,/*,顺序栈类型定义*/,SeqStack,*s；,/*s,为顺序栈类型变量的指针*/,顺序栈的几种状态以及在这些状态下栈顶指针,top,和栈中结点的关系,栈为空的条件：,top=0;,栈满的条件 ：,top-base=,Maxsize,若入栈动作使地址向高端增长，称为“,向上生成,”的栈；,若入栈动作使地址向低端增长，称为“,向下生成,”的栈；,对于向上生成的堆栈:,入栈,：栈指针,top“,先压后加,”,:,S,top+,=a,n+1,出栈,：栈指针,top“,先减后弹,”,:,e=S,-top,顺序栈的基本操作,构造一个空顺序栈,SeqStack,*,InitStack,(),SeqStack,*S;,S=(,SeqStack,*),malloc,(,sizeof,(,SeqStack,);,if(!S),printf,(,“,空间不足”,),；,return NULL;,else,S-top=0;,return S;,取顺序栈栈顶元素,datatype GetTop,(,SeqStack,*S),if(S-top=0),printf,(n,栈是空的,!);,return FALSE;,else,return S-stackS-top-1;,判别空栈,int StackEmpty,(,SeqStack,*S),if(S-top=0),return TRUE;,else,return FALSE;,顺序栈的入栈操作,例如用堆栈存放（,A，B，C，D）,A,A,C,B,A,B,A,top,核心语句：,顺序栈入栈函数,PUSH（）,SeqStack,*Push(,SeqStack,*S,，,datatype,x),if(S-top=,Maxsize,),return NULL;else,S-stackS-top=x;,S-top+;,return s;,Push(B);,Push(C);,Push(D);,top,top,top,top,低,地址,L,Push(A);,高地址,M,B,C,D,顺序栈出栈操作,例如从栈中取出,B,D,C,B,A,top,top,D,C,A,B,D,C,B,A,top,D,C,B,A,top,低,地址,L,高地址,M,D,核心语句：,Pop();,顺序栈出栈函数,POP(),datatype,Pop(,SeqStack,*S),if(S-top=0),printf,(,nThe,sequence stack is empty!);,return FALSE;,S-top-;,return S-stackS-top;,Pop();,Printf,(,Pop(),);,链栈的入栈操作和出栈操作,链栈的构造方式,以头指针为栈顶，,在头指针处,插入或删除.,栈顶,栈底,栈也可以用链式结构来表示，用链式结构来表示的栈就是,链栈,top,a,1,a,2,a,n-1,a,n,next,data,链栈中每个结点由两个域构成：,data,域和,next,域，其定义为：,Typedef struct,node,datatype,data;,struct,node*next;,LinkStack,;,LinkStack,*top;,将,x,入栈，修改栈顶指针:,top=p,a,n,出栈，修改栈顶指针:,top=top-next,LinkStack,*Push(,LinkStack,*top,，,datatype,x),LinkStack,*p;,p=(,Linkstack,*),malloc,(,sizeof,(,LinkStack,);,p-data=x;p-next=top;,top=p;return top;,链栈入栈操作,LinkStack,*Pop(,LinkStack,*top),LinkStack,*q;,if(!top),printf,(n,链栈是空的,!);,return NULL;q=top;,top=top-next;free(q);,return top;,链栈出栈操作,1、,数制转换（十转,N）,设计思路：用栈暂存低位值,2、,括号匹配问题,设计思路：用栈暂存左括号,3、,子程序的调用,设计思路：用栈暂存指令地址,4、,逆置一个单链表,设计思路：用栈暂存每一结点,3.2 栈的应用举例,例,3.2,将十进制整数转换成二至九之间的任一进制数输出,将一个十进制数,4327,转换成八进制数,(10347),8,：,1、,当,N0，,将,N%r,压入栈,s,中；,2、,用,N/r,代替,N；,3、,若,N0，,则重复（1）、（2）；若,N=0，,则将栈,s,的内容依次出栈。,解题,思路如下：,void conversion(,int,N,int,r),int,x=N,y=r;,SeqStack,*s;,s=,InitStack,();while(N!=0),Push(s,N%r);,N=N/r;,printf,(“n,十进制数%,d,所对应的%,d,进制数是:”，,x,y);,while(!,StackEmpty,(s),printf,(“%d”,Pop(s);,printf,(“n”);,例3.5 利用一个顺序栈将利用一个顺序栈将单链表（,a,1,a,2,a,n,）（,其中,n=0）,逆置为（,a,n,a,n-1,，,a,1,）,1、建立一个,带头结点的,单链表,head；,2、,输出该单链表；,3、建立一个空栈,s,（,顺序栈）,；,4、依次将单链表的数据入栈；,5、依次将单链表的数据出栈，并逐个将出栈的数据存入单链表的数据域（自前向后）;,6、再输出单链表。,解题,思路如下：,linklist,*,backlinklist,(,linklist,*head),linklist,*p;,p=head-next;,initstack,();,while(p),push(,p=head-next;,while(!,stackempty,(s),p-data=pop(,return(head);,；,3.3,队列,与线性表相同，仍为一对一关系,。,顺序队,或,链队,，以,循环顺序队,更常见。,只能在队首和队尾运算，且访问结点时依照,先进先出,（,FIFO）,的原则。,关键是掌握,入队,和,出队,操作，具体实现依顺序队或链队的不同而不同。,存储结构,运算规则,实现方式,逻辑结构,只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。,基本操作,：,入队或出队，建空队列，判队空或队满等操作。,尾部插入,首部删除,队列定义,队列（,Queue）,是仅在,表尾,进行插入操作，在,表头,进行删除操作的线性表。它是一种先进先出,（）,的线性表。,例如：队列,Q=(,a,1,a,2 ,a,3 ,.,a,n-1 ,a,n,),在队尾插入元素称为,入队,；在队首删除元素称为,出队,。,队首,队尾,问：为什么要设计队列？它有什么独特用途？,答：,1.离散事件的模拟（模拟事件发生的先后顺序,例如,CPU,芯片中的指令译码队列）；,2.操作系统中的作业调度（一个,CPU,执行多个作业）；,3.简化程序设计。,队的,实现方式,是本节重点，,关键是掌握,入队,和,出队,操作。,具体实现依,存储结构,（,链队,或,顺序队,）的不同而不同。,1.,链队列,2.,顺序队,（,1,）,InitQueue,(Q),：,构造一个空队列,Q,（2）,QueueEmpty,(Q)：,判断队列是否为空,（3）,QueueLength,(Q)：,求队列的长度,（4）,GetHead,(Q)：,返回,Q,的队头元素，不改变队列状态,（5）,EnQueue,(Q，x)：,插入元素,x,为,Q,的新的队尾元素,（6）,DeQueue,(Q)：,删除,Q,的队头元素,（7）,ClearQueue,(Q)：,清除队列,Q,中的所有元素,链队列类型定义：,typedef struct,Qnode,*front;,/*,队头指针*/,Qnode,*rear;,/*,队尾指针*/,LinkQueue,;,结点类型定义：,typedef Struct Qnode,datatype,data;,/*,数据域*/,Struct Qnode,*next;,/*,指针域*/,Qnode,;,链队列,链队的几种状态示意图：,此时，,front=rear,修改,rear,指针,修改头结点的指针域,空链队的特征？,front=rear,链队会满吗？,一般不会，因为删除时有,free,动作。除非内存不足！,入队（尾部插入）：,rear-next=S;rear=S;,出队（头部删除）：,front-next=p-next;,怎样实现链队的,入队和出队,操作？,若设,S,所指,结点为入队结点,LinkQueue,*,InitQueue,(),LinkQueue,*q;,Qnode,*p;,Q=(,LinkQueue,*),malloc,(,sizeof,(,LinkQueue,);,p=(,Qnode,*),malloc,(,sizeof,(,Qnode,);,p-next=NULL;q-front=q-rear=p;,return q;,构造一个空链队操作,datatype GetHead,(,LinkQueue,*Q),if(Q-.front-next=Q-rear),printf,(“n,链队列为空,!”);,return FALSE;,return Q-front-next-data,；,取链队队头元素操作,void,EnQueue,(,LinkQueue,*Q,，,datatype,x),Qnode,*p;,p=(,Qnode,*),malloc,(,sizeof,(,Qnode,),；,p-data=x,；,p-next=NULL,；,Q-rear-next=p,；,Q-rear=p,；,链队入队操作,datatype DeQueue,(,LinkQueue,*Q),Qnode,*p;,datatype,x;,if(Q-front=Q-rear),printf,(,队列为空，无法删除！,);,return FALSE;,p=Q-front-next,；,x=p-data,；,Q-front-next=p-next,；,if(Q-rear=p),Q-rear=Q-front,；,free(p),；,return x;,链队出队操作,顺序队类型定义：,#,define MAXSIZE 100,/*,最大队列长度 */,typedef struct,datatype,dataMAXSIZE,；,/*,存储队列的数据空间*/,int,front,；,/*,队头指针，若队列不空，则指向队头元素*/,int,rear,；,/*,队尾指针，若队列不空，则指向队尾元素的下一个位置*/,SeqQueue,;,顺序队的几种状态示意图,入队操作:,rear=(rear+1)%,Maxsize,出队操作:,front=(front+1)%,Maxaize,新问题：,在循环队列中，空队特征是,front=rear；,队满时也会有,front=rear；,判决条件将出现二义性！,循环队列示意图,循环队列的几种状态,队空条件,:,front=rear,(,初始化时：,front=rear),队满条件,：,front=(rear,+1,)%N,(N=,maxsize,),队列长度,（即数据元素个数）,：,L=（Nrearfront）%N,J2 J3,J1 J4,J5,front,rear,解决,方案,-,人为,浪费一个单元,：,即,front,和,rear,二者之一指向实元素，另一个指向空闲元素(假设,front,指向队头元素，,rear,指向队尾元素的下一个位置）。,6,5,循环队列的基本操作实现,以建队、入队和出队三种基本操作为例,1,）初始化一个空队列,算法要求：生成一空队列,算法操作：为队列分配基本容量空间,设置队列为,空队列,，其特征即：,front=rear=0,（,也可为任意单元，如1，2，甚至-1）,建队的完整算法,SeqQueue,*,InitQueue,(),SeqQueue,*q,；,q=(,SeqQueue,*),malloc,(,sizeof,(,SeqQueue,),；,/*,开辟一个足够大的存储队列空间*/,q-front=q-rear=0,；,/*,将队列头尾指针置为零*/,return q,；,/*,返回队列的首地址*/,算法说明：向循环队列的队尾插入一个元素,分 析,：,(1),插入前应当先判断队列是否满？,if(q-rear+1)%,Maxsize,)=q-front),return false;,(2）,插入动作,q-data q-rear=x;,q-rear=(q-rear+1)%,Maxsize,;,入队操作,队列尺寸,出队操作,算法说明：删除队头元素，返回其值,x,分 析：,（1）,在删除前应当判断队列是否空？,if(q-front=q-rear)return false;,（2）,删除动作分析；,前面约定指针,front,指向队首元素的位置，故：,x=q-data q-front ;,q-front=(q-front+1)%,Maxsize,;,front,指针在元素出队后再加,int EnQueue,(,SeqQueue,*q,datatype,x),if(q-rear+1),MAXSIZE=q-front),printf,(n,循环队列满,!);,return FALSE;,q-dataq-rear=x,；,q-rear=(q-rear+1)%MAXSIZE;,return TRUE;,循环队列入队操作,datatype,DeQueue,(,SeqQueue,*q),datatype,x;,if(q-front=q-rear),printf,(“n,循环队列空！不能做删除操作！,”);,return FALSE;,x=q-data q-front,；,q-front=(q-front+1),MAXSIZE,；,return x,；,顺序队列出队操作,3.4 队列的应用,1、打印杨辉三角形,2、迷宫问题：寻找一条从迷宫入口到出口的最短路径,例,3.7,打印杨辉三角形。,此问题是一个初等数学问题。系数表中的第,i,行有,i+1,个数，除了第1个和最后一个数为1外，其余的数则为上一行中位于其左、右的两数之和。,算法分析,如果要计算并输出二项系数表（即杨辉三角形）的前,n,行的值，则所设循环队列的最大空间应为,n+2。,假设队列中已存有第,i,行的值，为计算方便，在两行之间均加一个“0”作为行间的分隔符，则在计算第,i+1,行之前，头指针正指向第,i,行的“0”，而尾元素为第,i+1,行的“0”。由此，从左至右输出第,i,行的值，并将计算所得的第,i+1,行的值插入队列。,分析第,i,行元素与第,i+1,行元素的关系如图所示,：,假设,n=4，i=3，,则输出第3行元素并求解第4行元素值的循环执行过程中队列的变化状态如图所示,：,完整算法请看教材,迷宫问题：寻找一条从迷宫入口到出口的最短路径,迷宫问题是实验心理学的一个经典问题，心理学家把一只老鼠从一个无顶盖的迷宫入口处赶进迷宫，在迷宫的出口处设置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次实验终于得到学习走通迷宫的路线。,算法分析,如果用计算机来处理：求出一条从入口到出口的通路，或者得出没有通路的结论。通常采用一种称为回溯法的方法，即不断试探且及时纠正错误的搜索方法，这需要借助,“,栈,”,来实现。此法在许多书中都有介绍，在此不再赘述。,如果在一般走迷宫的方法上，更进一步要求不论试探方位为何，找出一条最短路径，那该如何解决呢？其算法的基本思想是：从迷宫的入口,11,出发，向四周搜索，记下所有一步能到达的坐标点；然后依次从每一点出发，向四周搜索，记下所有从入口点出发，经过两步可以到达的坐标点,依次进行下去，一直到达迷宫的出口处,mn,。,然后从出口处沿搜索路径回溯直到入口点，这样就找到了从入口到出口的一条最短路径。,0 1 1 1 0 1 1 1,1 0 1 0 1 0 1 0,0 1 0 0 1 1 1 1,0 1 1 1 0 1 1 1,1 0 0 1 1 0 0 0,0 1 1 0 0 1 1 0,入口,出口,迷宫,1 1 1 1 1 1 1 1 1 1,1 0 1 1 1 0 1 1 1 1,1 1 0 1 0 1 0 1 0 1,1 0 1 0 0 1 1 1 1 1,1 0 1 1 1 0 1 1 1 1,1 1 0 0 1 1 0 0 0 1,1 0 1 1 0 0 1 1 0 1,1 1 1 1 1 1 1 1 1 1,加哨兵后的迷宫,我们可以使用如下的数据结构：,maze1.m,1.n,表示迷宫，为了算法方便，在四周加上“哨兵,1,”即变为数组,maze1.m+1,1.n+1,，,如右图所示。用数组,move8,中的两个域,dx,，,dy,分别表示,X,，,Y,方向的移动增量,方向,下标,dx,dy,北,0,-1,0,东,1,-1,1,东,2,0,1,东南,3,1,1,南,4,1,0,西南,5,1,-1,西,6,0,-1,西北,7,-1,-1,各,方向的移动增进量表,由于先到达的点要先向下搜索，故引进一个“先进先出”数据结构队列来保存已到达的点的坐标。到达迷宫的出口点(,m,n),后，为了能够从出口点沿搜索路径回溯直至入口，对于每一点，在记下点的坐标的同时，还要记下到达该点的前驱点，因此，需用一个结构数组,sqnum,作为队列的存储空间。因为迷宫中每个点至多被访问一次，所以,num,至多等于,m*n。sq,的每一个结点有三个域：,x,，,y,和,pre,，,其中,x,y,分别为所到达的点的坐标，,pre,为前驱点在,sq,中的下标。除,sq,外，还有队头、队尾指针：,front,和,rear,用来指向队头和队尾元素。,初始状态是，队列中只有一个元素,sq,，,记录的是入口点的坐标（,），因为该点是出发点，因此没有前驱点，,pre,域为，队头指针,front,和队尾指针,rear,均指向它。此后搜索时都是以,front,所指点为搜索的出发点，当搜索到一个可到达的点时，就将该点的坐标及,front,所指点的位置入队，不但记下了到达点的坐标，还记下了它的前驱点的下标。若,front,所指点的个方向搜索完毕，则出队，继续对下一点搜索。搜索过程中若遇到出口点，则表示成功，搜索结束，打印出迷宫的最短路径，算法结束；如果当前队空，即表示没有搜索点了，则表明迷宫没有通路，算,法也结束。,