资源简介

(共26张PPT)
选择性必修1《数据与数据结构》
第三章 字符串、队列和栈
3.3 栈的概念、特性及基本操作
情境导入
消毒桶的餐盘
知识讲解
1.栈的概念【一种受限的线性表，仅允许在一端插入或删除】
栈顶：
栈底：
李岚
张栋
陈思思
刘力源
栈顶：
栈底：
允许插入或删除的一端
表的另一端
2.栈的特性
李览
张栋
陈思思
刘力源
栈顶：
栈底：
（1）先进后出、后进先出
最后入栈的栈顶元素“李览”最先出栈；
最先入栈的栈底元素“刘力源”最后出栈。
（2）有限序列性
栈可以为空，也可以包含多个元素。
栈中元素存在线性关系，栈顶元素有一个前驱点，栈底元素有一个后继点。
其他元素既有一个前驱又有一个后继。
？
问题与讨论
栈与队列有什么相同点和不同点？
不同点 相同点
栈 先进后出、后进先出； 只允许在一端进行操作 一种受限制的线性表
只允许在端点操作
队列 先进先出、后进后出； 出队（队首）、入队（队尾）
3.3.2 栈的基本操作
栈可用数组实现的原因——按顺序结构存储
C
B
A
栈顶：top=2
栈底
A B C
数组st 0 1 2
①图为栈结构
②图为用数组st存储该栈
当top=0时，st[top]存储栈底元素“A”
top=1时，st[top]存储栈中第2个元素“B”
top=2时，st[top]存储栈顶元素“C”
栈顶元素有一个前驱点，栈底元素有一个后继点
使用top变量来记录栈顶元素【在数组中的位置——栈顶元素的位置会变】
拓展链接
栈的链式存储结构
利用链式存储方式实现的栈称为链栈。它可以用单链表的方式实现。如图3.3.3所示，栈顶指针top为链栈的头指针。链栈的优点在于它克服了用数组实现的顺序栈空间利用率不高的缺点,但是要为每个栈元素分配额外的指针空间。
D
C
B
A ^
top
栈的基本操作
入栈
建栈
知识讲解
1.建栈
在Python中，当要存储n个元素的栈时，可以用列表创建一个长度为n的栈。例如，要使4个字母“A”“B”“C”“D’按序人栈、出栈,可以建一个长度为4的栈st，元素初始值均为空串。为了操作方便，把指向栈顶元素的指针变量top值设置为-1。
Python 代码实现如下:
top=-1
st=[“ ”]*4
建队与建栈的区别？
2.入栈、出栈
入栈又叫压栈操作，把数据元素压人栈顶。每次入栈时，栈顶指针变量top值加1,再给st[top]赋值。字母“A”“B”“C”“D”按序入栈的过程如图3.3.4所示。
A
top=0
top=1
C
B
A
B
A
top=3
D
C
B
A
top=2

图3.3.4 st栈中的入栈过程
top=1
C
B
A
B
A
top=3
D
C
B
A
top=2

Python代码实现如下：
top=top+1 #top=0
st[top]="A" #字母A入栈
top=top+1 #top=1
st[top]="B" #字母B入栈
top=top+1 #top=2
st[top]="C" #字母C入栈
top=top+1 #top=3
st[top]="D" #字母D入栈
A
top=0
问题与讨论
编号为1、2、3、4的4列火车，按顺序开进一个栈式结构的站点。问:开出火车站的顺序有多少种 请写出所有可能的出栈序列。
出栈顺序：1234 1243 1324 1342 1432
2134 2143 2314 2341 2431
3214 3241 3421
4321
共14种出栈方式
Python程序编写：十进制n转二进制
n=int(input("请输入任意十进制数n："))
number=n
s=""
while n!=0:
r=n%2
s=str(r)+s
n=n//2
print("十进制数%d的二进制数是:%s"%(number,s))
输出格式要求
对于第一章项目挑战中的“用户角色特征值”转换成二进制，可以采用“除二取余法”，并利用栈结构存储每次转换过程中得到的余数。
以特征值6为例，转成二进制的过程如图3.3.5所示。
除二取余数的过程中:
特征值的变化为6→3→1→0;
每一步得到的余数为0→1→1;
按序人栈，当特征值变为0时，依次取出栈中元素，得到对应的二进制数“110”。
【变量意义】
栈st:每次得到的余数，
number:特征值，
top:栈顶位置。
“除二取余数” 的入栈和出栈过程
0
top=0
top=1
1
1
0
1
0
top=2
number=3 number=1 number=0
入栈
1
1
0
top=2
top=1
1
0
0
top=0
top=-1
出栈
程序 测试结果
st=[-1]*100 top=-1 number=int(input("请输入十进制数：")) while number>0: x=number % 2 top=top+1 st[top]=x #入栈 number=number//2 while top>=0: #栈空标志top=-1 print(st[top],end=“”) #输出栈元素 top=top-1 请输入十进制数：13
输出：
1101
例1 括号匹配
数学计算式： （ a ÷（ b – c ）+ d ）× e
1 2 3 4 5 6 7 8 9 10 11 12 13
位置1 位置11
位置4 位置8
数学计算式： a ÷（ b – c ））
1 2 3 4 5 6 7 8
位置8无匹配括号！！！
（1）抽象与建模
数学计算式中既有数字，又有加减乘除等运算符号，判断括号是否匹配时，可以忽略这些括号以外的数字和运算符号。
对于数学计算式: (a÷(b-c)+d)x e，括号的序列如图3.3.8所示:
（ （ ） ）
1 2 3 4
匹配标准：左右括号数量相等 and 位置匹配
栈结构设计：
遇到左括号出栈；遇到右括号，将栈顶的左括号出栈
判断步骤如下：
①栈空，出现右括号时，不匹配。
②扫描结束，栈中还有左括号时，不匹配。
③扫描结束，栈空，则匹配。
！！！
（2）设计算法 ------ (a÷(b-c)+d)x e
设置一个栈st和栈顶指针top，从左往右逐步处理数学计算式。
若是左括号，栈顶指针 top值加1，并将其压入栈中。【入栈操作】
若是右括号:
如果top大于-1，那么栈中有元素，把栈顶的左括号弹出，top值减1，表示该右括号与弹出的左括号相匹配;
如果top等于-1，栈为空，表示没有与该右括号相匹配的左括号，是不匹配的数学计算式。
如果数学计算式处理完毕，栈中还有左括号，那么它也是不匹配的数学计算式。
（
下标
1
top 0
下标
top 1
0
（
（
（
下标
1
top 0
下标
1
0
top=-1
”(” ”(” ”)” ”)”
！！！
程序 测试结果
st=[""]*100 top=-1 flag=True #标记是否有不匹配的情况 s=input("请输入数学计算式：") for i in range(len(s)): if s[i]=="(": top=top+1 st[top]=s[i] elif s[i]==")": if top==-1: flag=False break else: top=top-1 if top>=0: #栈中还有做括号 flag=False if flag: print("括号匹配") else: print("括号不匹配") 请输入数学计算式：(((a+b)*(c-d)-e)/f)
括号匹配
请输入数学计算式：((a+b)*c-d)+(e
括号不匹配
拓展链接
用列表自带的函数和方法实现的栈
Python中用列表自带的函数和方法可以实现建栈、入栈、出栈、栈中元素个数的统计等操作。例如：
stacklist=[] #建立一个空栈
stacklist.append("A") #字母A入栈
stacklist.append("B") #字母B入栈
print(stacklist[1]) #输出栈顶元素，为字母B
print(len(stacklist)) #输出栈中元素的个数，为2
stacklist.pop() #弹出栈顶元素
print(len(stacklist)) #输出栈中元素的个数，为1，是字母A
实践与体验
逆波兰表达式
在数学运算表达式中，运算符总是置于与之相关的两个运算对象之间，在计算结果时，要考虑括号、运算符号的优先性。为了程序实现的方便，波兰逻辑学家J.Lukasiewicz提出了另一种表示法，将运算符置于其运算对象之后，没有括号，不用考虑运算符号的优先性。这种表达式称为后缀表达式，又叫逆波兰表达式，如表达式“682一2*3 ÷+”是“6+ ( 8-2 ) *2÷3”的逆波兰表达式。
实践内容:
输入逆波兰表达式，写一个程序，输出该逆波兰表达式的值。
实践步骤:
1.分析逆波兰表达式的计算方法。根据题意中的计算过程，用一个栈存储数字。从左往右扫描该表达式，遇到数字时，入栈;遇到运算符号时，把处于栈最上方的两个元素依次出栈，用运算符计算，并把计算结果压入栈中。如此反复操作，直至表达式扫描结束。
2.根据算法分析，设计程序。
结果呈现：
输入 输出
6 8 2 – 2 * 3 ÷ + 10
思考与练习
1.如何区分取栈顶元素与出栈操作 用程序如何实现
2.元素a, b, c, d,e按序入栈,在所有的出栈序列中,以元素d开头的出栈序列是哪些
出栈：原来的栈顶元素被删掉，由下一个替代；
取栈顶元素：只是获取栈顶元素的值，不删除该元素；
d c b a
decba
dceba
dcbea
dcbae 一共4种出栈顺序
栈的概念
栈的特性
栈的基本操作
栈的简单应用
课堂小结
学习评价
对自己和同伴的表现进行客观的评价，并思考后续完善的方向。（5=优秀，4=超出一般水平，3=满意，2=有待改进，1=不太理想）
评分项 自我评价 同学互评
能从新课导入中的感知栈结构的应用 5 4 3 2 1 5 4 3 2 1
能理解栈的概念、特性。 5 4 3 2 1 5 4 3 2 1
能自主学习教材中“栈的基本操作”，并迁移完成栈的出队操作。 5 4 3 2 1 5 4 3 2 1
能利用栈的基本操作，解决一些简单的含有栈结思想的问题。 5 4 3 2 1 5 4 3 2 1
谢谢观看

展开更多......

收起↑