1.4.2　抽象数据类型的描述

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

抽象数据类型包括3个方面的内容：数据对象、数据关系和基本运算，通常采用三元组（D,SP）来表示，其中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清空。这就像学校被撤销，不需要再保留教职工基本信息，将这些教职工信息全部清空。

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

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