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

Chapter3栈和队列3.1栈例如：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。例如：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。例如：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。二、基本操作三、顺序栈(栈的顺序存储结构)的表示和实现判空条件：S.base=S.top2.入栈
intPush(SqStack&S,SElemTypee){
if(S.top-S.base>=S.stacksize){//栈满
S.base=(SElemType*)realloc(S.base,.stacksize+STACKINCREMENT)*sizeof(SElemType));//申请扩大容量
if(!S.base)returnERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
S.top=e;S.top++;returnOK;
}3.出栈
intPop(SqStack&S,SElemType&e){
if(StackEmpty(S))returnERROR;
e=*(S.top-1);
S.top--;returnOK;
}3.1.3栈的链式存储
若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。如右图所示。
由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。3.2栈的应用十进制转换成二进制算法
voidconversion(){
//对于输入的任意一个非负十进制整数,
//打印输出与其等值的二进制数
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(栈不空);当前位置可通,指未曾走到过的通道块,即该方块位置不仅是通道块,而且既不在当前路径上(否则所求路径就不是简单路径),也不是曾经纳入过路径的通道块(否则只能在死胡同内转圈)。
typedefstruct{
intord;//通道块在路径上的”序号”
PosTypeseat;//通道块在迷宫中的”坐标位置”
int