本节书摘来自华章出版社《数据结构与算法：Python语言描述》一书中的第2章，第2.1节，作者 裘宗燕，更多章节内容可以访问云栖社区“华章计算机”公众号查看
第2章 抽象数据类型和Python类
在讨论具体的数据结构概念和技术之前，本章将首先介绍抽象数据类型的重要概念和Python面向对象的程序设计技术。后者可以看作一种实现抽象数据类型的技术，但还有所扩充，它也是本书中实现各种数据结构时使用的基本技术。
2.1抽象数据类型
抽象数据类型（Abstract Data Type，ADT）是计算机领域中被广泛接受的一种思想和方法，也是一种用于设计和实现程序模块的有效技术。ADT的基本思想是抽象，或者说是数据抽象（与函数定义实现的计算抽象或称过程抽象对应）。
按照抽象的思想，设计者在考虑一个程序部件时，应该首先给出一个清晰边界，通过一套接口描述说明这一程序部分的可用功能，但并不限制功能的实现方法。从使用者的角度看，一个程序部件实现了一种功能，如果适合实际需要，就可以通过其接口使用之，并不需要知道其实现的具体细节。Python的函数就是一种功能部件，其头部定义了它的接口，描述了函数的名字及其对参数的要求。使用者只需要考虑函数的功能是否满足实际需要，还要保证调用式符合函数头部的要求，并不需要知道函数实现的任何具体细节。
在程序开发实践中人们逐渐认识到，仅有计算层面的抽象机制和抽象定义还不够，还需要考虑数据层面的抽象。能围绕一类数据建立程序组件，将该类数据的具体表示和相关操作的实现包装成一个整体，也是组织复杂程序的一种有效技术，可以用于开发出各种有用的程序模块。要把这种围绕着一类数据对象构造的模块做成数据抽象，同样需要区分模块的接口和实现。模块接口提供使用它提供的功能所需的所有信息，但不涉及具体实现细节。另一方面，模块实现者则要通过模块内部的一套数据定义和函数（过程）定义，实现模块接口的所有功能，从形式上和实际效果上满足模块接口的要求。
2.1.1数据类型和数据构造
类型（数据类型）是程序设计领域最重要的基本概念之一。在程序里描述的、通过计算机去处理的数据，通常都分属不同的类型，例如整数或浮点数等。每个类型包含一集合法的数据对象，并规定了对这些对象的合法操作。各种编程语言都有类型的概念，每种语言都提供了一组内置数据类型，为每个内置类型提供了一批操作。
以Python为例，它提供的基本类型包括逻辑类型bool、数值类型int和float等、字符串类型str，还有一些组合数据类型。类型bool包括两个值（两个对象）True和False，可用操作包括and、or和not；数值类型int包含很多值（整数对象），对它们可做加减乘除等运算；其他类型的情况相仿。开发程序时，应该根据需要选择合适的数据类型。
但是，无论编程语言提供了多少内置类型，在处理较为复杂的问题时，程序员或早或晚都会遇到一些情况，此时各种内置类型都不能满足或者不适合于自己的需要。在这种情况下，编程语言提供的组合类型有可能帮助解决一些问题。例如，Python为数据的组合提供了list、tuple、set、dict等结构（它们也看作是类型），编程时可以利用它们把一组相关数据组织在一起，构成一个数据对象，作为一个整体存储、传递和处理。
举个例子，假设程序里需要处理有理数。最简单朴素的想法是用两个整数表示一个有理数，分别表示其分子和分母，在此基础上实现所需要的运算和操作。在这种安排下，把有理数3/5存入变量可能写成：
a1 = 3
b1 = 5
利用Python函数可返回多对象元组和多项赋值的机制，加法函数可以如下定义：
def rational_plus(a1, b1, a2, b2):
num = a1*b2 + b1*a2
den = b1*b2
return num, den
下面是一个简单的函数使用实例：
a2, b2 = rational_plus(a1, b1, 7, 10)
不难想到，如果真这样写程序，很快就会遇到非常麻烦的管理问题：编程者需要时时记住哪两个变量记录的是一个有理数的分子和分母，操作时不能混淆不同的有理数；如果需要换一个有理数参与运算，也会遇到成对变量名的代换问题。程序比较复杂时，做这类事情很容易出错，而如果真发现程序有错误，确定错误的位置和更正也将极其费时费力。总而言之，用独立的分别存在的两个整数表示一个有理数，这种技术完全不可取。
一种简单改进是利用编程语言的数据组合机制，把相关的多项简单数据组合在一起。还是看有理数的例子，可以考虑用一个Python元组（tuple）表示一个有理数，约定用其中的第0项表示分子，用第1项表示分母。这样就可以写：
r1 = (3, 5)
r2 = (7, 10)
def rational_plus(r1, r2):
num = r1[0]*r2[1] + r2[0]*r1[1]
den = r1[1]*r2[1]
return num, den
r3 = rational_plus(r1, r2)
现在情况显然好了很多，许多管理问题得到缓解。这就是数据构造和组织的作用。
但是，如果进一步考虑，就会发现这种做法仍然有多方面的缺陷，例如：
1）在这里使用的不是特殊的“有理数”，而是普通的元组，因此不能将其与其他元组相互区分。例如，假设程序里还需要处理平面上的整数格点数据，格点也可能用整数的二元组表示，例如，(3, 5) 表示平面上X坐标为3而Y坐标为5的点。从概念上说，把一个有理数与一个格点相加完全是荒谬的事情。但Python编程语言，包括上面定义的rational_plus函数都不会认为这样做是一个错误。
2）与有理数相关的操作并没有绑定于表示有理数的二元组。由于Python不需要说明函数参数的类型，这个问题表现得更加严重。
3）在为有理数对象定义运算（函数）时，需要直接按位置取得其元素。对有理数这样结构很简单的对象，操作中只需区分位置0和1，还算比较容易处理，给思维带来的负担也还可以忍受。如果需要处理的数据对象更复杂，例如其中包含了十几甚至几十个不同成员。在为这种组合数据对象定义操作时，记住每个成员在对象里的位置并正确使用，也会变成非常麻烦的事情。修改数据表示就更让人头痛了。
以上几点和其他一些情况都说明，简单地使用语言提供的数据组合机制，对于处理复杂程序里的数据组织问题是不够的。上面前两点表明的主要问题是，按照这种方式构造和使用的“有理数”不是一个类型，因此不能得到Python语言里的类型功能（如类型检查）的支持。第3点说明，简单地用元组等表示内部结构复杂的数据，经常会导致程序不易阅读和理解，使程序难以编写正确，难以修改。抽象数据类型的思想和支持这种思想的编程语言机制能帮助解决这些问题，至少是使问题大大缓解。
2.1.2抽象数据类型的概念
造成前一节中揭示出的编程缺陷，最重要的问题之一是数据的表示完全暴露，以及对象使用和操作实现对具体表示的依赖性。要克服这些缺点，就需要把对象的使用与其具体实现隔离开。理想情况是：在编程中使用一种对象时，只需考虑应该如何使用，不需要（最好是根本不能）去关注和触及对象的内部表示。这样的数据对象就是一种抽象数据单元，一组这样的对象构成一个抽象的数据类型，为程序里的使用提供了一套功能。
抽象数据类型的基本想法是把数据定义为抽象的对象集合，只为它们定义可用的合法操作，并不暴露其内部实现的具体细节，不论是其数据的表示细节还是操作的实现细节。当然，要使用一种对象，首先需要能构造这种对象，而后能操作它们。抽象数据类型提供的操作应该满足这些要求。一个数据类型的操作通常可以分为三类：
1）构造操作：这类操作基于一些已知信息，产生出这种类型的一个新对象。例如，基于一对整数产生出一个有理数对象；或者基于两个已有的有理数对象，产生出一个表示它们之和的有理数对象；等等。
2）解析操作：这种操作从一个对象取得有用的信息，其结果反映了被操作对象的某方面特性，但结果并不是本类型的对象。例如，可能需要有两个操作，分别从一个有理数获取其分子或者分母，操作的结果应该是整数（整数类型的对象）。
3）变动操作：这类操作修改被操作对象的内部状态。例如，对于一个银行账户对象，其类型就应该提供检查余额和修改余额的操作等。经过一次变动操作之后，对象还是原来的账户对象，仍然表示原来的银行客户的有关信息，但是对象内部记录的存款余额改变了，反映了实际客户账户的余额变动。
当然，一个抽象数据类型还应该有一个名字，用于代表这个类型。
其实，编程语言的一个内置类型就可以看作是一个抽象数据类型。Python的字符串类型str是一个典型实例：字符串对象有一种内部表示形式（无须对外宣布），人们用Python编程序时并不依赖于实际表示（甚至不知道其具体表示方式）；str提供了一组操作供编程使用，每个操作都有明确的抽象意义，不依赖于内部的具体实现技术。易见，Python的整数类型int和实数类型float等的情况与str类似。当然，对于内置类型，语言有可能为它们提供一些额外的方便。如Python为字符串提供了文字量书写方式，可以看作简化的构造操作。从其他角度看，内置类型也就是一种抽象数据类型。
作为数据类型，特别是比较复杂的数据类型，有一个很重要的性质称为变动性，表示该类型的对象在创建之后是否允许变化。如果某个类型只提供上面的第1和第2类操作，那么该类型的对象在创建之后就不会变化，永远处于一个固定的状态。这样的类型称为不变数据类型，这种类型的对象称为不变对象。对于这种类型，在程序里只能（基于其他信息或已有对象）构造新对象或者取得已有对象的特性，不能修改已建立的对象。如果一个类型提供了第3类操作，对该类型的对象执行这种操作后，虽然对象依旧，但其内部状态已经改变。这样的类型就称为可变数据类型，其对象称为可变对象。下面经常把不变数据类型和可变数据类型分别简称为不变类型和可变类型。
例如，Python语言对str类型只提供了前两类操作，因此str是一个不变数据类型；对list类型提供了所有三类操作，它是一个可变数据类型。Python语言里的str、tuple和frozenset是不变数据类型，而list、set和dict是可变数据类型。在编程中设计或定义抽象数据类型时，也要根据情况，决定是将其定义为不变类型还是可变类型。
前面的讨论实际上说明，程序员也需要掌握抽象数据类型的思想和技术。同时说明，编程语言应支持程序员定义自己的抽象数据类型。下面首先通过一些例子，考察在定义一个抽象数据类型时应该怎样思考问题，怎样描述抽象数据类型，描述中应该给出哪些信息。然后讨论Python语言怎样支持这一类定义。
2.1.3抽象数据类型的描述
定义一个抽象数据类型，目的是要定义一类计算对象，它们具有某些特定的功能，可以在计算中使用。这类对象的功能体现为一组可以对它们使用的操作。当然，还需要为这一抽象数据类型确定一个类型名。
下面为抽象数据类型引进一种描述方式，其形式体现了抽象数据类型的主要特点。在后面介绍各种数据结构时，有关章节中也经常是先给出一个抽象数据类型的描述。写出这种描述的过程本身也很有意义，因为它能帮助开发者理清对希望定义的数据类型的想法，清晰地表述出各方面的形式要求（如操作的名字、参数的个数和类型等）和功能要求（希望这个操作完成什么样计算，或产生什么效果等）。
现在考虑一个简单的有理数抽象数据类型，有下面描述：
这里用特殊名字ADT表示这是一个抽象数据类型类型的描述，随它之后给出被定义类型的名字。ADT定义的主要部分描述了一组操作，每个操作的描述由两个部分组成：首先是用标识符或者特殊符号的形式给出的操作名和操作的参数表，随后用类似Python注释的形式给出操作的功能描述。另请注意，在描述操作的参数时，可以考虑在参数名前写一个类型名，表示这个参数应该具有的类型；也可以省略，通过文字叙述说明。
具体到上面的抽象数据类型，其名字是Rational，其中共提供了7个操作。第一个操作以Rational作为名字，这种形式表示它是一个最基本的构造操作，从其他类型的参数出发构造本类型的对象。随后的几个算术运算也是构造操作，它们基于Rational类型的对象生成Rational类型的新对象。最后两个是解析操作，取得有理数对象的性质（成分）。
使用抽象数据类型的思想和技术，不但可以描述有理数一类数学类型，也可以描述实际应用中所需的各种类型。例如，下面描述了一个表示日期的抽象数据类型：
在这个描述里，同样用注释的形式给出了每个操作的解释。注意，上面这个类型里出现了一个第3类操作adjust。举例说明其用途：假设在一个实际应用中建立了一个表示开会日期的对象，随后这个对象被系统中的许多地方（体现为具体的功能模块）共享，如会务、交通、餐饮、住宿等方面的管理子系统。后来出现了一些情况，导致会议的会期需要修改。这时存在两种修改方案：其一是用adjust操作去修改那个日期对象，由于对象共享，这样修改的效果将被各有关机构直接看到；第二个方案是另行构造一个表示新会期的对象，然后重新给各个部门发一轮通知，要求它们都用新日期对象替换原来的对象。显然这两种方案都能解决问题，但是基于它们的工作细节却大不相同。
上面看了两个抽象数据类型的例子，现在总结其中的一些情况：
一个ADT描述由一个头部和按一定格式给出的一组操作描述构成。
ADT的头部给出类型名，最前面是表示抽象数据类型的关键词ADT。
操作的形式描述给出操作的名字、参数的类型和参数名。在ADT描述中，参数名主要用在解释这个操作的功能的地方（上面借用了Python的注释形式）。
各操作的实际功能用自然语言描述，这是一种非形式的说明，主要是为了帮助理解这些操作需要（能够）做什么，以便正确地实现和使用它们。
在抽象数据类型的描述中，其他方面都比较清晰和严格，用自然语言形式给出的功能描述则不然。自然语言有着天然的非精确性和歧义性，用它写的描述很难精确无误。这种描述的意义需要人去理解，误解是造成错误的最重要根源之一。
举例说，仔细考虑上面有关日期的ADT，会发现一些说得不够清楚的地方。例如，“求出d1和d2的日期差”是什么意思？是否包含两端（或者一端）的日期？对整数n“调整n天”的确切含义是什么？这些可能需要进一步解释。
实际上，这类问题确实比较难处理，因为上述说明是希望解释有关操作的“语义”，也就是它的意义、行为或者效果。对各种实际程序部件（或推而广之，各种程序和实际应用），精确而且正确地理解其中各种操作的功能，显然是最重要的一件事情。但是，语义的描述却很不简单。虽然在有关计算机科学技术的研究中，人们已经提出了一些描述语义的方法，但这些方法都比较复杂，确切的描述仍然不容易写好，也不容易理解。使用这些描述方式需要特别的学习和锻炼，绝大部分程序开发者没有这种经验，因此在实践中使用得不多。语义描述方面的进一步情况已经超出了本课程的范围，这里不再深入。所以，本书后面的实例还将继续使用自然语言的描述。当然，在写这种描述时，应该尽可能避免歧义性和误解。例如，可以在描述中结合使用数学符号和自然语言，对一些一般性情况和特殊情况，给出具体实例说明等。这种方式基本上能满足本书的需要。
ADT是一种思想，也是一种组织程序的技术，主要包括：
1）围绕着一类数据定义程序模块，如上面的Rational和Date都是这样。
2）模块的接口和实现分离。上面只给出了模块的接口规范，包括模块名、模块提供的各个操作的名字和参数。每个操作还有非形式化的语义说明。
3）在需要实现时，从所用的编程语言里选择一套合适的机制，采用合理的技术，实现这种ADT的功能，包括具体的数据表示和操作。
如何在Python里实现抽象数据类型，是下一节的主题。
