【数据结构刷题复习】

1、vector的insert函数用法

vector> s;
s[a-1].insert(s[a-1].end(),s[b-1].begin(),s[b-1].end());
//将s[b-1]插入到s[a-1]尾部

2、set：

插入元素：

set s;
s.insert(2);

删除元素：

s.erase(2);

判断某元素是否出现在set中，是则返回1，否则返回0：

s.count()

通过迭代器去访问set中的元素：

for(set::iterator it=s.begin();it!=s.end();it++)
{
    cout<<(*it)< 
 
3、 map：
 
 
 
 
 查找关键字：
 
dict.count("Mary")
 
 
 
 元素版本的遍历方法：
 
//2022.06.20
#include
using namespace std;
int main()
{
    int N;
    map> s;
    cin>>N;
    for(int i=0;i>fruit>>place>>num;
        map tmp=s[place];//注意等号右侧部分要写！
        tmp[fruit]+=num;
        s[place]=tmp;
    }
    for(auto iter:s)//注意这种元素的书写方式，与迭代器有区别
    {
        cout< 
 4、队列
 
访问队首元素：q.front()
 
访问队尾元素：q.back()
 
5、优先队列
 
输出从大到小，队首是top()
 
 
 6、并查集
 
初始化：
 
void init()
{
    for(int i=1;i<=n;i++)
    {
        father[i]=i;
    }
}
 
 查找：
 
int get(int x)
{
    if(father[x]==x)
        return x;
    return father[x]=get(father[x]);//路径压缩
}
 
合并：
 
void merge(int x, int y)
{
    x=get(x);
    y=get(y);
    if(x!=y)
    {
        father[y]=x;
    }
}
 
带权并查集
 
 
初始化：
 
void init()
{
    for(int i=1;i<=n;i++)
    {
        father[i]=i;
        dist[i]=0;
        size[i]=1;
    }
}
 
 查找：注意带权并查集的路径压缩方式和普通并查集的路径压缩方式不一样！！要分部写！！要不然会出错！！
 
int get(int x)
{
    if(father[x]==x)
        return x;
    int y=father[x];
    father[x]=get(y);
    dist[x]+=dist[y];//写在递归之后！！
    return father[x];
    //dist[x]+=dist[father[x]]; no
    //return father[x]=get(father[x]); no
    //这里的get一定要分部写 
 
合并：
 
void merge(int x,int y)
{
    x=get(x);
    y=get(y);
    if(x!=y)
    {
        father[y]=x;
        dist[y]=size[x];
        size[x]+=size[y];
    }
}