【数据结构】数据结构的基本概念

思维导图

数据结构的基本概念和术语

• 数据：数据是信息的载体。是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。
• 数据元素：是数据的基本单位。一个数据元素是可以由多个数据项组成。数据项是构成数据元素的不可分割的最小单元。
• 数据对象：具有相同性质的数据元素的集合，是数据的一个子集。
• 数据类型：一个值的集合和定义在此集合上的一组操作的总称。有原子类型、结构类型、抽象数据类型。
• 数据结构：结构是数据元素相互之间的关系。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。分为逻辑结构、存储结构、数据的运算。

数据结构三要素

逻辑结构

逻辑结构指数据之间的逻辑关系，从逻辑关系上描述数据，与数据的存储无关。

存储结构

数据的存储结构指数据结构在计算机中的表示，也称物理结构，包括关系的表示和数据元素的表示。分为顺序存储、链式存储、索引存储、散列存储（哈希存储）。

• 若采用顺序存储，则各个数据元素在物理上必须是连续的；若采用非顺序存储，则各个数据元素在物理上可以是离散的。
• 数据的存储结构会影响存储空间分配的方便程度。
• 数据的存储结构会影响对数据的运算速度。

数据的运算

施加在数据上的运算包括运算的定义与实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

重要知识

1. 可以用抽象数据类型定义一个完整的数据结构。
2. 在存储数据时，通常不仅要存储各数据元素的值，而且要存储数据元素之间的关系。
3. 数据的逻辑结构独立于其存储结构。
4. 链式存储设计时，结点内的存储单元地址一定连续。
5. 对于两种不同的数据结构，它们的逻辑结构和物理结构有可能相同。比如二叉树和二叉排序树，二叉排序树可以采用二叉树的逻辑表示和存储方式，前者通常用于表示层次关系，后者通常用于排序和查找。虽然它们的运算都有建立树、插入结点、删除结点和查找结点等功能，但对于二叉树和二叉排序树，这些运算的定义是不同的。
6. 线性表既可以用顺序存储方式实现，又可以用链式存储方式实现。在顺序存储方式下，在线性表中插入和删除元素，平均要移动近一半的元素，时间复杂度为O(n)；而在链式存储方式下，插入和删除的时间复杂度都是O(1)。