数据结构概览

本文中探讨的数据结构主要以 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(每个父节点最多拥有不超过两个子节点,如:树图⑴ 的 ①②③)
    • 一棵二叉树有 nn>0)个节点,它有 n-1 条边。
    • 一棵二叉树高度为 hh≥0),它最少有 h 个节点,最多有 2h-1 个节点。
    • 一棵二叉树有 nn>0)个元素,它的最大高度为 n,最小高度为 ⌈log₂(n+1)⌉⌈ ⌉ 向上取整,⌊ ⌋ 向下取整)。
    • 二叉树的遍历方式:

数据结构概览

  • 满二叉树:full binary tree(除叶子以外的其他节点均有两个孩子,如:树图⑴ 的 ②)
    • 满二叉树的节点刚好是 2h-1 个。
  • 完全二叉树:complete binary tree(由满二叉树从后往前顺序删除 kk≥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 等其他数字用来作为边的 值。

数据结构概览

图的 邻接链表 表示法:

数据结构概览

图的 邻接数组 表示法:

数据结构概览

图的两种遍历方式:

数据结构概览

本作品采用《CC 协议》,转载必须注明作者和本文链接
xiaer
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!