3.3栈课件(33PPT)2021—2022学年浙教版(2019)选修1

资源下载
  1. 二一教育资源

3.3栈课件(33PPT)2021—2022学年浙教版(2019)选修1

资源简介

(共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

展开更多......

收起↑

资源预览