项目五 模拟实现软件的撤消功能-栈的应用-高中信息技术同步精品课堂（沪科版2019选择性必修1）

项目五模拟实现软件的撤消功能 — 栈的应用 01 02 03 熟练使用算法来实现进栈和出栈，编写程序解决实际问题。 了解软件撤消操作的过程，知道栈的定义。 学习目标 分析问题、设计算法，再根据算法编程实现撤消操作。 01 问题导入 导入 日常学习和工作中，人们使用的许多应用软件，如办公软件，大多提供了“撤消”功能。该功能允许用户撤消有限的操作步骤，方便恢复到误操作之前的状态（图 3-6）。而这一功能在我们计算机程序中应该怎么实现呢？ 图 3-6 撤消键入示意图 1. 分析问题 要实现撤消功能，首先要思考操作的顺序问题。例如，输入 abcde 的操作顺序是先输入 a，然后是 b，再是 c……而撤消的时候是按逆序，先撤消 e，再撤消 d……可以看出，后输入的先撤消，先输入的后撤消，如图 3-7 所示。如果用某种后进先出的数据结构来存储 a，b，c，d，e 的话，可以方便地实现撤消。这种数据结构称为栈。 图 3-7 撤消菜单 活 动 5.1 请尝试写出栈的抽象数据类型定义。 5.2 网上搜索列车调度方法，根据图 3-8 画出用栈进行调度的过程示意图，并说 明调度的原理。 图 3-8 列车调度示意 2. 设计算法 在文档中依次输入 a，b，c，d，e 后，这些字母会依次进栈，每点击一下“撤消”按钮，栈内最后一个字母就会出栈。栈可以用数组来存储元素，也可以用链表存储元素。假设用数组存储元素，即用数组存放输入的字母，用一个变量作为栈顶指针，如图 3-9 中的 top。栈顶指针始终指向栈内的最后的元素。 5.3 在算法流程框图中完成进栈和出栈操作（数组名和变量名可以自取）。 活 动 根据上述的算法，可以编程实现撤消操作。首先要定义栈并进行初始化操作（即置空栈），指针变量要设定为初始值。 class Sqstack (object): def_init_ (self,size): self.size=size # 定义栈的长度 self.stack=[ ' ' ]*size # 存储栈元素的列表 self.top=-1 # 栈顶头指针 3. 程序实现 5.4 打开配套资源中的“顺序栈 .py”程序，补充完整以下代码，并运行测试，模 拟实现撤消功能。 活 动 def Push(self,e): # 进栈程序 else: if self.top==self.size-1: print("栈满 , 不能进栈 ") return e else: def Pop(self): # 出栈程序 if self.top==-1: print("栈空，没有元素出栈 ") return -1 02 知识链接 要理解栈这个概念，首先要明白“栈”这个字的字面意思，如此才能把握本质。“栈”的意思是存储货物或供旅客住宿的地方，可引申为仓库、中转站，所以引入到计算机领域里，就是指数据暂时存储的地方，是一种只能在表的一端进行插入（进栈或入栈）和删除（出栈或是退栈）操作的线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后进入的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后进去的一个数据被第一个读出）。日常生活中有很多后进先出的例子，如碗柜里的一叠碗（图 3-10），先放进去的在下面，后放进去的在上面，取碗时只能从上面开始取，即先取到的是最后放上去的；又如冰糖葫芦串（图 3-11），先串进去的冰糖葫芦在下面，后串进去的冰糖葫芦在上面，吃的时候通常是后串进去的冰糖葫芦先吃到，而先串进去的冰糖葫芦后吃到。 1.栈 图 3-10 碗柜里的碗 栈的抽象数据类型表示如下： 图 3-11 冰糖葫芦串 栈有两种存储方式，一种是用数组存储，这种方式存储的栈称为顺序栈；另一种用链表存储，这种方式存储的栈称为链式栈。一般根据进栈元素个数是否确定来选择存储结构，元素个数确定的用顺序栈，不确定的用链式栈。 栈的常用基本操作 1. 进栈 进栈就是从栈底开始，按顺序逐步向栈内添加数据。 算法思想：若栈不满，则先将栈顶指针增 1，然后送入进栈元素。栈满不能进栈。 出栈就是从栈顶开始，按逆序逐步将栈内数据取出。 算法思想：若栈不空，则将栈顶指针所指空间内容取出赋予变量，然后将栈顶指针减1。栈空则没有元素可出。 2. 出栈 非常感谢您的观看 $