下载掌阅APP，畅读海量书库
立即打开
在计算机处理过程中，需要把处理的对象抽象成计算机能理解的形式，即把数据信息符号转换成一定的数据类型，以方便问题的处理，这就是抽象数据类型的描述。
抽象数据类型 （Abstract Data Type，ADT）是对具有某种逻辑关系的数据类型进行描述，并在该类型上进行的一组操作。抽象数据类型描述的是一组逻辑上的特性，与在计算机内部表示无关。计算机中的整数数据类型是一个抽象数据类型，不同的处理器可能实现方法不同，但其逻辑特性相同，即加、减、乘、除等运算是一致的。
抽象数据类型通常是用户定义且用以表示应用问题的数据模型，通常由基本的数据类型组成，并包括一组相关服务操作。本课程将要介绍的线性表、栈、队列、串、树、图等结构就是一个个不同的抽象数据类型。以盖楼为例，直接用砖块、水泥、沙子来盖，不仅建造周期长，且建造高度规模受限。如果用公司提供的符合规格的水泥预制板，不仅可以高速、安全地建造高楼，水泥预制板使高楼的接缝量大大减少，从而降低了建造高楼的复杂度。由此可见，抽象数据类型是大型软件构造的模块化方法，数据结构中的线性表、栈、队列、串、树、图等抽象数据类型就相当于是设计大型软件的“水泥预制板”，用这些抽象数据类型就可以安全、快速、方便地设计功能复杂的大型软件。
抽象数据类型，就是对象的数据模型，它定义了数据对象、数据对象各数据元素之间的关系及对数据元素的操作。抽象数据类型通常是指用户定义的解决应用问题的数据模型，包括数据的定义和操作。例如，C++的类就是一个抽象数据类型，它包括用户类型的定义和在用户类型上的一组操作。
抽象数据类型体现了程序设计中的问题分解、抽象和信息隐藏特性。抽象数据类型把实际生活中的问题分解为多个规模小且容易处理的问题，然后建立起一个计算机能处理的数据模型，并把每个功能模块的实现细节作为一个独立的单元，从而使具体实现过程隐藏起来。这就好比我们日常生活中盖房子。我们可以把盖房子分成几个小任务，一方面需要工程技术人员提供房子的设计图纸，另一方面需要建筑工人根据图纸打地基、盖房子，房子盖好以后还需要装修工人装修，这与抽象数据类型中的问题分解类似。工程技术人员不需要知道打地基和盖房子的具体过程，装修工人不需要知道怎么画图纸和怎样盖房子，这就相当于抽象数据类型中的信息隐藏。
抽象数据类型可以用一个三元组表示：
ADT（D，S，P）
这里，D是数据对象集合，S是D上的关系集合，P是D的基本操作集合。
本书抽象数据类型可用如下形式描述：
其中，数据对象和数据关系的定义用伪代码描述，基本操作的定义格式如下：
例如，线性表的抽象数据类型描述如下：
知识点： 在C语言中，参数传递可以分为两种：一种是值传递，另一种是引用传递。前者仅仅是将数值传递给形参，而不返回结果；后者其实是把实参的地址传递给形参，实参和形参共用同一块内存区域，在被调用函数中修改形参的值其实就是修改实参的值，因此可将修改后的形参值返回给调用函数，从而实现返回多个参数值的目的。在算法描述时，如果参数前有&，则表示引用传递；如果参数前没有&，则表示是值传递。