JavaScript - 数据结构详解(一)

[GrapeCityChina]

存储结构

数据结构大致包含以下几种存储结构：

1. 线性表
   • 顺序表
   • 链表
   • 栈和队列
2. 树结构
   • 普通树
   • 二叉树
   • 线索二叉树等
3. 图存储结构

下面对各种数据结构做详细讲解。

线性表

将具有 「一对一」 关系的数据 「线性」 地存储到物理空间中，这种存储结构就称为线性存储结构（简称线性表）。

• 使用线性表存储数据的方式可以这样理解，即「把所有数据用一根线儿串起来，再存储到物理空间中」。
• 使用线性表存储的数据，要求数据类型必须一致。

线性表并不是一种具体的存储结构，它包含顺序存储结构和链式存储结构，是顺序表和链表的统称。

前驱和后继

数据结构中，一组数据中的每个个体被称为数据元素，简称元素。

另外，对于具有 「一对一」 逻辑关系的数据，我们一直在用「某一元素的左侧（前边）或右侧（后边）」这样不专业的词，其实线性表中有更准确的术语：

• 某一元素的左侧相邻元素称为 直接前驱，位于此元素左侧的所有元素都统称为 前驱元素；
• 某一元素的右侧相邻元素称为 直接后继，位于此元素右侧的所有元素都统称为 后继元素；

顺序表

顺序表，全名顺序存储结构，是线性表的一种。

• 顺序表存储数据时，会提前申请一整块足够大小的物理空间，然后将数据依次存储起来，存储时做到数据元素之间不留一丝缝隙。
• 由于顺序表结构的底层实现借助的就是数组，因此对于初学者来说，可以把顺序表完全等价为数组，但实则不是这样。数据结构是研究数据存储方式的一门学科，它囊括的都是各种存储结构，而数组只是各种编程语言中的基本数据类型，并不属于数据结构的范畴。

链表

链表，别名链式存储结构或单链表，用于存储逻辑关系为 「一对一」 的数据。

我们知道，使用顺序表（底层实现靠数组）时，需要提前申请一定大小的存储空间，这块存储空间的物理地址是连续的。链表则完全不同，使用链表存储数据时，是随用随申请，因此数据的存储位置是相互分离的，换句话说，数据的存储位置是随机的。

• 数据元素随机存储，并通过指针表示数据之间逻辑关系的存储结构就是链式存储结构。
• 链表中有头节点时，头指针指向头节点；反之，若链表中没有头节点，则头指针指向首元节点。

下期预告

• 静态链表
• 双向链表
• 循环链表
• 双向循环链表
• 栈和队列