C++服务端面试准备（3）数据结构与算法相关

声明：本文内容纯属博主自己查找和归纳的个人所需的知识点，仅作参考，如有错误，博主强烈希望您指出。如果您是某个知识点的原创博主，如有需要，可联系本人加上链接。本文内容会根据博主所需进行更新，希望大家多多关照。

你所知道的数据结构

数组 (Array)、栈 (Stack)、队列 (Queue)、链表 (Linked List)

树： 堆(heap)、（B-树、B+树、）二叉查找树、AVL树、红黑树、二叉树、哈夫曼树

图 (Graph)

散列表 (Hash)

• 数组：有序的元素序列，固定大小
• 栈：是一种运算受限的线性表，先进后出
• 队列：一种操作受限制的线性表，先进先出
• 链表：非连续、非顺序的存储结构，逻辑顺序是通过链表中的指针实现的

1.头插法：新插入的数据的指针指向最后的数据

2.尾插法：最后的数据的指针指向新插入的数据

• 堆：堆通常是一个可以被看做一棵完全二叉树的数组对象
• B-树：B树，是一种平衡的多路搜索树（这里的平衡指根节点到叶子节点的高度一样）
• B+树：B+树是应文件系统所需而出的一种B-树的变型树

（B-树和B+树比较复杂，暂时不作拓展，多用在文件和数据库种，不说出来应该也不会问到）

• 二叉查找树：每个节点的左子树比该节点小，右子树比该节点大，子树同样是二叉查找树
• 平衡二叉树：基于二叉查找树，又叫AVL树（这里的平衡指左右子树深度差的绝对值不超过1）
• 红黑树：一种特化的AVL树
• 二叉树：二叉树是每个结点最多有两个子树的树结构

1.完全二叉树：若设二叉树的深度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。

2.满二叉树：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树

3.二叉树遍历：前序中序后序分别是根左右、左根右、左右根

• 哈夫曼树：一种带权路径长度最短的二叉树，也称为最优二叉树
• 图：一些顶点的集合，节点之间的关系可以是任意的
• 散列表：又叫哈希表（Hash Table），是能够通过给定的关键字的值直接访问到具体对应的值的一个数据结构

树与二叉树的区别

1. 二叉树每个节点最多有2个子节点，树则无限制。
2. 二叉树中节点的子树分为左子树和右子树，即使某节点只有一棵子树，也要指明该子树是左子树还是右子树，即二叉树是有序的。
3. 树决不能为空，它至少有一个节点，而一棵二叉树可以是空的。

平衡二叉树的性质

平衡二叉树又叫AVL树，它的左子树上的所有节点的值都比根节点的值小，而右子树上的所有节点的值都比根节点的值大，且左子树与右子树的高度差最大为1

至于旋转的方法博主是参考这篇文章学习的： 今天终于懂了AVL树怎样旋转(带图理解) ，但是具体代码实现还需要进一步研究

红黑树的性质

红黑树基于AVL树，但没有追求左子树与右子树的高度差最大为1这个性质，而追求以下性质：

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

• 这些性质构造出红黑树的关键性质：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长
• 红黑树在任何不平衡的情况只需要最多三次旋转就能达到平衡，插入和删除的次数比AVL树少，查询效率稍逊于AVL树
• 一棵有n个结点的红黑树的高度至多为为2lg(n+1)
• STL容器中map、multimap、set、multiset都用到红黑树

至于变色和旋转的方法博主是参考这篇文章学习的： 红黑树的旋转与变色 ，但是具体代码实现还需要进一步研究

哈夫曼树

• 哈夫曼树通常用作通信的二进制编码
• 哈夫曼树的构建：

其中小于等于和的元素放左边，大于和的放右边，例如图中(d)B和7的和为14，D为13，D就放左边

• 哈夫曼树的编码生成：

树中从根到每个叶子节点都有一条路径，对路径上的各分支约定指向左子树的分支表示”0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为各个叶子节点对应的字符编码，即是哈夫曼编码。

就拿上图例子来说：A，B，C，D对应的哈夫曼编码分别为：111，10，110，0

图的性质

• 图通常分为有向图和无向图，而其表示基本的表示方式分为邻接矩阵、邻接表，还有另外的十字链表
• 邻接矩阵就是把2个点的关系用一个二维表表示出来
• 邻接表每个节点存放数据、权重和下一个邻接点，每个邻接表都表示出此顶点的所有邻接点
• 十字链表就是把有向图的邻接表和逆邻接表整合在一起
• 有向图分出度和入度，无向图的度就是邻边的数目

图的深度和广度优先遍历

• 深度优先遍历

又称为深度优先搜索，简称DFS。其实，就像是一棵树的前序遍历。它从图中某个结点开始访问，然后访问下一个邻接点，一直访问到最后没有未被访问到的邻接点，如果图中还有顶点未被访问，则回溯此路径，另选第一个点的未曾被访问的邻接点作起始点，重复上述过程，直至图中的所有顶点都被访问到为止。

• 广度优先遍历

又称为广度优先搜索，简称BFS。图的广度优先遍历就类似于树的层序遍历，顶点为第一层，与顶点连通的为第二层，以此类推逐层访问

• 两种遍历在时间复杂度上是一样的，不同之处仅仅在于对顶点的访问顺序不同

常用的哈希函数

• 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。
• 数字分析法：通过对数据的分析，发现数据中冲突较少的部分，并构造散列地址。
• 平方取中法：当无法确定关键字里哪几位的分布相对比较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为散列地址。这是因为：计算平方之后的中间几位和关键字中的每一位都相关，所以不同的关键字会以较高的概率产生不同的散列地址。
• 取随机数法：使用一个随机函数，取关键字的随机值作为散列地址，这种方式通常用于关键字长度不同的场合。
• 除留取余法：取关键字被某个不大于散列表的表长 n 的数 m 除后所得的余数 p 为散列地址。这种方式也可以在用过其他方法后再使用。该函数对 m 的选择很重要，一般取素数或者直接用 n

解决哈希表冲突的常用方法

• 开放地址法（也叫开放寻址法）：对计算出来的地址进行一个探测再哈希，比如往后移动一个地址，如果没人占用，就用这个地址。
• 再哈希法：在产生冲突之后，使用关键字的其他部分继续计算地址，如果还有冲突，则继续使用其他部分再计算地址。这种方式的缺点是时间增加了。
• 链地址法：链地址法其实就是对Key通过哈希之后落在同一个地址上的值，做一个链表。其实在很多高级语言的实现当中，也使用这种方式处理冲突。
• 建立一个公共溢出区：这种方式是建立一个公共溢出区，当地址存在冲突时，把新的地址放在公共溢出区里。

九种排序

• 直接插入排序：从第二个数开始，前面相邻的数进行比较，把大的数换到后面，如此循环
• 折半插入排序：在前面的有序区内不断使用二分法，即比本身小则low=mid+1，比本身大则high=mid-1，当low<=high时表示找到第一个比本身大的数，然后交换
• 希尔排序：实质为分组插入法，不断缩小步长进行插入排序
• 直接选择排序：从后面的数找出最小的数与本身交换
• 堆排序：选择排序的一种，近似完全二叉树，下标为n/2-1的元素才有子树，构造大顶堆，即结点都比子树大，最后根节点就为最大的数，将最大的数和最后的数互换，继续将剩下的数构造大顶堆，如此循环
• 冒泡排序：交换排序的一种，每次都从第一个数开始，相邻的数进行比较，将最大的数后移，不断缩小比较次数
• 快速排序：交换排序的一种，先拿第一个数作为分界点，把数组排列成前半部分的数都比分界点小，后半部分的数都比分界点大，然后这2半部分继续同样的操作，递归完成
• 归并排序：分组归并，分组从最小的组开始进行过比较和交换，比如10个数，比较的区间为[0,1] [0,2] [3,4] [0,4] [5,6] [5,7] [8,9] [5,9] [0,9]
• 桶排序：将元素按大小分到固定长度的区间也就是桶中排序，再拿出来放回数组

九种排序的具体实现代码请看： 九种排序具体实现代码

稳定的排序算法有冒泡排序、插入排序和归并排序，而选择排序、希尔排序、快速排序和堆排序都是不稳定的。

各种排序的时间复杂度和空间复杂度为下图所示：

注：Ο(1)＜Ο(logn)＜Ο(n)＜Ο(nlogn)＜Ο(n2)＜Ο(n3)＜…＜Ο(2^n)和Ο(n!)

常用算法

• 基础：枚举，递归，分治，模拟，贪心，动态规划，剪枝，回溯
• 排序：冒泡、快速、直接选择和堆、直接插入和希尔排序、归并排序
• 查找：顺序查找、二分查找、索引查找、二叉排序树、哈希查找
• 图算法：深度优先遍历与广度优先遍历， 最短路径，最小生成树，拓扑排序

博主掌握的数据结构与算法在上面已归纳完毕，这里列出的常用算法还有些博主没怎么研究，还有哪些在服务端开发中常用和重要的算法希望有会热心网友提醒！