2.5 数据结构（Data Structures）

2022-10-02

3分钟阅读时长

数据结构是用于表示算法所处理的数据在内存中存储的格式，当数据是结构化的，会更便于读取。

不同的数据结构有不同的特性，适用于不同的场景,正确选择数据结构会让工作更为简单。

大多数编程语言自带了预先做好的数据结构，比如 C++ 中的「标准模板库」（Standard Template Library）和 Java 中的「Java 类库」（Java Class Library）。

2.5.1 数组（Array）

数组又名列表（list）或是向量（Vector），其连续存储在内存中，可存储多个值。

数组中不同值使用下标（index）区分，下标从 0 开始，使用方括号 [ ] 表示所访问数组的数值。e.g 数组 j 的第一个元素为 j[0]，第三个元素为 j[2]。

本质上是通过计算第一个元素地址的偏移量，来得到数组中其他元素的地址。注意区分数组中第 5 个数字和数组中下标为 5 的数，前者下标为 4，后者实际为第六个数。

数组用途广泛，几乎所有的编程语言都自带了很多函数来处理数据，比如数组排序函数。

字符串（string）是由字母、数字、标点等组成的数组，以二进制值 \0 （null）结尾。处理字符串的常见函数有 strcat，其接受两个数组，将第二个放在第一个结尾处。

数组仅能操作一维数据，二维及以上数据需要使用矩阵（Matrix）。以二维矩阵为例，取值需要 2 个下标，如 j[2][1] :

结构体是指将几个逻辑上有关系的变量打包在一起的结构，比如将银行卡和余额打包在一个称为一个结构体放入数组中。

但数组创建时则大小固定，无法动态增加，同时其按序排列，在中间插入某值需移动后续诸多值，着实不便。因而可以使用结构体建立新的数据结构消除相关限制。

通常采用名为 node 的结构体构建，节点（node）是变量（variable）和指针（pointer）构成的结构体，指针是指向一个内存地址的特殊变量。

node

多个节点可以组成链表（linked list），通过链表中的每个节点指向下一个节点来实现灵活性。下图所示为「循环链表」（circular linked），若最后一个指针为 0(null)，则为非循环列表。

链表的大小可以动态增减，插入也比数组更加容易，只需改变指针即可（如下图）。在链表中，重新排序、两端缩减、分割以及倒序等操作也很容易进行。

链表插入

一种可以使用链表构建的复杂数据结构，采用「先进先出」（First-In First-Out, FIFO）的原则。

处理完一个数据则可以其「出队」（dequeue），将数据加入队列则称为「入队」（enqueue）。入队需要遍历整个链表直至结尾，然后将原先结尾节点的指针指向要加入的节点。

栈是一种「后进先出」（Last-In First-Out, LIFO）的数据结构，类似于放羽毛球进筒里。栈中数据的出入称为「进栈」（push）和「出栈」（pop）。

在 node 的基础上再新增一个指针可以构造出树：

树的结构体

抽象来看，可以将最高的节点称为「根节点」（root），节点下的所有节点称为「子节点」（children），任何子节点的直属上层节点称为「父节点」（parent node），没有任何子节点的节点（i.e. 树结束的地方）叫做「叶节点」（leaf）。

上图这种每个节点最多只有两个节点的树称为「二叉树」（binary tree），这是一种特殊的树。树的节点个数是任意的，甚至我们可以在 node 中使用链表来存储所有的子节点。

树的特性是从根到叶是单向进行，而非循环。若数据随意连接，则构成 2.4.4 节中提过的图（graph），图的指向任意，可以使用多个指针的 node 来表示。