栈的概念及顺序栈的基本操作.ppt

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Chapter 3,栈和队列,主要内容,3.1,栈,3.2,栈的应用,3.3,栈和递归的实现,3.4,队列,3.1,栈,一、栈,(stack),的概念,栈,(stack),：是插入和删除操作都限制在表尾的,线性表,。,入,(,压,),栈,出栈,(,弹出,),栈的逻辑表示：,S=(a1,a2,a3,an),栈底,栈顶,a1,：栈底元素,an,：栈顶元素,空栈：不含任何元素的空表,先进后出,(First In Last Out),：,FILO,后进先出,(Last In First Out),：,LIFO,栈的特性,例如：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。,练习：三个元素,A,、,B,、,C,依次入栈，入栈过程中允许栈顶元素出栈。出栈的序列可能有几种？,C,B,A,例如：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。,练习：三个元素,A,、,B,、,C,依次入栈，入栈过程中允许栈顶元素出栈。出栈的序列可能有几种？,C,B,A,例如：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。,练习：三个元素,A,、,B,、,C,依次入栈，入栈过程中允许栈顶元素出栈。出栈的序列可能有几种？,C,B,A,BAC,ABC,CBA,BCA,ACB,二、基本操作,InitStack(&S,),初始化，构造一个空栈,S,DestroyStack(&S,),销毁栈,S,ClearStack(&S,),清空栈,S,StackEmpty(S,),判断栈,S,是否为空,StackLength(S,),栈,S,的长度,(,栈中元素个数,),GetTop(&S,&e,),取栈顶元素,Push(&S,e,),入,(,压,),栈,(,即插入元素,),Pop(&S,&e,),出栈,(,弹出,)(,即删除元素,),三、顺序栈,(,栈的顺序存储结构,),的表示和实现,顺序栈的类型定义,#define STACK_INIT_SIZE 100/,栈的最大元素数目,#define STACKINCREMENT 10/,存储空间分配增量,typedef,struct,stack,SElemType,*base;/,栈底指针,SElemType,*top;/,栈顶指针,int,stacksize,;/,已分配存储空间数,SqStack,;,判空条件：,S.base,=,S.top,基本操作的算法描述,1.,初始化栈,S,void,InItStack(SqStack,&S),S.base,=(,SElemType,*),malloc,(STACK_INIT_SIZE*,sizeof(SElemType,);,if(!S.base,),exit(OVERFLOW,);,S.top,=,S.base,;,S.stacksize,=STACK_INIT_SIZE;,2.,入栈,int,Push(SqStack,&S,SElemType,e),if(,S.top-S.base,=,S.stacksize,)/,栈满,S.base,=(,SElemType,*),realloc(S.base,.,stacksize+STACKINCREMENT,)*,sizeof(SElemType,);/,申请扩大容量,if(!S.base,)return ERROR;,S.top,=,S.base+S.stacksize,;,S.stacksize,+=STACKINCREMENT;,S.top,=e;,S.top,+;return OK;,3.,出栈,int,Pop(SqStack,&S,SElemType,&e),if(,StackEmpty,(S)return ERROR;,e=*(S.top-1);,S.top,-;return OK;,4.,获取栈顶元素内容,int,GetTop,(,SqStack,S,SElemType,&e),if(,StackEmpty(S,)return ERROR;,else e=*(S.top-1);return OK;,3.1.3,栈的链式存储,若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。如右图所示。,由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。,top,base,3.2,栈的应用,【,例,1,】,十进制转换成二进制,使用展转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以,2,，并保留其余数；重复此操作，直到该十进制数值为,0,为止。最后将所有的余数反向输出就是所对应的二进制数值。比如：,(692),10,=(1010110100),2,，其展转相除的过程如右图所示：,692,346,173,86,43,21,10,5,2,1,0,2,2,2,2,2,2,2,2,2,2,1,0,1,0,1,1,0,1,0,0,十进制转换成二进制算法,void,conversion,(),/,对于输入的任意一个非负十进制整数,/,打印输出与其等值的二进制数,InitStack(S,);/,构造空栈,scanf(“%d”,N,);,while(N),Push(S,N%2);N=N/2;,while(!,StackEmpty(s,),Pop(S,e,);,printf(“%d”,e,);,【,例,2,】,四个方向的迷宫问题,迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次试验终于得到它学习走通迷宫的路线。,图中每个方块或为通道,(,以空白方块表示,),或为墙,(,以带阴影线的方块表示,),。,所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。,假设”,当前位置,”,指的是”在搜索过程中某一时刻所在图中某个方块位置,”,则求迷宫中一条路径的算法的基本思想是,:,若当前位置”可通”,则纳入”当前路径”,并继续朝”下一位置”探索,即切换”下一位置”为”当前位置”,如此重复直至到达出口,;,若当前位置”不可通”,则应顺着”来向”退回到”前一通道块”,然后朝着除”来向”之外的其他方向继续探索,;,若该通道块的四周四个方块均”不可通”,则应从”当前路径”上删除该通道块。所谓”下一位置”指的是”当前位置”四周四个方向,(,东、南、西、北,),上相邻的方块。,假设以栈,S,记录”当前路径”,则栈顶中存放的是”当前路径上最后一个通道块”。由此,”,纳入路径”的操作即为”当前位置入栈”,;”,从当前路径上删除前一通道块”的操作即为”出栈”。,/-,求迷宫路径的算法简述,-,设定当前位置的初值为入口位置,;,do,若当前位置可通,则,将当前位置插入栈顶,;/,纳入路径,若该位置是出口,则结束,;/,路径在栈中,否则切换当前位东邻方块为新的当前位,;,否则,若栈不空且栈顶位置尚有其他方向未探索,则,设定新的当前位置为沿顺时针方向旋转找,到的栈顶位置的下一相邻块,;,若栈不空但栈顶位置的四周均不可通,则,删去栈顶位置,;/,路径中删去该通道块,若栈不空,则重新测试新的栈顶位置,直至,找到一个可通的相邻块或出栈至栈空,;,while,(,栈不空,);,当前位置可通,指未曾走到过的通道块,即该方块位置不仅是通道块,而且既不在当前路径上,(,否则所求路径就不是简单路径,),也不是曾经纳入过路径的通道块,(,否则只能在死胡同内转圈,),。,typedef,struct,int,ord,;/,通道块在路径上的”序号”,PosType,seat;/,通道块在迷宫中的”坐标位置”,int,di,;/,从此通道块走向下一通道块的”方向”,SElemType,;/,栈的元素,类型,Status,MazePath,(,MazeType,maze,PosType,start,PosType,end),/,若迷宫,maze,中存在从入口,start,到出口,end,的通道,则求得一,/,条放在栈中,(,从栈底到栈顶,),并返回,TRUE;,否则返回,FALSE,InitStack(S,);,curpos,=start;/,设定”当前位置”为”入口位置”,curstep,=1;/,探索第一步,do,if(,Pass(curpos,)/,当前位置可以通过,/,即是未曾走到过的通道块,FootPrint(curpos,);/,留下足迹,e=(curstep,curpos,1);,Push(S,e,);/,加入路径,If(,curpos,=end)return TRUE;/,到达出口,curpos,=NextPos(curpos,1);/,下一位置是当前位置的东邻,curstep,+;/,探索下一步,/if,else /,当前位置不能通过,if(!,StackEmpty(S,),Pop(S,e,);,while(,e.di,=4&!,StackEmpty(S,),MarkPrint(e.seat,);,Pop(S,e,);,/,留下不能通过的标记,并退回一步,/while,if(,e.di,4),e.di,+;,Push(S,e,);/,换下一个方向探索,curpos,=,NextPos(e.seate.di,);/,设定当,/if /,前位置是该新方向上的相邻块,/if,/else,while(!StackEmpty(S,);,return FALSE;,/,MazePath,