基础篇01年09-11月pascal语言12堆栈

1、堆栈(Stack)堆栈是只能在其中一端进行插入操作或删除操作的特殊的线性表.堆栈有两端,固定不动的一端称为栈底,可浮动的一端称为栈顶.其中参与操作的数据元素只能从栈顶压入(进栈)或弹出(出栈).堆栈操作遵循后进先出(Last-in First-out)的原则.堆栈可以用数组来实现。258694258694堆栈的两种不同形式:SPSP图1图2对堆栈的操作：一.建立空栈步骤:1.确定堆栈长度N; 2.定义一维数组STACK(N); 3.令栈顶指针P为零,表示空栈.PROGRAM STACK(INPUT,OUTPUT);VAR STACK:ARRAY1.N OF REAL; P:INTEGER;PR

2、OCEDURE EMPSTABEGIN P:=0; END;二.往栈里压入数据-进栈(Push)步骤:1.先令栈顶指针P加1(上移); 2.给P指向的数组元素赋值.94 P1594 P94 P15三.从堆栈中弹出数据-(出栈POP)步骤:1.把栈指针P指向的数组元素赋给某一变量B; 2.令栈指针P的值减1,表示P仍指向栈顶.94 P1594 P15B94 P15进栈:PROCEDURE PUSH(X:REAL);BEGIN P:=P+1; STACKP:=XEND; 出栈:PROCEDURE POP(VAR B:REAL);BEGIN B:=STACKP; P:=P-1END;练习：判断包含有

3、括号,组成的字符串是否匹配。例如输入.jdslkfksdflkdldkjf(ksdfl)fdlk则显示匹配sdafals;kasdfak()则显示不匹配jdslkfksdflkdldkjf(ksdfl)fdlk P P PB-4B-3B-2B-1B0B1B2B3B4 check练习：一个只能装10斤重的网袋,现有白菜5斤,猪肉2斤,鱼3.5斤,油1.7斤,白糖1斤,土豆5.1斤,设计一个程序使网袋中物品总重量最大.一个只能装M斤重的网袋,现有N种物品，分别重A1斤、 A2斤、 A3斤 AN斤,设计一个程序使网袋中物品总重量最大.堆栈的应用例 一个只能装10斤重的网袋,现有白菜5斤,猪肉2斤,鱼

4、3.5斤,油1.7斤,白糖1斤,土豆5.1斤,设计一个程序使网袋中物品总重量最大.A1A2A3A4A5A6 5 23.51.7 15.1数组ASPTotal :每次计算出来的总重量;He,OUT(6):存放最佳组合;I:记录当前所选数据在数组A中的下标;0I 的值: 1堆栈的应用例 一个只能装10斤重的网袋,现有白菜5斤,猪肉2斤,鱼3.5斤,油1.7斤,白糖1斤,土豆5.1斤,设计一个程序使网袋中物品总重量最大.A1A2A3A4A5A6 5 23.51.7 15.1数组ASPTotal :每次计算出来的总重量;5He ,OUT(6):存放最佳组合;1I:记录当前所选数据在数组A中 的下标;I

5、 的值: 25堆栈的应用例 一个只能装10斤重的网袋,现有白菜5斤,猪肉2斤,鱼3.5斤,油1.7斤,白糖1斤,土豆5.1斤,设计一个程序使网袋中物品总重量最大.A1A2A3A4A5A6 5 23.51.7 15.1数组ASPTotal :每次计算出来的总重量;52He ,OUT(6):存放最佳组合;12I:记录当前所选数据在数组A中 的下标;I 的值: 37堆栈的应用例 一个只能装10斤重的网袋,现有白菜5斤,猪肉2斤,鱼3.5斤,油1.7斤,白糖1斤,土豆5.1斤,设计一个程序使网袋中物品总重量最大.A1A2A3A4A5A6 5 23.51.7 15.1数组ASPTotal :每次计算出来

6、的总重量;52He ,OUT(6):存放最佳组合;12I:记录当前所选数据在数组A中 的下标;I 的值: 69.7451.71堆栈的应用例 一个只能装10斤重的网袋,现有白菜5斤,猪肉2斤,鱼3.5斤,油1.7斤,白糖1斤,土豆5.1斤,设计一个程序使网袋中物品总重量最大.A1A2A3A4A5A6 5 23.51.7 15.1数组ASPTotal :每次计算出来的总重量;52He ,OUT(6):存放最佳组合;12I:记录当前所选数据在数组A中 的下标;I 的值: 68.741.7堆栈的应用例 一个只能装10斤重的网袋,现有白菜5斤,猪肉2斤,鱼3.5斤,油1.7斤,白糖1斤,土豆5.1斤,设

7、计一个程序使网袋中物品总重量最大.A1A2A3A4A5A6 5 23.51.7 15.1数组ASPTotal :每次计算出来的总重量;52He ,OUT(6):存放最佳组合;12I:记录当前所选数据在数组A中 的下标;I 的值: 68.7堆栈的应用例 一个只能装10斤重的网袋,现有白菜5斤,猪肉2斤,鱼3.5斤,油1.7斤,白糖1斤,土豆5.1斤,设计一个程序使网袋中物品总重量最大.A1A2A3A4A5A6 5 23.51.7 15.1数组ASPTotal :每次计算出来的总重量;52He ,OUT(6):存放最佳组合;12I:记录当前所选数据在数组A中 的下标;I 的值: 6851堆栈的应用

8、例 一个只能装10斤重的网袋,现有白菜5斤,猪肉2斤,鱼3.5斤,油1.7斤,白糖1斤,土豆5.1斤,设计一个程序使网袋中物品总重量最大.A1A2A3A4A5A6 5 23.51.7 15.1数组ASPTotal :每次计算出来的总重量;5He ,OUT(6):存放最佳组合;1I:记录当前所选数据在数组A中 的下标;I 的值: 35堆栈的应用例 一个只能装10斤重的网袋,现有白菜5斤,猪肉2斤,鱼3.5斤,油1.7斤,白糖1斤,土豆5.1斤,设计一个程序使网袋中物品总重量最大.A1A2A3A4A5A6 5 23.51.7 15.1数组ASPTotal :每次计算出来的总重量;53.5He ,O

9、UT(6):存放最佳组合;13I:记录当前所选数据在数组A中 的下标;I 的值: 69.551堆栈的应用例 一个只能装10斤重的网袋,现有白菜5斤,猪肉2斤,鱼3.5斤,油1.7斤,白糖1斤,土豆5.1斤,设计一个程序使网袋中物品总重量最大.A1A2A3A4A5A6 5 23.51.7 15.1数组ASPTotal :每次计算出来的总重量;51.7He ,OUT(6):存放最佳组合;14I:记录当前所选数据在数组A中 的下标;I 的值: 67.751堆栈的应用例 一个只能装10斤重的网袋,现有白菜5斤,猪肉2斤,鱼3.5斤,油1.7斤,白糖1斤,土豆5.1斤,设计一个程序使网袋中物品总重量最大

10、.A1A2A3A4A5A6 5 23.51.7 15.1数组ASPTotal :每次计算出来的总重量;23.5He ,OUT(6):存放最佳组合;23I:记录当前所选数据在数组A中 的下标;I 的值: 68.2451.71堆栈的应用例 一个只能装10斤重的网袋,现有白菜5斤,猪肉2斤,鱼3.5斤,油1.7斤,白糖1斤,土豆5.1斤,设计一个程序使网袋中物品总重量最大.A1A2A3A4A5A6 5 23.51.7 15.1数组ASPTotal :每次计算出来的总重量;2He ,OUT(6):存放最佳组合;2I:记录当前所选数据在数组A中 的下标;I 的值: 66.533.551堆栈的应用例 一个

11、只能装10斤重的网袋,现有白菜5斤,猪肉2斤,鱼3.5斤,油1.7斤,白糖1斤,土豆5.1斤,设计一个程序使网袋中物品总重量最大.A1A2A3A4A5A6 5 23.51.7 15.1数组ASPTotal :每次计算出来的总重量;21.7He ,OUT(6):存放最佳组合;24I:记录当前所选数据在数组A中 的下标;I 的值: 79.8155.16堆栈的应用例 一个只能装10斤重的网袋,现有白菜5斤,猪肉2斤,鱼3.5斤,油1.7斤,白糖1斤,土豆5.1斤,设计一个程序使网袋中物品总重量最大.A1A2A3A4A5A6 5 23.51.7 15.1数组ASPTotal :每次计算出来的总重量;2

12、He ,OUT(6):存放最佳组合;2I:记录当前所选数据在数组A中 的下标;I 的值: 32堆栈的应用例 一个只能装10斤重的网袋,现有白菜5斤,猪肉2斤,鱼3.5斤,油1.7斤,白糖1斤,土豆5.1斤,设计一个程序使网袋中物品总重量最大.A1A2A3A4A5A6 5 23.51.7 15.1数组ASPTotal :每次计算出来的总重量;23.5He ,OUT(6):存放最佳组合;23I:记录当前所选数据在数组A中 的下标;I 的值: 68.2451.71堆栈的应用例 一个只能装10斤重的网袋,现有白菜5斤,猪肉2斤,鱼3.5斤,油1.7斤,白糖1斤,土豆5.1斤,设计一个程序使网袋中物品总

13、重量最大.A1A2A3A4A5A6 5 23.51.7 15.1数组ASPTotal :每次计算出来的总重量;5.1He ,OUT(6):存放最佳组合;6I:记录当前所选数据在数组A中 的下标;I 的值: 75.1AI 值 ; He ,total ,sp 0 ; I 1(Sp=0) and (aI-1=a6)输出outi 各值以及he 只要I =6Total+aiheynHe Total;把这组解放在数组out中Pop(i) ; total total-ai; I I+1;计算有优先级的算术表达式。-利用堆栈3+4*22-3*6=所用到的数据结构：数组s1:存放输入的表达式中所有的数字；数组s2:存放输入的表达式中所有的运算符；堆栈st1,st2分别存放在运算过程中扫描过的数和运算符。算法示例： 输入：“3+4*22-6/3=”3+43+4*22-6/3=3+4