本文中探讨的数据结构主要以 PHP 语言为基础，并参考了 C/C++。所涉及的数据结构大致分为了以下几个大类：

• 元数据结构
• 复合数据结构
• 集合数据结构

一、元数据结构

编程语言中的最小数据单位。

• 空：null（PHP 表示无类型）
• 布尔：bool（true | false）
• 整型：int
• 浮点型：float、double（PHP 中没有单独的 double，统一都是 float）
• 字符：char（在 PHP 中没有这种类型，用单个字符的字符串来表示）
• 字符串：string

二、复合数据结构

复合数据结构复合数据结构是通过组合多个元数据形成的。

• 结构体：struct（PHP 中没有，但 C/C++ 中有）
• 联合体：union（PHP 中没有，但 C/C++ 中有）
• 对象：object

三、集合数据结构

相同或近似数据的集合体，根据集合方式可分为：顺序存储、索引存储、树、图等。

顺序存储

• 数组：array（有序；有索引号从0开始）
• 链表：link list（有序；无索引号；只能单向遍历；PHP 中需要自己用对象构造）
• 双向链表：double link list（较单链表可以双向遍历）

索引存储

• 哈希映射：hash map（无序；无索引号；在 PHP 中也是 array，存储 key-value 映射）

树：tree

由一个根节点发散出来的，父节点与子节点相连成边，且无循环边的结构。

树中没有孩子的节点我们称之为 叶子。

一个树的 高度（深度）等于树中最长分支的长度。

一个 节点的度 是指其孩子的个数，一棵 树的度 是其节点度的最大值。

一棵树每个节点都大于或等于其子节点，则称之为 大根树（max tree）。

一棵树每个节点都小于或等于其子节点，则称之为 小根树（min tree）。

树图⑴ 来自：码农小钻风的《数据结构——树、二叉树、二叉查找树》

• 二叉树：binary tree（每个父节点最多拥有不超过两个子节点，如：树图⑴ 的 ①②③）
• 一棵二叉树有 n（n>0）个节点，它有 n-1 条边。
• 一棵二叉树高度为 h（h≥0），它最少有 h 个节点，最多有 2h-1 个节点。
• 一棵二叉树有 n（n>0）个元素，它的最大高度为 n，最小高度为 ⌈log₂(n+1)⌉（⌈ ⌉ 向上取整，⌊ ⌋ 向下取整）。
• 二叉树的遍历方式：

• 满二叉树：full binary tree（除叶子以外的其他节点均有两个孩子，如：树图⑴ 的 ②）
• 满二叉树的节点刚好是 2h-1 个。
• 完全二叉树：complete binary tree（由满二叉树从后往前顺序删除 k（k≥0）个节点而来，如：树图⑴ 的 ②③）
• 用数组来存储完全二叉树的所有节点时，可以顺序存储没有间隙。
• 父节点与左子节点的索引满足：parent x 2 + 1 = left_child
• 父节点与右子节点的索引满足：parent x 2 + 2 = right_child
• 最后一个节点的索引：last = n - 1
• 最后一个节点的父节点索引：parent = (last - 1) ÷ 2

• 平衡二叉树：（未完待续）
• 堆：heap（既是大根树或小根树，也是完全二叉树）
• 大根堆：max heap（大根树构成的堆）
• 小根堆：min heap（小根树构成的堆）
• B+树：B+ tree（未完待续）

图：graph

用边连接在一起的顶点集合。带方向的边构成有向图，不带方向的边构成无向图。

下面三个都是图：

图的 邻接矩阵 表示法：

下图矩阵中每个 1 的位置都表示有边，0 的位置表示无边。此外还可以把 1 改成 7、10、16 等其他数字用来作为边的 权 值。

图的 邻接链表 表示法：

图的 邻接数组 表示法：

图的两种遍历方式：