数据结构与算法
绪论
数据结构:
- 在链接存储结构中,要求每个结点占用一片连续的存储区域。
- 数据结构由逻辑结构、存储结构和基本操作构成。
- 可以用数据元素、数据关系和基本操作定义一个完整的抽象数据类型。
- 顺序存储结构中的数据元素之间的逻辑关系是由存储位置表示的,链接存储结构中的数据元素之间的逻辑关系是由指针表示的。
算法设计与分析:
- 算法指的是对特定问题求解步骤的一种描述,是指令的有限序列。
- 算法所必须具备的特性:有穷性、确定性、可行性、输入、输出。
- 算法的时间复杂度属于一种事前分析估算的方法。
线性表
顺序表
顺序表的插入:将插入位置后的元素依次向后移动,然后将新元素插入到插入位置。
顺序表的删除:将删除位置后的元素依次向前移动,然后将最后一个元素删除。
链表
单链表:每个节点包含数据域和指针域,指针域指向下一个节点。
双向链表:每个节点包含数据域、前驱指针域和后继指针域。
循环链表:尾节点的指针域指向头节点。
栈
栈是一种特殊的线性表,只能在表尾进行插入和删除操作。
队列
队列是一种特殊的线性表,只能在表头进行删除操作,在表尾进行插入操作。
字符串
字符串(串)是由零个或多个字符组成的有限序列。
字符串的模式匹配:
朴素的模式匹配算法(BF 模式匹配算法):模式 P 与文本 T 从左到右逐个字符比较,若匹配失败,则模式 P 向右移动一位,继续比较。
int naive_match(const char *text, const char *pattern) {
int i = 0, j = 0;
while (text[i] && pattern[j]) { // 遇到字符串结尾 '\0' 时停止
if (text[i] == pattern[j]) {
i++;
j++;
} else {
i = i - j + 1;
j = 0;
}
}
if (pattern[j] == '\0') {
return i - j;
}
return -1;
}
KMP 模式匹配算法:在模式 P 与文本 T 从左到右逐个字符比较的过程中,当遇到不匹配的字符时,根据模式 P 的前缀与后缀的最长公共子串,将模式 P 向右移动一定的位数,以减少比较次数。
void get_next(const char *pattern, int *next) {
int i = 0, j = -1;
next[0] = -1;
while (pattern[i]) {
if (j == -1 || pattern[i] == pattern[j]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
}
int kmp_match(const char *text, const char *pattern) {
int i = 0, j = 0;
int next[strlen(pattern)];
get_next(pattern, next);
while (text[i] && pattern[j]) {
if (j == -1 || text[i] == pattern[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (pattern[j] == '\0') {
return i - j;
}
return -1;
}
树
- 节点:树中的每个元素称为节点。
- 根节点:树中的一个特殊节点,没有父节点。
- 子节点:树中的一个节点的子树的根节点称为该节点的子节点。
- 叶子节点:没有子节点的节点称为叶子节点。
- 分支节点:有子节点的节点称为分支节点。
- 节点的度:一个节点的子节点的个数称为该节点的度。
- 树的度:树中所有节点的度的最大值称为树的度。
- 节点的层次:根节点的层数为 0,其子节点的层数为 1,依此类推。
- 树的深度:树中所有节点的层次的最大值称为树的深度。
- 树的高度:树的深度+1。
树的性质:
- 树的节点数等于所有节点的度数之和加 1。
- 度为 的树中第 层的节点数最多为 (根节点为第 0 层)。
- 高度为 (深度为 )的度为 的树中最多有 个节点。
- 具有 个节点的 叉树的最小高度为 。
二叉树
- 完全二叉树: 除了最后一层外,每一层的节点数都达到最大值,最后一层的节点都靠左排列。
- 满二叉树: 所有分支节点的度都是 2 的完全二叉树,叶子节点都在同一层。
二叉树的性质:
- 二叉树度数为 0 的节点比度数为 2 的节点多一个。
- 二叉树的第 层最多有 个节点(根节点为第 0 层)。
- 高度为 (深度为)的二叉树最多有 个节点。
- 非空满二叉树的叶子节点的数量等于分支节点的数量加 1。
- 具有 个节点的完全二叉树的高度为 或 。
- 对于按层次编码的二叉树(根节点为 1),节点 的父节点为 ,左孩子为 ,右孩子为 。
二叉树的存储结构
顺序存储结构:将二叉树的节点按照从上到下、从左到右的顺序存储在一维数组中。
链式存储结构:每个节点包含数据域和两个指针域,分别指向左孩子和右孩子。
- 孩子表示法:
- 定长节点的多重链表:对于 n 叉树,每个节点包含一个数据域和 n 个指针域,分别指向 n 个孩子节点。
- 不定长节点的多重链表:每个节点包含一个数据域和一个指针链表,指针链表中的每个指针指向一个孩子节点。
- 孩子-兄弟表示法:每个节点包含一个数据域和两个指针域,分别指向第一个孩子节点和下一个兄弟节点。
- 双亲表示法:每个节点包含一个数据域和一个指针域,指针域指向父节点。
二叉树的遍历
广度优先遍历(层次遍历):从根节点开始,按照从上到下、从左到右的顺序遍历。
深度优先遍历:从根节点开始,沿着一条路径一直遍历到叶子节点,然后回溯到前一个节点,继续遍历其他节点。
- 前序遍历:根节点 -> 左子树 -> 右子树
- 中序遍历:左子树 -> 根节点 -> 右子树
- 后序遍历:左子树 -> 右子树 -> 根节点
线索二叉树
首先画出二叉树的链式存储结构,然后根据某种次序遍历二叉树,将遍历的前驱和后继指针取代链式存储结构中的左右孩子指针为空指针的指针域,并更新对应的标志位。
- leftTag=0:leftChild 指向左孩子
- leftTag=1:leftChild 指向前驱节点
- rightTag=0:rightChild 指向右孩子
- rightTag=1:rightChild 指向后继节点
二叉搜索树
二叉搜索树的左子树中的所有节点的值均小于根节点的值,右子树中的所有节点的值均大于根节点的值。
二叉搜索树的查找:从根节点开始,若查找的值等于根节点的值,则查找成功;若查找的值小于根节点的值,则在左子树中查找;若查找的值大于根节点的值,则在右子树中查找。
二叉搜索树的插入:从根节点开始,若插入的值小于根节点的值,则插入到左子树中,否则插入到右子树中。
二叉搜索树的删除:
- 被删除节点没有子节点:直接删除。
- 被删除节点只有一个子树:将子树移动到被删除节点的位置。
- 被删除节点有两个子树:
- 合并删除:将被删除节点的左子树按中序遍历的最后一个节点的右指针指向被删除节点的右子树,然后将被删除节点的左子树移动到被删除节点的位置。
- 复制删除:将被删除节点的左子树的最大节点或右子树的最小节点复制到被删除节点的位置,然后删除被复制的节点。
平衡二叉树(AVL 树)
平衡二叉树是一种特殊的二叉搜索树,其左右子树的高度差不超过 1。
平衡二叉树的插入:在插入节点后,从插入节点开始向上回溯,检查每个节点的平衡因子,若平衡因子超过 1,则进行旋转操作。
- 若不平衡的节点为
/
结构:对节点进行右旋。 - 若不平衡的节点为
\
结构:对节点进行左旋。 - 若不平衡的节点为
<
结构:先对左子树进行左旋,再对节点进行右旋。 - 若不平衡的节点为
>
结构:先对右子树进行右旋,再对节点进行左旋。
旋转操作:
- 左旋:将右子树的根节点作为根节点,右子树的左子树作为根节点的右子树,根节点作为右子树的左子树。
- 右旋:将左子树的根节点作为根节点,左子树的右子树作为根节点的左子树,根节点作为左子树的右子树。
平衡二叉树的删除:用一般的二叉搜索树的删除方法删除节点,然后从删除节点开始向上回溯,检查每个节点的平衡因子,若平衡因子超过 1,则进行旋转操作。
堆与优先队列
- 最大树:根节点的值大于等于子节点的值。
- 最小树:根节点的值小于等于子节点的值。
- 最大堆:最大的完全二叉树。
- 最小堆:最小的完全二叉树。
最大堆的插入:将新元素插入到堆的最后,然后向上调整。
最大堆的删除:将待删除节点与最后一个节点交换,然后删除最后一个节点。调整时,若待调整节点的值大于父节点的值,则将待调整节点与父节点交换,直到待调整节点的值小于等于父节点的值。
最大堆的构建:
- 插入法:依次将元素插入到堆中。
- 筛选法:将待排序元素按照层次顺序依次插入到堆中,然后从最后一个非叶子节点(第 个节点,根节点为第 0 个节点)开始,依次向上调整。
Huffman 树
不断选择两个权值最小的节点,合并成一个新的节点,直到只剩下一个节点。
树与森林
将树、森林转换为二叉树:
- 相邻兄弟节点和树之间添加连线。
- 删除每个节点和除第一个孩子节点外的其他孩子节点之间的连线。
将二叉树还原为树、森林:
- 删除相邻兄弟节点和树之间的连线(删除所有的右孩子连线)。
- 添加每个节点和除根节点外的其他孩子节点之间的连线。
图
图是由顶点的有穷非空集合和顶点之间的边的集合组成的。
图的存储结构
邻接矩阵表示法:
邻接表表示法:
图的遍历
深度优先搜索:类似于树的先序遍历,从图中某个顶点出发,沿着一条路径访问图中的所有顶点,直到路径末端,然后回溯到前一个顶点,继续访问其他顶点。
广度优先搜索:类似于树的层次遍历,从图中某个顶点出发,依次访问该顶点的所有邻接顶点,然后再依次访问这些邻接顶点的邻接顶点,直到访问完所有顶点。
最小生成树
Prim 算法:设生成树中的顶点集合为 ,未加入生成树的顶点集合为 ,每次从 中选取一个顶点 ,从 中选取一个顶点 ,使得 到 的边权值最小,将 加入 ,直到 为空。
Prim 算法的时间复杂度为 。
Kruskal 算法:将图中的所有边按照权值从小到大排序,依次选取权值最小的边,若该边的两个顶点不在同一个连通分量中,则将这两个顶点合并。否则选取下一条边。
Kruskal 算法的时间复杂度为 。
最短路径
Dijkstra 算法(单源最短路径):设 表示从源点到顶点 的最短路径长度, 表示从源点到顶点 的最短路径上的前一个顶点, 表示图中的所有顶点, 表示已经找到最短路径的顶点集合, 表示未找到最短路径的顶点集合。每次从 中选取一个顶点 ,使得 最小,将 加入 ,更新 中的顶点的最短路径长度。
顶点/S | ||||||
---|---|---|---|---|---|---|
12 | 12 | |||||
10 | ||||||
∞ | 60 | 60 | 50 | |||
30 | 30 | 30 | ||||
100 | 100 | 100 | 90 | 60 | ||
最短路径 | ||||||
新顶点 | ||||||
路径长度 | 10 | 12 | 30 | 50 | 60 |
Dijkstra 算法的时间复杂度为 。若使用优先队列实现,则时间复杂度为 。
Floyd 算法(多源最短路径):设 表示顶点 到顶点 的最短路径长度, 表示顶点 到顶点 的最短路径上的前一个顶点, 表示图中的所有顶点。每次从 中选取一个顶点 ,使得 最小,更新 和 。
Floyd 算法的时间复杂度为 。
拓扑排序
每次从图中选取一个入度为 0 的顶点,将该顶点加入拓扑序列,并将该顶点的所有邻接顶点的入度减 1。如果最后还剩下顶点,但是没有入度为 0 的顶点,则说明图中存在环。
关键路径
AOE 网络:用顶点表示事件,用边表示活动,用边上的权值表示活动持续的时间。
- 活动 的持续事件 表示从事件 到事件 的持续时间。
- 事件 的最早发生时间 ,其中 是 的前驱事件。
- 事件 的最迟发生时间 ,其中 是 的后继事件。
- 活动 的最早开始时间 ,其中 是活动 的前驱事件。
- 活动 的最迟开始时间 ,其中 是活动 的后继事件。
- 活动 的时间余量为 。
- 活动 是关键活动当 。
查找
静态查找
顺序查找法:从表头开始逐个比较,直到找到目标元素或者遍历完整个表。
折半查找法(二分查找法):在有序表中,每次将查找区间缩小一半,直到找到目标元素或者查找区间为空。
int binary_search(int *arr, int n, int target) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
分块查找法:将表分为若干块,块间有序,块内无序。首先通过二分查找出目标元素所在的块,然后在该块中进行顺序查找。
动态查找
B 树:树中每个节点至多有 个子节点,根节点至少有 2 个子节点,非根节点至少有 个子节点。所有叶子节点都在同一层。
2-3 树:每个节点至多有 3 个子节点,根节点至少有 2 个子节点,非根节点至少有 1 个子节点。所有叶子节点都在同一层。
- 2-3 树的插入:每次插入到最底层,若插入后节点的子节点个数超过 3,则将节点分裂为两个节点,中间节点上移。
- 2-3 树的删除:
- 从包含 2 个记录的叶子节点中删除 1 个记录:直接删除。
- 从包含 1 个记录的叶子节点中删除 1 个记录:将兄弟节点中的一个记录移动到父节点中,然后用父节点中的记录替换被删除的记录。若兄弟节点不够借(即兄弟节点中的记录数均小于 2),则将兄弟节点与父节点合并。
B+树
散列查找
排序
排序算法 | 时间复杂度(最好情况) | 时间复杂度(平均情况) | 时间复杂度(最坏情况) | 空间复杂度 | 稳定性 |
---|---|---|---|---|---|
直接插入排序 | 稳定 | ||||
希尔排序 | 不稳定 | ||||
直接选择排序 | 不稳定 | ||||
堆排序 | 不稳定 | ||||
冒泡排序 | 稳定 | ||||
快速排序 | 不稳定 | ||||
归并排序 | 稳定 | ||||
基数排序 | 稳定 |
排序算法的选择:
\元素数量 稳定排序\ | 少 | 多 |
---|---|---|
不要求 | 直接选择排序(元素不为逆序) | 快速排序(元素随机分布) 堆排序 |
要求 | 直接插入排序 | 归并排序(内存空间充足) |
插入排序
直接插入排序:每次将一个待排序的记录插入到已经排好序的有序表中。
- 时间复杂度:
- 稳定排序
void insert_sort(int *arr, int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
折半插入排序:在直接插入排序的基础上,使用二分查找法找到插入位置。
- 时间复杂度:
- 稳定排序
void binary_insert_sort(int *arr, int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int low = 0, high = i - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] > key) {
high = mid - 1;
} else {
low = mid + 1;
}
}
for (int j = i - 1; j >= low; j--) {
arr[j + 1] = arr[j];
}
arr[low] = key;
}
}
希尔排序:将待排序的记录按照一定的增量分组,对每组进行直接插入排序,然后逐渐减小增量,直到增量为 1。
交换排序
冒泡排序:每次比较相邻的两个元素,若逆序则交换。
- 时间复杂度:
- 稳定排序
void bubble_sort(int *arr, int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
}
}
}
}
快速排序:每次选取一个基准元素,将小于基准元素的元素放在基准元素的左边,将大于基准元素的元素放在基准元素的右边,然后递归地对左右两部分进行排序。
- 时间复杂度:
- 不稳定排序
- 不适用于基本有序的序列
void quick_sort(int *arr, int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quick_sort(arr, low, pivot - 1);
quick_sort(arr, pivot + 1, high);
}
}
分割策略一:取两个指针 left 和 right,重复执行以下操作,直到 left 和 right 相遇:
- 从右向左找到第一个小于基准元素的元素,将该元素放在 left 的位置。
- 从左向右找到第一个大于基准元素的元素,将该元素放在 right 的位置。
int partition(int *arr, int low, int high) {
int pivot = arr[low];
while (low < high) {
while (low < high && arr[high] >= pivot) {
high--;
}
arr[low] = arr[high];
while (low < high && arr[low] <= pivot) {
low++;
}
arr[high] = arr[low];
}
arr[low] = pivot;
return low;
}
分割策略二:取两个指针 left 和 right,重复执行以下操作,直到 left 和 right 相遇:
- 从右向左找到第一个小于基准元素的元素。
- 从左向右找到第一个大于基准元素的元素。
- 交换这两个元素。
int partition(int *arr, int low, int high) {
int pivot = arr[low];
int left = low, right = high;
while (left < right) {
while (left < right && arr[right] >= pivot) {
right--;
}
while (left < right && arr[left] <= pivot) {
left++;
}
std::swap(arr[left], arr[right]);
}
std::swap(arr[low], arr[left]);
return left;
}
选择排序
简单选择排序:每次选取最小的元素放在已排序的序列的末尾。
- 时间复杂度:
- 不稳定排序
void select_sort(int *arr, int n) {
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
std::swap(arr[i], arr[min]);
}
}
堆排序:将待排序的序列构建成一个大顶堆,然后将堆顶元素与堆尾元素交换,调整堆,直到堆中只剩下一个元素。
- 时间复杂度:
- 不稳定排序
归并排序
自顶向下的归并排序:将待排序的序列递归地分成两部分,然后将两部分合并。
- 时间复杂度:
- 稳定排序
void merge_sort(int *arr, int low, int high) {
if (low < high) {
int mid = low + (high - low) / 2;
merge_sort(arr, low, mid);
merge_sort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
}
自底向上的归并排序:先将序列中的每个元素看作一个长度为 1 的有序序列,然后两两合并,直到合并成一个长度为 的有序序列。
- 时间复杂度:
- 稳定排序
void merge_sort(int *arr, int n) {
for (int step = 1; step < n; step *= 2) {
for (int i = 0; i < n - step; i += 2 * step) {
int low = i, mid = i + step - 1, high = std::min(i + 2 * step - 1, n - 1);
merge(arr, low, mid, high);
}
}
}
基数排序
高位优先(MSDF)法:从最高位开始,依次对每一位进行计数排序。
低位优先(LSD)法:从最低位开始,依次对每一位进行计数排序。