高中信息技术浙教版（2019）选修1 第四章　课时3　抽象数据类型（学案 课件，2份打包）

(课件网) 课时3　抽象数据类型 第四章　树 1.理解抽象数据的概念，理解并体会抽象数据类型对数据处理的重要性。2.能用抽象数据类型表示栈、队列、二叉树，并定义其数据及基本操作，并尝试编写程序实现，进而提高学生的知识迁移能力。 目 录 CONTENTS 知识梳理 01 例题精析 02 随堂检测 03 巩固与提升 04 知识梳理 1 1.数据类型与抽象数据类型 (1)数据类型是指一组_____的值的集合及定义在此集合上的一些_____的总称。 (2)抽象数据类型是指一个_____及定义在该模型上的一组操作，即一个_____、数据对象中_____以及对_____。 性质相同 操作 数学模型　 数据对象 各数据元素之间的关系 数据元素的操作 抽象数据类型与数据结构的关系。 抽象数据类型与数据结构是两个不同的概念，不能混为一谈。具体为： ①数据结构是计算机存储、组织数据的方式，是指相互之间存在一种或多种特定关系的数据元素的集合。 ②抽象数据类型是指一个数学模型及定义在该模型上的一组操作，“抽象数据类型”本质是“数据类型”。我们可以用“抽象数据类型”来实现“数据结构”。 2.抽象数据类型(ADT)的描述 (1)定义一个抽象数据类型(ADT)，需要清晰地表述出_____(如操作的名字、参数的个数和类型等)和_____(这个操作完成什么样的计算或产生什么效果等)。 (2)描述抽象数据类型的标准格式： ADT 抽象数据类型名： Data 数据元素之间逻辑关系的定义 Operation 各方面的形式要求 功能要求 操作1 　　　　 　初始条件 　　　　 　操作结果描述 操作2 　　　　　 …… 操作n 　　　　　 …… end ADT (3)线性表抽象数据类型 ADT List： List(self)　　　#创建一个新表 is_empty(self)　#判断self是否为一个空表 len(self)　　　　#返回列表的长度 prepend(self，elem)　 #在表头插入元素elem append(self，elem)　#在表尾插入元素elem insert(self，elem，i)　#在表的第i个位置入元素elem del_first(self)　#删除第一个元素 del_last(self)　　　 #删除最后一个元素 del (self，i)　　　　 #删除第i个元素 search(self，elem)　#查找元素elem在表中第一次出现的位置 forall(self，op)　#对表中的每个元素执行op操作 3.抽象数据类型的作用 (1)_____，便于程序正确性的证明和复杂性的分析； (2)因为其_____的特点，在程序设计中容易纠正，具有很好的_____； (3)由于抽象数据类型的表示和实现都可以封装起来，_____； (4)_____算法与程序设计的复杂度，有助于在开发过程中少出差错，保证编写的程序有较高的_____，有益于算法的_____，提高程序的_____。 程序结构清晰、层次分明 模块化 可维护性 便于移植和重用 降低了 可靠性 优化 运行效率 例题精析 2 例1 抽象数据类型的三个组成部分分别为数据对象、数据关系和(　　) B 解析　本题主要考查的是抽象数据类型的组成。抽象数据类型的三个组成部分分别为数据对象、数据对象中各数据元素之间的关系和对数据元素的操作，因此答案为B。 A.数据类型 B.基本操作 C.数据结构 D.数据元素 变式训练　下列有关抽象数据类型的说法，正确的是(　　) 解析　本题主要考查的是抽象数据类型的定义。抽象数据类型是由一种数据结构和在其上的一组操作(运算)所组成，因此A选项错误；抽象数据类型和其在计算机内部如何表示和实现无关，因此B选项错误；定义一个抽象数据类型，不仅需要清晰表述出各方面的形式要求，还需要清晰表达出功能要求，因此D选项错误；Python的整型、字符串类型等也是一种抽象数据类型，因此答案为C。 C A.抽象数据类型其实就是数据结构 B.抽象数据类型和其在计算机内部如何表示和实现有关 C.Python的整型其实也是一种抽象数据类型 D.定义一个抽象数据 ... ...