(
课件网) 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) #对表中的每个 ... ...
