README.md

数据结构

概念

c/c++实现

经典教程

数据结构汇总

算法时间复杂度的计算

逻辑结构:

具体问题抽象出来的数学模型

1. 集合(数据元素之间无关系)
2. 线性结构(1:1)
3. 树形结构(1:n)
4. 图状结构(n:n)

存储结构/物理结构：

数据在计算机内存中的存储(顺序结构 链式结构 索引结构 哈希结构)

抽象数据类型(ADT):

ADT=（D，S, P） D是数据对象 S是D上的关系集 P是对D的基本操作集
类似面向对象程序中的类

数据类型

原子类型：整形 浮点型 结构类型：可拆解的类型

算法和其5个特性：

算法是描述计算机解决给定问题的操作过程，即为决解某一特定问题而由若干条指令组成的有穷序列

有穷行 确定性 可行行 输入 输出

线性表

线性表是n(n>=0)个相同类型数据元素构成的有限序列，其中n为线性表的长度

1. 顺序存储(顺序表):数组(连续的存储单元)
2. 链式存储:每个元素（data + next指针，不连续的存储单元，链表不是随机存取结构，只能顺序存取

数组

特点:

• 连续的内存空间和相同类型的数据,基于这2个特点,实现随机访问 O(1),CPU预读对缓存友好
• 插入和删除数据,为了保证连续性,需要做数据搬移,O(n)

链表

特点:零散的内存块

不管链表是不是空，head 指针都会一直指向这个哨兵结点,可以简化编程难度。我们也把这种有哨兵结点的链表叫带头链表

1. 单向链表：
2. 循环链表:表中的尾节点指向头节点，形成一个环，操作和线性链表基本一致，没有NULL指针，故终止条件为，是否等于某一个指定的指针
3. 双向链表:双向链表是在单链表的每个结点里再增加一个指向其直接前驱的指针域prior。这样就形成了链表中有两个方向不同的链

跳表

• 为链表添加多级索引的结构,就是跳表,利用了二分查找思想
• 解决链表查找需要遍历全部链表的缺点

散列表

• 散列函数
• 散列冲突:开放寻址法 链表法
• 装载因子: 填入表中的元素个数/散列表的长度

位图(BitMap)

• 特殊的散列表
• 位的映射(数组下表为key,值为bit,1为存在,0为不存在)
• 应用:
  1. 快速排序
  2. 快速去重
  3. 快速查询

布隆过滤器(Bloom Filter)

• 位图的拓展
• 当一个元素被加入集合中时,通过k各散列函数将这个元素映射成一个位数组中的k个点,并将这k个点全部置为1
• 存在误判(不存在一定不存在,存在不一定存在):和哈希函数的个数,位图的大小有关

栈和队列

栈(LIFO)

限制在表的一端进行插入和删除运算的特殊线性表

栈的存储

顺序栈:利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素 链栈: 采用链表作为存储结构实现的栈。为便于操作，采用带头结点的单链表实现栈,因为栈的插入和删除操作仅限制在表头位置进行，所以链表的表头指针就作为栈顶指针

队列(FIFO)

先进先出的线性表，它只允许在表的一端进行插入，而在另一端删除元素

顺序队列： 链式队列: 循环队列:

广义表

是由零个或多个原子或子表组成的优先序列，是线性表的推广

广义表中的数据元素可以具有不同的结构，因此，难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可用一个节点表示。由于广义表中有两种数据元素，因此需要有两种结构的节点——一种是表结点，一种是原子结点

树

Tree:是n（你>=0）个节点的有限集T

结点：表示树中的元素，包括数据项及若干指向其子树的分支

结点的度：结点拥有的子树树

树的度：一棵树中最大的结点度数

深度：从上到下度量,经过的边数

高度：从下到上,经过的最大边数

叶子结点：度为0的结点

树的性质:树中的结点数等于所有结点的度数加1

二叉树

满二叉树：特殊的完全二叉树,特点——每一层上的结点数都是最大结点数

完全二叉树：最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大,适合用数组存储节省空间,先序遍历

遍历二叉树（相对根节点）

1. 先序遍历：根节点->左子树->右子树
2. 中序遍历:左子树->根节点->右子数
3. 后序遍历:左子树->右子数->根节点
4. 层次遍历:从上到下，从左到右

二叉查找树

二叉查找树要求，在树中的任意一个节点，左子树值<节点值<右子树值

特性

中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是O(n)

支持重复数据的二叉查找树

1. 节点存对象,不存值
2. 值相同,放右子树,当要查找数据的时候，遇到值相同的节点，我们并不停止查找操作,只到叶子节点

为什么有散列表还需要二叉查找树

1. 散列表数据无序存储,无法输出有序数据
2. 散列表扩容耗时,有散列冲突,不稳定
3. 散列表构造复杂(散列函数的设计,扩容,缩容,散列冲突)

红黑树

一种近视平衡的二叉查找树,是为解决二叉查找树频繁对数据更新过程中,复杂度退化的问题,性能稳定,O(logn)

为什么工程上喜欢用红黑树而不是AVL树

AVL树每次插入,删除,更新都要调整树,比较复杂,耗时,而红黑树是近似平衡树,不需要每次调整

特点

• 根节点是黑色
• 每个叶子节点都是黑色的空节点(NIL)
• 任何相邻的节点都不能同时为红色
• 每个节点,到其可达的叶子节点的所有路劲,都包含相同的黑色节点

堆

• 完全二叉树
• 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点
• 大顶堆和小顶堆
• 插入一个数据的时候，我们把新插入的数据放到数组的最后，然后从从下往上堆化；删除堆顶数据的时候，我们把数组中的最后一个元素放到堆顶，然后从上往下堆化。这两个操作时间复杂度都是O(logn)

为什么堆排序没有快速排序快

• 堆排序数据访问的方式没有快速排序友好,跳着访问,对cpu不友好
• 对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序

堆的应用

1. 优先级队列(如:高性能定时器)
2. 求TopK问题(静态数据:维护一个K的小顶堆,依次比较[O(nlogK)],动态数据类似)
3. 求动态数据中位数(维护一个大顶堆,一个小顶堆,而且小顶堆中的元素都大于大顶堆中的元素,通过动态调整堆大小来满足数据平衡)

Trie树 也叫“字典树

1. 就是利用字符串之间的公共前缀，将重复的前缀合并在一起
2. 主要操作:构造一个Trie树 在Trie树中查找一个字符串
3. Trie树不如红黑树和散列表适合精确匹配,它更加适合前缀匹配
4. 比较耗内存
5. 时间复杂度是 O(k)，k 表示要匹配的字符串的长度
6. 应用场景:字符串的字符集不能太大，前缀重合比较多

图

在图形结构中，结点之间关系可以是任意的，图中任意两个数据元素之间都可能相关

1. 有向图
2. 无向图

图的存储结构

邻接矩阵

邻接矩阵是表示顶点之间相邻关系的矩阵

1. 优点：容易实现图的操作，如判断顶点间是否有边（弧）
2. 缺点: 对稀疏图浪费空间

邻接表

一种顺序分配与链式分配相结合的存储方法。它包括两部分：一部分是单链表，用来存放边的信息；另一部分是数组，主要用来存放顶点本身的数据信息

1. 优点:空间利用率高，容易找顶点的邻接点
2. 缺点:判断2顶点间是否有弧，需搜索2结点对应的单链表

逆领接表

为了解决领接表的缺点,查找入度需要遍历所有的顶点对应的边

十字链表

十字链表是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中，每条弧和每个顶点分别对应着一个结点

邻接多重表

邻接多重表是无向图的另一种链式存储结构。邻接多重表和十字链表一样，每条边和每个顶点分别对应着一个结点

图的遍历

图的暴力搜索

时间复杂度都是 O(E)，空间复杂度是 O(V)

1. 深度优先搜索（DFS）

   • 回溯思想
   • 借助栈来实现

2. 广度优先搜索（WFS）

   • 地毯式层层推进
   • 借助队列来实现

B+ tree vs LSM tree

比较