# 数据结构基础

学习思路

避免孤立的学习知识点，要关联学习。比如实际应用当中，我们经常使用的是查找和排序操作，这在我们的各种管理系统、数据库系统、操作系统等当中，十分常用，我们通过这个线索将知识点串联起来：

数组的下标寻址十分迅速，但计算机的内存是有限的，故数组的长度也是有限的，实际应用当中的数据往往十分庞大；而且无序数组的查找最坏情况需要遍历整个数组；后来人们提出了二分查找，二分查找要求数组的构造一定有序，二分法查找解决了普通数组查找复杂度过高的问题。任何一种数组无法解决的问题就是插入、删除操作比较复杂，因此，在一个增删查改比较频繁的数据结构中，数组不会被优先考虑

普通链表由于它的结构特点被证明根本不适合进行查找

哈希表是数组和链表的折中，同时它的设计依赖散列函数的设计，数组不能无限长、链表也不适合查找，所以也不适合大规模的查找

二叉查找树因为可能退化成链表，同样不适合进行查找

AVL树是为了解决可能退化成链表问题，但是AVL树的旋转过程非常麻烦，因此插入和删除很慢，也就是构建AVL树比较麻烦

红黑树是平衡二叉树和AVL树的折中，因此是比较合适的。集合类中的Map、关联数组具有较高的查询效率，它们的底层实现就是红黑树。

多路查找树 是大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的(如果元素数量非常多的话，查找就退化成节点内部的线性查找了)，这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。

B树与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。它的应用是文件系统及部分非关系型数据库索引。

B+树在B树基础上，为叶子结点增加链表指针(B树+叶子有序链表)，所有关键字都在叶子结点 中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中。通常用于关系型数据库(如Mysql)和操作系统的文件系统中。

B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针, 在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3。

R树是用来做空间数据存储的树状数据结构。例如给地理位置，矩形和多边形这类多维数据建立索引。

Trie树是自然语言处理中最常用的数据结构，很多字符串处理任务都会用到。Trie树本身是一种有限状态自动机，还有很多变体。什么模式匹配、正则表达式，都与这有关。

A. 数据结构 知识点：数据结构是基础中的基础，任何进阶都逃不开这些知识点。

• 数据结构 - Overview

B. 数据结构之 线性结构：首先理解数据结构中线性结构及其延伸：数组和矩阵，链表，栈和队列等。

• 线性表 - 数组和矩阵
  • 数组是一种连续存储线性结构，元素类型相同，大小相等，数组是多维的，通过使用整型索引值来访问他们的元素，数组尺寸不能改变
• 线性表 - 链表
  • n个节点离散分配，彼此通过指针相连，每个节点只有一个前驱节点，每个节点只有一个后续节点，首节点没有前驱节点，尾节点没有后续节点。确定一个链表我们只需要头指针，通过头指针就可以把整个链表都能推出来
• 线性表(散列) - 哈希表
  • 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。@pdai
• 线性表 - 栈和队列
  • 数组和链表都是线性存储结构的基础，栈和队列都是线性存储结构的应用

C. 数据结构之 逻辑结构：树：然后理解数据结构中逻辑结构之树：二叉搜索树(BST)，平衡二叉树(AVL)，红黑树(R-B Tree)，哈夫曼树，前缀树(Trie)等。

• 树 - 基础和Overview
  • 树在数据结构中至关重要，这里展示树的整体知识体系结构和几种常见树类型
• 树 - 二叉搜索树(BST)
  • 本文主要介绍 二叉树中最基本的二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
• 树 - 平衡二叉树(AVL)
  • 平衡二叉树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。
• 树 - 红黑树(R-B Tree)
  • 红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组，是平衡二叉树和AVL树的折中。
• 树 - 哈夫曼树
  • 哈夫曼又称最优二叉树, 是一种带权路径长度最短的二叉树。
• 树 - 前缀树(Trie)
  • Trie，又称字典树、单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

D. 数据结构之 逻辑结构：图：最后理解数据结构中逻辑结构之图：图基础，图的遍历，最小生成树(Prim & Kruskal)，最短路径(Dijkstra & Frolyd)，拓扑排序(Topological sort)，AOE & 关键路径等。

• 图 - 基础和Overview
  • 图(Graph)是由顶点和连接顶点的边构成的离散结构。在计算机科学中，图是最灵活的数据结构之一，很多问题都可以使用图模型进行建模求解。例如: 生态环境中不同物种的相互竞争、人与人之间的社交与关系网络、化学上用图区分结构不同但分子式相同的同分异构体、分析计算机网络的拓扑结构确定两台计算机是否可以通信、找到两个城市之间的最短路径等等。
• 图 - 遍历(BFS & DFS)
  • 图的深度优先搜索(Depth First Search)，和树的先序遍历比较类似; 广度优先搜索算法(Breadth First Search)，又称为"宽度优先搜索"或"横向优先搜索"
• 图 - 最小生成树(Prim & Kruskal)
  • Kruskal算法是从最小权重边着手，将森林里的树逐渐合并；prim算法是从顶点出发，在根结点的基础上建起一棵树
• 图 - 最短路径(Dijkstra & Frolyd)
  • 最短路径有着广泛的应用，比如地图两点间距离计算，公交查询系统，路由选择等
• 图 - 拓扑排序(Topological sort)
  • 拓扑排序主要用来解决有向图中的依赖解析(dependency resolution)问题
• 图 - AOE & 关键路径
  • 关键路径在项目管理计算工期等方面有广泛等应用，提升工期就是所见缩减所有关键路径上的工期，并且在实现时需要应用到之前拓扑排序的算法(前提: 有向无环图，有依赖关系)

---

# 排序算法详解

A. 常见排序概要：重点理解几个排序之间的对比，时间和空间复杂度，以及应用。PS：越简单越要提高认知效率，做到战略上藐视战术上重视。

• 排序 - Overview

B. 常见排序详解：具体分析各种排序及其复杂度，查漏补缺；在综合复杂度及稳定性情况下，通常希尔, 快排和 归并需要重点掌握。

• 排序 - 冒泡排序(Bubble Sort)
  • 它是一种较简单的排序算法。它会遍历若干次要排序的数列，每次遍历时，它都会从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，一次遍历之后，最大的元素就在数列的末尾！ 采用相同的方法再次遍历时，第二大的元素就被排列在最大元素之前。重复此操作，直到整个数列都有序为止
• 排序 - 快速排序(Quick Sort)
  • 它的基本思想是: 选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
• 排序 - 插入排序(Insertion Sort)
  • 直接插入排序(Straight Insertion Sort)的基本思想是: 把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。
• 排序 - Shell排序(Shell Sort)
  • 希尔排序实质上是一种分组插入方法。它的基本思想是: 对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的。
• 排序 - 选择排序(Selection sort)
  • 它的基本思想是: 首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置；接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
• 排序 - 堆排序(Heap Sort)
  • 堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
• 排序 - 归并排序(Merge Sort)
  • 将两个的有序数列合并成一个有序数列，我们称之为"归并"。归并排序(Merge Sort)就是利用归并思想对数列进行排序。
• 排序 - 桶排序(Bucket Sort)
  • 桶排序(Bucket Sort)的原理很简单，将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）
• 排序 - 基数排序(Radix Sort)
  • 它的基本思想是: 将整数按位数切割成不同的数字，然后按每个位数分别比较。具体做法是: 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列

---

# 算法思想详解

A. 算法思想 详解：紧接着我们通过理解算法背后常用的算法思想，进行归纳总结，并通过leetcode练习来辅助理解和提升。

• 算法思想 - 分治算法
  • 分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解
• 算法思想 - 动态规划算法
  • 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解
• 算法思想 - 贪心算法
  • 本文主要介绍算法中贪心算法的思想: 保证每次操作都是局部最优的，并且最后得到的结果是全局最优的
• 算法思想 - 二分法
  • 本文主要介绍算法思想中分治算法重要的二分法，比如二分查找；二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
• 算法思想 - 搜索算法
  • 本文主要介绍算法中搜索算法的思想，主要包含BFS，DFS
• 算法思想 - 回溯算法
  • Backtracking(回溯)属于 DFS, 本文主要介绍算法中Backtracking算法的思想。回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法

---

# 领域算法详解

A. 领域算法 梳理知识点：在了解基础算法之后，我们还要学习和了解在不同专业领域有哪些特有的算法。这里不一定要求复杂度，而是要有知识面以及解决问题的思路。

• 一些领域算法 - Overview

B. 领域算法之 安全算法：主要包括摘要算法和加密算法两大类。

• 安全算法 - 摘要算法
  • 消息摘要算法的主要特征是加密过程不需要密钥，并且经过加密的数据无法被解密，目前可以解密逆向的只有CRC32算法，只有输入相同的明文数据经过相同的消息摘要算法才能得到相同的密文。消息摘要算法不存在密钥的管理与分发问题，适合于分布式网络上使用。
• 安全算法 - 加密算法
  • 数据加密的基本过程就是对原来为明文的文件或数据按某种算法进行处理，使其成为不可读的一段代码为“密文”，使其只能在输入相应的密钥之后才能显示出原容，通过这样的途径来达到保护数据不被非法人窃取、阅读的目的。 该过程的逆过程为解密，即将该编码信息转化为其原来数据的过程
• 安全算法 - 国密算法
  • 国密即国家密码局认定的国产密码算法。主要有SM1，SM2，SM3，SM4，SM7, SM9。

C. 领域算法之 字符串匹配算法：字符串匹配(String Matchiing)也称字符串搜索(String Searching)是字符串算法中重要的一种，是指从一个大字符串或文本中找到模式串出现的位置。

• 朴素的字符串匹配算法（Naive String Matching Algorithm)
  • 朴素的字符串匹配算法又称为暴力匹配算法（Brute Force Algorithm），最为简单的字符串匹配算法
• Knuth-Morris-Pratt 字符串匹配算法（即 KMP 算法）
  • Knuth-Morris-Pratt算法（简称KMP）是最常用的字符串匹配算法之一
• Boyer-Moore 字符串匹配算法
  • 各种文本编辑器的"查找"功能（Ctrl+F），大多采用Boyer-Moore算法，效率非常高
• 字符串匹配 - 文本预处理：后缀树（Suffix Tree）
  • 上述字符串匹配算法(朴素的字符串匹配算法, KMP 算法, Boyer-Moore算法)均是通过对模式（Pattern）字符串进行预处理的方式来加快搜索速度。对 Pattern 进行预处理的最优复杂度为 O(m)，其中 m 为 Pattern 字符串的长度。那么，有没有对文本（Text）进行预处理的算法呢？本文即将介绍一种对 Text 进行预处理的字符串匹配算法：后缀树（Suffix Tree）

D. 领域算法之 大数据处理：这里其实想让大家理解的是大数据处理的常用思路，而不是算法本身。

• 大数据处理 - Overview
  • 本文主要介绍大数据处理的一些思路
• 大数据处理 - 分治/hash/排序
  • 就是先映射，而后统计，最后排序:
  • 分而治之/hash映射: 针对数据太大，内存受限，只能是: 把大文件化成(取模映射)小文件，即16字方针: 大而化小，各个击破，缩小规模，逐个解决
  • hash_map统计: 当大文件转化了小文件，那么我们便可以采用常规的hash_map(ip，value)来进行频率统计。
  • 堆/快速排序: 统计完了之后，便进行排序(可采取堆排序)，得到次数最多的IP。
• 大数据处理 - Bitmap & Bloom Filter
  • 布隆过滤器有着广泛的应用，对于大量数据的“存不存在”的问题在空间上有明显优势，但是在判断存不存在是有一定的错误率(false positive)，也就是说，有可能把不属于这个集合的元素误认为属于这个集合(False Positive)，但不会把属于这个集合的元素误认为不属于这个集合(False Negative)
• 大数据处理 - 双层桶划分
  • 其实本质上还是分而治之的思想，重在“分”的技巧上！适用范围: 第k大，中位数，不重复或重复的数字；基本原理及要点: 因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。
• 大数据处理 - Trie树/数据库/倒排索引
  • 适用范围: 数据量大，重复多，但是数据种类小可以放入内存；基本原理及要点: 实现方式，节点孩子的表示方式；扩展: 压缩实现
• 大数据处理 - 外排序
  • 适用范围: 大数据的排序，去重；基本原理及要点: 外排序的归并方法，置换选择败者树原理，最优归并树
• 大数据处理 - Map & Reduce
  • MapReduce是一种计算模型，简单的说就是将大批量的工作(数据)分解(MAP)执行，然后再将结果合并成最终结果(REDUCE)。这样做的好处是可以在任务被分解后，可以通过大量机器进行并行计算，减少整个操作的时间。但如果你要我再通俗点介绍，那么，说白了，Mapreduce的原理就是一个归并排序

E. 领域算法之 分布式算法：接着向大家介绍分布式算法，包括一致性Hash算法，经典的Paxos算法，Raft算法，ZAB算法等；顺便也介绍了经典用于全局ID生成的Snowflake算法。

• 分布式算法 - Overview
  • 本文总结下常见的分布式算法
• 分布式算法 - 一致性Hash算法
  • 一致性Hash算法是个经典算法，Hash环的引入是为解决单调性(Monotonicity)的问题；虚拟节点的引入是为了解决平衡性(Balance)问题
• 分布式算法 - Paxos算法
  • Paxos算法是Lamport宗师提出的一种基于消息传递的分布式一致性算法，使其获得2013年图灵奖。自Paxos问世以来就持续垄断了分布式一致性算法，Paxos这个名词几乎等同于分布式一致性, 很多分布式一致性算法都由Paxos演变而来
• 分布式算法 - Raft算法
  • Paxos是出了名的难懂，而Raft正是为了探索一种更易于理解的一致性算法而产生的。它的首要设计目的就是易于理解，所以在选主的冲突处理等方式上它都选择了非常简单明了的解决方案
• 分布式算法 - ZAB算法
  • ZAB 协议全称：Zookeeper Atomic Broadcast（Zookeeper 原子广播协议）, 它应该是所有一致性协议中生产环境中应用最多的了。为什么呢？因为他是为 Zookeeper 设计的分布式一致性协议！
• 分布式算法 - Snowflake算法
  • Snowflake，雪花算法是由Twitter开源的分布式ID生成算法，以划分命名空间的方式将 64-bit位分割成多个部分，每个部分代表不同的含义。这种就是将64位划分为不同的段，每段代表不同的涵义，基本就是时间戳、机器ID和序列数。为什么如此重要？因为它提供了一种ID生成及生成的思路，当然这种方案就是需要考虑时钟回拨的问题以及做一些 buffer的缓冲设计提高性能。

F. 领域算法之 其它算法汇总：最后概要性的了解常见的其它算法：负载均衡算法，推荐算法，数据挖掘或机器学习算法。因为有其专业性，一般总体上了解就够了。

• 负载均衡算法 - 汇总
  • 本文主要介绍常用的负载均衡算法和Nginx中支持的负载均衡算法：轮询法(Round Robin)，加权轮询法(Weight Round Robin)，平滑加权轮询法(Smooth Weight Round Robin)，随机法(Random)，加权随机法(Weight Random)，源地址哈希法(Hash)，最小连接数法(Least Connections)
• 数据挖掘 - 10大算法汇总
  • 国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 2006年12月评选出了数据挖掘领域的十大经典算法: C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART

---