首页 > 软件开发 > 软件开发

软件开发2021-5-22-PM学习笔记(SET红黑树、PAIR、MAP遍历)

admin 软件开发 2021-05-25 09:25:30
后台-系统设置-扩展变量-手机广告位-内容正文底部

一)红黑数

1、set基本函数

//set自带去重的有序集合
set <int> st;//定义一个整形集合
st.begin();		//集合第一个元素地址
st.rbegin();	//集合最后一个元素地址
st.insert():	//插入数据
st.size();		//获取集合长度
st.erase();		//删除指定元素

2、实例代码

#include<bits/stdc++.h>
using namespace std;
set <string> st;
int main(){
    int n=5;
    while(n--){
        st.insert(str);
    }
	cout<<*st.brgin()<<endl;
	//最小值 O(1)
	cout<<*st.rbegin()<<endl;
	//最大值 O(1)
	cout<<st.size()<<endl;
	//集合长度O(st.size())
	
	return 0;
}

二)map键值对

1、基本函数

map<int,int> m;

2、实例代码

#include<bits/stdc++.h>
using namespace std;
map<string,string> m;
int main()
{
    // ID to 姓名
    int n; cin >> n;
    for (int i = 1 ; i <= n ; i++){
        string id , name;
        cin >> id >> name;
        // 插入一个键值对
        // id 相同 相当于修改
        // id 不同 相当于插入
        m[id] = name;
    }
    // 假设我们有q次询问.每次询问一个id,问他的姓名
    int q; cin >> q;
    for (int i = 1 ; i <= q ; i++){
        string id ; cin >> id;
        if (m.find(id) == m.end()){
            cout << "没有此id" << endl;
            continue;
        }
        cout << m[id] <<endl;
    }
    return 0;
}

三)Pair

1、基本函数

pair<int ,int> p;
p=make_pair(x,y);
p.first;	//访问第一个元素
p.second;	//访问第二个元素

2、实例代码

#include<bits/stdc++.h>
using namespace std;

map<pair<int,int>,int>m;
int main()
{
  int n,m;
  cin >> n;
  while(n--){
  	cin>> x >> y >> z;
  	m[make_pair(x,y)]=z;
  }
  cin >> m;
  while(m--){
  	cin >> x >> y;
  	cout << m[make_pair(x , y)] << endl;
  }
  return 0;
}

四)IO流提升输入速度

 ios::sync_with_stdio(false);

五)存图

1、点少/邻接矩阵

a[x][y]=c;

2、点多,边无限

vector < int> e[1000];				//不带权值
vector < pair<int ,int> > e[1000];	//带权值
//e一维数组,e[i]动态数组

六)图的遍历

1、DFS深度优先遍历
PS:递归三要素:1做什么 2递归出口 3转移

#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
vector<int> e[maxn];
int bk[maxn]; // 某个点是否被访问
// 任务:输出所有可能的简单路径(不含环)
vector<int> way; // 记录当前的访问路径
void dfs(int u/*现在在哪个点*/)
{
    bk[u] = 1; // 该点已经被访问过了
    way.push_back(u);
    bool ok = false;
    for (auto v : e[u]){
        if (bk[v] == 1) continue;
        dfs(v);
        ok = true;
    }
    // 无路可走
    if (ok == false){
        for (auto g : way)
            cout << g << " ";
         cout << endl;
    }
    bk[u] = 0; // 返回之前,将改点置为0
    way.pop_back();
    return ;
}
int main()
{
    int n , m; cin >> n >> m;
    for (int i = 1 ; i <= m ; i++){
        int x , y; cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1);
    return 0;
}

文章来源:https://blog.csdn.net/jasdasdhja/article/details/117161371

后台-系统设置-扩展变量-手机广告位-内容正文底部
版权声明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,未经许可,不得转载。
本文地址:https://www.jcdi.cn/ruanjiankaifa/30749.html

留言与评论(共有 0 条评论)
   
验证码:
后台-系统设置-扩展变量-手机广告位-评论底部广告位

教程弟

https://www.jcdi.cn/

统计代码 | 京ICP1234567-2号

Powered By 教程弟 教程弟

使用手机软件扫描微信二维码