资源简介

(共33张PPT)
3.3栈
情景导入
PART
1
栈的概念与特性
一 栈的概念与特性
栈是一种操作受限的线性表，仅允许在表的一端的进行插入和删除
蓝莓味
葡萄味
草莓味
栈顶
栈底
蓝莓味
葡萄味
草莓味
哈密瓜味
推入
弹出
进行插入或删除操作的一端称为栈顶，位于栈顶位置的元素称为栈顶元素;
相应地，将表的另一端称为栈底，位于栈底位置的元素为栈底元素。
一 栈的概念与特性
(1)先进后出、后进先出
（last in first out ,故栈也称为后进先出表(LIFO表)）
由栈的定义可知，栈具备“先进后出、后进先出”的特点。
(2)有限序列性
栈中的元素是有限的。栈可以是空的，也可以包含多个元素。栈中元素呈现线性关系，栈顶元素有一个前驱点，栈底元素有一个后继点，其他元素既有一个前驱点，又有一个后继点。
练习
1.元素A,B,C,D依次进栈后，栈顶元素是（ ）栈底元素是（ ）
D
A
2.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印缓冲区，主机将要打印的数据依次写进该缓冲区，而打印机一次从该缓冲区取出数据，该缓冲区的逻辑结构应该是（ ）
A.栈 B.队列 C.树 D.图
B
练习
3.有六个元素以6,5,4,3,2,1的顺序进栈，（ ）不是合法的出栈顺序
A.5,4,3,6,1,2
B.4,5,3,1,2,6
C.3,4,6,5,2,1
D.2,3,4,1,5,6
C
练习
4.若元素a、b、c、d、e、f依次进栈，允许进栈退栈操作交替进行，但不允许连续3次进行退栈操作，则不可能得到的出栈序列是（ ）
A.d,c,e,b,f,a
B.c,b,d,a,e,f
C.b,c,a,e,f,d
D.a,f,e,d,c,b
D
PART
2
栈的基本操作
一 栈的基本操作
1.栈的创建
栈的创建方式有很多种（链栈、顺序栈），一般按照顺序存储，可以用数组来实现。由于栈顶元素在数组中的位置会发生改变，因此用top变量来记录栈顶元素在数组中的位置。当top为-1时，表示栈为空。
st=[“”]*4
top=-1
st
top=-1
一 栈的基本操作
2.入栈
入栈又叫压栈操作，把数据元素压入栈顶。
字母“A”、“B”、“C”、“D”依次入栈。
st
top=-1
top=top+1
st[top]=“A”
top
A
B
C
D
一 栈的基本操作
3.出栈操作
出栈时把栈顶元素取出，同时top减一，当top为-1时，表示栈为空。
st
top=-1
print（st[top]）
top=top-1
top
A
B
C
D
练习
【例1】下列代码段能够实现分离正整数,并输出其各位数字(用空格隔开)的功能。请在划线处填入合适的代码。
st=[0]* 10#创建一个空栈
top=-1
num=int(input(“请输入一个正整数:"))
while num>0:
①
st[top]= ②
num=num//10
print("输出结果为:",end="")
while top>-1:
print( ③，end=" ")
top-=1
top+=1
num%10
st[top]
例题1
1.十进制转二进制
st=[-1]*100 #列表中元素初始值-1
top=-1
number=int(input("请输入十进制整数: "))
while number>0:
x=number % 2
______________
______________ #入栈
number=number // 2
while top>-0:
print(st[top],end=‘’) #出栈
______________
top=top+1
st[top]=x
top=top-1
例题2
2.括号匹配
在一个数学计算式“(a÷(b-c)+d)×e”中，位置1和位置4有左括号“("， 位置9和位置12有右括号“)”。 位置1的左括号与位置12的右括号相匹配，位置4的左括号与位置9的右括号相匹配。而对于数学计算式“a÷(b-c))"，位置8的右括号没有可匹配的左括号。设计一个程序，判断输入的数学计算式中的括号(只有小括号)是否匹配。
( ( ) )
( ) )
(()
) ) ( (
数量、位置
例题2
2.括号匹配
st-=[""]* 100
top=-1
flag=True #标记是否有不匹配的情况
s=input("请输入数学计算式: ")
for i in range(len()):
if s[i]=="(":
____________
____________
elif s[i]== ")":
if top==-1:
____________
break
else:
____________
iftop>=0: #栈中还有左括号
flag=False
if flag:
print("括号匹配”)
else:
print("括号不匹配")
top=top+1
st[top]=s[i]
flag=False
top=top-1
PART
3
列表自带函数实现栈
列表自带方法
1.栈的创建
stacklist=[]
2.字母A、B入栈
stacklist.append(“A”)
stacklist.append(“B”)
3.输出栈顶元素
print(stacklist[1])
4.输出栈中元素个数
print(len(stacklist))
5.弹出栈顶元素
stacklist.pop()
……
stacklist
A
B
练习
【举一反三1】有如下Python程序段:
num=int(input(“请输入一个整数[-128,127]:”))
st=[]
if num>=0:
for i in range(7):
st.append(str(num%2))
num//=2
st.append("0")
else:
num=-num
for i in range(7):
st.append(str(1-num%2))
num//=2
st.append("1")
print(".join(st[::-1]))
则当输入26时,程序输出结果为（ ）
A.10011010 B.11100101 C.0001 1010 D.11010
C
练习
【举一反三2】有如下Python程序段:
s="0123456789ABCDEF“
a=“1A2B”
ans=[]
for ch in a:
num=s.index(ch)
st=[]
for i in range(4):
st.append(str(num%2))
num//=2
ans.append(".join(st[:：-1]))
print(".join(ans))
则程序执行后,输出的结果为( )
A .0001101000101011 B.1101000101011
C.100001010100110 D.11010101011
A
练习
【举一反三1】有如下Python程序段:
if__name__==__main__
st=LinkStack()
num=72
while num>0:
st.push(num%2)
num//=2
while not st.is_empty():
print(st.pop(),end="")
则程序输出结果为_________________。
1001000
PART
4
逆波兰表达式问题
一 生成逆波兰表达式
在数学表达式中，运算符总是在与之相关的两个运算符之间，在计算结果时，要考虑括号、运算符号优先性。为了程序实现方便，波兰逻辑学家J.Lukasiewicz提出了另一种方法，将运算符置于其运算对象之后，没有括号，不用考虑运算符号优先性，这种方式称为逆波兰表达式。
a + b
a b +
6+(7-1)
6 7 1 - +
A * B * C
A B * C *
一 练习：中缀转后缀
C-A*B
A*(B+C)-D
-A+B-C+D
6+(8-2)*2/3
5*(17-3)+9
(2+3)*5-6*4
CAB*-
ABC+*D-
A-B+C-D+
6 8 2–2*3/+
5 17 3-*9+
2 3+5*6 4*-
一 中缀转后缀
中缀表达式：9+（3-1）*3+10/2
后缀表达式：
栈
9
+
(
-
3
1
-
*
3
*
+
10
+
/
2
/
+
一 中缀转后缀
def translate(inorde_ exp):
operators="()+- */“
priority={"(":1,"+":2,"- ":2,"*":3,"/":3}
st=[]
#当作栈使用,用来存储运算符
postorde_exp=[]
“用来存储逆波兰表达式”
exp_list=inorde_exp.split()
for x in exp_list:
if x not in operators:
①
elif len(st)==0 or x=="(":
②
elif x==")":
while st and st[-1]!="(":
postorde_exp.append(st.pop())
st.pop()
else:
while st and priority[st[-1]>=priority[x]:
postorde_ exp.append(st.pop())
st.append(x)
while st:
postorde_ exp.append( ③)
return "".join(postorde_exp)
postorde_exp.append(x)
st.append(x)
st.pop(x)
二 逆波兰表达式程序实现
中缀表达式：9+（3-1）*3+10/2
后缀表达式：9 3 1 - 3 * + 10 2 / +
二 逆波兰表达式程序实现
中缀表达式：9+（3-1）*3+10/2
后缀表达式：9 3 1 - 3 * + 10 2 / +
9
3
1
1
b=
a=
3
PART
5
火车进出站问题
一 火车进出站
14
BD
一 火车进出站
14
卡特兰数：
一 火车进出站
BD
THANKS

展开更多......

收起↑