1.3　抽象数据类型

1．数据类型

数据类型是指性质相同的值的集合以及定义在该值集上的运算集合。C语言常用的基本数据类型有整型、字符型、指针类型等。数据类型规定了数据的取值范围和允许执行的运算。例如，若在C语言中声明int a,b，则可以给变量a和b赋值0，但不可以赋值2.5，这超出了int型变量的取值范围。a和b之间可以执行加法运算，但不可以执行求交集运算，这也超出了int型变量所允许的运算范围。

2．抽象数据类型

了解一个数据类型的对象（变量、常量）在计算机内的表示是有一定用处的，但如果每个数据使用者都要考虑基本数据类型的实现细节，这将给数据使用者增加一项繁杂的工作，并且使用者一旦随意改变数据存储表示，也会滋生不可预知的错误。目前普遍认为对数据类型进行抽象，对使用者隐藏一个数据类型的实现是一个好的设计策略，由此产生了抽象数据类型。

抽象数据类型（Abstract Data Type，ADT）是一个数学模型以及在其上定义的运算集合。其最主要的两个特征是数据封装和信息隐蔽。数据封装是指把数据和操纵数据的运算组合在一起的机制。信息隐蔽是指数据的使用者只需知道这些运算的定义（也称规范）便可访问数据，而无须了解数据的存储以及运算算法的实现细节。通过实行数据封装和信息隐蔽，可使数据的使用和实现相分离。

本书中，抽象数据类型的定义格式如下：

3．数据结构与抽象数据类型

本书将一种数据结构视为一个抽象数据类型，从规范和实现两方面来讨论数据结构。规范是对数据结构中数据元素及其关系、运算给出定义，即逻辑结构和运算的定义组成了数据结构的规范。规范指明了一个数据结构可以“做什么”。数据结构的使用者通过规范中的说明使用一个数据结构，不必了解具体的实现细节。数据的存储表示和运算算法的描述构成数据结构的实现，它解决了“怎样做”的问题。