提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

提示：这里可以添加本文要记录的大概内容：

哈喽大家好呀,今天就是我们数据结构与算法学习日志的最后一天了,不知道大家有没有跟我一起坚持呢,相信各位一定做得比我好得多吧,哈哈 那么接下来就进入今天的内容吧!

---

提示：以下是本篇文章正文内容，下面案例可供参考

堆排序

从最后一个节点开始找到他的根节点并比较根节点与两个子节点的大小,将根节点与值最大节点进行交换 不断进行这个过程,从而使数组有序

#include<iostream>
#include<vector>
using namespace std;
//调整当前子树为最大堆结构
void Adjust(vector<int>& vec, int start, int end)
{
	int root = start;
	int son = root * 2 + 1;
	//从子树中找到最大值并于根节点交换
	while (son <= end)
	{
		//比较左右子节点大小找出较大的
		if (son + 1 <= end && vec[son] < vec[son + 1]) son++;
		//与根节点进行比较
		if (vec[root] < vec[son]) swap(vec[root], vec[son]);
		root = son;
		son = root * 2 + 1;
	}
}
	
void Heap_Sort(vector<int>& vec)
{
	//最后一个节点
	int n = vec.size() - 1;
	//(n-1)/2为最后一个节点的根节点的下标 从这里也就是最后一个子树开始调整最大堆
	for (int i = (n - 1) / 2; i >= 0; i--)//i为根节点下标
	{
		Adjust(vec, i, n);//节点下标不能超过n
	}
	//调整之后将最大值也就是根节点与最后一个元素进行交换
	for (int i = n; i >= 1; i--)//i为被交换的元素下标 n个元素交换n-1次
	{
		swap(vec[0], vec[i]);
		Adjust(vec, 0, i-1);//交换后将剩下的再次调整为最大堆 只需要调整到i-1 后面的已经有序
	}

}
int main()
{
	vector<int>vec = {9,3,7,2,45,2,4,5,4,234,5,63,};
	Heap_Sort(vec);
	for (auto i : vec) cout << i << ' ';

	return 0;
}

堆结构 Priority Queues (优先级队列)

Priority Queues是STL提供的堆结构

KMP算法

KMP算法用于实现字符串匹配问题,例如查找某个字符串是否是s的子串,普通方法(时间复杂度$O(n\ast m)$)是从头开始进行比较,KMP是对普通方法的优化

KMP算法的关键:

前缀表:记录下标i之前的字符串中有多大长度的相同前后缀

前缀:以第一个字符开始不包含最后一个字符的连续子串

后缀:以最后一个字符结尾不包含第一个字符的连续子串

next数组:记录前缀信息(例中B字符串),遇到不匹配时指引短串使用哪一个位置和长串中不匹配位置进行比较(例如B中第二次应使用B[2]与A[3]开始比较)

例:A.aabaabaaf

​ B.aabaaf

KMP代码实现

#include<iostream>
#include<vector>

using namespace std;
void getNext(vector<int>& next,const string& s)
{
	int j = 0;
	next[0] = 0;
	for (int i = 1; i < s.size(); i++)
	{
		if (s[i] == s[j]) j++;
		else
		{
			while (j > 0 && s[i] != s[j]) j = next[j - 1];
		}
		next[i] = j;
	}
}

int KMP(string s,string s1)
{
	if (s1.size() == 0 || s.size() == 0 || s.size() < s1.size()) return -1;
	//需要next数组记录前缀表信息
	vector<int>next(s1.size());//记录s1前缀和
	getNext(next,s1);//调用next函数
	int j = 0;
	for (int i = 0; i < s.size(); i++)
	{
		//不等通过next前缀和调整j的位置
		while (j > 0 && s[i] != s1[j]) j = next[j - 1];

		//如果相等则向后遍历
		if (s[i] == s1[j]) j++;
		
		//j等于s1的长度说明在s中找到了s1
		if (j == s1.size()) return i - s1.size() + 1;
	}
	//通过i跳出循环说明没有在s找到s1
	return -1;
}

int main()
{
	string s = "aabaabaaf";
	string s1 = "aabaaf";
	cout << KMP(s, s1);
	return 0;
}

2-3查找树

2-3查找树定义:

2-3查找树由以下节点组成:

2-节点:含有一个键(val)和两个指针,左指针指向子树的键都小于该节点,右指针指向子树中的键都大于该节点

3-节点:含有两个键和三个指针,左指针指向子树的键都小于第一个键,中指针指向子树的键大于第一个键小于第二个键,右指针指向子树中的键都大于第二个键,3-节点中第二个键大于第一个键

注:

2-3树是平衡树,并且可以保证插入节点后不需要旋转仍然保持平衡性

2-3树保持绝对平衡(绝对平衡:任意空节点到根节点的节点个数都相同)

一棵完全平衡的2-3树具有以下性质：

（1）任意空链接到根节点的路劲长度都是相等的

（2）4-节点变换为3-节点时，树的高度不会发生变化，只有当根节点是临时的4-节点，分解节点时，树的高度+1

（3）2-3树与普通查找树最大的区别在于，普通查找树时自顶向下生长，而2-3树时自底向上生长的。

2-3查找树的时间复杂度

最坏情况下的查找、插入、删除时间复杂度均为 O(log n)，其中n是树中元素个数。性能稳定。

红黑树

红黑树的最长长度不会超过最短长度的两倍,因此红黑树是广义上的平衡

1. 2 节点 → 单独黑节点
2. 3 节点 → 拆成二叉，一黑一红
3. 4 节点 → 拆成二叉，中间黑、两边红
4. 红节点 = 没分层，只是多叉树压扁成二叉的标记
5. 2-3-4 树绝对平衡 → 转成红黑树天然满足每条路径黑节点个数相同，就是红黑树的平衡底层原理

红黑树 5 条性质（源于 2-3 树）

1. 节点红 / 黑
2. 根是黑
3. 叶子 (NIL) 都是黑
4. 红节点根节点和两个子节点都是黑（不能红红相连，对应 2-3-4 树不会叠多层复合节点）
5. 任意节点到叶子，黑节点数量相同（直接继承 2-3-4 树绝对平衡）

---

总结

以上就是本文的全部内容了,截至本文数据结构与算法学习日志也就告一段落了,接下来会给大家更新Linux相关的学习内容,每天也会保持一到两道算法题的进度,感谢大家敢看我的文章,我们后天见!(明天跟大家请个假,最近因该是太久没怎么休息了,连着几天睡午觉闹钟响了我都还没睡着,明天打算休息一天了,感谢大家的理解!)