开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 《算法笔记》第六章学习(上) -> 正文阅读

[数据结构与算法]《算法笔记》第六章学习(上)

1.vector学习

1.1vector定义

    vector<int> name1;
    vector<char> name2;
    vector<double> nanme3;
    vector<node>name;
    vector<vector<int>> name4;

1.2 vector 容器内元素的访问

通过下标访问

vi[0];

通过迭代器访问

    vector<int> vi;
    for(int i =1;i<=5;i++){
        vi.push_back(i);
    }
    vector<int>::iterator it = vi.begin();
    for(int i =0;i<5;i++){
        printf("%d %d",*(it+i),vi[i]);
    }

迭代器方法2

    vector<int> vi;
    for(int i =1;i<=5;i++){
        vi.push_back(i);
    }
    for(vector<int>::iterator it = vi.begin();it!=vi.end();it++){
        printf("%d ",*it);
    }

1.3 vector常用函数实例解析

push_back():就是在vector后面添加一个元素，时间复杂度为O(1).

    vector<int> vi;
    for(int i =1;i<=5;i++){
        vi.push_back(i);
    }

pop_back()可以删除vector的尾元素，时间复杂度为O(1)

    vi.pop_back();
    for(int i = 0;i<vi.size();i++){
        printf("%d ",vi[i]);
    }

size()用来获得vector中元素的个数，时间复杂度为O(1),size()返回的是unsigned类型，

vi.size()

clear()用来清空vector中所有元素，时间复杂度为O(N),其中N为vector元的个数

    vi.clear();

insert(it,x)用来向vector的任意迭代器it处插入一个元素x，时间复杂度O(N);

    vector<int> vi;
    for(int i =1;i<=5;i++){
        vi.push_back(i);
    }
    for(int i = 0;i<vi.size();i++){
        printf("%d ",vi[i]);
    }
    printf("\n");
    vi.insert(vi.begin()+2,-5);
    for(int i = 0;i<vi.size();i++){
        printf("%d ",vi[i]);
    }

erase()有两种用法，删除一个区间内的所有元素，时间复杂度均为O(N)
①删除单个元素
erase(it)即删除迭代器为it处的元素

    vector<int> vi;
    for(int i =5;i<=9;i++){
        vi.push_back(i);
    }
    vi.erase(vi.begin()+3);
    for(int i = 0;i<vi.size();i++){
        printf("%d ",vi[i]);
    }

②删除区间内元素

    vector<int> vi;
    for(int i =0;i<=9;i++){
        vi.push_back(i);
    }
    vi.erase(vi.begin()+3,vi.end()-2);
    for(int i = 0;i<vi.size();i++){
        printf("%d ",vi[i]);
    }

在这里插入图片描述
如果要用区间内删除元素

vi.erase(vi.begin(),vi.end());

在这里插入图片描述

1.4 vector的常见用途

(1)储存数据
①vector本身可以作为数组使用，而且在一些元素个数不确定的长河可以很好地节省空间
②有些场合需要根据一些条件把部分数据输出在同一行，数据中间用空格隔开，由于输出数据的个数是不确定的，为了更方便地处理最后一个满足条件的数据后面不输出额外的空格，可以先用vector记录所有需要输出的数据，然后一次性输出。
(2)用领接表储存图
使用vector实现邻接表可以让一些对指针不太熟悉的读者有一个比较方便的写法。

2.set学习

内部自动有序且不含重复元素的容器，在考试中，有可能出现需要去掉重复元素的情况

2.1 set的定义

	set<typename>
    set<int> name;
    set<double> name1;
    set<char>name3;
    set<node>name

set数组的定义

set<int> a[10];

set容器内元素的访问
set只能通过迭代器(iterator)访问

    set<typename> s1;
    set<int> se;
    set<int>::iterator it;

由于除了vector和string之外的stl容器都不支持*(it+i)的访问方式，因此只能用枚举

set<int>st;
    st.insert(3);
    st.insert(5);
    st.insert(2);
    st.insert(3);
    for(set<int>::iterator it=st.begin();it!=st.end();it++){
        printf("%d\n",*it);

    }

在这里插入图片描述
结果发现，自动递增，去除重复，
insert()
insert()将x插入set容器中，并自动递增排序去重，时间复杂度O(logN),其中N为set内的元素个数。
find()
find(value)返回set对应值为value的迭代器，时间复杂度为O(logN);

 printf("%d",*(st.find(2)));

在这里插入图片描述
跟vector一样，可以删除单个也可以一个区间内的所有元素
①删除单个元素
删除单个元素有两种方法
st.erase(it),it为需要删除元素的迭代器，时间复杂度为O(1).
st.erase(value),value为所需要删除元素的值，时间复杂度为O(logN),N为set内的元素个数。
②删除一个区间内的所有元素
st.erase(first,last)可以删除一个区间内的所有元素，其中first为所需要删除区间起始迭代器，而last则为所需要删除区间的末尾迭代的下一个地址，也即为删除[first,last),时间复杂度为O(last-first)

    set<int>st;
    st.insert(100);
    st.insert(200);
    st.insert(300);
    st.insert(200);
    set<int>::iterator it = st.find(200);
    st.erase(it,st.end());
    for(it=st.begin();it!=st.end();it++)
        printf("%d ",*it);

    return 0;

在这里插入图片描述

size()

size()用来获得set内元素的个数，时间复杂度为O(1)

    set<int>st;
    st.insert(100);
    st.insert(200);
    st.insert(300);
    st.insert(200);
    printf("%d\n",st.size());

在这里插入图片描述

clear()

clear()用来清空set中的所有元素，复杂度为O(N),其中N为set内元素的个数。

    st.clear();
    printf("%d\n",st.size());

在这里插入图片描述

set的常见用途

set最主要作用是自动去重并按升序排序，因此碰到需要去重但是却不方便直接开数组的情况，可以尝试用set解决。
延伸：set中元素是唯一的，如果需要处理不唯一的情况，则需要使用multiset。另外C++11标准中还在增加了unordered_set，以散列代替set内部的红黑树实现，使其可以用来处理只去重但不排序的需求，速度比set要快得多。

3.string的用法

3.1 string访问

    string str = "bacd";
    for(int i =0;i<str.length();i++)
        printf("%c",str[i]);
    return 0;

如果读入和输出整个字符串，则只能用cin和cout

    string str;
    cin >> str;
    cout << str;

用c_str()将string类型转化为字符数组进行输出

    string str;
    cin >> str;
    printf("%s\n",str.c_str());

用迭代器访问

    string str;
    cin >> str;
    for(string::iterator it=str.begin();it!=str.end();it++){
        printf("%c",*it);
    }

string和vector一样，支持直接对迭代器进行加减某个数字，如str.begin()+3的写法是可行的。

3.2 operator+=

将两个string直接拼接起来

    string str1 = "abc",str2="xyz",str3;
    str3 = str1+str2;
    str1+= str2;
    cout << str1 << endl;
    cout << str3 << endl;

在这里插入图片描述

3.3 compare operator

两个string类型可以直接使用==,!=，<,>,<=,>=比较大小，比较规则是字典序

    string str1 = "aa";
    string str2 = "aaa";
    string str3 = "abc";
    string str4 = "xyz";
    if(str1 < str2) printf("ok1\n");//如果str1字典序小于str2，输出ok1
    if(str1 != str3) printf("ok2\n");//如果str1和str3不等,输出ok2
    if(str4 >= str3) printf("ok3\n");//如果str4字典序大于等于str3,输出ok3
    return 0;

在这里插入图片描述

3.4 length()/size()

length返回string的长度，即存放的字符数，时间复杂度O(1),size()与length()基本相同

    string str2 = "aaa";
    cout << str2.length() << " " << str2.size() << endl;

在这里插入图片描述

3.5 insert()

string 的insert()函数有多种写法，时间复杂度O(N)。
①insert(pos,string),在pos号位置插入字符串string

    string str2 = "aaa";

    str2.insert(1,str2);
    cout << str2;
    return 0;

在这里插入图片描述
②insert(it,it2,it3),it为原字符串的欲插入位置，it2和it3为待插字符串的首尾迭代器，用来表示串[it2,it3)将被插在it的位置上。

    string str = "abcxyz",str2="opq";
    str.insert(str.begin()+3,str2.begin(),str2.end());
    cout << str << endl;

在这里插入图片描述

3.6 erase()

删除单个元素或者删除一个区间内的所有元素.时间复杂度为O(N).
①删除单个元素
st.erase(it),它是一个迭代器。

    string str = "abcdefg",str2="opq";
    str.erase(str.begin()+4);
    cout << str << endl;

在这里插入图片描述

②删除一个区间内的所有元素
str,erase(first,last)其中first为需要删除的区间的起始迭代器，而last则为需要删除的区间的末尾迭代器的下一个地址，也即为删除[first,last)

    string str = "abcdefg";
    str.erase(3,2);
    cout << str << endl;

在这里插入图片描述

3.7 clear()

可以清空string中的数据，时间复杂度一般为O(1)

    string str = "abcdefg";
    str.clear();
    cout << str.length() << endl;
    return 0;

在这里插入图片描述

3.8 substr()

sub(pos,len)返回从pos号位开始，长度为len的子串，时间复杂度为O(len).

    string str = "Thank you for your smile.";
    cout << str.substr(0,5) << endl;
    cout << str.substr(14,4) << endl;
    cout << str.substr(19,5) << endl;

在这里插入图片描述

3.9 string::npos

string::npos是一个常数，其本身的值为-1,但由于是unsigned_int 类型，因此实际上也可以认为是unsigned_int 类型最大值,string::npos用以作为find()函数失配时的返回值，可以是-1或者4294967295.

    if(string::npos==-1){
        cout << "-1 is true." << endl;
    }
    if(string::npos == 4294967295){
        cout << "4294967295 is also true." << endl;
    }

    return 0;

在这里插入图片描述

3.10 find()

str.find(,str2)，当str2是str的子串，返回其在str中第一次出现的位置；如果1str2不是str的子串，那么返回string::npos;
str.find(str2,pos),从str的pos号位开始匹配str2,返回值与上相同。
时间复杂度O(nm),其中n和m分别为str和str2长度

string str = "Thank you for your smile";
    string str2 = "you";
    string str3 = "me";
    unsigned int  pos = string::npos;
    if(str.find(str2) != string::npos){
        cout << str.find(str2) << endl;
    }
    if(str.find(str2,7) != pos){
        cout << str.find(str2,7) << endl;
    }
    if(str.find(str3) != pos){
        cout << str.find(str3)<<endl;
    }else{
        cout << "I know there is no position for me"<< endl;
    }

在这里插入图片描述

3.11 replace()

str.replace(pos,len,str2)把str从pos号位开始长度为len的子串替换为str2
str.replace(it1,it2,str2)把str的迭代器[it1,it2)范围的子串替换为str2
时间复杂度为O(str.length())

    string str = "Maybe you will turn around.";
    string str2 = "will not";
    string str3 = "surely";
    cout << str.replace(10,4,str2) << endl;
    cout << str.replace(str.begin(),str.begin()+5,str3) << endl;
    return 0;

在这里插入图片描述

4. map

map可以将任何基本类型(包括stl容器)映射到任何基本类型(包括stl容器)，也就可以建立string类型到int型的映射。

4.1 map的定义

map需要确定映射前类型(键key)和映射后类型(值value)，所以需要在<>内填写两个类型，其中第一个是键的类型，第二个是值的类型，如果是int型映射到int类型，就相当于是普通的int型数组。

    map<typename1,typename2>map;

如果是字符串到整型的映射，必须使用string而不能用char数组。这是因为char数组作为数组是不能作为键值，如果想用字符串做映射，必须用string


    map<string,int>str;
    map<set<int>,string>mp;

4.2 map容器内元素的访问

下标访问或者迭代器访问。

    map<char,int>mp;
    mp['c']= 20;
    mp['c'] = 60;
    printf("%d",mp['c']);

在这里插入图片描述
map迭代器的使用方式和其他STL容器的迭代器不同，因为map每一对映射都有两个typename，这决定了必须能通过it来同时访问键和值，事实上，map可以使用it->first,来访问键，使用it->second来访问值.

    map<char,int>mp;
    mp['m']= 20;
    mp['r'] = 40;
    mp['a'] = 60;
    for(map<char,int>::iterator it=mp.begin();it!=mp.end();it++){
        printf("%c %d\n",it->first,it->second);
    }
    return 0;

在这里插入图片描述

4.4 常用函数

find()

find(key)返回键为key的映射的迭代器，时间复杂度为O(logN),N为map中映射的个数.

    map<char,int>mp;
    mp['m']= 20;
    mp['r'] = 40;
    mp['a'] = 60;
    map<char,int>::iterator it = mp.find('r');
    printf("%c %d\n",it->first,it->second);

在这里插入图片描述

erase()

删除单个元素，删除一个区间内的所有元素
①删除单个元素有两种方法
mp.erase(it),it为需要删除的元素的迭代器，时间复杂度为O（1）

    map<char,int>mp;
    mp['m']= 20;
    mp['r'] = 40;
    mp['a'] = 60;
    map<char,int>::iterator it = mp.find('a');
    mp.erase(it);
    for(map<char,int>::iterator it =mp.begin();it!=mp.end();it++){
        printf("%c %d\n",it->first,it->second);
    }

在这里插入图片描述
mp.erase(key),key为欲删除的映射的键，时间复杂度为O(logN),N为map内元素的个数

map<char,int>mp;
mp['m']= 20;
mp['r'] = 40;
mp['a'] = 60;
map<char,int>::iterator it = mp.find('a');
mp.erase('a');
for(map<char,int>::iterator it =mp.begin();it!=mp.end();it++){
 	printf("%c %d\n",it->first,it->second);
}

在这里插入图片描述
②删除一个区间内的所有元素
map.erase(first,last),其中first为需要删除的区间的起始迭代器，而last则为需要删除的区间的末尾迭代器的下一个地址，也即为删除左闭右开的区间[first,last)时间复杂度为O(last-first)

 map<char,int>mp;
 mp['m']= 20;
 mp['r'] = 40;
 mp['a'] = 60;
 map<char,int>::iterator it = mp.find('r');
 mp.erase(it,mp.end());
 for(map<char,int>::iterator it =mp.begin();it!=mp.end();it++){
     printf("%c %d\n",it->first,it->second);
 }

size()

size()用来获得map映射的对数，时间复杂度为O(1)

    map<char,int>mp;
    mp['m']= 20;
    mp['r'] = 40;
    mp['a'] = 60;
    printf("%d\n",mp.size());

在这里插入图片描述

clear()

用来清空map中的所有元素，复杂度为O(N),其中N为map中元素的个数

    mp['m']= 20;
    mp['r'] = 40;
    mp['a'] = 60;
    mp.clear();
    printf("%d\n",mp.size());

在这里插入图片描述

map常见用途

需要建立字符(或字符串)与整数之间映射的题目，使用map可以减少代码量
判断大整数或者其他类型数据是否存在的题目，可以把map当bool数组用
字符串和字符串映射有可能会遇到。

延伸;map的键和值是唯一的，而如果一个键需要对应多个值，就只能用multimap，另外c++11标准增加了unordered_map 以散列代替map内部的红黑树实现，使其可以用来处理只映射而不安key排序的需求，速度比map快得多。

5.queue用法

5.1 queue定义

    queue<int>q;

5.2 queue容器内元素的访问

由于队列queue本身就是一种先进先出的限制性数据结构，因此在STL中只能通过front()来访问队首元素，或是通过back()来访问队尾元素

    queue<int>q;
    for(int i =1;i<=5;i++){
        q.push(i);//push(i)用以将i压入队列，因此依次入队
    }
    printf("%d,%d\n",q.front(),q.back());
    return 0;

在这里插入图片描述

5.3 常用函数解析

push()

push(x)将x进行入队，时间复杂度为O(1)

front(),back()

front()和back()可以分别获得队首元素和队尾元素，时间复杂度为O(1)

pop()

pop()令队首元素出队，时间复杂度为O(1)

   queue<int>q;
    for(int i =1;i<=5;i++){
        q.push(i);//push(i)用以将i压入队列，因此依次入队
    }
    for(int i =1;i<=3;i++){
        q.pop();
    }
    printf("%d,%d\n",q.front(),q.back());
    return 0;

在这里插入图片描述

empty()

empty()检测queue是否为空,返回true则空，返回false则非空，时间复杂度为O(1)

    queue<int>q;
    if(q.empty() == true){
        printf("Empty\n");
    }else{
        printf("No Empty\n");
    }
    q.push(1);
    if(q.empty() == true){
        printf("Empty\n");
    }else{
        printf("No Empty\n");
    }
    return 0;

在这里插入图片描述

size()

size()返回queue内元素的个数，时间复杂度为O(1)

 queue<int>q;
    for(int i =1;i<=5;i++){
        q.push(i);
    }
    printf("%d\n",q.size());
    return 0;

在这里插入图片描述

5.4 queue的常见用途

当需要实现广度优先搜索是时，可以不用自己手动实现一个队列，而不是用queue作为代替，以提高程序的正确性。另外有一点注意的是，使用front()和pop()函数1前，必须用empty()判断队列是否为空，否则可能因为队空出现错误
延伸:STL的容器中还有两种容器跟队列有关，分别是双端队列(deque)和优先队列(priority_queue)，前者是首尾都可插入和删除的队列，后者是使用堆实现的默认将当前队列最大元素置于队首的容器。

6 priority_queue

6.1priority_queue的定义

记得使用#include<queue>，

priority_queue<typename> name;

6.2 priority_queue 容器内元素的访问

和队列不一样的是，优先队列没有front()函数与back()函数,而只能通过top()函数来访问队首元素(也可以称为堆顶元素)，优先级最高的元素

    priority_queue<int>q;
    q.push(3);
    q.push(4);
    q.push(1);
    printf("%d\n",q.top());
    return 0;

在这里插入图片描述

6.3 priority_queue常用函数

push()

push(x)将令x入队，时间复杂度为O(logN),其中N为当前优先队列中的元素个数

top()

top()可以获得队首元素即堆顶元素，时间复杂度为O(1)

pop()

pop()令队首元素(即堆顶元素)出队，时间复杂度为O(logN),其中N为当前优先级队列中的元素个数。

    priority_queue<int>q;
    q.push(3);
    q.push(4);
    q.push(1);
    printf("%d\n",q.top());
    q.pop();
    printf("%d\n",q.top());

在这里插入图片描述

empty()

empty()检测优先队列是否为空，返回true则空，返回false则非空，时间复杂度为O(1)

    priority_queue<int>q;
    if(q.empty() == true){
        printf("Empty\n");
    }else{
        printf("Not Empty\n");
    }
    q.push(1);
    if(q.empty() == true){
        printf("Empty\n");
    }else{
        printf("Not Empty\n");
    }

在这里插入图片描述

size()

size()返回优先队列内元素的个数，时间复杂度为O(1)

    priority_queue<int>q;
    q.push(3);
    q.push(4);
    q.push(1);
    cout << q.size();

在这里插入图片描述

6.4 优先队列元素优先级设置

    priority_queue<int,vector<int>,less<int>>q;

尖括号多两个参数，一个是vector,另一个是less,其中vector也就是第二个参数填写的是承载底层数据结构堆(heap)的容器，如果第一个参数是double型或char型，则此处只需要填写vector·<double>或·vevector<char>·而第三年个参数less <int> 则是对第一个参数的比较累，less<int>表示数字大的优先级越大，而gerater<int>表示数字小的优先级越大
因此，如果想让优先队列总是把最小的元素放在队首，只需进行如下定义

    priority_queue<int,vector<int>,greater<int>>q;

    priority_queue<int,vector<int>,greater<int>>q;
    q.push(3);
    q.push(4);
    q.push(1);
    printf("%d",q.top());
    return 0;

在这里插入图片描述
水果的价格，如果想要以价格低的水果为优先级高，那么只需要把return中的小于号改为大于号

struct fruit{
    string name;
    int price;
    friend bool operator < (fruit f1,fruit f2){
        return f1.price>f2.price;
    }
}f1,f2,f3;
    priority_queue<fruit> q;
    f1.name = "pairs";
    f1.price = 3;
    f2.name = "pears";
    f2.price = 4;
    f3.name = "apple";
    f3.price = 1;
    q.push(f1);
    q.push(f2);
    q.push(f3);
    cout << q.top().name << " " << q.top().price << endl;

在这里插入图片描述
当然也可以用第二种方式进行定义水果价格

struct fruit{
    string name;
    int price;

}f1,f2,f3;
struct cmp{
    bool operator () (fruit f1,fruit f2){
        return f1.price > f2.price;
    }
};
int main()
{


    priority_queue<fruit,vector<fruit>,cmp> q;
    f1.name = "pairs";
    f1.price = 3;
    f2.name = "pears";
    f2.price = 4;
    f3.name = "apple";
    f3.price = 1;
    q.push(f1);
    q.push(f2);
    q.push(f3);
    cout << q.top().name << " " << q.top().price << endl;

    return 0;

}

即使基本数据类型或者其他STL容器，也可以通过同样的方式来定义优先级，如果结构体内的数据较为庞大的，建议使用引用来提高效率，此时比较类的参数中需要加上"const和“&”如下所示

#include<queue>
using namespace std;
struct fruit{
    string name;
    int price;
//    friend bool operator < (const fruit &f1,const fruit &f2){
//        return f1.price > f2.price;
//    }
}f1,f2,f3;
struct cmp{
    bool operator() (const fruit &f1,const fruit &f2){
        return f1.price >f2.price;
    }
};
int main()
{

//    priority_queue<fruit>q;
    priority_queue<fruit,vector<fruit>,cmp> q;
    f1.name = "pairs";
    f1.price = 3;
    f2.name = "pears";
    f2.price = 4;
    f3.name = "apple";
    f3.price = 1;
    q.push(f1);
    q.push(f2);
    q.push(f3);
    cout << q.top().name << " " << q.top().price << endl;

    return 0;

}