该文档用于记录数据结构一些知识点和它的解释.记录的内容是按下面图片表示而来👇脑图

线性表

线性表（英语：Linear List）是由n（n≥0）个数据元素（结点）a[0]，a[1]，a[2]…，a[n-1]组成的有限序列。

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。

线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的“线性表”，可以自由的删除或添加节点。受限线性表主要包括栈和队列，受限表示对节点的操作受限制。

受限线性表

对节点的操作是受限制的,不能像非受限线性表一样自由操作节点.

栈(Stack)

堆栈（英语：stack）又称为栈或堆叠，是计算机科学中的一种抽象数据类型，只允许在有序的线性数据集合的一端（称为堆栈顶端，英语：top）进行加入数据（英语：push）和移除数据（英语：pop）的运算。因而按照后进先出（LIFO, Last In First Out）的原理运作。

它的特点:

  1. 先入后出,后进先出
  2. 除头尾节点之外,每一个元素都有一个前驱和后继

它的操作:

  1. 推入(压栈:push): 将数据放入堆栈顶端，堆栈顶端移到新放入的数据
  2. 弹出(弹栈:pop): 将堆栈顶端数据移除，堆栈顶端移到移除后的下一笔数据。

stack常用一维的数组和链表来实现.

堆(Heap)

堆（英语：Heap）是计算机科学中的一种特别的树状数据结构。若是满足以下特性，即可称为堆：“给定堆中任意节点P和C，若P是C的母节点，那么P的值会小于等于（或大于等于）C的值”。

大顶堆(max heap)

根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大顶堆。大根堆要求根节点的关键字既大于或等于左子树的关键字值，又大于或等于右子树的关键字值。

小顶堆(min heap)

根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者，称为小顶堆。小根堆要求根节点的关键字既小于或等于左子树的关键字值，又小于或等于右子树的关键字值。

队列 Queue

队列，又称为伫列（queue），是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。

普通队列

用顺序和链式实现的,先进先出队列

双边队列

队列两边都可以增加和删除数据的队列

优先队列

每个元素都分配一个数字来标记其优先级，如果设较小的数字具有较高的优先级，就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作.

优先权相同的元素，可按先进先出次序处理或按任意优先权进行.

实际应用 LRU Cache

LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法。
LRU Cache 的替换原则就是将最近最少使用的内容替换掉。

非受限线性表

对节点的操作没有限制的线性表

顺序结构

顺序数据结构是指把数据元素放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。

数组

  1. 支持O(1)的随机访问
  2. 平均O(n)的插入和删除
  3. 警惕越界错误,导致 stack over flow

链式结构

链式存储结构是指数据元素放在任意的存储单元中，存储单元可以是连续的，也可以是不连续的。

单链表

链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

2880px-Singly-linked-list.svg.png

它的特点:

  1. 不能随机访问,需要遍历去访问节点
  2. 插入和删除只需要移动指针,时间复杂度为O(1)
  3. 每个节点都需要额外的空间存储指针,需要的内存比数组大

双链表

双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针。这样可以从任何一个节点访问前一个节点，当然也可以访问后一个节点，以至整个链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。双向链表也可以配合下面的其他链表的扩展使用。

1220px-Doubly-linked-list.svg.png

它的特点:

  1. 在单链表的基础上,除了头节点外,每个节点多了一个存放前驱节点内存地址的指针

循环链表

循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。

700px-Circularly-linked-list.svg.png

它的特点:

  1. 尾节点指针指向头节点

静态链表

静态链表的表现形式即为结构体数组，结构体变量包括数据域data和指针。

它的特点:

  1. 借助数组,伴随指向后继节点的指针.

树

在计算机科学中，树（英语：tree）是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

  • 每个节点都只有有限个子节点或无子节点；
  • 没有父节点的节点称为根节点；
  • 每一个非根节点有且只有一个父节点；
  • 除了根节点外，每个子节点可以分为多个不相交的子树；
  • 树里面没有环路(cycle)

二叉树

二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。

二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根节点的度不大于2。有了根节点之后，每个顶点定义了唯一的父节点，和最多2个子节点。

二叉树特点

顺序和链式都可以实现

遍历方式

广度优先搜索

广度优先搜索算法（英语：Breadth-First-Search，缩写为BFS），又译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。

截屏2019-10-1022.46.52.png

BFS是一种盲目搜索法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能地址，彻底地搜索整张图，直到找到结果为止。BFS并不使用经验法则算法。

深度优先搜索

深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

截屏2019-10-1022.49.58.png
前序遍历

指先访问根，然后访问子树的遍历方式

截屏2019-10-1022.57.10.png
中序遍历

指先访问左（右）子树，然后访问根，最后访问右（左）子树的遍历方式

截屏2019-10-1022.58.43.png
后序遍历

指先访问子树，然后访问根的遍历方式

截屏2019-10-1023.00.15.png

完全二叉树

最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此为完全二叉树（Complete Binary Tree）

满二叉树

一棵深度为k，且有{\displaystyle 2^{\begin{aligned}k+1\end{aligned}}-1}个节点的二叉树，称为满二叉树（Full Binary Tree）

FullBT_CompleteBT.jpg

二叉搜索树

二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree）是指一棵空树或者具有下列性质的二叉树：

  1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  3. 任意节点的左、右子树也分别为二叉查找树；
  4. 没有键值相等的节点。

平衡二叉搜索树

平衡二叉搜索树（英语：Balanced Binary Tree）是一种结构平衡的二叉搜索树，它是一种每个节点的左右两子树高度差都不超过一的二元树。它能在O(\log n)内完成插入、查找和删除操作

红黑树

红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

  1. 节点是红色或黑色。
  2. 根是黑色。
  3. 所有叶子都是黑色（叶子是NIL节点）。
  4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

霍夫曼树

霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1L1+W2L2+W3L3+…+WnLn），N个权值Wi（i=1,2,…n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,…n）。可以证明霍夫曼树的WPL是最小的。

字典树

在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

排序

在计算机科学与数学中，一个排序算法（英语：Sorting algorithm）是一种能将一串数据依照特定排序方式进行排列的一种算法。

排序算法的输出必须遵守下列两个原则：

  1. 输出结果为递增序列（递增是针对所需的排序顺序而言）
  2. 输出结果是原输入的一种排列、或是重组

分类:

在计算机科学所使用的排序算法通常被分类为：

  • 计算的时间复杂度（最差、平均、和最好性能），依据列表（list）的大小(n)。一般而言，好的性能是O(nlog n)(大O符号)，坏的性能是O(n^{2})对于一个排序理想的性能是O(n)，但平均而言不可能达到。基于比较的排序算法对大多数输入而言至少需要O(nlogn)。
  • 内存使用量（以及其他计算机资源的使用）
  • 稳定性：稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的纪录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。
  • 依据排序的方法：插入、交换、选择、合并等等。

O(n^2)

冒泡排序

  • 冒泡排序只会操作相邻的两个元素
  • 每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求.如果不满足就让它们俩互换.
  • 冒泡排序算法最多进行 n-1次(n 排序数组长度),每次算法执行元素对比次数是n - i -1次(n 排序数组长度, i 当前算法循环次数)

插入排序

直接插入排序的实现方式是:将未排序的数据,插入到有序序列中!插入的方式是,从后向前扫描有序序列,找到相应的位置插入.

  1. 从第一个元素开始,该元素被认为已排序的有序序列.
  2. 取出最后一个有序序列的下一个元素,在已排序的元素中从后向前扫描.
  3. 如果该元素(已排序)大于新元素(未排序),将该元素移到下一位置.
  4. 重复步骤3,直到找到已排序的元素小于或等于新元素的位置.
  5. 将新元素插入到第四步找到的位置.
  6. 重复步骤2 ~ 5.

选择排序

选择排序算法的实现思路和插入排序有些类似,将元素划分为已排序区间和未排序区间.选择排序每次从未排序区间中找到最小的元素,将其放到已排序区间的末尾.

步骤:

  1. 首先在未排序序列中找到最小(大)元素,存放在排序序列的起始位置.
  2. 再从剩余的未排序序列元素中寻找最小(大)元素,然后放到已排序序列的末尾.
  3. 重复第二步,直到所有元素排序完成.

O(nlogn)

快速排序

快速排序通过在未排序队列中找一个基准点,通过和基准点比较,将比基准点大的元素放一个数组,比基准点小的元素放另一个数组.再在分类过一次的数组中找基准点重复上面的步骤,直至数组最后长度<=1.这时数组数据已经排序完成,只需要合并.

步骤:

  1. 先找到一个基准点(一般使用数组的中部或第一个元素),然后数组被该基准点分为两部分,依次与该基准点数据比较,如果比它小,放左边;反之,放右边.

  2. 左右分别用一个空数组去存储比较后的数据.

  3. 最后递归执行1、2操作,直到数组长度<=1;

快速排序是效率最高的排序算法之一,但它需要另外声明两个数组,需要使用内存资源更多.

归并排序

归并排序是将一个数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了.

步骤,假设一个数组有N个元素:

  1. 将每对单个元素（默认情况下，已排序）归并为2个元素的有序数组
  2. 将2个元素的每对有序数组归并成4个元素的有序数组，重复这个过程……
  3. 最后一步：归并2个N / 2元素的排序数组（为了简化讨论，我们假设N是偶数）以获得完全排序的N个元素数组

归并排序采用分而治之（Divide and Conquer，缩写为D＆C）的思想，这是一个强大的解决问题的范例。
分而治之算法通过以下步骤解决（某种类型的）问题 - 比如我们的排序问题：划分步骤：将大的原始问题划分成较小的子问题并递归地解决较小的子问题，
解决步骤：结合较小的子问题的结果来产生较大的原始问题的结果。

O(n)

桶排序

桶排序是计数排序的升级版，也采用了分治思想。

思想

  • 将要排序的数据分到有限数量的几个有序的桶里。
  • 每个桶里的数据再单独进行排序（一般用插入排序或者快速排序）。
  • 桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

计数排序

思想

  • 找出待排序的数组中最大和最小的元素。
  • 统计数组中每个值为 i 的元素出现的次数，存入新数组 countArr 的第 i 项。
  • 对所有的计数累加（从 countArr 中的第一个元素开始，每一项和前一项相加）。
  • 反向填充目标数组：将每个元素 i 放在新数组的第 countArr[i] 项，每放一个元素就将 countArr[i] 减去 1 。

关键在于理解最后反向填充时的操作。

使用条件

  • 只能用在数据范围不大的场景中，若数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序。
  • 计数排序只能给非负整数排序，其他类型需要在不改变相对大小情况下，转换为非负整数。
  • 比如如果考试成绩精确到小数后一位，就需要将所有分数乘以 10，转换为整数。

基数排序

思想

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。

例子

假设我们有 10 万个手机号码，希望将这 10 万个手机号码从小到大排序，你有什么比较快速的排序方法呢 ？

这个问题里有这样的规律：假设要比较两个手机号码 a，b 的大小，如果在前面几位中，a 手机号码已经比 b 手机号码大了，那后面的几位就不用看了。所以是基于位来比较的。

桶排序、计数排序能派上用场吗 ？手机号码有 11 位，范围太大，显然不适合用这两种排序算法。针对这个排序问题，有没有时间复杂度是 O(n) 的算法呢 ？ 有，就是基数排序。

使用条件

  • 要求数据可以分割独立的位来比较；
  • 位之间由递进关系，如果 a 数据的高位比 b 数据大，那么剩下的地位就不用比较了；
  • 每一位的数据范围不能太大，要可以用线性排序，否则基数排序的时间复杂度无法做到 O(n)。