下载掌阅APP，畅读海量书库
立即打开
为了在计算机上实现某种操作，需要把处理的对象描述成计算机能识别的形式，即一定形式的数据类型，并定义其上的一组操作。这在数据结构这门课中称为抽象数据类型。
抽象数据类型 （abstract data type，ADT）是描述具有某种逻辑关系的数学模型，并对在该数学模型上进行的一组操作。抽象数据类型描述的是一组逻辑上的特性，与在计算机内部表示无关。计算机中的整数数据类型是一个抽象数据类型，不同的处理器可能实现方法不同，但其逻辑特性相同，即加、减、乘、除等运算是一致的。在用户看来，各种计算机所提供的整数类型数学特性都是相同的，因此，“抽象”的意义在于数据类型的数学抽象特性，而不是它们的实现方法。
抽象数据类型不仅包括在计算机中已经定义了的数据类型，例如整型、浮点型等，还包括用户自己定义的数据类型，例如结构体类型、类等。
一个抽象数据类型定义了一个数据对象、数据对象中数据元素之间的关系及对数据元素的操作。抽象数据类型通常是指用来解决应用问题的数据模型，包括数据的定义和操作。
抽象数据类型体现了程序设计中的问题分解、抽象和信息隐藏特性。抽象数据类型把实际生活中的问题分解为多个规模小且容易处理的问题，然后建立起一个计算机能处理的数据模型，并把每个功能模块的实现细节作为一个独立的单元，从而使具体实现过程隐藏起来。这就类似人们日常生活中盖房子，把盖房子分成若干个小任务：地皮审批、图纸设计、施工、装修等，工程管理人员负责地皮的审批，地皮审批下来之后，工程技术人员根据用户需求设计图纸，建筑工人根据设计好的图纸进行施工（包括打地基、砌墙、安装门窗等），盖好房子后请装修工人装修。
盖房子的过程与抽象数据类型中的问题分解类似，工程管理人员不需要了解图纸如何设计，工程技术人员不需要了解打地基和砌墙的具体过程，装修工人不需要知道怎么画图纸和怎样盖房子，这就是抽象数据类型中的信息隐藏。
对于初学者来说，抽象数据类型不太容易理解，用一大堆公式会让不少读者迷茫，因此，本书采用通俗的语言去讲解抽象数据类型。本书把抽象数据类型分为两个部分来描述，即数据对象集合和基本操作集合。其中，数据对象集合包括数据对象的定义及数据对象中元素之间关系的描述，基本操作集合是对数据对象的运算的描述。数据对象和数据关系的定义可采用数学符号和自然语言描述，基本操作的定义格式如下。
基本操作名（参数表）：初始条件和操作结果描述。
例如线性表的抽象数据类型，描述如下。
线性表的数据对象集合为{a 1 ，a 2 ，…，a n }，每个元素的类型均为DataType。其中，除了第一个元素a 1 外，每一个元素有且只有一个直接前驱元素，除了最后一个元素a n 外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
线性表的基本操作如下所述。
（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清空。这就像学校被撤销，不需要再保留教职工基本信息，将这些教职工信息全部清空。
大多数教材用以下方式描述线性表的抽象数据类型。
ADT List
{
数据对象：D={ai|ai
∈ElemSet
，i=1
，2
，…，n
，n
≥0}
数据关系：R={<ai-1
，ai>|ai-1
，ai
∈D
，i=2
，3
，…，n}
基本操作如下。
（1
）InitList
（&L
）
初始条件：表L
不存在。
操作结果：建立一个空的线性表L
。
（2
）ListEmpty
（L
）
初始条件：表L
存在。
操作结果：若表L
为空，返回1
，否则返回0
。
（3
）GetElem
（L
，i
，&e
）
初始条件：表L
存在，且i
值合法，即1
≤i
≤ListLength
（L
）。
操作结果：返回表L
的第i
个位置元素值给e
。
（4
）LocateElem
（L
，e
）
初始条件：表L
存在，且e
为合法元素值。
操作结果：在表L
中查找与给定值e
相等的元素。如果查找成功，则返回该元素在表中的序号；如果这样的元素不存在，则返回0
。
（5
）InsertList
（&L
，i
，e
）
初始条件：表L
存在，e
为合法元素且1
≤i
≤ListLength
（L
）。
操作结果：在表L
中的第i
个位置插入新元素e
。
（6
）DeleteList
（&L
，i
，&e
）
初始条件：表L
存在且1
≤i
≤ListLength
（L
）。
操作结果：删除表L
中的第i
个位置元素，并用e
返回其值。
（7
）ListLength
（L
）
初始条件：表L
存在。
操作结果：返回表L
的元素个数。
（8
）ClearList
（&L
）
初始条件：表L
存在。
操作结果：将表L
清空。
}ADT List
以上是抽象数据类型的两种描述方式，显然前者会更容易被理解和接受。
需要注意的是，在基本操作的描述过程中，参数传递有两种方式，一种是数值传递，另一种是引用传递。前者仅仅是将数值传递给形参，并不返回结果；后者其实是把实参的地址传递给形参，实参和形参其实是同一个变量，被调用函数通过修改该变量的值返回给调用函数，从而把结果带回。在描述算法时，在参数前加上&表示引用传递；如果参数前没有&，表示是数值传递。