高中信息技术教科版 (2019)选修1 数据与数据结构5.1 栈结构及其实现集体备课课件ppt

这是一份高中信息技术教科版 (2019)选修1 数据与数据结构5.1 栈结构及其实现集体备课课件ppt，共16页。PPT课件主要包含了栈应用2括号匹配，编写程序等内容，欢迎下载使用。

汉诺塔游戏，玩法如下: 1.有三根杆子A,B,C。A杆上有若干碟子 2.每次移动一块碟子,小的只能叠在大的上面 3.把所有碟子从A杆全部移到C杆上完成游戏，分析各个环移动的特征
是一种“先进后出”的线性表，仅允许在一端进行插入和删除允许插入或删除的一端称为栈顶，对应元素称为栈顶元素另一端叫栈底，对应元素称为栈顶元素
（1）先进后出，后进先出 元素入栈顺序和元素出栈顺序相反（2）有限序列性：栈元素个数有限 栈可以为空，也可以包含多个元素， 栈顶元素只有一个前驱点， 栈底元素只有一个后继点， 其他元素既有一个前驱点，又有一个后继点。
栈操作（建栈\入栈IN\出栈OUT）
例：有4个字母“a”“b”“c”“d”“e”按序入栈，可创建长度为5的栈st：初始为空串， 栈顶指针tp设置为-1代码示例：tp=-1st=[“”]*5
栈按顺序结构存储，通过数组实现，所以Pythn可使用列表创建栈
栈顶指针tp记录栈顶元素的位置，初始值为-1，进栈一个元素，tp指针加1，即st[tp]=栈顶元素
tp=-1 #初始值tp=tp+1 #tp=0st[tp]=”a” #a入栈，tp指向a的位置tp=tp+1 #tp=1st[tp]=”b” #b入栈，tp指向b的位置tp=tp+1 #tp=2st[tp]=”c” #c入栈，tp指向c的位置tp=tp+1 #tp=3st[tp]=”d” #d入栈，tp指向d的位置tp=tp+1 #tp=4st[tp]=”e” #e入栈，tp指向e的位置
栈操作（建栈\入栈IN总结\出栈OUT）
入栈过程用算法的什么结构实现？停止入栈的条件是什么？st=[“”]*5tp=-1while tp出栈，排在栈顶的元素依次出栈，tp指针变量依次减1，直至tp的值等于-1
tp=4 #初始值st[tp]=”” #e出栈tp=tp-1 #tp=3 ，tp指向d的位置st[tp]=”” #d出栈tp=tp-1 #tp=2 ，tp指向c的位置st[tp]=”” #c出栈tp=tp-1 #tp=1 ，tp指向b的位置st[tp]=”” #b出栈tp=tp-1 #tp=0 ，tp指向a的位置st[tp]=”” #a出栈tp=tp-1 #tp=-1 ，栈空
栈操作（建栈\入栈IN\出栈OUT总结）
出栈过程用算法的什么结构实现？停止出栈的条件是什么？tp=len(st)-1while tp!=-1:print(st[tp])st[tp]=“”stp-=1
算法思想： 1）用栈结构存放每次获得的余数 2）根据栈特征输出每次获得的余数
栈应用1：十进制数转换为二进制数
st=[0]*100 #初始值为0tp=-1num=int(input(“输入十进制数”))while num!=0:stp+=1st[tp]=num%2 #将余数放入栈num=num//2
while tp!=-1:print(st[tp],end=“”)st[tp]=“”stp-=1
一、抽象与建模将表达式中数字和运算符号忽略，直接判断左右括号的数量和位置是否匹配，判断过程用栈结构来实现：若出现左括号则进栈，右括号则把栈顶的左括号出栈，判断是否匹配，分下列3种情况：（1）栈空，出现右括号，不匹配（2）扫描结束，栈中还有左括号，不匹配（3）扫描结束，栈空，匹配
二、设计算法（1）设置一个栈st和栈顶指针tp（2）从左往右处理数学计算式，遇到左括号，tp的值加1，并将其压入栈中；若是右括号： ①如果tp大于-1，把栈顶的左括号弹出，tp的值减1 ②如果tp等于-1，栈为空，输出不匹配（3）如果数学计算式处理完毕，tp大于-1，栈中还有未匹配的左括号，输出不匹配
st=[""]*100tp=-1flag=Trues = input("请输入数学表达式:")fr i in range(len(s)): if s[i] == "(": tp=tp+1 st[tp]=s[i] elif s[i] == ")": if tp==-1: flag=False break else: tp=tp-1
if tp>=0: flag=Falseif flag: print("该数学表达式括号匹配")else: print("该数学表达式括号不匹配")