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

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

1、3.3栈栈选修1数据与数据结构 栈的概念和特性栈：一种操作受限的线性表，仅允许在表的一端进行插入或删除。进行插入或删除操作的一端称为栈顶，位于栈顶位置的元素称为栈顶元素；相应地，将表的另一端称为栈底，位于栈底位置的元素为栈底元素。栈的概念和特性1.先进后出、后进先出DCBA栈顶栈底最后入栈的D最先出栈，最先入栈的A最后出栈弹匣的装弹过程（入栈）栈的概念和特性2.有限序列性栈可以是空的，也可以包含多个元素。栈中元素呈现线性关系，栈顶元素有一个前驱点，栈底元素有一个后继点，其他元素既有一个前驱点，又有一个后继点。栈的概念和特性【思考】栈与队列有什么相同点和不同点？数据结构 队列栈相同点都是一种操作

2、受限的线性表，都具有有限序列性的特点。不同点两端开放：队尾入队，队首出队先进先出一端开放：栈顶入栈出栈先进后出 栈的基本操作栈，一般按顺序结构存储，可以用数组实现。由于栈顶元素在数组中的位置会发生改变，因此使用top变量来记录栈顶元素在数组中的位置。如下图所示，图为栈结构，图为用数组st存储该栈。CBA栈顶：top=2栈底：ABC数组st012top栈的存储 栈的基本操作1.建栈在Python中，当要存储n个元素的栈时，可以用列表创建一个长度为n的栈。例如，要使4个字母ABCD按序入栈、出栈，可以建一个长度为4的栈st，元素初始值均为空串。为了操作方便，把指向栈顶元素的指针变量top值设置为-

3、1。Python代码实现如下：top=-1st=*4 栈的基本操作2.入栈入栈又叫压栈操作，把数据元素压入栈顶。每次入栈时，栈顶指针变量top值加1，再给sttop赋值。字母A,B,C,D按序入栈的过程如下图所示。0123空栈ABACBADCBAtop 0123top 1023top 2013top 3012满栈st栈的入栈过程top=-1st=*4top+=1sttop=Btop+=1sttop=Atop+=1sttop=Ctop+=1sttop=Dtop -1 栈的基本操作Python代码实现如下：top=-1st=*4top=top+1#top=0sttop=A#字母A入栈top=top

4、+1#top=1sttop=B#字母B入栈top=top+1#top=2sttop=C#字母C入栈top=top+1#top=3sttop=D#字母D入栈top=-1st=*4s=A,B,C,Dfor i in s:#所有字母依次入栈_ _ top=top+1sttop=i 栈的基本操作3.出栈出栈时把栈顶元素取出，同时top值减1。如果栈中没有元素时，即top=-1，不能进行出栈操作。DCBA1top 302满栈CBAtop 2031print(sttop)top-=1BAtop 1023print(sttop)top-=1Atop 0123print(sttop)top-=1print(s

5、ttop)top-=10123空栈top -1 栈的基本操作Python代码实现如下：st=A,B,C,Dtop=3print(sttop)#字母D出栈top-=1#top=2print(sttop)#字母C出栈top-=1#top=1print(sttop)#字母B出栈top-=1#top=0print(sttop)#字母A出栈top-=1#top=-1st=A,B,C,Dtop=3while _:#所有字母依次出栈 print(sttop)_ top-1top-=1 问题与讨论编号为1、2、3、4的4列火车，按顺序开进一个栈式结构的站点。问：开出火车站的顺序有多少种？请写出所有可能的出栈序

6、列。进入栈中的元素可停留、可出栈（1）若火车最先出栈，只能是进出，剩下，则有：出入栈方式出栈序列进出，进出，进出进出，进，进出，出进，进出，出，进出进，进出，进出，出进，进，进出，出，出先进后出 问题与讨论（2）若火车最先出栈，只能是进，进出，剩下，则有：出入栈方式出栈序列出，进出，进出出，进，进出，出进出，出，进出进出，进出，出进，进出，出，出 问题与讨论（3）若火车最先出栈，只能是进，进，进，出，剩下，则有：出入栈方式出栈序列出，出，进出出，进出，出进出，出，出（4）若火车最先出栈，只能是进，进，进，进，进出，则有：出入栈方式出栈序列出，出，出先进后出先进后出 解题方法出栈序列的判断1.原

7、则：要出栈必先进栈，只能将栈顶元素依次出栈。2.判断方法总结：先确定入栈顺序一个元素出栈后，下一个出栈元素只能是入栈序列中它上一个元素或者是未入栈序列的任一元素。练习1.一个序列的入栈顺序为 1,2,3,4,5,6，若 4 第一个出栈，则下列出栈序列中不可能的是()A.4,2,3,1,5,6 B.4,6,5,3,2,1 C.4,3,5,2,6,1 D.4,5,3,6,2,1【答案】A【解析】（本题考查栈）根据栈先进后出的特点，4第一个出栈，只可能是1，2，3依次入栈，4入栈出栈，故1，2，3出栈的顺序只能为3，2，1 栈的应用1.十进制数转换为二进制数st=-1*100#列表中元素初始值为-1

8、top=-1#建栈number=int(input(请输入十进制整数：)while number0:x=number%2 _#入栈 sttop=x _while top=0:print(sttop,end=)top=top-1#出栈算法思想：1）用栈结构存放每次获得的余数 2）根据栈特征输出每次获得的余数请输入十进制整数：13输出：1101top=top+1number=number/2 练习2.一个栈的入栈序列为 1，2，3，4，5，其出栈序列为 s1，s2，s3，s4，s5。若 s2 是 3，则 s1 不可能是()A.1 B.2 C.4 D.5【答案】D【解析】（本题考查栈）根据栈先进后出

9、的特点，如果s1是5，只能是1，2，3，4入栈，5入栈出栈，此时出栈顺序只能是5，4，3，2，1。故s2 不可能是 3。栈的应用2.括号匹配在一个数学计算式(a(b-c)+d)e中，位置1和位置4有左括号(，位置8和位置11有右括号)。位置1的左括号与位置11的右括号相匹配，位置4的左括号与位置8的右括号相匹配。而对于数学计算式a(b-c)，位置8的右括号没有可匹配的左括号。设计一个程序，判断输入的数学计算式中的括号(只有小括号)是否匹配。数量、位置都要匹配！数量、位置都要匹配！一、抽象与建模将表达式中数字和运算符号忽略，直接判断左右括号的数量和位置是否匹配，判断过程用栈结构来实现：若出现左括

10、号则进栈，右括号则把栈顶的左括号出栈，判断是否匹配，分下列3种情况：(1)栈空，出现右括号，不匹配(2)扫描结束，栈中还有左括号，不匹配(3)扫描结束，栈空，匹配()()()(栈的应用2.括号匹配二、设计算法（1）设置一个栈st和栈顶指针top（2）从左往右处理数学计算式，遇到左括号，top的值加1，并将其压入栈中；若是右括号：如果top大于-1，把栈顶的左括号弹出，top的值减1 如果top等于-1，栈为空，输出不匹配（3）如果数学计算式处理完毕，top大于-1，栈中还有未匹配的左括号，输出不匹配 栈的应用Python代码实现如下：st-=*100top=-1flag=True#标记是否有不

11、匹配的情况s=input(请输入数学计算式:)for i in range(len():if si=(:_ elif si=):if top=-1:_ break else:_iftop=0:#栈中还有左括号 flag=Falseif flag:print(括号匹配)else:print(括号不匹配)top=top+1sttop=siflag=Falsetop=top-1练一练1.有如下Python程序段：a=0*5b=A,B,C,D,Etop=-1while top=0:s1=sttop+sl;top-=1执行该程序段后，变量s1的值是()A.acba B.cbac C.abca D.cab

12、cD练一练下列代码段能够实现分离正整数,并输出其各位数字(用空格隔开)的功能。请在划线处填入合适的代码。st=0*10#创建一个空栈top=-1num=int(input(请输入一个正整数:)while num0:sttop=num=num/10print(输出结果为:,end=)while top-1:print(，end=)top-=1top+=1num%10sttopst=*100;top=-1s=input(请输入字符串：)k=len(s)/2for i in range(k):top+=1 sttop=siif _:k=k+1_ for i in range(k,len(s):c=sttop_ if c!=si:flag=False;breakif flag:print(字符串：,s,是回文字符串)else:print(字符串：,s,不是回文字符串)练一练abcdcba0123456栈2c1b0a2.判断回文字符串的问题可以通过多种方法来解决。如下Python程序利用栈来解决回文字符串的问题，请补全划线处的代码。flag=Truetop-=1len(s)%2=1