XP02-DAY06-栈、队列、递归
1、栈
栈的定义格式:stack<数据类型> 栈名;
栈的操作
入栈:push(data);
出栈:pop();
判断栈是否为空:empty();
获取栈顶元素:top();
栈的大小:size();
函数的调用格式:栈名.函数名();
2、队列
队列的定义格式:queue<数据类型> 队列名;
队列的操作
入队:push(data);
出队:pop();
判断队列是否为空:empty();
获取队首元素:front();
获取队尾元素:back();
获取队列大小:size();
函数调用方式:队列名.函数名();
3、递归
//函数内部自己调用自己
1、递归边界
2、递归调用
XP02-DAY07-树与图
树
树是一种非线性的数据结构,族谱就是一棵树
树的存储:双亲表示法、孩子表示法
完全二叉树:除了最后一层以外,其他每一层都是满的,并且最后一层的结点连续靠左
满二叉树:每个结点都有 2 个孩子(除了叶子结点以外)
二叉树:
性质1: 二叉树的第 i 层 最多有 2 ^ (i - 1)
性质2: 深度为 k 的二叉树最多有 2 ^ k - 1
性质3:n0 = n2 + 1
性质4:具有 n 个结点的完全二叉树的深度为 log2(n)向下取整 + 1
性质5:对于一棵完全二叉树从上到下,从左到右从1开始编号,对于 i 号结点来说,它的父结点的编号为 i / 2,它的左孩子的编号为2 * i,右孩子的编号为 2 * i + 1
图
图的分类:
根据有无方向有向图和无向图
根据有无权值带权图和无权图
有向完全图和无向完全图
根据边的数量稀疏图和稠密图
图的存储:
1、邻接矩阵(二维数组)
无向无权图 g[u][v] = g[v][u] = 1
有向无权图 g[u][v] = 1
无向带权图 g[u][v] = g[v][u] = z
有向带权图 g[u][v] = z
2、邻接表(vector)
无向无权图 g[u].push_back(v),g[v].push_back(u);
有向无权图 g[u].push_back(v)
无向带权图 g[u].push_back({v,z}),g[v].push_back({u,z});
有向带权图 g[u].push_back({v,z})
3、vector<dataType> 数组名;
vector<int> v;//表示定义了一个空的数组v
vector<int> v(10);//表示定义一个大小为10的数组,里面的值为0
vector<int> v(10,1e9);//表示定义一个大小为10的数组,里面的值为100
for(int i = 0;i < v.size();i++) cout << v[i] << " ";
for(int i : v) cout << i << " ";
for(auto i : v) cout << i << " ";
XP02-DAY08~09-深度优先搜索、广度优先搜索
深度优先搜索(暴力枚举)
深度优先搜索是一种搜索算法,搜索方式是:不撞南墙不回头,一条路走到黑
迷宫中的可达性问题
//题目场景:给出一个迷宫,给定一个起点和终点,问能否从起点走到终点
void dfs(int x,int y){
if(x == fx && y == fy){
flag = 1;
return;
}
for(用当前坐标去扩散一层){
判断周围点是否符合题目要求(是否越界、是否访问过、是不是障碍物)
标记新的点已经访问
dfs(nx,ny);
}
}
迷宫中的方案数问题
//题目场景:给出一个迷宫,给定一个起点和终点,问起点走到终点的方案数
void dfs(int x,int y){
if(x == fx && y == fy){
方案数++;
return;
}
for(用当前坐标去扩散一层){
判断周围点是否符合题目要求(是否越界、是否访问过、是不是障碍物)
标记新的点已经访问
dfs(nx,ny);
标记新的点未访问
}
}
广度优先搜索的概念
广度优先搜索是一种搜索算法,搜索方式是:一层一层往外扩散
迷宫中的可达性问题
//题目场景:给出一个迷宫,给定一个起点和终点,问能否从起点走到终点
bool bfs(int sx,int sy){
1、定义结构体类型的队列
2、起点入队
3、标记起点已经访问
4、
while(!q.empty()){
5、获取队首
6、队首出队
7、判断队首是否是终点,是终点就直接return true
8、
for(用队首去扩散一层){
判断周围点是否符合题目要求(是否越界、是否访问过、是不是障碍物)
新的点入队
标记新的点已经访问
}
}
9、return false;
}
迷宫中的最短路径
//题目场景:给出一个迷宫,给定一个起点和终点,问从起点走到终点最少需要几步?
int bfs(int sx,int sy){
1、定义结构体类型的队列 (增加step步数的属性)
2、起点入队
3、标记起点已经访问
4、
while(!q.empty()){
5、获取队首
6、队首出队
7、判断队首是否是终点,是终点就直接return t.step;
8、
for(用队首去扩散一层){
判断周围点是否符合题目要求(是否越界、是否访问过、是不是障碍物)
新的点入队 (nx,ny,t.step + 1)
标记新的点已经访问
}
}
9、return -1;
}