(
课件网) 4.3 抽象数据类型 在程序开发实践中,仅有计算层面的抽象还不够,还需要考虑数据层面 的抽象。抽象数据类型能够将数据定义表示与数据操作实现分离,以更 好地支持程序的模块化组织,它也是分解和实现大型复杂系统的最重要 基础技术。 Sum( ) Average( ) Sin( ) tan( ) cos( ) 数据类型与抽象数据类型 数据类型是程序设计领域最重要的基本概念之一,它是指一组性质 相同的值的集合及定义在此集合上的一些操作的总称。使用计算机 程序处理的数据,通常属于不同的类型,如整数型、浮点数型或逻 辑型等。 每种程序设计语言都提供了一些内置数据类型,并为每个内置类型 提供了一批操作。例如,有下列Python程序语句: a=13 #语句1 b=10 #语句2 c=a+b #语句3 print(c) 整型变量 抽象是指抽取出事物具有的普遍性本质,是对具体事物的一个概括。 抽象是一种思考问题的方式,它隐藏了繁杂的细节,只保留实现目标 所必需的信息,实现抽象化后有利于对事物的抽象,便于实现功能、 提高模块独立性。 人们对已有数据类型进行抽象,就有了抽象数据类型。 抽象数据类型(Abstract Data Type,简称ADT)是指一个数学 模型及定义在该模型上的一组操作。ADT的基本思想是抽象,它的 定义仅取决于它的一组逻辑特性,把数据结构及其操作作为一个整体 来研究,而与其在计算机内部如何表示和实现无关。 取字符串长度(len) 截取子串(substr) 拼接字符串(concat) 替换子串(subst) 操作 编程者 字符串抽象数据类型的内部表现 抽象数据类型除了那些已经定义并实现的数据类型,还可以是 编程者在程序设计时使用的函数或者单独定义的数据类型等。 如使用Python的内建函数时,编程者只需考虑函数的功能是否满 足实际需要,再确保函数调用时的表达式是否符合函数构造的要 求,就可以使用此函数,而不需要知道该函数内部实现的任何具 体细节。 max( ) insert( ) head( ) plot( ) 根据抽象数据类型的定义,它还包括定义在该模型上的一组操作, 即一个数据对象、数据对象中各数据元素之间的关系及对数据元素 的操作。 唱歌 跳跃 吃饭 抽象数据类型的描述 定义一个抽象数据类型,需要清晰地表述出各方面的形式要求(如 操作的名字、参数的个数和类型等)和功能要求(希望这个操作完 成什么样的计算或产生什么效果等)。这类对象的功能体现为一组 可以对它们使用的操作。当然,还需要为这一抽象数据类型确定一 个类型名。 为了便于对抽象数据类型进行规范的描述,下面给出了描述抽象数 据类型的标准格式: ADT 抽象数据类型名: Data 数据元素之间逻辑关系的定义 Operation 操作1 初始条件 操作结果描述 操作2 …… 操作n …… endADT 在前三章有关线性表数据结构的学习中,已经知道了线性表数据结构会 涉及的一些操作。比如: 1.如何为创建操作提供初始元素序列; 2.检查线性表中是否存在某个特定数据对象; 3.改变线性表中的内容,包括加入新元素或删除已有元素等; 4.实现一个或两个表的操作,包括表的组合操作等; 5.实现对线性表中的每一个元素的操作,即对表元素的遍历。 下面呈现的是一个简单的线性表抽象数据类型,其中定义了一组 最基本的操作。 ADT List: List(self) #创建一个新表 is_empty(self) #判断sellf是否为一个空表 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) #对表中的每个 ... ...