数据结构与算法初级 - HelloWorld开发者社区

复杂度讲解

算法效率

算法效率分为两种：时间效率（时间复杂度）和空间效率（空间复杂度）
它们分别衡量一个算法的运行时间和所占的空间大小。

时间复杂度

时间复杂度计算的是一个函数中算法基本操作的执行次数。
时间复杂度针对的是一整个函数。

时间复杂度的计算方法（大O渐进表示法）

大O渐进表示法是一种估算：只取表达式中对结果影响最大的一项。
推导大O阶方法：
- 用数字1取代算数中的所有常数。
- 在修改后的算数中，只保留最高项。
- 如果最高阶存在且不是1，则去除这个项的常数，得到的结果就是大O阶。
例如：
- 下列的时间复杂度算数为：F(N) = 2*N + 10
- 所以大O阶表达式为：O(N)

void Fun1(int N)
{
    int count = 0;
    for (int i = 0; i < 2 * N; i++)
    {
        ++count;
    }
    int M = 10;
    while (M--)
    {
        ++count;
    }
    printf("%d", count);
}

注意：当函数中未知数有多个时
例如：
- 时间复杂度表达式为：F(N) = M + N + 10 时，大O阶为 O(M+N) 或者 O(N)
- 时间复杂度表达式为：F(N) = 1000 时，大O阶为 O(1) （第一步将所有常数用1代替）
- O(1) 表示的是算法中基本操作执行常数次，而不是真的只执行一次。
- 时间复杂度表达式为：F(N) = M*M + N + 10 时，大O阶为 O(M^2)
时间复杂度中：为了方便一般把log2N（以2为底数）写作logN （log3N等就不会缩写了）
所谓的线性时间复杂度就是指O(N)。

空间复杂度

空间复杂度是对一个算法在运算过程中，临时占用的内存空间大小。
空间复杂度不是计算程序占用了多少个字节，而是计算临时变量的个数。
空间复杂度的计算方法也采用大O渐进表示法。
O(1) 代表常数个变量。
递归算法的空间复杂度就是递归的深度乘以每个算法的空间复杂度（每递归一次，就会在栈中创建一个临时的函数）
注意：
- 时间是累计的，空间是可以复用的
- 创建局部变量后，在程序出大括号后，就会销毁。

顺序表和链表

线性表

线性表是 n 个具有相同特性的数据元素的有限序列
常见的线性表：顺序表、链表、栈、队列等。
线性表在逻辑上是线性结构，但实际物理存储上通常是以数组和链式结构的形式存储的。

顺序表和链表

顺序表：
- 顺序表本质就是数组，能够动态增长的，并且里面的数据是连续存储的（从左到右）
- 顺序表的逻辑结构和物理结构是一致的，都是连续的。
链表：
- 链表的逻辑结构和物理结构不是一致的
- 物理上内存空间是按需分配，所以不存在空间浪费，但是分配的空间是随机的。
- 单链表分为两部分，前一部分用来存储数据，后一部分用来存储指针，指向下一个节点
- 最后一个链表的指针指向NULL。

顺序表和链表的比较

顺序表的缺点：
- 顺序表动态增容有性能消耗，增容一般是按两倍增加，可能有一定程度的空间浪费。
- 在顺序表中插入数据时，需要挪动数据，效率较低（O(N)）
顺序表优点：
- 可以按下标进行随机访问。
- 顺序表的CUP高速缓存命中率比较高。
- CPU读取数据时，因为CPU的速度远高于内存，所以一般内存中的数据会提前被加载到高速缓存（Cache）中，然后CPU再从Cache中读取数据。
- 但是提前加载数据是按顺序缓存的，所以顺序表被提前加载时，命中率较高，因为它们的地址是连续的。而链表被提前加载时，因为地址不连续，所以命中率较低。（所谓的命中率就是被提前加载的数据就是CPU刚好需要的数据）
链表的缺点：
- 不支持下标的随机访问。
- 链表的CPU高速缓存命中率较低，而且可能会造成缓存污染。
链表的优点：
- 按需申请内存，需要存一个数据，就申请一个内存，不存在空间浪费。
- 在链表中插入删除数据时，不需要挪动数据，效率高。

链表分类

链表分为：
- 单链表带头循环、单链表带头不循环、单链表不带头循环、单链表不带头不循环。
- 双链表带头循环、双链表带头不循环、双链表不带头循环、双链表不带头不循环。
实际中主要使用两种链表
- 无头单向链表：结构简单，一般不会单独用来存储数据，实际中更多的是作为其他数据结构的子结构。
- 带头双向链表：结构最复杂，一般单独存储数据。
所谓的带头和不带头：
- 带头链表：是链表在首节点之前设置的一个头节点，但是它不存储有效数据，只是它的指针指向首节点。
- 头结点的作用：是为了方便对链表的操作。保证链表中每个元素都有一个前驱。

单链表定义方法

struct SListNode
{
    int date;         //前一部分存储数据
    struct SListNode* next;  //后一部分存储下一个节点的指针
}

双链表定义方法

数据结构与算法初级

struct ListDouble {
    struct ListDouble* prev;  //存放上一个结点的地址
    struct ListDouble* next;  //存放下一个结点的地址
    int val;
};

栈和队列

栈

一种特殊结构的顺序表，只允许在一端进行插入和删除元素，进行数据插入和删除的一端称为栈顶，另一端称为栈底。
栈中数据遵循后进先出原则。
队列
只允许在一端插入数据，在另一端删除数据。
队列遵循先进先出原则。

二叉树

树的概念

树是一种非线性的数据结构，它由n个有限节点组成一个具有层次关系的集合，形状看着像一个倒挂的树。
有一个特殊节点，称为根节点，就是第一层的节点，它没有前驱节点。
树是递归定义的。
节点的度：一个节点含有的子节点个数。
叶节点或终端节点：度为0的节点。
父节点：一个节点含有子结点，那么这个结点就是根结点的父结点。
兄弟结点：相同父结点的节点。
树的度：根结点的度就是树的度。
空树的层数为0。
森林：多个不相交的树组成的集合。

二叉树的概念

一个节点只能有两个子节点，但是这个两个子节点不一定都存在。
例如：空节点是二叉树，一个节点也是二叉树。
对于任何一个二叉树，叶子节点（度为0的节点）永远比度为2的节点多一个。

满二叉树

它是一个二叉树，并且每层节点数都达到最大值
满二叉树的层数为k，则节点总数为（2^k）-1。
每一层都有 2^(n-1) 个节点（也是每层最大节点数）（n是层数）

完全二叉树

完全二叉树是效率很高的数据结构。
完全二叉树的前k-1层都是满的，最后一层可以不是满的。
但是最后一层必须是从左到右依次排列的。

堆

堆在逻辑上是完全二叉树结构。
堆只存在两种类型：大根堆和小根堆。
大根堆：父节点的值大于子节点的值。
小根堆：父节点的值小于等于子节点的值。

堆的下标规律

设父节点下标为 x，左边子节点下标为 y，右边节点下标为 z。
y = x*2 + 1；
z = x*2 + 2；
x = （x - 1）/ 2 或者（y-1）/ 2；

二叉树的存储

二叉树一般用链式结构存储，即用链表来表示一个二叉树。
通常方法是：链表中每个节点由三个部分组成，数据域和左右指针。
左右指针分别用来指向该节点的左孩子和右孩子，数据域用来存储数据。
目前使用的都是二叉链表。

二叉树链式存储的遍历方法

深度优先遍历：
- 前序遍历：先访问根，然后在访问左子树，最后访问右子树。
- 中序遍历：先访问左子树，然后访问根，最后访问右子树。
- 后序遍历：先访问左子树，然后访问右子树，最后访问根。
广度优先遍历：
- 层序遍历：从左到右一层一层的访问。

排序算法

常见排序算法

插入排序：直接插入排序（适用于小量数据）、希尔排序（可以将大的数快速地移动都后面，适用于大量数据）
选择排序：选择排序、堆排序
交换排序：冒泡排序、快速排序（挖坑法、前后指针法）
归并排序：归并排序

快速排序

时间复杂度 O(N * logN)
空间复杂度O(logN)
稳定性：不稳定

如何取关键数key

先取数组的第一个数、最后一个数和中间位置的数，然后取这三个数中不是最大也不是最小的那个数作为key。
这种方法可以避免key直接选到最大值或者最小值。

左右指针法快排

数据结构与算法初级

一前一后两个指针，选择一个关键数key（一般是开头位或者末位）
如果选择开头位为关键数key，则让end向后先走，寻找比key小的数，找到小的数后停下。
然后pre向前走，寻找比key大的数，找到后停止。
然后交换pre的值和end的值，交换完后，end继续向后移动。
一直循环，直到pre和end相遇为止，相遇时的值一定是比key小的，所以交换key和pre的值
这样，key的数就会被移动到整个数组的中间值位置，它左边的都比它小，右边的都比它大
最后使用递归。

挖坑法快排

数据结构与算法初级

另外定义一个变量sum，用来保存第一个pre，pre的位置则空出来了。
然后end先向前移动，寻找比sum小的数，找到后将end与pre交换，现在end的位置为空。
然后pre向前移动，寻找比sum大的数，找到将pre与end交换，现在pre的位置为空。
然后再是end向前移动………………
这样循环直到pre和end相遇为止，相遇时的位置为空，再将sum的值放到相遇的位置上。
这样这个数的左边都是比它小的数，右边都是比它大的数。
最后使用递归即可。

前后指针法快排

数据结构与算法初级

起始位置，pre在第一位，end在第二位。
然后end向后移动，寻找比key小的值，找到后，pre++，然后交换pre和end的值。
然后继续end向后移动，直到end访问完为止
最后在交换pre和key的值
这样key这个数的左边都是比它小的数，右边都是比它大的数。
最后递归即可。

快排的小区间优化

当数据量很大时，在最后几层递归时，会出现大量递归（出现大量递归时可能会栈溢出），但是每个递归处理的数据较小。
所以为了避免最后几层的递归，在数据量较小时，直接使用插入排序
这样大数据处理的最后几层递归，则变为插入排序，可以减少大量递归，降低处理时间。

归并排序

时间复杂度O(N * logN)
空间复杂度O(N)
稳定性：稳定
此方法需要借助另外一个临时数组。
将数组分为两部分，如果两边都是有序的，那么分别从两部分的起始位置开始比较，将小的值尾插在新数组中，直到有一部分遍历完为止，再将另一部分剩下的尾插到新数组后面。
然后再将排序好的新数组赋值给原数组。
如果分开的两部分不是有序的，则分别再次差分，直到最后两部分都有序，执行上述步骤，将其排序。
因为判断是否有序比较麻烦，所以一般不判断是否有序，而是将两部分都当做无序，进而一直拆分，直到最后两部分都只剩下一个数时进行尾插到新数组，然后再赋值给原数组，这样因为都是排序得到的，所以即使是无序的也会变成有序，所以可以不判断是否有序。
注意要释放临时数组。