栈的概念及顺序栈的基本操作.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依次入栈，入栈过程 中允许栈顶元素出栈。出栈的序列可能有几种 ？ CB A BAC ABC CBA BCA ACB 二、基本操作 InitStack( /栈底指针 SElemType *top; /栈顶指针 int stacksize; /已分配存储空间数 SqStack; 判空条件：S.base=S.top 基本操作的算法描述 1. 初始化栈S void InItStack(SqStack if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; 2. 入栈 int Push(SqStack /申请扩大容量 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 e=*(S.top-1); S.top-; return OK; 4. 获取栈顶元素内容 int GetTop (SqStack S, SElemType 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 Pop(S,e);