Faith学习笔记：算法入门（二）

科技2025-02-08 13

算法入门（二）STL和基本数据结构

一、容器1. vector2.栈和stack3.队列和queue4.优先队列和priority_queue5.链表和list6.set7.map 二、sort()1.sort()的比较函数2.相关函数三、next_permutation

一、容器

顺序式容器 vector：动态数组，从末尾能快速插入与删除，直接访问任何元素list：双链表，从任何地方快速插入与删除deque: 双向队列，从前面或后面快速插入与删除，直接访问任何元素priority_queue: 优先队列，最高优先级元素总是第一个出列stack：栈后进先出关联式容器 set:集合，快速查找，不允许重复值multiset：快速查找，允许重复值map：一对一映射，基于关键字快速查找，不允许重复值multimap：一对多映射，基于关键字快速查找，允许重复值

1. vector

定义 // 定义int 型数组 vector<int> a //默认初始化，a为空 vector<int> b(a) //用a定义b vector<int> a(100) //a有100个值为0的元素 vector<int> a(100,6) //100个值为6的元素 //定义string型数组 vector<string> a(10,"null") //10个值null的元素 vector<string> a(10,"hello") //10个值为hello的元素 vector<string> b(a.begin(),a.end()) //b是a的复制 //定义结构型数组 struct point{ int x, y;}; // a用来存坐标 vector<point> a; 常用操作 //在尾部添加元素 a.push_back(100) //元素个数 int size = a.size() //判断是否为空 bool isEmpty = a.empty() //打印第一个元素 cout<<a[0]<<endl //在第i个元素前面插入k a.insert(a.begin()+i,k) //尾部插入值为8的元素 a.push_back(8); //尾部插入10个值为5的元素 a.insert(a.end(),10,5) //删除末尾元素 a.pop_back() //删除区间【i,j-1】的元素 a.erase(a.begin()+i,a.begin()+j) //删除第3个元素 a.erase(a.begin()+2) //数组大小变为n a.resize(n) //清空 a.clear() //用函数reverse()翻转数组 reverse(a.begin(),a.end()) //用函数sort()排序，从小到大排 sort(a.begin(),a.end())

2.栈和stack

导入头文件 #include<stack> 栈有关的操作 //定义栈，Type为数据类型,例如int、float、char stack<Type> s; //把item放到栈顶 a.push(item); //返回栈顶的元素，但不会删除 a.top() //删除栈顶的元素，但不会返回，在出栈时需要进行两步操作，即先top() //获取栈顶元素，再pop()删除栈顶元素 s.pop() //返回栈中元素的个数 s.size() //检查栈是否为空，如果为空，返回true,否则返回false s.empty()

3.队列和queue

导入头文件 #include<queue> 队列有关操作 //定义栈，Type为数据类型,例如int、float、char queue<Type> q //把item放进队列 q.push(item) //返回队首元素，但不会删除 q.front() //删除队首元素 q.pop() //返回队首元素 q.back() //返回元素个数 q.size() //检查队列是否为空 q.empty()

4.优先队列和priority_queue

优先队列有关操作 //返回具有最高优先级的元素值，但不删除该元素 q.top //删除最高优先级元素 q.pop() //插入新元素 q.push(item)

5.链表和list

list和vector的优缺点正好相反，它们的应用场景不同

vector：插入和删除操作少，随机访问元素频繁list：插入和删除频繁，随机访问较少

6.set

STL的set用二叉搜索树实现，特别是处理数据

set有关操作

//定义 set<Type> A //把item放进set A.insert(item) //删除元素item A.erase(item) //清空set A.clear() //判断是否为空 A.empty() //返回元素个数 A.size() //返回一个迭代器，指向键值k A.find(k) //返回一个迭代器，指向键值不小于k的第一个元素 A.lower_bound(k) //返回一个迭代器，指向键值大于k的第一个元素 A.upper_bound(k)

7.map

map是关联容器，它实现从键（key）到值（value）的映射。 map的操作

//定义 map<string,int> student //赋值 student["Tom"] = 15 //查找 a = student["Tom"]

二、sort()

1.sort()的比较函数

sort()可以用自定义的比较函数进行排序，也可以用系统的4种函数排序，即less()、greater()、less_equal()、greater_equal()

sort()的基本操作

#include<std/stdc++.h> using namespace std; bool my_less(int i, int j) {return(i<j);} bool my_greater(int i, int j) { return (i>j);} int main(){ vector<int> a = {3,7,2,5,6,8,5,4}; sort(a.begin(),a.begin()+4); sort(a.begin(),a.end()); sort(a.begin(),a.end(),less<int>()); sort(a.begin(),a.end(),my_less); sort(a.begin(),a.end(),greater<int>()); sort(a.begin(),a.end(),my_greater); for(int i=0;i<a;i++){ cout<<a[i]<<" " } return 0; }

2.相关函数

stable_sort()：当排序元素相等时，保留原来的顺序partial_sort()：局部排序，可以直接输出。

三、next_permutation

排列组合函数next_permutation()。例如3个字符a、b、c组成的序列， next_permutation()能按字典书序返回6个组合, 即abc、acb、bac、bca、cab、cba