数据结构知识总结

逻辑关系→计算机内部的表示→具体操作如何实现

存储中的几种实现方式：顺序实现/链接实现/散列存储/索引存储
大 $O$ 表示法：给出算法在问题规模达到一定程度后运行时间增长率的上界。（ $\Omega$ ，给出下界； $\Theta$ ，相等； $o$ ，严格小于）

O(1)<O(\log N)<O(N)<O(N\log N)<O(N^2)<O(N^3)

O(2^N)<O(N!)<O(N^N)

集合结构

表示常借鉴线性表或者树。唯一一个仅适合处理集合的数据结构是散列表。

查找

静态查找表（元素个数及其值不允许变化）

顺序查找表：0号单元做岗哨，无论有序还是无序，时间复杂度为 $O(N)$
二分查找：查找有序的元素

int low=1,high=size,mid;
while(low<=high){
	mid=(low+high)/2;
	if (x==data[mid].key)
		return mid;
	if (x<data[mid].key){
		high = mid-1;
	}
	else
		low = mid+1;
}

插值排序：
- 把上边代码中mid计算方法改为mid=low+((x-data[low].key)/(data[high].key-data[low].key))*(high-low-1)
- 效率高须满足：计算代价＜查找代价；数据有序且均匀。
分块查找：
- 先查找索引表（有序：顺序or二分），再在块内查找（一般无序：顺序查找）
- 时间性能高于顺序查找低于二分查找，大量数据须保存在外存时是一种很好的方法。

动态查找表

查找树

二叉树

左子树的所有值都比根节点的值小；右子树的所有值都比根节点的值大；左右子树也是二叉查找树；第k小二叉树直接中序遍历之后找第k个最小数。二叉查找树中，删除叶结点不会改变树的结构，但是删除非叶结点会改变树的结构。

二叉树的删除

void BinarySearchTree<KEY,OTHER>::remove(const KEY &x,BinaryNode *&t){
	if (t==NULL) return;
	if (x<t->data.key) remove(x,t->left);
	else if(x>t->data.key) remove(x,t->right);
	else if (t->left!=NULL && t->right!=NULL){
		BinaryNode *tmp=t->left;
		while(tmp->right!=NULL) tmp=tmp->right;
		t->data=tmp->data;
		remove(t->data.key,t->left);
	}
	else{
		BinaryNode *oldNode=t;
		t=(t->left!=NULL)?t->left:t->right;
		delete oldNode;
	}
}

AVL树

平衡度：左子树高度-右子树高度
高度 $H$ 小于等于 $1.44\log(N+1)-0.328$
其Node中多了一个表示高度的int结点
AVL树的插入是递归的，做两次旋转时，第一次如果没转过来也没关系。
find函数的实现

while(t!=NULL && t->data.key!=x){
	if(t->data.key<x) t=t->left;
	else t=t->right;
}

LL函数的实现

void AvlTree<KEY,OTHER>::LL(AvlNode*&t)
{
	AvlNode *tl=t->left;
	t->left=tl->right;
	tl->right=t;//进行一个位置的替换
	t->height=max(height(t->left),height(t->right))+1;
	tl->height=max(height(tl->left),height(t))+1;//重置高度
	t=tl;//重置根节点
}

LR函数的实现

void AvlTree<KEY,OTHER>::LR(AvlNode *&t){
	RR(t->left);
	LL(t);
}

删除函数的实现

template <class KEY,class OTHER>
bool AvlTree<KEY,OTHER>::remove(const KEY & x,AvlNode * & t)
{
	if (t==NULL) return true;
	if(x==t->data.key){
		if(t->left==NULL||t->right==NULL){
			AvlNode *oldNode=t;
			t=(t->left!=NULL)? t->left:t->right;
			delete oldNode;
			return false;
		}
		else{
			AvlNode *tmp=t->right;
			while(tmp->left!=NULL) tmp=tmp->left;
			t->data=tmp->data;
			if(remove(tmp->data.key,t->right)) return true;
			return adjust(t,1);
		}
	}
	if(x<t->data.key){
		if(remove(x,t->left)) return true;
		return adjust(t,0);
	}
	else{
		if(remove(x,t->right)) return true;
		return adjust(t,1);
	}
}
template <class KEY,class OTHER>
bool AvlTree<KET,OTHER>::adjust(AvlNode *&t, int subTree){
	if(subTree){
		if(height(t->left)-height(t->right)==1) return true;
		if(height(t->right)==height(t->left)){--t->height;return false;}
		if(height(t->left->right)>height(t->left->left)){
			LR(t);
			return false;
		}
		LL(t);
		if(height(t->right)==height(t->left)) return false;else return true;
	}
	else{
		if(height(t->right)-height(t->left)==1)return true;
		if(height(t->right)==height(t->left)){--t->height;return false;}
		if(height(t->right->left)>height(t->right->right)){
			RL(t);
			return false;
		}
		RR(t);
		if(height(t->right)==height(t->left)) return false;else return true;
	}
}

散列表（哈希）

散列函数

直接定址
除留余数（数组大小最好是素数）
数字分析-略去相同的数字，剩下的数字再做前两种操作
平方取中（关键字值域比较大的时候，平方后取中间几位）
折叠法（关键字值域>>散列结果）选取一个长度之后关键字分组相加

解决碰撞

闭散列表
- 线性探测法，定义了一个函数指针int(*key)(const KEY &x);
  - 散列表结点有一个数据成员state，用来辨认节点为空/满/已删除
  - 一般会留超过一半的空间，防止哈希冲突
- 二次探测法，表大小是一个素数，表至少有一半空单元，新元素总能被插入。
开散列表
- 插入：直接插入到散列表的第一个元素array[pos]=new node(x,array[pos])

外部查找（访问次数决定运行时间）

B树（m阶）

根节点不止有一个孩子该死！关键字其实就是你要查找的值！！！！叶子结点中的指针其实指向的就是存储这个值的地方。在B树中，一个关键字仅出现在树中的一个节点，无论是在叶子节点还是非叶子节点。

B树的插入（分裂）
B树的合并：可以一直合并到根节点。

B+树

支持每个记录的随机访问，也能支持整个文件按关键字次序的访问。
在B+树中，非叶节点的关键字也出现在叶子节点中。在B+树中，所有关键字都出现在叶子节点的链表中，叶子节点包含了数据的所有关键字以及指向包含这些关键字的记录的指针。非叶子节点的关键字仅作为分隔值，用于指导搜索，而非叶子节点并不直接表示数据。
在B+树中，根节点的子节点数量有一些特殊的规则。对于一棵M阶的B+树，如果树的高度大于1（即树有多于一层的节点），那么根节点至少有两个子节点，并且最多有M个子节点。这符合B+树的定义，因为非叶子节点（包括根节点）至少有⌈M/2⌉个子节点，且最多有M个子节点，但是对于根节点，当树的高度大于1时，至少有两个子节点。然而，如果树的高度为1，即只有根节点和它的叶子节点，那么根节点可能有少于两个（甚至只有一个）子节点。这是因为在这种情况下，根节点也作为叶节点，所以它可能只有一个子节点。（只有一层的情况基本不考虑）
分出去的时候，分出去的树带的节点数最少
与B树的区别：叶节点的孩子指针指向一定的数据块。
- $L$ ：每个数据块至少有 $\lceil L/2 \rceil$ 个记录，至多有 $L$ 个记录； $M$ 则代表了儿子数，每个非叶结点最多有 $M-1$ 个键
- 有k个孩子的借点保存了k-1个键引导查找，每个键代表了它后面节点的最小值
- 所有叶结点按序连接成单链表→可以支持顺序查找

排序

内排序

直接插入排序（稳定），复杂度为 $O(n^2)$
二分插入排序（稳定），复杂度仍为 $O(n^2)$
希尔排序（不稳定）

template<class KEY,class OTHER>
void shellSort(SET<KEY,OTHER>a[],int size){
	int step,i,j;
	SET<KEY,OTHER> tmp;
	for(step=size/2;step>0;step/=2){
		for(i=step;j>=0&&a[j].key>tmp.key;j-=step)
			a[j+step]=a[j];
		a[j+step]=tmp;
	}
}

直接（选择）排序（不稳定），复杂度 $O(n^2)$
堆排序（不稳定），复杂度 $O(n\log n)$ ，首先建立一个堆，然后把堆顶的值和堆最后的值进行互换，然后执行向下过滤。
冒泡排序（稳定），复杂度 $O(n^2)$ ，最好情况下 $O(n)$

template<class KEY,class OTHER>
void bubbleSort(SET<KEY,OTHER>a[],int size){
	int i,j;
	SET<KEY,OTHER> tmp;
	bool flag=true;
	for(i=1;i<size && flag;++i){
		flag=false;
		for(j=0;j<size-1;++j){
			if(a[j+1].key<a[j].key){
				tmp=a[j];
				a[j]=a[j+1];
				a[j+1]=tmp;
				flag=true;
			}
		}
	}
}

快速排序（不稳定），最好情况下 $O(n\log n)$ ，最坏情况下 $O(n^2)$

template<class KEY,class OTHER>
void quickSort(SET<KEY,OTHER> a[],int low,int high){
	int mid;
	if(low>=high) return;
	mid=divide(a,low,high);
	quickSort(a,low,mid-1);
	quickSort(a,mid+1,high);
}
template<class KEY,class OTHER>
int divide(SET<KEY,OTHER> a[],int low,int high){
	int k=a[low];
	do{
		while(low<high&&a[high].key>=k.key)--high;
		if(low<high){a[low]=a[high];++low;}
		while(low<high&&a[low].key<=k.key)++low;
		if(low<high){a[high]=a[low];--high;}
	}while(low!=high);
	a[low]=k;
	return low;
}

归并排序，时间复杂度为 $O(n\log n)$ ，且需要额外的 $O(n)$ 的空间（稳定排序）

template<class KEY,class OTHER>
void merge(SET<KEY,OTHER>a[],int left,int mid,int right){
	SET<KEY,OTHER> *tmp=newSET<KEY,OTHER>[right-left+1];
	int i=left,j=mid,k=0;
	while(i<mid&&j<=right){
		if(a[i].key<a[j].key) tmp[k++]=a[i++];
		else tmp[k++]=a[j++];
	while(i<mid) tmp[k++]=a[i++];
	while(j<=right)tmp[k++]=a[j++];
	for(i=0,k=left;k<=right) a[k++]=tmp[i++];
	delete [] tmp;
	}
}
template<class KEY,class OTHER>
void mergeSort(SET<KEY,OTHER>a[],int left,int right){
	int mid=(left+right)/2;
	if(left==right)return;
	mergeSort(a,left,mid);
	mergeSort(a,mid+1,right);
	merge(a,left,mid+1,right);
}

基数排序，时间复杂度是 $O(len\times n)$ ，空间复杂度是 $O(1)$ （按照位数丢到链表里，再拿出来）

外排序（访问次数决定运行时间）

使用：归并排序（2路或者k路）

置换选择（预处理，置换-选择排序）：输出到外存之后直接取出一个新元素，如果放入堆符合顺序，就放入，反之，就不放入。数据比较接近于排好序的序列效率比较高
多阶段归并：尽可能使已排序片段的数目符合斐波那契数列。不符合的情况：添加虚拟的排序片段。

线性结构

顺序实现

注意这个结构包含一个指针，一个目前的长度，数组的最大长度（在清除数组中所有的数字时，直接删除就好了），以及一个扩大数组size的函数
定位访问性能好，插入删除时间复杂度为 $O(n)$ ，部分空间被浪费了

链接实现

单链表有一个头结点，有一个工具函数move，返回第i个节点的地址
单链表的清空：先将头指针指向的位置置空，之后挨个删除
创建双链表时，创建一个头结点一个尾结点。
保存单循环链表或者双循环链表都只需要一个指向线性表中起始结点的指针
适合经常需要执行插入删除但很少访问特定位置元素，线性表

栈

入栈出栈序列：可以入栈后立即出栈。
均摊分析法：入栈的时间复杂度为 $O(1)$
链接法实现栈：top_p是头指针，push是插入表头，pop是删除表头
无论是顺序实现栈还是链接实现栈，时间复杂度都是 $O(1)$

队列

循环队列：front是空节点，rear不是
循环队列入队：rear=(rear+1)%MaxSize
队列满的条件(rear+1）% MaxSize == front，队列空的条件front == rear
循环队列的doubleSpace函数，在拷贝队列的时候把front放在数组下标为[0]的位置。
链接存储的队列基本运算的时间复杂度都是 $O(1)$
循环链表实现队列的删除：首先用一个指针指向队尾的下一个节点，然后从队尾那里断掉链表，之后按照单链表的方式删除。
循环链表实现队列：加入节点：在rear节点后插入一个值，并且把rear移到这个值上；删除节点：直接删除rear后（front 指向）的节点。
入队和出队：操作不唯一，考虑队为空的情况，以及队内仅有一个元素的情况。

树状结构

度：一个节点直接后继的数目

二叉树

二叉树是有序树，必须严格区分左右子树。
非空二叉树第 $i$ 层最多有 $2^{i-1}$ 个节点
叶子结点数与度为二的节点之间的关系： $n_{0}=n_{2}+1$ （用总结点/边的关系）
$n$ 个结点的完全二叉树的高度 $k=\lfloor\log_{2}n\rfloor+1$
完全二叉树父/左儿子/右儿子之间编号的关系 $i$ ， $2i$ ， $2i+1$
当 $n$ 为偶数时， $n$ 个点的完全二叉树有 $\frac{n}{2}$ 个叶子结点（不光是最后一层！）；当 $n$ 为奇数时，有 $\frac{{n+1}}{2}$ 个叶子结点。
可以确定唯一二叉树：中序遍历+前序/后序/层次序
只有0/2度节点的二叉树：可以通过前序+后序确定二叉树。若把空结点填满，则仅凭前序遍历就可以确定二叉树。
二叉树的前序/后序/中序都用了封装函数
二叉树的层次序列：利用一个队列。（根节点入队，出队，访问左右子节点）
生成二叉树也使用了队列
孩子兄弟表示法表示二叉树的形态唯一。

哈夫曼树

待编码的元素是叶结点，其他结点都是度数为2的结点。
规模为 $2n-1$
把叶子结点放在数组的后面，归并的树放在数组的前面。

森林

森林→二叉树：先把森林每一棵树用孩子兄弟表示法表示，再把它们看作兄弟，挨个链接在右子树上

优先级队列/二叉堆

向上过滤（最小化堆）

int hole=++currentSize;
for(;hole>1 && x<array[hole/2];hole/=2)//x是传进来的值，用在将新值插入堆中的情况
	array[hole]=array[hole/2];
array[hole]=x

向下过滤（最小化堆）

int child;
Type tmp=array[hole];//这里hole的值已经是堆中最后一个数的值了
for(;hole*2<=currentSize;hole=child){
	child=hole*2;
	if(child+1!=currentSize && array[child]>array[child+1]){
		child++;
	}
	if(array[child]<tmp){
		array[hole]=array[child];
	}
	else break;
}
array[hole]=tmp;//需要注意的是，hole的值在上面的for循环中已经发生了变动，因此，这里hole所在的位置实际上是child的位置。

建立一个堆

for(int i = currentSize/2;i>0;i--){//跳过了叶结点，因为没有必要
	percolateDown(i);//逆向调用向下过滤的函数，保证整个堆都满足有序性。
}//时间复杂度为n

一棵高度为 $h$ ，包含 $N=2^K-1$ 个节点的满二叉树，向下过滤的最大值为 $N-h$
堆排序：请人类大脑严格按照代码步骤走捏

图状结构

一些基础

$G=(V,E)$ ， $<>$ ， $()$
强连通：有向图任意两个结点都连通；弱连通：不强联通，看成无向图时是连通的
完全图：
- 无向：每两个结点之间都有边，一共有 $C^2_{n}$ 条边。
- 有向：每两个结点之间都有两条弧（两个方向都有），一共有 $2C^2_{n}$ 条边
生成树：无向连通图的极小连通子图，包含 $n$ 个结点，只含 $n-1$ 条边，添加一条边之后，一定产生回路或环。
连通图：边数≥顶点数-1；握手条件：边 * 2=所有度的和
邻接矩阵表示有向图的时候，如果是加权图，没有边地方权值为 $\infty$
图的抽象类中有结点数和边数两个数据成员
邻接矩阵的构造函数有三个参数：大小，结点值，以及权值为无穷大的标志 noEdgeFlag ；构造函数要把自己到自己的边权值设为 $0$ ；行表示出度，列表示入度。
对稀疏图来说，邻接矩阵浪费了太多空间
邻接表中，表示一个边的 Node 有三个数据成员：终点编号，边权值和下一个节点。
邻接表中插入边的时候也是直接插到表头。

遍历

dfs-类似于前序遍历
- 思路：加一个记录节点是否被访问的数组；从第一个节点开始，挨个对其邻接表里的每个节点进行深度遍历。
- 邻接表时间复杂度： $O( \mid V \mid+\mid E\mid )$
- 邻接矩阵时间复杂度： $O(\mid V \mid^2)$
bfs-类似于层次遍历
- 思路：找到一个节点，把它入队，循环以下内容（出队，打印它的值，之后将其所有相邻节点入队），直到所有结点都被访问。

应用

连通性：利用两种搜索即可

欧拉回路

欧拉路径：在一个图中找到一条路径，使得该路径对图的每一条边刚好经过一次，若起点终点相同，称为欧拉回路。
计算出度入度个数，确定为2的倍数→创建一份邻接表的复本→深度优先搜索找到一条路径→查找路径中是否有没访问过的边→拼接

有向图的连通

找强连通分量：深度优先搜索→深度优先生成树→后序遍历→找编号最大的→从这里开始深度优先搜索→找强连通分量
连通：深度，广度，拓扑排序

拓扑排序

AOV网：顶点表示活动，边表示活动的先后关系
图一定是有向无环图，拓扑排序可以判断是否存在回路。
利用广度优先搜索的思想
计算每个节点的入度，如果入度为0，就入队，把它子结点入度减掉，然后再出队。
时间复杂度 $O(\mid V\mid+\mid E\mid)$

关键路径

AOE网：活动定义在边上，顶点表示事件。
源点和收点/汇点
源点到收点为止最长的路径：关键路径
最早发生时间：首先拓扑排序，之后按照拓扑排序序列遍历每个节点的边，更新其子节点的时间，其中最大的就是它的最早发生时间
汇点的最早发生时间是关键路径的长度
最迟发生时间：拓扑排序，之后倒序遍历每个结点的边，更新其子节点的时间，其中最小的就是它的最迟发生时间。
最早发生时间和最迟发生时间相等的那些点组成了关键路径。

CPP知识点

杂七杂八

strcmp，比较两个字符串的大小
cout.put(x)接受一个字符参数，并将其输出到控制台
srand(time(NULL))初始化随机数发生器
SET<KEY,OTHER>是一种泛型声明，它表示一个集合（Set）数据结构，其中的元素类型是KEY和OTHER。KEY和OTHER可以是任何合法的数据类型，例如整数、字符串、对象等。泛型是一种在编程语言中用来增加代码的灵活性和重用性的技术。它允许在不指定具体类型的情况下编写通用的代码，以在不同的数据类型上工作。在这种情况下，SET<KEY,OTHER>表示一个可以存储KEY类型和OTHER类型的元素的集合。
在template后面的尖括号中，应该填写模板参数。模板参数是指在模板声明中使用的类型、非类型或模板参数列表的占位符。以下是一些常见的模板参数类型：
- 类型参数：使用关键字class或typename，后面跟着参数名。例如：template<typename T>
- 非类型参数：可以是整数、枚举、指针或引用等，用于在编译时进行计算。例如：template<int N>
- 模板参数列表：可以是其他模板类型，用于接受其他模板作为参数。例如：template<template<typename> class Container> 在尖括号中，可以使用一个或多个模板参数，并且它们可以根据需要进行逗号分隔。
*&t 是一个指针引用类型的声明。它是由两个符号组成的。首先，* 表示指针类型，表示指向某个变量或对象的内存地址。其次，& 表示引用类型，表示将一个变量或对象的引用作为参数传递给函数或方法。在 *&t 中，t 是一个变量或对象的名称。*&t 可以理解为将变量 t 的引用取地址，得到该变量的指针。这种用法在某些场景下很有用，特别是在需要将指针作为参数传递给函数或方法时，可以使用 *&t 来传递变量的引用。有时候，你可能需要在函数或方法中修改指针本身的值。这种情况下，只有通过 *&t 来传递变量的引用作为指针，才能够修改指针本身的值。
函数指针是指向函数的指针变量。它可以用来存储和调用函数的地址。在cpp中，函数指针的类型由函数的参数和返回值类型确定。函数指针可以像普通变量一样进行声明、赋值和使用。通过函数指针，我们可以动态地选择要调用的函数，从而实现程序的灵活性和可扩展性。函数指针的声明方式如下：返回类型 (*指针变量名)(参数列表)，赋值方式：指针变量名 = 函数名;，使用（直接使用）
在cpp中，auto关键字用于自动类型推断。编译器会根据初始化表达式来推断变量的类型。在你给出的示例中：auto merged = new TreeNode(t1->val + t2->val);。auto关键字让编译器自动推断merged的类型。编译器看到new TreeNode(t1->val + t2->val) 返回的是一个TreeNode的指针，所以merged的类型被推断为TreeNode*。这样，我们就不需要明确指定merged是TreeNode*类型，编译器会自动处理。使用auto可以增加代码的可读性和可维护性，特别是当类型名称较长或复杂时。同时，auto也减少了因类型错误导致的一些问题。

带有参数的`main`函数

当main函数带有参数时，它接受命令行输入。让我给你一个例子来说明。

#include <iostream>

int main(int argc, char* argv[]) {
    std::cout << "命令行参数数量：" << argc << std::endl;
    
    for (int i = 0; i < argc; i++) {
        std::cout << "命令行参数 " << i << "：" << argv[i] << std::endl;
    }
    
    return 0;
}

在这个例子中，main函数接受两个参数：int argc和char* argv[]。argc表示命令行参数的数量，argv是一个指向字符串数组的指针，每个字符串表示一个命令行参数。程序运行时，您可以在命令行中输入参数，并通过这些参数来操作程序。

例如，如果您在命令行中运行以下命令：

./program arg1 arg2 arg3

那么argc将被设置为4（包括程序名称本身），argv将包含以下内容：

argv[0] = "./program"
argv[1] = "arg1"
argv[2] = "arg2"
argv[3] = "arg3"

您可以使用这些参数来根据需要在程序中执行特定的操作。在上面的例子中，我们简单地打印出命令行参数的数量和每个参数的值。

try-catch

try 是 cpp 中的一个关键字，用于定义一个异常处理的代码块。try 块用于包含可能会引发异常的代码，并且会与 catch 块一起使用。

以下是 try-catch 块的基本语法：

try {
    // 可能会引发异常的代码
} catch (ExceptionType1 e1) {
    // 处理 ExceptionType1 类型的异常
} catch (ExceptionType2 e2) {
    // 处理 ExceptionType2 类型的异常
} catch (...) {
    // 处理其他类型的异常
}

在 try 块中，我们可以放置可能会引发异常的代码。如果在 try 块中的某个地方发生了异常，那么程序会跳转到与该异常类型匹配的 catch 块，并执行其中的代码。

catch 块用于捕获和处理特定类型的异常。如果异常类型与 catch 块中定义的类型匹配，那么对应的 catch 块中的代码会被执行。如果没有找到匹配的 catch 块，那么异常会传播到调用栈的上一级。

最后一个 catch (...) 块是一个特殊的 catch 块，用于捕获所有类型的异常，即不指定特定的异常类型。它通常用于处理未知类型的异常或作为最后一个 catch 块来处理所有未被前面的 catch 块捕获的异常。

以下是一个示例：

#include <iostream>

int main() {
    try {
        int result = 10 / 0; // 除以零，引发异常
    } catch (const std::exception& e) {
        std::cout << "捕获到异常: " << e.what() << std::endl;
    } catch (...) {
        std::cout << "捕获到未知类型的异常" << std::endl;
    }
    
    return 0;
}

在这个示例中，我们在 try 块中进行了一个除以零的操作，这会引发一个异常。然后，我们使用 catch 块来捕获并处理这个异常。由于除以零是一个特定的异常情况，我们可以使用 std::exception 类型来捕获并输出异常信息。如果发生了其他类型的异常或未知类型的异常，那么会被 catch (...) 块捕获并处理。

重载运算符

函数体定义egoperator+
输入输出定义egLongLongint & operator (const LongLongInt &)

STL

vector/list

#include<vector> or #include<list>
vector<elemtype> a
insert在给出的位置前插入
pop和push都加在表尾
迭代器：vector<int>::const_iterator p

栈

#include<stack>
stack<elemType,list/vector<elemType>> s1
pop()，push()，empty()，top()

队列

#include<queue>
queue<int,list/vector/deque<int>>（deque速度比较慢）
push()，pop()，front()，empty()

静态查找表

包括find（顺序查找），binary_search（二分查找）
#include<algorithm>，#include<vector>
find/binary_search(v.begin(),v.end().n)

动态查找表

set一个关键字的查询；map以关键字-值对的形式组织。
set
- #include<set>
- std::set<type>mySet，函数有insert erase count
- set<int>::inerator p ++p
map
- #include<map>
- map<string,string> s map<string,string>::iterator p s.insert(pair<string,string>(xx,xx))

排序

#include<algorithm> 使用greaterotless的参数要#include<functional>
sort和stable_sort
三个参数，前两个是va.begin()或va.end()这样的迭代器，第三个是比较方法（less递增/greater递减）

算法的集合

最大连续子序列和-复杂度为线性算法

int maxSubsequenceSum(int a[],int size,int &start,int &end)
{
	int maxSum,startmp,thisSum;
	start=end=maxSum=startmp=thisSum=0;
	for(int i=0;i<size;++i){
		thisSum+=a[j];
		if(thisSum <= 0){
			thisSum=0;
			startmp=j+1;
		}
		else if (thisSum>maxSum){
			maxSum=thisSum;
			start=startmp;
			end=j;
			}
	}
	return maxSum;
}

速记

XX表达式

后缀计算：读到运算符弹出两个运算数，后弹出的为左运算数，之后结果进栈。栈中最后一个运算数就是表达式的结果
中缀转后缀：两个栈，操作数进OPND，符号进OPTR。保证OPTR同一括号内栈顶优先级最高，否则要进行运算。运算完之后弹出。

dfs/bfs

dfs：先狠狠执行到底，然后再回过头访问下一个结点。
bfs：用一个队列：访问元素，将其所有后继元素入队

时间复杂度

图：矩阵 $V^2$ ，邻接表 $V+E$
堆：
- 入队： $O(\log N)$
- 删除： $O(\log N)$
- 建堆： $O(N)$

非递归

前序：pop，push，push
中序：push根，pop根（1/2），push根，push左子树，···，pop根（2/2），访问，push右子树。
后序：push根，pop根（1/3）。push根，push左子树，···，pop根（2/3），push根，push右子树，···，pop根（3/3），访问

零散

哈夫曼树规模 $2n-1$
队列/栈/链表：应考虑空以及只剩一个的情况
树：应考虑根节点为空的情况，注意观察题目是否为叶子结点
插入位置： $1\le i \le len+1$
const elemType &x引用+常量
森林不一定是二叉树
高度为 $h$ 的二叉树插入一个新的节点，高度改变的节点个数最多为 $O(h)$
图的题目直接画出即可
前中后序遍历叶子结点顺序均相同
两个链表只要搭扣接上了就算是接上了

集合结构​

查找​

静态查找表（元素个数及其值不允许变化）​

动态查找表​

查找树​

二叉树​

AVL树​

散列表（哈希）​

散列函数​

解决碰撞​

外部查找（访问次数决定运行时间）​

B树（m阶）​

B+树​

排序​

内排序​

外排序（访问次数决定运行时间）​

线性结构​

顺序实现​

链接实现​

栈​

队列​

树状结构​

二叉树​

哈夫曼树​

森林​

优先级队列/二叉堆​

图状结构​

一些基础​

遍历​

应用​

连通性：利用两种搜索即可​

欧拉回路​

有向图的连通​

拓扑排序​

关键路径​

CPP知识点​

杂七杂八​

带有参数的main函数​

try-catch​

重载运算符​

STL​

vector/list​

栈​

队列​

静态查找表​

动态查找表​

排序​

算法的集合​

最大连续子序列和-复杂度为线性算法​

速记​

XX表达式​

dfs/bfs​

时间复杂度​

非递归​

零散​

集合结构

查找

静态查找表（元素个数及其值不允许变化）

动态查找表

查找树

二叉树

AVL树

散列表（哈希）

散列函数

解决碰撞

外部查找（访问次数决定运行时间）

B树（m阶）

B+树

排序

内排序

外排序（访问次数决定运行时间）

线性结构

顺序实现

链接实现

栈

队列

树状结构

二叉树

哈夫曼树

森林

优先级队列/二叉堆

图状结构

一些基础

遍历

应用

连通性：利用两种搜索即可

欧拉回路

有向图的连通

拓扑排序

关键路径

CPP知识点

杂七杂八

带有参数的`main`函数

try-catch

重载运算符

STL

vector/list

栈

队列

静态查找表

动态查找表

排序

算法的集合

最大连续子序列和-复杂度为线性算法

速记

XX表达式

dfs/bfs

时间复杂度

非递归

零散