第三章 栈和队列.ppt

1、第三章堆栈和队列，中国海洋大学信息学院魏振刚电话子邮件3360，一般认为堆栈和队列是线性表，只在表的“端点”限制插入和删除。线性表堆栈队列插入(l，I，x)插入(s，n 1，x)插入(q，n 1，x)1删除(l，I)删除(s，n)删除(q，1) 1in。堆栈和队列是两种常用的数据类型，3.1堆栈和3.2堆栈3.3堆栈和递归的实现，3.4队列，3.5离散事件模拟，以及本章的主要内容：3.1堆栈，它是一个线性表，只在表的末尾限制插入或删除。通常，页脚被称为顶部，页眉被称为底部。假设堆栈S=ai | ai元素集，i=1，2，n，n0，那么a1是底部元素，an是顶部元素，

2、堆栈中的元素按照a1，a2，an的顺序堆叠，并且离开堆栈的第一个元素应该是顶部元素。换句话说，根据后进先出的原则修改堆栈。因此，堆栈也被称为后进先出线性表(简称后进先出表)。3.1.1抽象数据类型栈的定义，ADT栈数据对象：D ai | ai ElemSet，i=1，2，n，n0数据关系：R1 | ai-1，aiD，i=2，n指定一个端点是顶部，一个端点是底部。基本操作：ADT Stack，堆栈的抽象数据类型定义：数据对象：D=ai| aiElemSet，i=1，2，n，n0数据关系：R1=|ai-1，aiD，i=1，2，n指定一个结束是堆栈的顶部，一个结束是堆栈的底部。基本操作：init/堆

3、栈顶部指针int stacksizeSqStack，其中stacksize表示当前可以使用的最大容量。Top是堆栈的顶部指针，其初始值指向堆栈的底部。插入新元素时，指针顶端增加1，删除顶端元素时，指针顶端减少1。在非空堆栈中，top总是指向堆栈顶部元素的下一个位置。序列堆栈的定义：以下是序列堆栈的模块描述。/-ADT STACK的表示和实现-/-堆栈的顺序存储表示-# define STACK _ INIT _ SIZE 100；/存储空间的初始分配#定义STACKINCREMENT 10/存储空间分配增量typedef结构选择类型*基；/在堆栈构造之前和堆栈销毁之后，基值为空选择类型*顶部；

4、/堆栈顶部指针int stacksize/当前分配的存储空间，以元素为单位的sqstack，基本操作的函数原型的描述，状态初始化堆栈(SqStack /构造一个空堆栈，状态销毁堆栈(SqStack /销毁堆栈，S不再存在)，状态清除堆栈(SqStack/重置为空堆栈，状态堆栈(SqStack S)；/如果堆栈为空，则返回真，否则返回假。/返回s的元素数，即堆栈的长度。statusgettop (sqstacks，selem type/)从底部到顶部对堆栈中的每个元素调用函数visit()。一旦访问()失败，操作将失败。/-基本操作(部分)的算法描述-状态initstack (sqstack/i

5、nitstack)，状态gettop (sqstacks，selemtype/gettop)，状态push (sqstack/push)，状态pop (sqstack/pop，3.2堆栈应用示例，3.2.1数字系统转换，3.2.2括号匹配测试，3.2.3行编辑器问题，3.2.4迷宫求解，3.2.5表达式求值，3.2.1转换十进制数字N和其他D数字的算法基于以下原则：N=(，例如：(1348)10=(2504)8，其运算过程如下：n n div 8n mod 8 1348 168 4 168 21 0 21 25 202，计算顺序，输出顺序，因为上述计算过程按从低到高的顺序生成八进制数的每一位数

6、字，而打印输出一般应按照从高到低的顺序进行，只需计算即可。因此，如果在计算过程中获得的八进制数的每一位都按顺序堆叠，则对应于输入的八进制数将根据堆叠顺序打印并输出。请参见算法3.1，无效转换()/对于任何输入的非负十进制整数，/打印出其等效的八进制数InitStack(S)；/构造空堆栈扫描(%d，N)；同时(N)推(S，N % 8)；N=N/8；while(！流行音乐；printf (%d，e)；/转换，算法3.1，检查括号是否匹配的方法可以用“预期紧急度”的概念来描述。3.2.2括号匹配测试，假设在表达式中，()或()等。格式正确，()或()或()格式不正确。分析可能的不匹配情况：右边括号

7、不是“预期的”；例如，考虑以下括号序列：(1)2 3 4 5 6 7 8，到达是一个“不速之客”；直到最后，也没有来到“期待”括号。该算法的设计思想如下：1)只要有一个左括号，它就会被放在堆栈上；2)当出现右括号时，首先检查堆栈是否为空。如果堆栈为空，则表示“右括号”是多余的；否则，它将与堆栈的顶部元素进行比较。如果匹配，则“左括号从堆栈中出来”；否则，表示不匹配。3)在表达式检查结束时，如果堆栈为空，则表示表达式中的匹配是正确的，否则表示有多个“左括号”。状态匹配(字符串.3.2.3行编辑器问题，问题：简单行编辑器的功能是接受用户从终端输入的程序或数据，并将其存储在用户的数据区。如何实现它？

8、“接受的每个字符都存储在内存中”？这样做是不合适的！应该是，在用户输入一行的过程中，允许用户输入错误，并且发现错误可以及时纠正。设置一个输入缓冲区以接受用户输入的一行字符，然后将它们逐行存储在用户数据区中，假设“#”是退格字符，“”是倒退字符。假设从终端接受两行字符是合理的：WHLL # # ILR # E(S # * S)OuthaUTCHAR(* S=#)；实际有效行如下：while(* s)put char(* s)；而(ch！=EOF /从终端接收下一个字符，而(ch！=EOF) /EOF是全文终止符，Void LineEdit () /使用字符堆栈从终端接受/一行，并将其传输到调用过

9、程的数据区。初始堆栈；/构造空堆栈S ch=getchar()；/从终端接收第一个字符，ClearStack/如果(ch！=EOF)ch=getchar()；销毁堆栈；/LineEdit，将字符从栈底转移到栈顶，转移到调用进程的数据区；算法3.2、3.2.4迷宫求解通常采用“穷举法”。迷宫路径算法的基本思想是：如果当前位置是“可访问的”，则路径被包括并继续向前移动；如果目前的位置“遥不可及”，回去改变方向继续探索；如果周围没有入口，从路径中删除当前位置。将当前位置的初始值设置为入口位置；如果当前位置是可访问的，请将当前位置插入堆栈顶部；/合并路线。如果该位置是退出位置，则结束。/找到路径并存储

10、在堆栈中，否则将当前位置的东块切换到新的当前位置；否则，在迷宫中寻找从入口到出口的路径的算法是：如果堆栈不是空的，并且堆栈顶部还有其他方向没有被探索，则通过顺时针旋转：度，将新的当前位置设置为找到的堆栈顶部的下一个相邻块；如果堆栈不是空的，但是顶部位置的外围不可访问，则删除顶部位置；/从路径中删除通道块。如果堆栈不是空的，重新测试堆栈的新顶部位置，直到找到可通过的相邻块，或者堆栈被弹出到空堆栈；而(堆栈不是空的)，如果堆栈是空的，则表示迷宫中没有路径。、typedef结构内部顺序；/路线上通道座的后置型；/“坐标位置”在迷宫中通道块的中间；/“方向”选择从这个通道块到下一个通道块的类型；/堆栈

11、的元素类型是状态迷宫路径(迷宫类型为迷宫，pos类型为开始，pos类型为结束)/如果在迷宫中有一个从入口开始到出口结束的通道，则/得到一个并将其存储在堆栈中(从堆栈的底部到顶部)，然后返回/true；否则，它返回假的初始堆栈；curpos=开始；/将“当前位置”设置为“入口位置”curs step=1；/探索第一步，做if (Pass (curpos) /当前位置可以通过，也就是说，通道块足迹(curpos)从来没有达到；/留下足迹e=(curstep，curpos，1)；推(S，e)；/如果(curpos=end)返回(TRUE)，则添加路径；/到达出口(终点)curpos=NextPos

12、(curpos，1)；/下一个位置在当前位置的东面；/探索下一步/如果否则/当前位置不能通过，如果(！流行音乐；而(e.di=4 /MazePath，算法3.3，表达式定义限于二进制运算符：表达式：3360=(操作数)(运算符)(操作数)操作数：3360=简单变量|表达式简单变量33603360=标识符|无符号整数，3.2.5表达式求值，表达式的三种识别方法：让Exp=S1 OP S2，然后OP S1 S2是前缀符号，S1 OP S2是中缀符号，S1 S2 OP是后缀符号， 例如： Exp=a b (c d/e) f前缀公式： a b c/d e f中缀公式： a b c d/e f后缀公式：

13、 a b c d e/f，结论：1)操作数之间的相对顺序不变； 2)中缀丢失括号信息，使得操作顺序不确定；3)前缀型运算规则是：中连续出现的两个操作数及其前后的操作数构成一个最小表达式；4)后缀公式的运算规则是：运算符在公式中出现的顺序就是表达式的运算顺序；每个运算符及其前后的两个操作数构成一个最小表达式。如何从后缀开始计算？首先查找运算符，然后是操作数，例如：a b c d e/f、a b、d/e、c-d/e、(c-d/e) f、如何从原始表达式中获取后缀？每个操作员的操作顺序应由其后的操作员决定。在后缀公式中，优先级高的运算符位于优先级低的运算符之前。本文对“原始表达式”和“后缀公式”中的

14、运算符：进行了分析，得到了后缀公式： a b c d/e f。后缀公式的规律如下：1)建立算子栈；2)让表达式的终止符为“#”，操作符堆栈的堆栈底部为“#”；3)如果当前字符是操作数，则直接发送到后缀类型。4)如果当前操作员的优先级数高于顶层操作员，则推栈；5)否则，退出栈顶操作符并将其发送到后缀类型；6)(在它之前和之后隔离操作符，并且)可以被认为是从相应的开始括号开始的表达式的终止符。void转换(charsuffix，char exp)/已知表达式exp，找到它的后缀表达式后缀InitStack(S)；推(S，#)；p=exp。ch=* p；while(！StackEmpty(S)如果(！通过(后缀，通道)；否则如果(ch！=#)p；ch=* p；否则流行音乐；通过(后缀，ch)；/当/CrtExptree，/参见下一页，开关(ch)外壳(: Push(S，ch)；打破；案例): Pop(S，c)；而(c！=()通过(后缀，c)；破裂；在(gettop (s，c)/开关时，用运算符优先算法计算表达式值的过程如下：1)建立运算符堆栈OPTR、操作数或运