1.4　抽象数据类型及其描述

在数据结构中，我们把一组包含数据类型、数据关系及在该数据上的一组基本操作统称为抽象数据类型。

1.4.1　什么是抽象数据类型

抽象数据类型（Abstract Data Type，ADT）是描述具有某种逻辑关系的数学模型，以及在该数学模型上进行的一组操作。抽象数据类型有点类似于Java中的类，例如Java中的String类定义了一些常用的方法和属性，如charAt()、subString()、split()、valueOf()等。它们的区别在于，抽象数据类型描述的是一组逻辑上的特性，与在计算机内部如何表示无关；Java中的类是依赖具体实现的，是抽象数据类型的具体化表现形式。

抽象数据类型不仅包括在计算机中已经定义了的数据类型，例如数字类型、字符串、数组、元组等，还包括用户自己定义的数据类型。

一个抽象数据类型定义了一个数据对象、数据对象中数据元素之间的关系以及对数据元素的操作。抽象数据类型通常是指用来解决应用问题的数据模型，包括数据的定义和操作。

抽象数据类型体现了程序设计中的问题分解、抽象和信息隐藏特性。抽象数据类型把实际生活中的问题分解为多个规模小且容易处理的问题，然后建立起一个计算机能处理的数据模型，并把每个功能模块的实现细节作为一个独立的单元，从而使具体实现过程隐藏起来。这就类似于人们日常生活中盖房子，把盖房子分成若干个小任务，如地皮审批、图纸设计、施工、装修等，工程管理人员负责地皮审批，地皮审批下来之后，工程技术人员根据用户需求设计图纸，建筑工人根据设计好的图纸进行施工（包括打地基、砌墙、安装门窗等），盖好房子后请装修工人装修。

盖房子的过程与抽象数据类型中的问题分解类似，工程管理人员不需要了解图纸如何设计，工程技术人员不需要了解打地基和砌墙的具体过程，建筑工人不需要知道怎么画图纸和怎样盖房子，这就是抽象数据类型中的信息隐藏。

1.4.2　抽象数据类型的描述

对于初学者来说，抽象数据类型的概念及描述不太容易理解，这主要是由于很多读者不清楚为什么要定义抽象数据类型，其作用类似于Java语言中的类，区别在于这里的数据类型是抽象的，不依赖具体语言实现，是更高层次的抽象描述，使用抽象数据类型描述的算法可通过任何语言实现。为方便读者理解，本书尽量使用较为通俗的语言进行描述，并通过具体的实例解释。

抽象数据类型包括3个方面的内容：数据对象、数据关系和基本运算，通常采用三元组（D,S,P）来表示，其中D表示数据对象，S是D上的关系集合，P是D中数据的基本运算集合。其基本格式如下：

数据对象和数据关系的定义可采用数学符号和自然语言描述，基本操作的定义格式如下：

     基本操作名（参数表）：初始条件和操作结果描述

大多数教材用以下方式描述线性表的抽象数据类型：

有的教材把抽象数据类型分为两个部分来描述，即数据对象集合和基本操作集合。其中，数据对象集合包括数据对象的定义及数据对象中元素之间关系的描述；基本操作集合是对数据对象的运算的描述。

例如，线性表的抽象数据类型说明如下。

1．数据对象集合

线性表的数据对象集合为{a₁,a₂,…,a_n}，每个元素的类型均为DataType。其中，除了第一个元素a₁外，每一个元素有且只有一个直接前驱元素，除了最后一个元素a_n外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

2．基本操作集合

线性表的基本操作如下。

（1）InitList(&L)：初始化操作，建立一个空的线性表L。这就像是在日常生活中，某院校为了方便管理建立一个教职工基本情况表，准备登记教职工信息。

（2）ListEmpty(L)：若线性表L为空，则返回1，否则返回0。这就像刚刚建立了教职工基本情况表，还没有登记教职工信息。

（3）GetElem(L,i,&e)：返回线性表L的第i个位置元素值给e。这就像在教职工基本情况表中，根据给定序号查找某个教师的信息。

（4）LocateElem(L,e)：在线性表L中查找与给定值e相等的元素，若查找成功，则返回该元素在表中的序号表示成功，否则返回0表示失败。这就像在教职工基本情况表中，根据给定的姓名查找教师信息。

（5）InsertList(&L,i,e)：在线性表L中的第i个位置插入新元素e。这就类似于经过招聘考试，引进了一名教师，这个教师的信息被登记到教职工基本情况表中。

（6）DeleteList(&L,i,&e)：删除线性表L中的第i个位置的元素，并用e返回其值。这就像某个教职工到了退休年龄或者被调入其他学校，需要将该教职工从教职工基本情况表中删除。

（7）ListLength(L)：返回线性表L的元素个数。这就像查看教职工基本情况表中有多少个教职工。

（8）ClearList(&L)：将线性表L清空。这就像学校被撤销，不需要再保留教职工的基本信息，将这些教职工信息全部清空。

以上是抽象数据类型的两种描述方式，本书沿用大多数教材的描述方式。

需要注意的是，在基本操作的描述过程中，参数传递有两种方式：一种是数值传递，另一种是引用传递。前者仅仅是将数值传递给形参，并不返回结果；后者其实是把实参的地址传递给形参，实参和形参其实是同一个变量，被调用函数通过修改该变量的值返回给调用函数，从而返回结果。在描述算法时，在参数前加上&表示引用传递；若参数前没有&，则表示是数值传递。