上课笔记
2023-07-28 15:00:01
发布于：广东
埃氏筛
质数的倍数一定不是质数
所有合数的因子一定都有质数
set
类似优先队列，与集合相似，能存储同一类型的数据，具备互异性，内部自动有序
set升序排列，自动去重
只能通过迭代器访问：set<数据类型>::iterator it
在set里，迭代器名称
函数：
val.insert(data) 对val插入data数据 O(log(n))
val.erase(it) 1.删除一个迭代器it所指的位置 O(1)
2.删除一个值为it的数据 O(log(n))
val.erase(first,last) 删除迭代器于[first,last)的数据 O(last-first)
val.size() 当前val内元素个数（通用） O(1)
val.empty() 判断val是否为空（通用） O(n)
val.clear() 清空当前val容器 O(n)
val.begin() 起始迭代器
val.end() 末尾迭代器
val.find(data) 在val中查找data O(log(n))
遍历：
for(auto 迭代器名称 : 容器名){
//C++11才能用
}
set<数据类型>::iterator it;
for(it = 迭代器名称.begin();it != 迭代器名称.end();i++){
//C++9就能用 it要写*it
}
map
map直译为映射，类似普通数组<下标,值>的对应，_____________________________________________-
可通过“下标” 访问，即键值对访问；或通过迭代器iterator访问元素：set<数据类型1，数据类型2>::iterator it
迭代器有两个参数，first和second，使用方法：迭代器名称 + .first，迭代器名称 + .second
函数：
mp.erase(it) 1.删除一个迭代器it所指的位置 O(1)
2.删除一个值为it的数据 O(log(n))
mp.erase(first,last) 删除迭代器于[first,last)的数据 O(last-first)
mp.size() 当前mp内元素个数（通用） O(1)
mp.empty() 判断mp是否为空（通用） O(n)
mp.clear() 清空当前mp容器 O(n)
mp.begin() 起始迭代器
mp.end() 末尾迭代器
mp.find(data) 在mp中查找data O(log(n))
遍历：
for(auto 迭代器名称 : 容器名){
键：迭代器名称.first
值：迭代器名称.second
}
前缀和
差分
差分是前缀和的逆运算
递归
递归函数自我调用流程图：如果 达到递归边界 那么 结束 否则 继续调用
递推
顺推：从已知条件出发，逐步推出要解决的问题
逆推：___________________________
快速排序
语法如下：
void quick_sort(int a[],int left,int right){
if(left>=right){
return ;
}
int l,r,val=a[left];
while(l<right && a[l]<=val){
l++;
r++;
}
while(r<=right){
while(r<=right && a[r]>=val){
r++;
}
if(r<=right){
swap(a[l],a[r]);
l++;
r++;
}
}
swap(a[left],a[l-1]);
quick_sort(a,left,l-2);
quick_sort(a,l,right);
}
深度优先搜索
例如走迷宫：锁定一个方向一直走，直到不能再走，退回前一个位置，继续尝试其他方向，无其他方向可选，继续退。以此类推...
广度优先搜索
例如走迷宫：从初始状态开始，将第一个开始节点放入队列中。然后弹出这个结点，扩展它能达到的所有结点。将扩展的节点插入到队列末尾。以此类推
适合找出最短路径
树
树是一种非线性的数据结构，是由n(n>=0)个结点组成的有限集合，如果n==0
度：结点所拥有的子树的数量，度为0的结点为叶子结点
二叉树
二叉树是一种度数最大为2的树形结构，每个结点的子结点严格区分左结点和右结点。
若某一二叉除叶子结点外，其他结点的度均为2，且每一层的结点总数达最大值，这种特殊形态的二叉树，称之为满二叉树
任意一棵二叉树，若其叶子结点（度为1结点 ）的数量为n0,度为2的结点数量为n2，则n0与n2 _________________
具有n个结点的完全二叉树的深度为向下取整log2(n)+1
若将一个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1,2,…,n。则若结点编号i=1，则结点i为根无父结点；若i>1，则i的父结点编号为i/2；针对编号为i的结点，其左编号为2*i，其右编号为_________________
二叉树遍历分为：先序遍历（根->左->右）、中序遍历（左->根->右）、后序遍历（左->右->根）
先序遍历：到达结点，直接打印；遍历左子树；遍历右子树；浅入深再深入浅
先序遍历代码如下：
struct node{
char data;
int left,right;
}tree[n];
void preorder(int root){
if(root0){
return ;
}
cout<<tree[root].data<<" ";
preorder(tree[root].left);
preorder(tree[root].right);
}
中序遍历：_____________________________
中序遍历代码如下：
struct node{
char data;
int left,right;
}tree[n];
void preorder(int root){
if(root0){
return ;
}
preorder(tree[root].left);
cout<<tree[root].data<<" ";
preorder(tree[root].right);
}
后序遍历：________________________________
后序遍历代码如下：
struct node{
char data;
int left,right;
}tree[n];
void preorder(int root){
if(root==0){
return ;
}
preorder(tree[root].left);
preorder(tree[root].right);
cout<<tree[root].data<<" ";
}
图
图是一种顶点与边组成的的数据结构______________
无向图：由没有方向的边组成的图，也称为无向网络（双向道路）
单向图：由有方向的边组成的图，也称为有向网络或有向图形（双向道路）。有向边从一个顶点指向另一个顶点，表示一个方向的关系，在有向图中，顶点也称为起点或终点
有权图：边上带有权值的图
权值：可以形象地理解为通过这条边花费的时间、金额等
自环：一条边的两端连接的是同一个顶点
无向完全图：图中任意两个顶点之间都存在边。拥有n个顶点的有向完全图含有n*(n-1)/2条边
有向完全图：图中任意两个顶点之间都存在方向相反的两条边。拥有n个顶点的有向完全图含有n*(n-1)条边
稀疏图：图中的边相对较少，边之间的连接相对稀疏，容易出现有一个点被孤立的情况
稠密图：图中的边相对较多，边之间的连接相对密集
度：指与一个顶点相连的边的数量。在无向图中，一个顶点的度就是它的边的连接数。在有向图中，一个顶点的入度是指向该顶点的边数量，出度是从该顶点出发的边数量
路径：指从______________
环路：指一路径的起点和终点是同一个顶点，且路径上的每个顶点可重复（同一条边可经过多次）
连通性：若某图中任意两个顶点之间都存在路径，则称该图为连通图。若某图不是连通图，则该图可分为多个连通分量
强连通图：指任意两个顶点u和v____________________________
图用邻接矩阵存储（适合有向图）：定义一个一维数组v[]用以存储顶点信息，v[i]表示编号为i的顶点，定义一个二维数组g[][]用以存储图中边信息，g[i][j]表示顶点i到顶点j的边
图用邻接表存储（适合无向图）：数组+动态链表（效率高，可变空间，门槛高）；数组+静态链表（效率高，不可变空间，门槛高）；数组+vector（效率低，可变空间，门槛低），构造一个长度为顶点个数的vector数组g[]，_________________________
有帮助，赞一个