ADT 抽象数据类型

§ 101 ADT 抽象数据类型#

一、问题#

学数据结构时看到”顺序表和链表都是线性表的实现”这句话，没理解为什么——线性表、顺序表、链表到底是什么关系？ADT 在哪一层？

二、为什么是这样#

数据结构有三层，经常混在一起：

• 逻辑层：数据元素之间是什么关系（线性、树形、图形……）
• 操作层：这种结构应该支持什么操作（插入、删除、查找……）
• 实现层：用什么存储结构实现（顺序存储 / 链式存储……）

ADT 站在前两层——先规定”这个东西是什么、能做什么”，不规定底层怎么存。所以同一个线性表 ADT（一对一关系 + 插入删除查找等操作）既可以用数组实现（顺序表），也可以用节点+指针实现（链表）。两种实现都满足 ADT 的接口约定，只是内部结构不同。

这也是为什么教材会说”线性表是逻辑结构”——它是 ADT 层的概念，和存储方式无关。

三、关联#

• 0.1 数据结构基本概念：ADT 概念出处，三层结构的完整解释
• 201-时间复杂度计算技巧：复杂度分析是评价 ADT 操作效率的工具

四、我的理解#

把 ADT 理解成产品说明书：说明书只说这个产品能干什么（接口），不说里面怎么造（实现）。线性表这份说明书说”能按位取元素、能插入、能删除”，至于里面是用数组还是链表实现，是工厂的事。

所以顺序表 ≠ 线性表，顺序表是线性表的一种实现方式，两者不在同一层。