数据结构 —— 常见与不常见

Posted by Mars at

数据结构原始笔记转Blog,然后边学边记。

数据结构学完了忘,别忘了及时回来看看啊。

一、基本常见数据结构

1. 队列、栈、背包

队列:先进先出;

栈:先进后出;

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

2. 数组与链表

2.1 数组

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

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

2.1.1 数组的优缺点

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

缺点:插入数据、删除数据都很慢。

2.2 链表

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

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

2.2.1 链表的优缺点

优点:便于插入、删除数据;

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

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 哈希表的优缺点

优点:

快速查找、插入;

缺点:

① 空间利用率低,中间存在空元素;

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

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

4. 二叉树

  • 二叉树一个节点最多可以有两个子节点,拥有的子节点数目叫做这个节点的
  • 二叉树的最深层数,叫做二叉树的深度
  • 完全二叉树:只允许最底层没有填满,而且最低层元素必须靠左分布;
  • 满二叉树:每一层都填满的二叉树。(除了叶子节点外,所有节点的度都为2。)

4.1 二叉搜索树

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

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

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

4.2 二叉树的存储方式

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

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

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

4.3 二叉树遍历方式

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

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

4.2 红黑树

5. 图

Keywords: Data Structure
previousPost nextPost
已经有 1000000 个小伙伴看完了这篇推文。