visual c 网站开发,旅游网站建设策划方案,网站建设实例分析,网络运维工程师是做什么的数据结构
前言#xff1a;这个是针对于蓝桥杯竞赛常考的数据结构内容#xff0c;基础算法比如高精度这些会在下期给大家总结
数据结构
竞赛中#xff0c;时间复杂度不能超过10的7次方#xff08;1秒#xff09;到10的8次方#xff08;2秒#xff09;
空间限制#x…数据结构
前言这个是针对于蓝桥杯竞赛常考的数据结构内容基础算法比如高精度这些会在下期给大家总结
数据结构
竞赛中时间复杂度不能超过10的7次方1秒到10的8次方2秒
空间限制int类型数组总大小不能超过3*10的7次方二维数组不能超过5000*5000顺序表就是一个数组加上标记数组中有多少元素的数(n)
eg:尾删就是n--
注意事项在实行插入和删除操作时记得检查数组中有无位置可以进行vector容器创建变量常用的方法中的类型可以换
vectorinta;//搭建一个可变长的数组
vectorinta;//指定好了一个空间大小为N
vectorinta[N];//创建N个vector,vector里存放的是int类型的数据
N个vector用时要eg:a[2].resize(3)存在迭代器的容器才可以用范围for去遍历程序超时一般不考虑是容器的问题
链表的静态实现单链表要头指针下一个元素的分配的位置指针域和数据域 然后下标0位置是哨兵位
注意在进行操作时一直让h为头指针前提h是头指针id是下一个元素分配的位置e[n]是数据域ne[n]是指针域头插一个数据x
将x放在e[id]中 x的右指针指向哨兵位的后继 哨兵位的右指针指向x所在位置遍历链表
for(int i ne[h];i;i ne[i])按值查找
1.遍历链表
2.多次查询并且链表中没有重复数的话可以用哈希表优化在任意位置之后插入元素
(在存储位置p后插入一个元素x)
x放在e[id]里面把x位置指向p后面的位置把p位置指向x删除任意元素之后的元素
(删除存储位置为p后面的元素)
先判断p是不是最后一个元素让p指向下一个元素的下一个元素双向链表
比单链表加了一个前指针域pre[n]头插
x所在位置id左指向哨兵位右指向哨兵位的下一个位置
之后先修改头结点的指针再修改哨兵位的在任意位置之后插入元素
先让x的左指针指向p右指针指向p的后继
先让p的后继的左指针指向id,再让p的右指针指向id在任意位置之前插入元素
先让x的左指针指向p的前驱右指针指向p
先p的前驱的右指针指向x再让p的左指针指向id删除任意位置(q)的元素
将q位置的左右指针那两端缝合在一起就可以了循环列表的话就是让单链表的最后一个位置的右指针指向头结点就可以了栈只允许在栈顶进行数据插入和删除
STL中是stack
进栈和出栈时记得检查空间还有没有有时写一行会好看些
eg
int b st.top();st.pop();队列 特性先进先出 只允许在表尾进行插入操作在表头进行删除操作 树
孩子表示法(用于在无根树中即父子关系不明确因为把与该结点相连的点全部保存下来)
实现方法
1.用vector数组实现
假如树有n个结点的话
创建一个n1大小的vector数组edge[n1]
vectorintedge[n1];
edge[i]中储存着i号结点所连接的结点
对于i的孩子直接edge[i].push_back()进去即可2.用链式前向星(其本质是用数组来模拟链表)实现
用的是双向链表
链式前向星具体怎么实现的自己要知道树的遍历
1.DFS(深度优先遍历)
一条路走到黑 具体流程
1.从根节点出发依次遍历每一棵子树 2.遍历子树的时候,重复第一步
时间复杂度ON2.BFS宽度优先搜索
一层搜索完了再去下一层搞 具体流程(借助队列)
1.初始化一个队列 2.根节点入队同时标记该节点已经入队
3.当队列不为空时拿出队头元素访问然后将队头元素的孩子入队同时打上标记
4.重复3过程直到队列为空
这里标记其实是为了跟图结构那里统一好记这两种方式的时间复杂度都是O(N)
像这种有英文简写的在设置自定义函数时直接写eg:bfs就很不错二叉树 分类满二叉树、完全二叉树等 一般用顺序存储和链式存储 1.顺序存储(一般只用于接近满的二叉树或者满二叉树) 其实就是用数组去存储 规则针对与结点i来说 如果父存在父结点的下标为i/2; 如果左孩子存在其结点下标为i*2; 如果右孩子存在其结点下标位为i*21 2.链式存储: 也是用数组模拟 创建两个数组l[N],r[N]; l[i]表示结点i的左孩子r[i]表示结点i的右孩子 二叉树的遍历
1.DFS:分为三种
先序遍历的顺序根 左 右
中序遍历的顺序左 根 右
后序遍历的顺序左 右 根
先中后其实就是看根被插在哪(一直是左右)
eg自定义命名可以先序遍历dfs1
自己手动模拟的话
先序遍历就是经过一次就行
中序遍历的话就是经过两次才那啥
后序遍历的话就是经过三次2.BFS
跟常规树的方法差不多借助队列堆 1.是完全二叉树 2.要么是大根堆要么是小根堆 存储方式的话一般用顺序储存 优先级队列(即堆)priority_queue
当优先级队列中存储结构体时要重载运算符才行
eg
struct node
{int a,b,c;
//以b为基准定义大根堆
bool operator(const nodex)const
{
return b x.b;}//以b为基准定义小根堆
bool operator(const nodex)const
{
return b x.b;//第一个b是调用的那个数}
当然这里只能要一个}
结构体在里面的使用方法
eg:
priority_queuenodeheap;
heap.push({2,3,4})二叉搜索树的性质(BST的性质) 1.左子树的结点值根结点右子树的结点值 2.左子树和右子树也分别是一颗二叉搜索树 AVL和常规的二叉搜索树很少用一般用STL里面的红黑树 红黑树简称BST其规则 1.左根右 2.根叶黑这里的根节点指最上面那一个{一般都是指这个}叶子结点指的是补为满二叉树时的空结点(最后的叶子结点下面要补上空节点这个建议看一下图) 3.不红红 4.黑路同 5.为二叉搜索树 其的两个性质 1.从根结点到叶结点的最长路径不大于最短路径的两倍(理解) 2.有n个结点的红黑树高度h2log2(n1) 排序的话一般都是用的sort
像插入排序 选择排序 冒泡排序 堆排序 快速排序 归并排序这些没有sort快
sort是综合了三种排序的C中的随机函数
#includectime
srand(time(0));//种下一个随机数种子
b rand();//会生成一个随机值给b
c b%mn//获得的是在[n,mn]的随机数
pair类型的的重命名方式一般是采用eg:两个都是int类型的话就是PII,I为int的首字母的大写
vectorint a[10];
在C中声明了一个数组这个数组有10个元素每个元素都是一个 vectorint 。
每个vectorint里可以存很多个数但是要扩容才行
这种数据结构在需要固定数量的动态数组时非常有用
例如当你有一个固定数量的学生但每个学生的成绩数量不固定时。常见的算法知识
前面的数据先不验从某个相邻(有多少搞多少)开始才逐个向外验
这种题通常要用栈
eg:题目有效的括号(leetcode里面有)、后缀表达式(洛谷里面有)还原字符串中整数的方法
eg:ch 9;t 9-0;常用bool st[N]来表示i这个元素是否已经在了
用此可以解决快速查找i是不是已经在了或者有无被访问过
(在第一次录入时改成true)先进先出数组问题一般用队列去解决
eg:海港(洛谷)处理一个地方不同种人进出时种类个数:
int cnt[N];//cnt[i]表示这个地方第i个种类的有多少个
int kinds;//统计种类个数
cnt[i]从1变成0时kinds--;从0变成1时kinds
例题:海港(洛谷)树的问题一般都要用到递归
堆适合用于每次取出最大或者最小(再将最大或最小衍生的给放进去)想把一组数变成堆的话有两种方法
1.用数组存下这组数然后把数组调整成一个堆
2.创建一个堆然后将这组数依次插入到堆中topK问题
用堆解决
如果是求第k小就用大根堆
1.维护一个大小为k的大根堆
2.对于每次来的元素先进堆再删除堆顶元素此时堆顶元素就是第k小(每个元素都要放进来过)
如果是求第k大就用小根堆...像这种可以用单调性简化问题的题的做法
1.先存认为小的数(怎么写方便怎么来就算跟后面的比又不是特别小了)
2.堆中一般还要存关系量(3要用)
3.将堆顶弹出后搞入与堆顶关系量相近的有时要设置左右护法防止越界访问
eg:做--时 特别是红黑树那里找小于等于x的最大值模加模
解决取模之后的模变成负数的问题(让他变为正数):
(key%NN)%N哈希表常用来解决一个东西有没有重复出现或者重复出现了几次的问题算法题中的经典操作:用空间代替时间模拟得到浮点数的小数部分p
double d 6.5;
int q (int)d;
double p d - q;小数四舍五入成整数的方法
假设a是四舍五入之后的b是四舍五入之前的
有a (int)(b0.5);
数据结构这里常用的头文件和容器以及其接口
这个点的话是C比C语言在解题时优越的地方可以用容器来省略很多过程 而且使用容器的话一般比赛是不会无聊到用容器去卡你的时间也就是说如果超时了大概率不是容器的问题
#includevector
size-返回实际元素个数
empty-返回顺序表是否为空空则返回true非空则返回false
begin-返回起始位置的迭代器
end-返回终点位置的下一个位置的迭代器
push_back-尾部插入一个元素
pop_back-尾部删除一个元素
front-返回首元素
back-返回尾元素
resize-修改vector的大小
clear-清空vector(把大小搞为1)stack容器栈
头文件#includestack
创建:stackTst;//st是变量名可以改T是任意类型的数据
size empty
push:进栈
pop:出栈
top:返回栈顶元素但是不会删除栈顶元素queue(队列)
头文件:#includequeue
创建:queueTq;//q是变量名T是任意类型的数据
size empty push pop
front:返回队头元素但不会删除
back:返回队尾元素但不会删除
不可以用clear来直接清除队列deque(双端队列):
头文件#includedeque
创建-和queue方式一样
size empty front back
push_front头插
push_back尾插
pop_front头删
pop_back尾删
clear清除队列priority_queue(优先级队列)
头文件#includequeue
size empty
push往优先级队列里面添加一个元素(自动排序了)
pop删除优先级最高的元素(也会自动排序)
top获取优先级最高的元素
创建:
priority_queue数据类型,存数据的结构数据之间的比较方式
存数据的结构没写时默认是vector
数据之间比较方式没写时默认是大根堆
如果想改成小根堆数据之间的比较方式这里就要写greater数据类型红黑树
set和multiset的区别:set不能存相同元素multiset可以存相同元素
(其余使用方式完全一致)下面以set举例
头文件:#includeset//multiset也为此
创建setTq//T为任意数据类型q为变量名
size empty begin end
可以用范围for遍历整个红黑树(遍历是按照中序遍历的顺序因此是有序的序列)
insert:向红黑树中插入一个元素(时间复杂度logN)
erase:删除一个元素(时间复杂度:logN)
find:查找一个元素返回的是迭代器(时间复杂度:logN)
count查询元素出现的次数一般用来判断元素是否在红黑树中(时间复杂度:logN)
如果想查找元素是否在set中我们一般使用countcount不是返回的迭代器
lower_bound(x):大于等于x的最小元素返回的是迭代器(时间复杂度logN)
upper_bound(x):大于x的最小元素返回的是迭代器(时间复杂度logN)
如果尝试向 set 中插入相同的元素 set 会忽略后续的插入操作因为 set 中已经存在该元素。红黑树
map和multimap的区别map不能存相同元素multimap可以其余使用方法一样
和set的区别set里面存的一个关键字map里面是一个关键字key 一个与关键字绑定的值value
头文件:#includemap//multimap也为此
创建mapkey,valuemp1
egmapint,vectorintmp2;
size empty begin end erase find count lower_bound upper_bound//跟set使用方法差不多
用范围for遍历时也为中序遍历得到有序的序列
insert:向红黑树中插入一个pair类型的要用{}形式
eg:mp.insert({1,2})
此外map 和multimap重载了[],使其能够像数组一样使用
eg:mp[2]......//...这里的值是value的
但是注意如果用[]插入的时候[]里面的内容不存在于map里会先插入然后再拿值
插入的时候第一个关键字就是[]里面的内容第二个关键字是一个默认值
所以一般要eg:
if(mp.count(赵六)mp[赵六]4)....如果单单后面那个就会插入一个赵六了
找小于等于x的最大值的话要lower_bound的迭代器--即可哈希表
unordered_set 和unordered_multiset
和set的区别set有序unordered_set无序
头文件:#includeunordered_set//unordered_multiset也为此
创建unordered_setTq;
size empty begin end insert erase find count
也可以用范围for遍历但是遍历出来的结果是无序的哈希表:
unordered_map和unordered_multimap
和map的区别以及和map的共同点都和上面一样
除了范围for遍历出来是无序的以外其他都和map的接口用途一样查询库函数和容器用法的网站
查询具体用法https://legacy.cplusplus.com/reference/ 如果对用法还是不会的话可以点击这个链接去查询具体用法
