什么是数据结构？ ​

数据结构 (data structure) 是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。

简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

数据结构的三个方面：数据逻辑结构、数据存储结构、数据运算（即算法）。

数据的逻辑结构 ​

线性结构 ​

线性结构就是表中各个结点具有线性关系。如果从数据结构的语言来描述，线性结构应该包括如下几点：

1. 线性结构是非空集。
2. 线性结构有且仅有一个开始结点和一个终端结点。
3. 线性结构所有结点都最多只有一个直接前驱结点和一个直接后继结点。

线性结构可细分为：

• 线性表
  • 顺序表
  • 链表
• 栈
• 队列
• 串

线性表和数组的区别：从概念上来看，线性表是一种抽象数据类型；数组是一种具体的数据结构。线性表与数组的逻辑结构是不一样的，线性表是元素之间具有 1 对 1 的线性关系的数据元素的集合，而数组是一组数据元素到数组下标的一一映射。

非线性结构 ​

非线性结构就是表中各个结点之间具有多个对应关系。如果从数据结构的语言来描述，非线性结构应该包括如下几点：

1. 非线性结构是非空集。
2. 非线性结构的一个结点可能有多个直接前驱结点和多个直接后继结点。

在实际应用中，数组、广义表、树结构和图结构等数据结构都属于非线性结构。

数据的存储结构 ​

• 顺序

指采用一组物理上连续的存储单元来依次存放所有的数据元素。因此我们只需要存储数据元素，不需要存储这些数据元素之间的关系

• 链接

每一数据元素均使用一个结点来存储，并且每个结点的存储空间是单独分配的，因此这些不一定连续。我们不仅需要存储数据元素，而且还要存储数据元素之间的逻辑关系（将结点分为两部分，一部分存储数据元素本身，称为数据域；一部分存储下一个结点的地址，称为指针域。）

• 索引

在索引存储结构中，不仅需要存储所有数据元素（称为主数据表），还需要建立附加的索引表。每个数据元素都由一个唯一的关键字来标识，由该关键字和对应的数据元素的地址构成一个索引项，存入索引表

• 散列

哈希存储结构是指依据数据元素的关键字，通过事先设计好的哈希函数计算出一个值，再将其作为该数据的存储地址。

数据运算 ​

1. 检索：检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。
2. 插入：往数据结构中增加新的节点。
3. 删除：把指定的结点从数据结构中去掉。
4. 更新：改变指定节点的一个或多个字段的值。
5. 排序：把节点按某种指定的顺序重新排列。例如递增或递减。