4.3 抽象数据类型（教学课件）信息技术浙教版2019选择性必修1

第3节 抽象数据类型（1课时） 第4章 树 浙教版（2019） 选修一 数据类型与抽象数据类型 01 抽象数据类型的描述 02 抽象数据类型的作用 03 学习目录 围绕教学目标，通过具体案例，解读抽象数据类型，帮助学生理解抽象数据类型的概念。 01 结合前面两章的数据结构，引导学生深入领会抽象数据类型在数据处理中的重要性。 03 在现有抽象数据类型描述的基础上，指导学生尝试定义抽象数据类型。 02 学习目标 PART 01 数据类型与抽象数据类型 新课导入 抽象？ 抽象是指抽取出事物具有的普遍性本质，是对具体事物的一个概括。 抽象是一种思考问题的方式，它隐藏了繁杂的细节，只保留实现目标所必需的信息。 姓名 班级 学籍 排名 新课导入 数据类型:指的是具有相同性质的计算机数据的集合及在这个数据集合上的一组操作。 数据类型 基本数据类型由计算机编程环境提供，编程者可以在编程时直接用系统提供的标识符进行定义，如Python编程语言中的整型、实型、布尔型等。 新课导入 在程序开发实践中，仅有计算层面的抽象还不够，还需要考虑数据层面的抽象。抽象数据类型能够将数据定义表示与数据操作实现分离，以更好地支持程序的模块化组织，它也是分解和实现大型复杂系统的最重要基础技术。 象 sum（） tan（） print() average() len() sin（） 抽 类 型 据 数 数据类型与抽象数据类型 一 1 概念 抽象数据类型:(Abstract Data Type,简称ADT)是指一个数学模型及定义在该模型上的一组操作。 ADT的基本思想是抽象，它的定义仅取决于它的一组逻辑特性，把数据结构及其操作作为一个整体来研究，而与其在计算机内部如何 表示和实现无关。 数据类型与抽象数据类型 一 Python的字符串类型（str）就是一个抽象数据类型，在字符串对象的内部提供了一组操作可供编程者使用，每个操作都有明确的抽象意义，编程者不必受制于操作内部的具体实现技术，在程序设计时可以直接使用。 字符串抽象数据类型的内部表现 数据类型与抽象数据类型 一 抽象数据类型除了那些已经定义并实现的数据类型，还可以是编程者在程序设计时使用的函数或者单独定义的数据类型等。 象 sum（） tan（） print() average() abs() sin（） 抽 类 型 据 数 数据类型与抽象数据类型 一 根据抽象数据类型的定义，它还包括定义在该模型上的一组操作，即一个数据对象、数据对象中各数据元素之间的关系及对数据元素的操作。 跑动 跳跃 下蹲 在设计某互动媒体中的一个角色对象时，设计者可以对其定义几种基本操作，如跑动、跳跃等；一个角色对象到底需要哪些操作，只能由设计者根据实际需要来确定，如为角色对象增加下蹲等操作。 抽象数据类型的描述 二 描述 定义一个抽象数据类型，需要清晰地表述出各方面的形式要求（操作的名字、参数的个数和类型等）和功能要求（希望这个操作完成什么样的计算或产生什么效果等）。 当然，还需要为这一抽象数据类型确定一个类型名。 描述抽象数据类型的标准格式 抽象数据类型的描述 二 2 4 5 3 1 如何为创建操作提供初始元素序列； 检查线性表中是否存在某个特定数据对象； 改变线性表中的内容，包括加入新元素或删除已有元素等； 实现一个或两个表的操作，包括表的组合操作等； 实现对线性表中的每一个元素的操作，即对表元素的遍历。 在前三章有关线性表数据结构的学习中，已经知道了线性表数据结构会涉及的一些操作。 抽象数据类型的描述 二 线性表抽象数据类型 ADT List: List(self) is_empty(self) len(self) prepend(self,elem) append(self,elem) insert(self,elem,i) del_first(self) del_last(self) del(self,i) search(self,elem) forall(self,op) #创建一个新表 #判断self是否为一个空表 #返回表的长度 #在表头插入元素elem #在表尾插入元素elem #在表的第i个位置插入元素elem #删除第一个元素 #删除最后一个元素 #删除第1个元素 #查找元素elem在表中第一次出现的位置 #对表中的每个元素执行op操作 抽象数据类型的描述 二 探讨与讨论 1.如何定义一个矩形抽象数据类型？ ADT jx: chang; #长度数据 kuan; #宽度数据 zc(self) #求矩形的周长 mj(self) #求矩形的面积 ADT 抽象数据类型名: Data 数据元素之间逻辑关系的定义 Operation 操作1 初始条件 操作结果描述 操作2 …… 操作n …… endADT 抽象数据类型的描述 二 抽象数据类型（链表节点） # # 定义一个链表节点的抽象类 class Node( ): # 初始化链表节点为空 def __init__(self, value, next=None): self._value = value self._next = next # 取当前节点的数值 def getValue(self): return self._value ADT类型：class 抽象数据类型名：Node 初始化条件：__init__函数 操作：getValue函数 抽象数据类型的描述 二 列表，字符串，队列，树等都是抽象数据类型。 列表： ADT List: List( self ) is _empty( self ) len( self ) append( self, elem ) insert( self, elem, i ) del( self, i ) #创建一个新表 #判断self是否为一个空表 #返回表的长度 #在表尾插入元素elem #在表的第i个位置插入元素elem #删除第i个元素 抽象数据类型的描述 二 列表，字符串，队列，树等都是抽象数据类型。 字符串： ADT String: String( self, sseq ) is_empty( self ) len( self ) char( self, index) substr( self, a, b) match( self, string ) #基于字符串序列sseq建立一个字符串 #判断字符串是否空串 #取字符串的长度 #取得字符串中位置index的字符 #取得字符串中[a,b]的字串，左闭右开区间 #查找字符串string在本字符串中第一次出现的位置 现有一字符串对象str,若要获取字符串[a,b](左闭右闭）区间内的字串，正确的调用方式为 substr(str,a,b+1） 抽象数据类型的描述 二 列表，字符串，队列，树等都是抽象数据类型。 队列： ADT Queue: Queue( self) is_empty( self ) enqueue( self, elem ) dequeue( self ) peek( self) #创建空队列 #判断队列是否为空，空时返回True,否则返回False #将元素elem加入队列，即入队 #出队 #查看队列里最早进入的元素，不删除 抽象数据类型的描述 二 列表，字符串，队列，树等都是抽象数据类型。 栈： ADT Stack: Stack( self) is_empty( self ) push( self, elem ) pop( self ) peek( self) #创建空栈 #判断栈是否为空，空时返回True,否则返回False #将元素elem加入栈，即入栈 #出栈 #查看栈顶元素，不删除 抽象数据类型的作用 三 2 4 5 3 1 程序结构清晰、层次分明，便于程序正确性的证明和复杂性的分析; 因为模块化的特点，便于改正错误的代码，利于维护系统; 抽象数据类型的表示和实现利于封装，便于代码的移植和重用； 使得算法设计和数据结构设计分开，降低了程序的复杂性，利于编写代码实现的可靠性； 使得数据结构可自由选择，给了算法的优化空间，提高了程序运行的效率。 抽象数据类型的作用 抽象数据类型的作用 三 探讨与讨论 1.试说明数据结构和抽象数据类型之间的联系和区别。 ①“数据结构”定义为一个二元组(D,S),即两个集合,D是数据元素的集合,S是数据元素之间一个或多个关系的集合。 ②“抽象数据类型”本质是“数据类型”,与计算机相关,涉及数据的存储及如何用存储来反应数据元素之间的关系。它定义为一个三元组(D,S,P),加上的P是定义的一组针对存储的数据操作(如插入,删除,排序等)。 ③总之“抽象数据类型”是“物理”概念,“数据结构”是“逻辑”概念.“抽象数据类型”来实现“数据结构”。 课堂练习 四 探讨与讨论 1.下列关于抽象数据类型的说法，不正确的是（ ） A.程序设计语言的一个内置类型可以看作是一个抽象数据类型 B.抽象数据类型的定义仅取决于它的一组逻辑特性，与其在计算机 内部的表示与实现无关 C.定义一个抽象数据类型，只需要清晰地表达出各方面的形式要求 即可 D.使用抽象数据类型编写的程序结构清晰、层次分明，也便于程序 的移植和重用 C 课堂练习 四 2.创建一个简单的ADT，如下所示： classNd( ): def _init_(self,data): self.data=data def judge(self): if self.data%5==0: print(self.data,“是5的倍数”) else: print(self.data,“不是5的倍数”) #创建实例 my_data=Nd(10) my_data.judgeodd( ) 下列有关该抽象数据类型（ADT）实例的说法中，不正确的是（ ） A.创建的类名称为Nd B.def judge(self)的功能是定义judge函数 C.程序代码执行后的结果为“10是5的倍数” D.my_data为Nd类的一个对象 B 抽象数据类型 四 小 结 一、数据类型与抽象数据类型 1.数据类型 2.抽象数据类型 二、抽象数据类型的描述 1.描述抽象数据类型的标准格式 2.线性表数据结构 3.抽象数据类型 三、抽象数据类型的作用 谢谢观看 第3节 抽象数据类型 浙教版（2019） 选修一 $$