栈　课件--浙教版（2019）高中信息技术选修1.pptx

《栈　课件--浙教版（2019）高中信息技术选修1.pptx》由会员分享，可在线阅读，更多相关《栈　课件--浙教版（2019）高中信息技术选修1.pptx（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、XXXX中学栈新课导入装置只有一端是开放的，所有的操作都只能在这开放的一端进行。数据具有“先进后出、后进先出”的特征，可采用“栈”这种数据结构。栈栈是一种后进先出后进先出的线性表，仅允许在表的一端进行插入或删除操作。进行插入或删除操作的一端称为栈栈顶顶，位于栈顶位置的元素称为栈顶元素；另一端称为栈栈底底，位于栈底位置的元素称为栈底元素。栈顶元素栈底元素栈的特性1.1.先进后出、后进先出先进后出、后进先出2.有限序列性元素的个数是有限的，栈可以为空，也可包含多个元素。栈中元素呈现线性特征，栈顶元素有一个前驱点，栈底元素有一个后继点，其它元素既有一个前驱点又有一个后继点。栈顶元素栈底元素牛刀小试1

2、.有六个元素按照6,5,4,3,2,1的顺序依次进栈，则出栈顺序不可能是（）A.5,4,3,6,1,2B.4,5,3,1,2,6C.3,4,6,5,2,1D.2,3,4,1,5,62.一个栈的入栈序列是1,2,3,4,5，其出栈序列为s1,s2,s3,s4,s5，若s2是3，则s1不可能是（）A.1 B.2 C.4 D.5 CD栈的创建：数组创建栈一般按照顺序结构存储，可以使用数组来实现。栈顶元素在数组中的位置会发生改变，因此使用toptop变量变量来记录栈顶元素栈顶元素在数组中的位置。栈的创建：链表创建栈的链式存储链式存储称为链栈，设置栈顶指针top为链栈的头指针。特点：克服了用数组实现的顺

3、序栈空间利用率不高的缺点，但要为每个栈元素分配额外的指针空间。建栈、入栈、出栈栈以数组形式存储，因此Python中用列表列表创建栈。为了操作方便，把指向栈顶元素的指针变量toptop值设置为值设置为-1-1。创建长度为6，初始值为空串的空栈st字母A、B、C、D、E、F依次入栈，然后依次出栈并输出st=*6top=-1for i in ABCDEF:top+=1 sttop=iwhile top -1:print(sttop,出栈出栈)top-=1st=for i in ABCDEF:st.append(i)print(len(st)for i in range(len(st):print(s

4、t.pop(),出栈出栈“)括号匹配将表达式中数字和运算符号忽略，直接判断左右括号的数量和位置是否匹配，判断过程用栈结构来实现：若出现左括号则进栈，右括号则把栈顶的左括号出栈，判断是否匹配，分下列3种情况：栈空，出现右括号，不匹配。扫描结束，栈中还有左括号，不匹配。扫描结束，栈空，匹配。数据合并问题程序程序备注备注st=*100#初始化top=-1#初始化为空栈flag=True#标记是否有不匹配的情况s=input(请输入数学表达式：)初始化各项数据for i in range(len(s):if si=(:#左括号入栈 top+=1 sttop=si elif si=):#右括号与栈顶元素

5、比较 if top=-1:flag=False break else:top-=1从左往右逐步处理数学表达式：若为左括号则入栈；若为右括号则与栈顶指针进行匹配。数据合并问题程序程序备注备注if top 0:#栈中还有剩余元素 flag=False栈中还有剩余元素，即左括号数量大于右括号。if flag:print(括号匹配)else:print(括号不匹配)请输入数学表达式：(a+b)*(c-d)-e)/f)括号匹配请输入数学表达式：(a+b)*c)-d)+(e括号不匹配逆波兰表达式逆波兰表达式（后缀表达式）：将运算符置于其运算对象之后，没有括号，无需考虑运算符号的优先级。中缀表达式转后缀表达

6、式中缀表达式转后缀表达式：表达式中加入括号；将所有运算符移到对应括号的右边；删除所有的括号。逆波兰表达式计算：从左往右扫描逆表达式，遇遇到到数数字字入入栈栈；遇到运算符号，将栈中最上方的两两个个元元素素依次出栈并用运算符计算，将计算结果压入栈中。重复上述过程直至表达式扫描结束。表达式表达式第一步第一步第二步第二步第三步第三步a+b*c(a+(b*c)(a(bc)*)+abc*+6+(8-2)*2/3(6+(8-2)*2)/3)(6(82)-2)*3)/)+682-2*3/+a/b-c+d*e-a*c(a/b)-c)+(d*e)-(a*c)(ab)/c)-(de)*)+(ac)*)-ab/c-de*+ac*-表达式表达式第一步第一步第二步第二步第三步第三步a+b*c6+(8-2)*2/3a/b-c+d*e-a*c表达式表达式结果结果6+(8-2)*2/310感 谢 聆 听Thankstolisten