关于c:数据结构与算法初级

复杂度解说

算法效率

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

工夫复杂度

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

工夫复杂度的计算方法（大 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)
• 稳定性：稳固
• 此办法须要借助另外一个长期数组。
• 将数组分为两局部，如果两边都是有序的，那么别离从两局部的起始地位开始比拟，将小的值尾插在新数组中，直到有一部分遍历完为止，再将另一部分剩下的尾插到新数组前面。
• 而后再将排序好的新数组赋值给原数组。
• 如果离开的两局部不是有序的，则别离再次差分，直到最初两局部都有序，执行上述步骤，将其排序。
• 因为判断是否有序比拟麻烦，所以个别不判断是否有序，而是将两局部都当做无序，进而始终拆分，直到最初两局部都只剩下一个数时进行尾插到新数组，而后再赋值给原数组，这样因为都是排序失去的，所以即便是无序的也会变成有序，所以能够不判断是否有序。
• 留神要开释长期数组。
  

排序算法的稳定性判断

• 数组中雷同的值，排序完后绝对程序不变的就是稳固，反之则为不稳固。