一些常见数据结构

发表于 | 分类于 |

##数据结构

一般来说，对于问题，解决步骤有

  1. 解决一个跟数据相关的问题
  2. 分析这个问题，想出对应的数据结构
  3. 分析数据结构，想出算法

而对于算法的思想，则有如下的分类

  • 分治法
  • 动态规划法
  • 贪婪算法
  • 线性规划法
  • 简并法

而我们的大前端则主要使用分治法

哈希

算法中经常会用到哈希，那么什么是哈希(hash)呢?

a <- {
    '0': 0,
    '1': 1,
    'key': 'value',
    '键': '值'
}

像以上代码中拥有类似 key-value 的结构形式的就是所谓哈希(hash)

队列

特点就是先进先出,可以用数组实现

var q = []
q.push('张三')
q.push('李四')
q.push('王二麻子')

// 出队
q.shift() // 张三
q.shift() // 李四
q.shift() // 王二麻子

栈

特点就是先进后出,也可以用数组实现

var stack = []
stack.push('张三')
stack.push('李四')
stack.push('王二麻子')

// 出栈
stack.pop() // 王二麻子
stack.pop() // 李四
stack.pop() // 张三

链表

数组无法直接删除中间的某一项,如用 hash (JS 中用对象表示 hash)实现链表

var a = {
    value:0,
    next:{
        value:2,
        next:{
            value:1,
            next: undefined
        }
    }
}
// 从链表中删除掉第二个节点
a.next = a.next.next

树

树的层级结构图如下所示

所以树是什么呢，树就是由 n 个节点组成的一个具有层次关系的集合(这里 n > 0),我们之所以叫树是因为它看起来像树，一个倒着的树。由图中可以看出，一颗树有如下的特点

  1. 每个爸爸节点有 0 个或多个儿子节点
  2. 根节点是没有爸爸节点的，如图中 A
  3. 每一个不是根节点的节点不可能有多个爸爸节点
  4. 除了根节点，每个儿子节点可以分为多个不相交的子树

这里还有几个比较重要的概念:层数、深度、节点个数

  • 层数
    就是根节点为第一层，根节点的儿子节点为第二层，根节点的儿子的儿子节点为第三层…
  • 深度
    对于任意的节点 X，X 的深度为根节点到 X 的唯一路径长,比如设 A 到 B 的路径是 1, B 到 D 的路径是 2 的话，那么 A 到 D 的深度就是 3
  • 节点个数
    就是一颗树有多少个节点，如上图所示的，一共有 16 个节点

二叉树

树中很重要的一个概念就是二叉树，二叉树是什么？就是每个节点最多有两个儿子节点的树,如下图就是一颗二叉树

满二叉树

什么是满二叉树？假设一颗树的深度为 n，且一共有 $2^{n+1} - 1$ 个节点的树就叫做满二叉树，如下图所示

满二叉树的特点就是每一层上的节点数都是最大节点数，看起来很满就是它了

完全二叉树

什么是完全二叉树？假设一颗树的深度为 n,至少有 $2^k$ 个节点，至多有 $2^{k+1} - 1$ 个节点的树就叫做完全二叉树。那么问题来了，完全二叉树如何与其他的树做区分呢？可以参考下图

其实有个小技巧，即

  1. 先对一个满二叉树进行广度优先遍历,按照这个顺序进行编号
  2. 对要测试的树也进行广度有限遍历并按照顺序编号，然后与这颗满二叉树一一比对，若所有编号所在位置能和满二叉树对应，那么这个就是完全二叉树(如上图中的 c、d 就不是完全二叉树)

完全二叉树和满二叉树可以用数组实现,方法如下

// 假如有这样的数组，存储树数据如下所示
a = [1,  2,3,  4,5,6,7,  8,9,10,11,12,13,14,15]
// 取树的第几层(layer)的第几个数(index)
function getValue(array, layer, index) {
  return array[(2 ** (layer-1) + index)]
}
getValue(a, 2, 2) // 3
getValue(a, 3, 1) // 4

如上所示就通过一个公式就可以取数，但是用数组来存储树有个缺点，就是可能浪费数组空间，若这个树不是满二叉树或者是完全二叉树，比如如下

a = [1,  2,3,  4,5,undefined,undefined,  undefined,undefined,6,7] // 上图中 (c)
a = [1,  2,3,  4,5,undefined,6] // 上图中 (d)

可以观察到在数组中虽然申请了空间，但是没有用到

其他树可以用 hash (对象)来实现

B 树

// todo

红黑树

// todo

AVL 树

// todo