教科版 高二选择性必修1信息技术第5单元第1课《栈结构及其实现》课件+教案

5.1栈结构及其实现高中信息技术/教科版/选择性必修1目录1.引入与车辆调度探究对线性表的操作限制可不仅只有这一种，我们再来考察另外一种。一条单行道，因为突发原因堵车了。请大家阅读教科书第 124 页至第 127 页的内容，并完成教科书上的问题。 任务一体验单行道车辆调度 活动1记录车辆停放信息道路被大树堵塞后，交通协管员被立即派往新华路负责疏散车辆和行人。通过查看道路监控录像得知，大树倒下的时间大概为早上8点，车牌号为A101的黄色轿车8:05驶入新华路，2分钟后车牌号为B102的绿色轿车停靠在黄色轿车后面，随后车牌号为 C102的蓝色轿车8:08驶入新华路，2分钟后红色轿车D102停靠在其后。图5.1.1 新华路交通状态 任务一体验单行道车辆调度 活动1记录车辆停放信息根据轿车停放时间的先后顺序，完成图5.1.2。图5.1.2 新华路车辆信息1C102D102 任务一体验单行道车辆调度 活动2根据路况更新车辆停放信息红色轿车司机等了半个小时后，还是不见前方车辆有启动的迹象，便于8:40倒车驶回主路，选择其他路线。请用笔画掉已驶出的车辆，更新图5.1.2中的信息，得出图5.1.3。图5.1.3 新华路车辆信息2C102D102 任务一体验单行道车辆调度 活动2根据路况更新车辆停放信息8:42分在主路行驶的车牌号为E201的黑色轿车进入新华路，减速慢行后停在蓝色轿车后面。请根据新华路路况更新图 5.1.4。图5.1.4新华路车辆信息3C102E201栈是一种出入有序的数据集合。作为一种操作受限的线性结构，数据元素的插入和删除都仅发生在同一端，这一端为栈顶 ( Top)，相应地，另一端则为栈底(Bottom)。数据元素的插入操作一般称为入栈(Push)，又称进栈;删除操作则称为出栈(Pop)，又称退栈。栈的概念2.问题抽象：栈及其ADT 任务一体验单行道车辆调度 活动3新华路车辆调度操作交通协管员被告知事故现场短时间内无法清理完毕，建议出行者选择其他的行车路线。与四位司机沟通后，他们选择规划新路线去往目的地。下一步新华路上的车辆该如何进行指挥调度呢?请填写下面的车辆调度信息。第一步:车牌号为 的轿车倒车驶出新华路，这时新华路还停有 辆轿车，下一辆即将驶出的轿车车牌号为 .第二步车牌号为 的轿车倒车驶出新华路，这时新华路还停有 辆轿车，下一辆即将驶出的轿车车牌号为 .E2014C102C1022B102 任务一体验单行道车辆调度 活动3新华路车辆调度操作请填写下面的车辆调度信息。第三步:车牌号为 的轿车倒车驶出新华路，这时新华路还停有 辆轿车，下一辆即将驶出的轿车车牌号为 .第四步车牌号为 的轿车倒车驶出新华路，这时新华路还停有 辆轿车，道路已被清空。分析以上调度过程，思考并回答下面的问题。(1) 最早驶入新华路的车辆为 ，最晚驶出新华路的车辆 .(2)最晚驶入新华路的车辆为 ，最早驶出新华路的车辆 . A1011B102A1010A101A101E201E201 任务一体验单行道车辆调度 活动3新华路车辆调度操作数据元素入栈和出栈的次序正好相反并且所有操作都是对栈顶数据元素进行。距离栈底越近的数据元素，留在栈中的时间就越长，而最新加入栈的数据元素会被最先移除，这种特点通常称为“后进先出”，即Last InFirst Out，简称LIFO。 任务一体验单行道车辆调度 活动3新华路车辆调度操作栈抽象数据类型的接口如下。ADT Stack:Stack0:创建并返回一个不包含任何数据元素的空栈push(item):将数据元素item压入栈顶，无返回值。pop( ):弹出并返回栈顶的数据元素。peek( ):查看、返回但不移除栈顶的数据元素·isEmpty0:判断是否为空栈，返回布尔型的值;size( ):计算并返回栈中数据元素的个数。 任务一体验单行道车辆调度 活动4实现车辆调度过程了解了栈抽象数据类型的基本操作，我们可以利用栈来实现新华路车辆调度过程。用车牌号来表示轿车，补全下面的代码。01.s=Stack( ) #建栈类的实例s02.s.push("A101") #车牌号为A101的黄色轿车入栈s03. #车牌号为B102的绿色轿车人栈s04. #车牌号为C102的蓝色轿车入栈s05. #车牌号为D102的红色轿车入栈 s06. #查看栈中轿车数量07. #车牌号为D102的红色轿车出栈ss.push("B102") s.push("C102") s.push("D102") print (s.size( )) s.pop( ) 任务一体验单行道车辆调度 活动4实现车辆调度过程了解了栈抽象数据类型的基本操作，我们可以利用栈来实现新华路车辆调度过程。用车牌号来表示轿车，补全下面的代码。08. #查看栈顶是什么轿车09. #车牌号为E201的黑色轿车入栈s10. #车牌号为E201的黑色轿车出栈s11. #车牌号为C102的黑色轿车出栈s12. #车牌号为B102的黑色轿车出栈s13. #车牌号为A101的黑色轿车出栈s14. #查看是否为空栈print (s.peek( )) s.push("E201") s.pop( ) s.pop( ) s.pop( ) s.pop( ) print (s.isEmpty( )) 3.课堂实践，实现栈数据类型 任务二 编程实现单行道车辆调度 活动1用顺序存储实现栈栈抽象数据类型主要包括创建栈、入栈、出栈、判断栈是否为空、查看栈顶数据元素和返回栈中数据元素个数。用Python内置的数据类型列表来实现栈的操作如下所示。(1)创建空栈。创建空栈，就是建立一个空的列表，用items来保存栈中的数据元素。01.#创建stack类02. class Stack:03.def __init__(self): #栈初始化为空列表04.self.items=[] 任务二 编程实现单行道车辆调度 活动1用顺序存储实现栈(2)判断栈是否为空。05.def isEmpty(self): #判断是否为空栈06.return self.items==[](3)入栈入栈就是在栈顶 (列表末尾) 加入新的数据元素。例如，车牌号为F201的轿车驶入单行道。请补全下面的代码。07.def push(self，item): #入栈操作08.self .items. .append(item) 任务二 编程实现单行道车辆调度 活动1用顺序存储实现栈(2)判断栈是否为空。05.def isEmpty(self): #判断是否为空栈06.return self.items==[](3)入栈入栈就是在栈顶 (列表末尾) 加入新的数据元素。请补全下面的代码。07.def push(self，item): #入栈操作08.self .items. .append(item) 任务二 编程实现单行道车辆调度 活动1用顺序存储实现栈(4)出栈出栈是将栈顶数据元素弹出并返回。09.def pop(self):10.if self.isEmpty():11.return self.items12.else:13.return self.items ..pop() 任务二 编程实现单行道车辆调度 活动1用顺序存储实现栈(5) 查看栈顶数据元素列表的最后一项即为栈顶数据元素。请补全下面的代码。14.def peek(self): #查看栈顶数据元素15.if self.isEmpty():16.return self.items17.else:18.return self.items[ ]-1(6)计算并返回栈中数据元素的个数19.def size(self):20.return len(self.items) #返回栈中数据元素的个数 任务二 编程实现单行道车辆调度 活动1用顺序存储实现栈将实现栈抽象数据类型顺序存储的代码输入到文件中，保存为stack.py,利用单行道车辆调度测试各个接口的效果。请补全下面的代码。01. from stack import Stack #导入栈类02.s= #创建栈对象03.s.push("A101") #车牌号为A101的轿车驶入单行道04. #车牌号为B102的轿车驶入单行道05. #车牌号为B102的轿车驶出单行道06. print( )#显示当前单行道车辆总数Stack ()s.push("B102")s.pop( )s.size( )栈的列表实现可以将列表的任意一端 (index=0 或者-1)设置为栈顶，上面的活动我们选用列表的末端(idex=-1)作为栈顶，栈的操作通过列表的append和pop方法实现。若选用列表的首端(index=0)为栈顶，则栈的操作需要用列表的insert和pop 方法来实现。栈的顺序存储实现 任务二 编程实现单行道车辆调度 活动2用链式存储实现栈根据链表的特征分析链表实现栈的基本操作并补全下面的代码。 (1)创建空栈。栈的初始化，栈顶节点引用为空。01.class Stack: #创建栈类82.def __init__(self):03.self.head=None #栈初始化为空链表(2)判断栈是否为空通过判断栈顶节点引用是否指向空来判定栈是否为空04..def isEmpty(self): #判断栈是否为空05return self.head==None 任务二 编程实现单行道车辆调度 活动2用链式存储实现栈(3)入栈操作。入栈的链表实现是通过在栈顶加入新节点完成的。例如，车牌号为E201的轿车驶入单行道，如图所示06. def push(self，item): #入栈07.temp=Node(item) #生成新节点08. #新节点引用指向原栈顶节点09.self.head=temp #栈顶节点引用指向新节点temp.next=self.head 任务二 编程实现单行道车辆调度 活动2用链式存储实现栈(4)出栈操作。出栈的链表实现是通过弹出栈顶节点完成的。例如，车牌号为E201的轿车驶出单行道，如图所示。请补全下面的代码。原栈顶 新栈顶 栈底 任务二 编程实现单行道车辆调度 活动2用链式存储实现栈10.def pop(self): #出栈11.if self.isEmpty(): #判断栈是否为空12.print("Can't pop from empty stack.")13.else:14.temp=self.head.data #保存原栈顶节点数据元素15. #栈顶节点引用指向下一个节点16.return temp #返回原栈顶节点数据元素self.head=self.head.next 任务二 编程实现单行道车辆调度 活动2用链式存储实现栈(5) 查看栈顶数据元素17.def peek(self): #查看栈顶数据元素18.if not self.isEmpty():19.return self.head.data(6)查看栈中数据元素的个数。20.def size(self): #查看栈中数据元素的个数21.count=022.index=self.head23.while index!=None: #判断节点是否为空24.count+=125.index=index.next26.return count栈的另一种实现方式是基于节点引用的链式存储方式。数据元素被存放在节点对象中，每个节点对象除了拥有存储数据元素的数据域外，还包括对下个节点的引用。显然，当节点为栈底时，引用为空。栈的链式存储实现6.课堂小结本节课我们学习了栈的抽象数据类型的定义、栈的顺序存储和链式存储两种实现方法。作为只在同一端进行数据元素的插入和删除操作的特殊线性结构栈的操作并不会发生大量的数据移动。作业布置：请同学们认真完成教材中的拓展练习哦！下节课见！