抽象数据类型和数据结构的定义

抽象数据类型和数据结构的定义​#数据结构#先回顾一下数据结构的完整定义数据结构的三要素是​逻辑结构——数据元素之间的关系​存储结构物理结构——数据在计算机中怎么存​数据的运算——能对数据做哪些操作你说数据结构是有关系的数据元素这个说法只描述了逻辑结构那一部分是不完整的。完整的数据结构 逻辑结构 存储结构 运算。那 ADT 定义了什么ADT抽象数据类型定义了数据的逻辑结构数据的​运算这些运算的功能但不涉及具体怎么实现注意 ADT ​不包含存储结构——这正是它抽象二字的含义刻意把怎么存这个实现细节剥离出去。为什么说定义了 ADT 就等于定义了一个数据结构关键在于​存储结构是实现层面的事不是本质。举个例子栈Stack这个 ADT逻辑结构线性、后进先出LIFO运算Push、Pop、Top、IsEmpty……这就把栈这个数据结构的本质说清楚了。至于底层是用数组实现还是用链表实现那是两种不同的存储方案但它们都是栈。换句话说顺序栈 栈的ADT 数组存储链栈 栈的ADT 链表存储不管哪种存储方式它们都是同一个数据结构——栈。所以 ADT 抓住了是什么和能干什么剩下的存储方式只是怎么做的实现选择。一句话总结王道这里想强调的是​ADT 是数据结构在抽象层面的完整描述。三要素里逻辑结构和运算决定了它是什么数据结构存储结构决定了它的性能怎样。所以定义了 ADT就等于在抽象意义上定义了一个数据结构。你提的这个疑问其实是408选择题特别爱考的辨析点记住这个区分对后面学顺序表/链表、顺序栈/链栈、邻接矩阵/邻接表的对比会很有帮助。