数据结构基础

Posted by Mars . Modified at

基础数据结构

一、基本常见数据结构

1. 队列、栈、背包

队列：先进先出；

栈：先进后出；

背包：集合类型。只收集元素，无法按顺序遍历，也无法删除元素。（可以判断是否为空，也可以迭代所有收集到的元素）

2. 数组与链表

2.1 数组

数组是长度在创建时就固定的一种数据格式，每个元素类型统一，因此每个数组元素占用的内存空间相同。

一般会为数组分配一块连续的内存空间，这样只需要一个起始内存地址，就可以利用【起始地址 + 元素大小 * 索引】快速访问数组内任意索引位置的元素.

2.1.1 数组的优缺点

优点：访问一个固定位置的数据很迅速；

缺点：插入数据、删除数据都很慢（因为影响到操作位置后面的元素）。

2.1.2 数组各操作的时间复杂度

对于一个数组Array：

  1. 获取元素：O(1);
  2. 从非尾部删除元素：O(n);
  3. 从尾部删除元素: O(1);
  4. 更新元素：O(1)；
  5. 非尾部插入元素：O(n);
  6. 尾部插入元素：
    • 静态数组：O(n);
    • 动态数组：平均为O(1)；
  7. 复制数组：O(n)

2.2 链表

链表由一个个节点组成，每个节点都储存有自己的数据data和下一个节点的引用地址next。

链表默认是单向的，只能从头到尾。当然特殊情况也可以选择双向链表。

如果链表中的元素，从前到后按序排列（从大到小、从小到大），则称为有序链表。

2.2.1 链表的优缺点

优点：便于插入、删除数据；

缺点：访问数据比较慢，访问任何数据都需要从头遍历。

2.2.3 链表的各操作时间复杂度

对于一个双向链表：

  1. 获取头部：O(1);
  2. 获取尾部：O(1);
  3. 获取中间结点：O(n);
  4. 插入、删除头部：O(1);
  5. 插入、删除尾部：O(1);
  6. 插入中间结点：查找O(n) + 插入O(1)
  7. 查找结点：O(n)

3. 哈希表 （Hash Table）

3.1 什么是哈希表

哈希表也叫散列表。

本质上，哈希表是将字符串或其他数据类型的数据，通过函数映射为一个唯一（或基本唯一）的数字值（叫做哈希值），然后将这些数字值通过某种函数与一个数组的索引一一对应，从而实现将数组索引与原始数据一一对应。

这样就可以利用数组索引查询的快速性，达到迅速查找一个数据的功能。

哈希表原理

当两个不同元素哈希后的数组索引冲突时，可以采用链地址法（在当前数组位置创建链表，用来储存冲突的数据）。

3.2 哈希函数的实现方法

哈希函数将原始数据计算为一个唯一（或基本唯一）的数字哈希值，然后将其压缩到哈希表长度范围内。

// Hash a string to array index. -- Marswiz
function M_hashStringToArrayIndex(str, size) {
    // `str` for original string data
    // `size` for aim array length range

    // initial hashCode is set to zero.
    let hashCode = 0;
    for (let i = 0; i < str.length; i++) {
    // choose 37 here for cal the hash code. Any prime number can be chosen.
        hashCode = hashCode * 37 + str.charCodeAt(i);
    }
    // compress into aim array length range.
    return hashCode % size;
}

3.3 哈希表的优缺点

优点：

快速查找、插入；

缺点：

① 空间利用率低，中间存在空元素；

② 无序，无法通过固定顺序遍历，也不能快速找到最大最小值；

③ 一旦需要扩容，代价很大。

3.4 哈希表各操作时间复杂度

对于一个哈希表HashMap:

  1. 插入键值对：平均O(1)，最坏O(n)；
  2. 删除键值对：平均O(1)，最坏O(n)；
  3. 查找键值对：平均O(1)，最坏O(n)；

最坏情况： 哈希表中所有元素都冲突了，在一个键上形成了很长的链表。这时哈希表相当于链表。

4. 二叉树

  • 二叉树一个节点最多可以有两个子节点，拥有的子节点数目叫做这个节点的度。
  • 二叉树的最深层数，叫做二叉树的深度。
  • 完全二叉树(Complete Binary Tree)： 除最后一层外，每层结点都完全填满。最后一层上允许不填满，但是结点必须靠左排列。
  • 完美二叉树(Perfect Binary Tree)：所有非叶子节点都具有2个子节点，而且所有叶子节点的深度都相同。（每一层都被填满的二叉树）
  • 完满二叉树(Full Binary Tree)：所有非叶子节点都有2个子节点。
  • 平衡二叉树(Balanced Binary Tree)： 所有结点的左子树和右子树深度差不超过1；
  • 扩充二叉树：将二叉树所有的空子树位置，都用一个特殊的空树叶填充，形成的二叉树。

4.1 二叉搜索树

二叉搜索树是有序的树。它有以下特点：

  1. 二叉搜索树必须是完全二叉树；
  2. 二叉搜索树的所有节点的值，大于其左子节点，小于其右子节点；
  3. 二叉搜索树的任意子树也是二叉搜索树。

如果一个二叉搜索树左右两个子树深度差≤1，则叫做平衡二叉搜索树。

4.2 二叉树的存储方式

二叉树有两种存储方式：1. 指针 2. 数组

指针形式是通过节点设置left、right指针，将节点连接成二叉树。

数组形式是将二叉树按从上到下，从左到右的顺序储存在一个数组里。任一索引位置i的左子节点为2i+1，右子节点为2i+2

4.3 二叉树遍历方式

二叉树主要有两种遍历方式：

  • 深度优先遍历：先往深走，遇到叶子节点再往回走。
    • 前序遍历
    • 中序遍历
    • 后序遍历
  • 广度优先遍历：一层一层的去遍历。
    • 层序遍历

5. 图

图的组成

图由顶点和边组成。

图的术语

  • 相邻顶点：一条边连接的两个顶点；
  • 度：依附于一个顶点的边的总数；
  • 子图：一幅图中所有边的一个子集；
  • 路径：由边顺序依次连接的一系列顶点；
  • 路径长度：路径中包含的边的个数；
  • 简单路径：没有重复顶点的路径；
  • 简单环：除了起点和终点相同外，其余没有重复顶点的路径；
  • 连通：两个顶点间存在路径；
  • 连通图：所有顶点都相互连通的图；
  • 无环图：不包含环的图；
  • 密度：已经连接的顶点对占全部可连接的顶点对的比例；
  • 有向图：图中的边是有方向的，只能单向通过；
  • 无向图：图中的边是无方向的，两边都可以走通；
  • 二分图：能够将顶点分为两部分，每个边连接的两个顶点都分别属于不同的部分；
  • 强连通：有向图中的两个顶点，如果互相可达，则它们是强连通的；（一个有向环的所有顶点，都是强连通的）
  • 反向图：有向图中的边全部反转，所形成的图；（图G的反向图，用GR表示）

图的一些特殊结构

  • 自环：一条边连接的两个顶点，是同一个顶点；
  • 平行边：无向图中，连接同一对顶点的两条不同边；

无向图的基本API

标准图的输入、输出结构表示：

V E

edge1

edge2

edge3

…

其中第一行中的V和E表示图中的总顶点数和边数，后续的每一行为一对用空格隔开的顶点编号，表示这两个顶点间存在一条边。

  • 构造：Graph(in)，从标准输入读取一个图；
  • 顶点数： getVNum()，获取图的全部顶点数；
  • 边数：getENum()，获取图的边数；
  • 添加边：addEdge(v1, v2)，在v1和v2之间添加一个边；
  • 获取相邻顶点：getAdjV(v)，获取顶点v的全部相邻顶点；
  • 转化为标准图输出：toString()，将当前图转化为标准图输出结构；

图的搜索

  • 深度优先；
  • 广度优先；
  • 连通分量个数、连通性查询；
Keywords: Data Structure
previousPost nextPost
已经有 1000000 个小伙伴看完了这篇推文。