DS03-栈及队列.ppt

,*,栈（,Stack,）,栈的应用,队列,(Queue),队列的应用,第三章,栈与队列,定义：,3.1,栈,限定只能在表的,一端,进行插入与删除运算的线性表。,在栈中,通常将表中允许进行插入、删除操作的一端称为,栈顶,(Top),，同时表的另一端被称为,栈底,(Bottom),。栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。当栈中没有元素时称为,空栈,。,栈的插入操作被形象地称为,进栈,或入栈，删除操作称为出栈或,退栈,。,栈的示意图,与线性表相同，仍为一对一,(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,称为栈底元素,强调：,插入与删除都只能在表的一端（栈顶）进行！,栈的物理表示法,一、顺序栈的存储结构与操作的实现,顺序栈,:,是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。,在,C,语言中，预设一个数组的最大空间,栈底设置在,0,下标端，栈顶随着插入与删除元素而变化，用一个整型变量,top,来指示栈顶的位置,。,a,1,a,2,a,n,顺序栈,S,a,i,0,n+1,栈底,栈顶,top,压入,(,PUSH):,S,top,+,=a,弹出,(,POP),:,e=S,-,top,栈的基本操作,ClearStack(S),：,栈,S,已经存在，清除栈,S,中的所有元素,将,S,置成空栈,。,InitStack(),：,初始化，构造一个空栈,S,StackEmpty(S),：,判断栈,S,是否为空，若为空，则返回,true,；否则返回,false,GetTop(S),：,返回,S,的栈顶元素，但不移动栈顶指针,也不改变栈顶元素的值,Push(S,x),：,在,S,的顶部插入,(,亦称压入,),元素,x,；若,S,栈未满，将,x,插入栈顶位置，若栈已满，则返回,FALSE,，表示操作失败，否则返回,TRUE,。,（入栈操作,),Pop(S),：,删除,S,的栈顶元素并返回其值（出栈操作）,顺序栈存储结构的描述：,#define Maxsize 100,/*,设顺序栈的最大长度为,100,，可依实现情况而修改*,/,typedef int datatype;,typedef,struct,datatype stackMaxsize;,int top,；,/*,栈顶指针*,/,SeqStack,；,/*,顺序栈类型定义*,/,SeqStack*s,；,/*s,为顺序栈类型变量的指针*,/,顺序栈的几种状态以及在这些状态下栈顶指针,top,与栈中结点的关系,栈为空的条件：,top=0;,栈满的条件 ：,top=Maxsize,若入栈动作使地址向高端增长，称为,“,向上生成,”,的栈；,若入栈动作使地址向低端增长，称为,“,向下生成,”,的栈,；,对于向上生成的堆栈,:,栈指针指向待压入位置,入栈,：栈指针,top,“,先压后加,”,:S,top+,=a,i,出栈,：栈指针,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;,该函数返回一个,datatype,类型的值,判别空栈,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(s,B);,Push(s,C);,Push(s,D);,top,top,top,top,低地址,L,Push(s,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(),);,例,3.1,用,main,函数以及,display,函数，调试上述各种栈的基本操作算法。,#define Maxsize 50,typedef int datatype;,typedef,struct,datatype stackMaxsize;,int top,；,SeqStack,；,void display(SeqStack*s),/*,显示栈中所有元素值,*,/,int t;,t=s-top;,if(s-top=0),/*,栈为空,*,/,printf(the stack is empty!n);,else,while(t!=0),t-;,printf(%d-,s-stackt);,main(),int a6=3,7,4,12,31,15,i;,SeqStack*p;,p=InitStack();,for(i=0;itop=0;,/*,清空栈*,/,else,/*c1,是普通字符*,/,push(s,c1);,/*,入栈*,/,Scanf(,“,%c,”,display(s);,/*,输出栈,s,的所有元素值,*,/,链 栈,二、链栈的存储结构及操作的实现,栈也可以用链式结构来表示，用链式结构来表示的栈就是,链栈,链栈的构造方式,以头指针为栈顶，,在头指针处,插入或删除,.,一般情况下，头结点即为第一个结点,栈顶,栈底,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,入栈，修改栈顶指针,:p-next=top;top=p;,链栈的入栈操作,LinkStack*Push(LinkStack*top,，,datatype x),LinkStack*p;,p=(Linkstack*)malloc(sizeof(LinkStack);,p-data=x;,p-next=top;,top=p;,return top;,链栈入栈操作,栈顶指针,指向新申请结点的地址,修改栈顶指针,链栈的出栈操作,a,n,出栈，使工作指针,q,指向要出栈结点，然后修改栈顶指针,:,top=top-next,LinkStack*pop(LinkStack*top),LinkStack*q;,if(!top),/*,说明指针,top,指向,NULL,*/,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,：,N,是十进制数，要将,N,转换成,r,进制数,1,、当,N0,，将,N%r,压入栈,s,中，即余数进栈；,2,、用,N/r,代替,N,；,3,、若,N,0,，则重复上两步；若,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%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),/*,利用顺序栈逆置单链表,head,*/,linklist*p;,/*,工作指针*,/,p=head-next;,/*p,指向单链表的第一个结点*,/,initstack();,/*,初始化一个顺序栈,s,s,是结构体类型*,/,while(p)push(,p=head-next;,while(!stackempty(s),/*,将顺序表的数据出栈,*,/,/*,将出栈后的数据存入单链表,head,中,*,/,p-data=pop(,p=p-next;,return(head);,3.3,队 列,队列,(Queue),是另一种限定性的,线性表,，它只允许在表的一端插入元素，而在另一端删除元素,，所以队列具有,先进先出,(Fist In Fist Out,，缩写为,FIFO),的特性。,队列的定义,在队列中，允许插入的一端叫做,队尾,(rear),，允许删除的一端则称为,队头,(front),。假设队列为,q=(a,1,，,a,2,，,，,a,n,),，那么,a,1,就是队头元素，,a,n,则是队尾元素。队列中的元素是按照,a,1,，,a,2,，,，,a,n,的顺序进入的，退出队列也必须按照同样的次序依次出队，也就是说，只有在,a,1,，,a,2,，,，,a,n-1,都离开队列之后，,a,n,才能退出队列。,问：为什么要设计队列？它有什么独特用途？,离散事件的模拟（模拟事件发生的先后顺序,例如,CPU,芯片中的指令译码队列）；,操作系统中的作业调度（一个,CPU,执行多个作业）；,队 列 的 实 现,与线性表相同，仍为一对一关系。,顺序队,或,链队,，以,循环顺序队,更常见。,只能在队首与队尾运算，且访问结点时依照,先进先出,（,FIFO,）,的原则。,关键是掌握,入队,与,出队,操作，具体实现依顺序队或链队的不同而不同。,存储结构,运算规则,实现方式,逻辑结构,基本操作,：,入队或出队，建空队列，判队空或队满等操作。,队列的,实现方式,是本节重点，,关键是掌握,入队,与,出队,操作。,具体实现依,存储结构,（,链队,或,顺序队,）的不同而不同。,1.,链队列,（,1,）,InitQueue(),：构造一个空队列,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,中的所有元素,队列,（,Queue,）,的逻辑表示,假设队列为,Q=(a,1,，,a,2,，,，,a,n,),，那么,a,1,就是队头元素，,a,n,则是队尾元素。队列中的元素是按照,a,1,，,a,2,，,，,a,n,的顺序进入的，退出队列也必须按照同样的次序依次出队，也就是说，只有在,a,1,，,a,2,，,，,a,n-1,都离开队列之后，,a,n,才能退出队列。,例如：队列,Q=(,a,1,a,2 ,a,3 ,.,a,n-1 ,a,n,),队首,队尾,链队列类型定义：,typedef,struct,Qnode *front;,/*,队头指针*,/,Qnode *rear;,/*,队尾指针*,/,LinkQueue;,结点类型定义：,typedef,Struct Qnode,datatype data;,/*,数据域*,/,Struct Qnode *next;,/*,指针域*,/,Qnode;,链队列,队列,（,Queue,）,的物理表示,链队的几种状态示意图：,空链队的特征？,front=rear,链队会满吗？,一般不会，因为删除时有,free,动作。除非内存不足！,(b),元素,x,入队,(d),元素,x,出队,此时，,front=rear,修改,rear,指针,修改头结点的指针域,入队（尾部插入）：,rear-next=S;rear=S;,出队（头部删除）：,front-next=S-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=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=y,；,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),/*,此时,p,出队,则队列为空,*,/,Q-rear=Q-front,；,free(p),；,return x;,链队出队操作,2,、顺序队列,顺序队列类型定义：,#define MAXSIZE 100,/*,最大队列长度*,/,typedef struct,datatype dataMAXSIZE,；,/*,存储队列的数据空间*,/,int front,；,/*,队头指针*,/,int rear,；,/*,队尾指针,*,/,SeqQueue;,约定：,队头指针,front,，若队列不空，则指向队头元素,。,队尾指针,rear,，若队列不空，则指向队尾元素的下一个位置,。,顺序队的几种状态示意图,头指针始终指向队头元素，尾指针始终指向队尾元素的下一个元素,为了防止出现假溢出，即在假溢出时，还能进行入队操作，我们采取循环队列。,循环队列示意图,在入队时：,将数据区,data0Maxsize-1,看成是首尾相接的圆环,当入队到,Maxsize-1,时,若队头元素的前面仍有空闲位置,下一个地址就应翻转为,0,使,data0,接在,dataMaxsize-1,之后,在出队时：,队头指针也要采用,front=(front+1)%Maxaize,通过求余运算,rear=(rear+1)%Maxsize,来求得。,循环队列的几种状态,在循环队列中当采用,入队操作,:,rear=(rear+1)%Maxsize,出队操作,:,front=(front+1)%Maxaize,就会出现新问题：,空队与队满时都有,front=rear,；,那么又如何判断队空与队满？,队空条件,:,front=rear,(,初始化时：,front=rear),队满条件,：,front=,（,rear,+1,)%N,(N=maxsize),J2 J3,J1 J4,J5,front,rear,解决方案,-,人为,浪费一个单元,：,即对大小为,Maxsize,的数组，只允许存,Maxsize-1,个结点,。,为此我们约定：,front,与,rear,二者之一指向实元素，另一个指向空闲元素,(,假设,front,指向队头元素，,rear,指向队尾元素的下一个位置，,即,rear,所指的单元始终为空,）。,队列长度（即数据元素个数）：,L=,（,N,rear,front,）,%N,循环队列的基本操作实现,1,）初始化一个空队列,算法要求：生成一空队列,算法操作：为队列分配基本容量空间,设置队列为,空队列,，其特征即：,front=rear=0,（,front,与,rear,也可为任意单元编号，如,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;,循环队列入队操作,队列尺寸,int EnQueue(SeqQueue*q,datatype x),if(q-rear+1),MAXSIZE=q-front),printf(n,循环队列满,!);return FALSE;,q-dataq-rear=x,；,/*,元素,x,入队*,/,q-rear=(q-rear+1)%MAXSIZE;,/*,修改尾指针*,/,return TRUE;,循环队列入队操作,循环队列的出队操作,算法说明：,删除队头元素,返回其值,x,并修改队头指针,分 析：,（,1,）在删除前应当判断队列是否空？,if(q-front=q-rear)return false;,（,2,）删除动作分析；,前面约定指针,front,指向队首元素的位置，故：,x=q-data q-front;,q-front=(q-front+1)%Maxsize;,front,指针在元素出队后再加,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,外，其余的数则为上一行中位于其左、右的两数之与。,（,a+b,）,n,的系数,算法分析,如果要计算并输出二项系数表（即杨辉三角形）的前,n,行的值，则所设循环队列的最大空间应为,n+2,。,如第四行为：,0 1 4 6 4 1,第五行为：,0 1 5 10 10 5 1,假设队列中已存有第,i,行的值，为计算方便，在,两行之间均加一个“,0”,作为行间的分隔符，则在计算第,i+1,行之前，头指针正指向第,i,行的“,0”,，而尾元素为第,i+1,行的“,0”,。由此，从左至右输出第,i,行的值，并将计算所得的第,i+1,行的值插入队列。,分析第,i,行元素与第,i+1,行元素的关系如图所示,：,在,i=2,时,队列的头指针指向,0,，尾指针指向,1,的下一位，,我们看如何 由第二行得到第三行的。,第三行的,0,入队,队头元素,0,出队并送入,s,中,取队头元素,1,并送入,t,中,s+t,的值,1,入队。,front,rear,这时队列的队头指针指向,1,，队尾指针指向第三行的第一个,3,的位置。,重复三步就得到第三行；类推，我们由第三行又得到第四行,从第,2,行数据计算并存放第,3,行数据,0,在运算的任一时刻,要产生下一个入队的元素,均是队头方向的两元素相加后入队,.,杨辉三角形元素入队顺序,0,0,0,0,0,0,假设,n=4,，,i=3,，则输出第,3,行元素并求解第,4,行元素值的循环执行过程中队列的变化状态如图所示,：,void YangHui(int n),/*,打印杨辉三角形的前,n,行*,/,SeqQueue *q;,int i,j,s,t;,for(i=1;i=n;i+),printf();,printf(1n);,/*,在中心位置输出杨辉三角最顶端的,1*/,q=InitQueue();,/*,设置容量为,n+2,的空队列*,/,EnQueue(q,0);,/*,添加行分隔符，,即,0,入队,*,/,EnQueue(q,1);EnQueue(q,1);,/*,第一行的值入队*,/,、出队并保存出队元素,、取出,front,所指元素并保存,、计算前两步得到的元素值之,与,并入队,重复这三步。（当由第,i,行求得第,i+1,行时，先入队,）,上图的操作过程是：,for(j=1;jn;j+),/*,利用循环队列输出前,n-1,行的值*,/,for(i=1;i 0,时,n!,2,递归函数：一个直接调用自己或通过一系列调用间接调用自己的函数称为递归函数。,A,（,）,A();,B()C(),C();B();,A,直接调用自己,B,间接调用自己,3,递归算法的编写,1,）将问题用递归的方式描述,2,）根据问题的递归描述编写递归算法,例,n!,的递归定义,基本项：,n!=1,当,n=0,，,1,递归项：,n!=n(n-1)!,当,n 0,递归算法的编写与执行过程,问题的递归描述（定义）,递归定义包括两项,基本项（终止项）：描述递归终止时问题的求解；,递归项：将问题分解为与原问题性质相同，但规模较小的问题；,例,1,求解 阶乘,n!,的递归算法,有,n!,的递归定义，很容易写出对应的递归算法：,int fact(int n),/,算法功能是求解并返回,n,！,if,（,n=1,）,return,（,1,）；,else,return,（,n*fact(n-1),）；,例,2.,编写求解,Hanci,塔问题的递归算法,有三个各为,X,，,Y,，,Z,的塔座，在,X,项有,n,个大小不同，依小到大编号为,1,，,2n,的圆盘。,现要求将,X,上的,n,个圆盘移至,Z,上，并仍以同样顺序叠放，,圆盘移动时必须遵守下列原则：,1,）每次移动一个盘子；,2,）圆盘可以放在,X,，,Y,，,Z,中的任一塔座上；,3,）任何时刻都不能将较大的圆盘压放在较小圆盘之上；,例,n=3,时圆盘移动的过程如下图所示：,a,b,c,3,2,1,1,1,2,1,3,1,2,1,Y,X,Z,求解,Hanci,塔问题,的递归描述,基本项：,n=1,时，将,n,号圆盘从,X,移至,Z,；,递归项：,n1,时，,将,X,上,1n-1,号圆盘移至,Y,；,将,X,上的,n,号圆盘从,X,移至,Z;,将,Y,上,1n-1,号圆盘从,Y,移至,Z;,有了问题的递归定义，其对应的递归算法如下,将规模为,n,的问题的求解归结为规模为,n-1,的问题的求解,void hanoi(int n,char x,char y,char z),/,将塔座,x,上按直径由小到大且自上而下编号为,1,至,n,的,n,个圆盘按规则搬到,/,塔座,z,上，,y,可用作辅助塔座。,/,搬动操作,move(x,n,z),可定义为,(c,是初值为,0,的全局变量，对搬动计数,),：,/printf(“%d Move disk%di from%c to%cn”,+c,n,x,z);if(n=1)move(x,1,z);/,将编号为,1,的圆盘从,x,移动,z else hanoi(n-1,x,z,y);/,将,x,上编号为,1,至,n-1,的圆盘移到,y,z,作辅助塔,move(x,n,z);/,将编号为,n,的圆盘从,x,移到,z hanoi(n-1,y,x,z),；,/,将,y,上编号为,1,至,n-1,的圆盘移到,z,，,x,作辅助塔,算法,3.5,Hanci,塔问题,3,递归函数的实现,在递归函数的执行中，,需多次自己调用自己，递归函数是如何执行的？,先看一般函数的调用机制如何实现的。,A(),B();,C(),B(),C();,调用,调用,返回,返回,函数调用顺序,A B C,函数返回顺序,C B A,后调用的函数先返回,函数调用机制可通过栈来实现,计算机正是利用栈来实现函数的调用与返回的,n=3,阶乘函数,fact(n),的执行过程,Main(),int n=3,y;,L,y=fact(n);,调用,调用,调用,int fact(n),If,（,n=1,）,return,（,1,）；,Else,L1,return,（,n*fact(n-1),）；,n=3,int fact(int n),If,（,n=1,）,return,（,1,）；,Else,L1,return,（,n*fact(n-1),）；,n=2,int fact(int n),If,（,n=1,）,return,（,1,）；,Else,L1,return,（,n*fact(n-1),）；,/fact,n=1,L 3,L1 1,L1 2,返,回,1,返回,2,返,回,6,1,n*fact(n-1),n*fact(n-1),fact(n),返回地址 实参,递归调用中,栈的变化,