第4章-栈和队列

1、1、数据结构和应用算法教程(修订)、课件、第2、4章堆栈和队列、堆栈和队列是通过限制线性表中的某些操作而派生的结构。他们的操作本身不难，但难点在于理解栈和队列的应用思想，掌握该算法的设计技术。讲授本章课程大约需要6节课。3，通常，堆栈和队列是线性表，仅限制在表的“结束”插入和删除。线性表堆栈队列insert (l，I，x) insert (s，n1，x) insert (q，n1，x) 1in1 delete (l，I) delete，8，init stack(# define stack increment 10；Typedef struct SElemType * elemInt top-

2、堆栈顶部下标，顺序表length int stacksizeInt incrementSqStack补充：长度=顶部1；19，void InitStack_Sq(将初始值附加到SqStack /堆栈中的其他成员，20，将数据点插入SqStack /堆栈顶部，s.ell S. tops . elems . top=e；摘要：首先变更top(top 1)，然后指定值。21，boolpop _ sq (sqstack，e=s . elems . top-；您可以将此语句更改为：e=s . elems . top；s . top-；摘要：首先分配值，然后转换塔(top-1)、22、24、示例1计数，示

3、例例如：(1348)10=(2504)8计算如下：N N div 8N mod 8 1348 168 4 168 21 0 21 2 2 0 2，评估顺序，输出顺序，27，void conversion CinWhile (N) Push(S，N % 8)；N=N/8；While(！stack empty(S)Pop(S，e)；cout e；/conversion，28，示例2，括号匹配检查假定表达式()或()是正确的格式，而()或()或()是错误的格式。检查括号是否匹配的方法可以用“期待的紧急度”的概念来说明。29，分析可能发生的不一致情况：到达的右括号不是“期待”。例如，考虑以下括号顺序：

4、()1 2 3 4 5 6 7 8，“不速之客”来了。直到结束，“期待”括号才出现。30，算法的设计思想：1)出现左括号时进入堆栈。2)每次出现右括号时，首先检查堆栈是否为空。如果堆栈为空，则表示“右括号”重复。否则，将与堆栈顶部元素进行比较，如果匹配，则“左括号将被堆栈”否则，将出现不一致。3)表示式检查结束时堆叠为空，表示式中的相符正确；否则，会留下左括号。31，bool matching(charexp)intstate=1；Ch=* expWhile (ch！=#、32、范例3。背包问题：假设有可以分别装入w1、w2和wn的体积和T的体积的背包，否则。W(1，8，4，3，5，2)，T=

5、10范例(1，4，3，2)，(1，4，5)，(8，33，W，T=10，)规则是“后进先出”。这意味着背包通过堆栈操作解决。，34，void knapsack (int w，int t，int n)/t算法中剩馀的卷，初始值为背包的卷InitStack(S)。k=0；Do while (T0，35，限制为二进制运算符的表达式定义：表达式：3:=操作数操作数3:=简单变量|表达式简单变量：=标识符|无符号整数，示例4，表达式求值示例： Exp=a b (c d/e) f前缀： a b c/d e f中间后缀3360 a b c d/e f后缀： a b c d/e f后缀3360 a b c d

6、e/f，结论：1)操作数之间的相对顺序保持不变。 2)运算符的相对顺序不同。3)中值表达式没有括号信息，运算顺序不确定。4)前缀式运算规则，其中：连续发生的两个操作数及其前面的运算符构成了最小表达式。5)后缀表达式的运算规则是：运算符在表达式中出现的顺序是表达式的运算顺序。出现在每个运算符和运算符前面的两个操作数构成了最小表达式。38，后缀中如何评价？示例：a b c d e/f，a b，d/e，c-d/e，(c-d/e)、40、Computy(suffix)Stack s；I=0；Initstack(，suffix=a b c d e/f #，41，if suffix I是操作数吗？if(0

7、=suffix I=9 )；扩展思维：如果是多个数字，如何判断？42，N=operate(x，y，suffixi)；/表示运算符=operate(x布列克；盘柜-:n=y-x；return N；布列克；case * :n=y * x；return N；布列克；Case:N=yxreturn N；布列克；default : return ERROR:/switch，43，如何从原始表达式中获取后缀？每个运算符的运算顺序由其后的运算符确定，在后缀中，优先级较高的运算符优先于优先级较低的运算符。分析“原始表达式”和“后缀”运算符：原始表达式： a b c d/e f后缀： a b c d e/f，4

8、4，运算符优先级表，45，从原始表达式中获取后缀模式的规则设置，1)操作，2，3)如果当前字符是操作数，则直接发送到后缀。4)如果当前运算符的优先级大于堆栈顶部运算符，则进入堆栈。5)否则(小于或等于)，堆栈顶部终止操作符将作为后缀发送。6)“(”与前面和后面的运算符隔离，“)”被视为从相应左括号开始的表达式的结束符。46，在原始表达式中获取后缀的规则如下：设定原始表示式阵列。exp=原始表达式设置运算符堆栈。s阵列字尾表示式suffix，2)设定表示式的结尾为#，设定运算子堆叠的堆叠底部为#。/push(，逐个读取和处理原始表达式中的字符。分别考虑操作数、运算符(考虑优先级)、左括号(，右括

9、号)的处理方法。运算符：对于，48，获取原始表达式中后缀的规则如下：运算符：4)如果当前运算符的优先级高于堆栈顶部运算符，则进入堆栈。5)否则，堆栈顶部终止操作符将作为后缀发送。在某些情况下：方案1:符号是-*/:比较优先级，是进入堆栈还是进入堆栈，后缀表达式方案2: (-堆栈情况3:)-不进入堆栈，而是在堆栈顶部(前面的运算符已堆栈并作为后缀发送，49，求原始表达式中后缀的法则是，1)设置运算符堆栈。2)设置表达式的结束符为“#”，设置运算符堆栈的堆栈底部为“#”。3)如果当前字符是操作数，则直接发送到后缀。4)如果当前操作符的优先级高于堆栈顶部操作符，则进入堆栈。5)否则，堆栈顶部终止操作

10、符将作为后缀发送。6)“(”与前面和后面的运算符隔离，“)”被视为从相应左括号开始的表达式的结束符。50，void transform (charsuffix，charexp)init stack(s)；推(s，#)；P=expch=* p；k=0；While(！stack empty(S)if(！op menber(ch)suf fixk=ch；Else if (ch！=#)p；ch=* p；/while suf fixk=0；对于/transform、/运算符，后面的swich部分，51，switch (ch) case (: push (s，ch)；布列克；/左括号堆叠case) : P

11、op(S，c)；由上至下(后缀数组while (c！=()suf fixk=c；流行(s，c)break；defult 3360/其他比较优先级while(Gettop(S，c) /switch，C是堆栈顶部运算符，ch是当前运算符precede(c，ch)return 1是chelse return 1；说明：如果是操作数，则返回0，int precede(c，ch) c作为堆栈顶部的运算符。Ch表示当前运算符chc的0 switch(ch)case : case : if(堆栈顶部的c为#或()，return 0；/chc else返回1。/其他chc /switch，如果表达式为234

12、56/2*11-8，如何处理多个数字？55，示例5，实现递归并将所有实际参数、返回地址等信息传递给调用函数进行存储。-将存储分配控件发送到在保护站点调用函数的本地变量中调用的函数的入口。在运行一个函数的同时调用另一个函数时，必须先完成三个任务，然后才能执行调用的函数。56，存储调整后函数的计算结果。释放曹征函数的数据区域。(本地变量)根据调用函数中存储的返回地址，将控件发送到调用函数。调用函数返回调用函数之前，必须完成以下三项任务：57，多个函数嵌套调用的规则如下：此时，内存管理实现“堆栈管理”，然后首先返回调用！例如void main()void a()void b()a()；b()；/main /a /b，main的数据区域、函数a的数据区域、函数b的数据区域、迭代定义：函数本身直接或间接调用自身。在计算机上，某个函数调用另一个函数与调用自己没有区别。难以理解的只是人类的思维。(阿尔伯特爱因斯坦，计算机名言)，59，迭代函数执行的过程可以嵌套在同一函数中调用，在迭代函数执行过程中需要“迭代任务堆栈”。角色：(1)将递归调用的实际参数、返回地址传递给在下一级别运行的递归函数。(2)保存此层的参数和局部变量，以便在从下一层返回时重复使用。60，Ackerman函数定义：使用实例模拟编译器解决迭代问题的过程(无需掌