[数据结构与算法]程序设计与算法（一）C语言程序设计

第十一周（笔记）

11.3 11.4 STL中的平衡二叉树数据结构

• 有时需要在大量增加、删除数据的的同时，还要进行大量数据的查找，希望增加数据、删除数据、查找数据都能在log(n)复杂度完成
• 排序+二分查找显然不可以，因加入新数据就要重新排序
• 可以使用“平衡二叉树”数据结构存放数据，体现在STL中，就是以下四种“排序容器”：multiset，set，multimap，map

1. multiset
   • multiset < T > st;
   • 定义了一个multiset变量st，st里面可以存放T类型的数据，并且能自动排序，开始st为空
   • 排序规则：表达式 “a < b" 为 true，则a排在b前面
   • 可用== st.insert 添加元素==，st.find查找元素，st.erase删除元素，复杂度都是log(n)

//multiset 用法
#include <iostream>
#include <cstring>
#include <set> //使用multiset和set需要此头文件
using namespace std;
int main() {
    multiset <int> st;
    int a[10] = {1,14,12,13,7,13,21,19,8,8};
    for (int i = 0;i<10;i++) {
        st.insert(a[i]); //插入的是a[i]的复制品
    }
    multiset <int>::iterator i; //迭代器，近似于指针
    for (i = st.begin(); i!=st.end();i++) {
        cout << *i << ",";
    }
    cout << endl;
    i = st.find(22);    //查找22，返回值是迭代器
    if (i == st.end())  //找不到则返回值为end()
        cout << "not found" << endl;
    st.insert(22);     //插入22
    i = st.find(22);
    if (i == st.end())
        cout << "not found" << endl;
    else 
        cout << "found: " << * i << endl;
    //找到则返回指向找到的元素的迭代器
    i = st.lower_bound(13);
    //返回最靠后的迭代器 it，使得[begin(),it)中的元素都在13的前面，复杂度log(n)
    cout << *i << endl;
    i = st.upper_bound(8);
    //返回最靠前的迭代器 it，使得[it,end())中的元素都在8的后面，复杂度log(n)
    cout << * i << endl;
    st.erase(i);
    //删除迭代器i指向的元素，即12
    for (i = st.begin();i!=st.end();i++) 
        cout << *i << ",";
    return 0;
}
/*multiset上的迭代器
multiset<T>::iterator p;
p 是迭代器，相当于指针，可用于指向multiset中的元素。访问multiset中的元素要通过迭代器。
与指针不同：multiset上的迭代器可++，--，用！=和==比较，不可比大小，不可加减整数，不可相减
st.begin() 返回值类型为multiset<T>::iterator,是指向st中的头一个元素的迭代器
st.end() 返回值类型为multiset<T>::iterator,是指向st中的最后一个元素后面的迭代器
对迭代器++，其就指向容器中下一个元素，--则令其指向上一个元素。
*/

2. 自定义排序规则的multiset

#include <iostream>
#include <set>
#include <cstring>
using namespace std;
struct Student {
    char name[20];
    int id;
    int score;
};
Student students[] = {
    {"Jack",112,78},
    {"Mary",102,85},
    {"Ala",333,92},
    {"Zero",101,70},
    {"Cindy",102,78}
};
struct Rule {
    bool operator() (const Student & s1,const Student & s2) const {
        if (s1.score != s2.score)
            return s1.score > s2.score;
        else 
            return (strcmp(s1.name,s2.name) < 0);
    }
};
int main()
{
    multiset <Student,Rule> st;
    for (int i = 0;i<5;i++) 
        st.insert(students[i]);//插入的是students[i]的复制品
    multiset <Student,Rule>::iterator p;
    for (p = st.begin(); p != st.end();p++) 
        cout << p->score << " " << p->name << " " << p->id << endl;
    Student s = {"Mary",1000,85};
    p = st.find(s);
    if (p!=st.end())
        cout << p->score << " " << p->name << " " << p->id << endl;
    return 0;
}

11.5 set

• set的用法
  • set 和 multiset的区别在于容器里不能有重复的元素
  • a和b重复 等价于 ”a必须排在b的前面“和 ”b必须排在a的前面“都不成立
  • set插入元素可能不成功

#include <iostream>
#include <set>
#include <cstring>
using namespace std;
int main()
{
    set <int> st;
    int a[10] = {1,2,3,8,7,7,5,6,8,12};
    for (int i = 0;i<10;i++) {
        st.insert(a[i]);
    }
    cout << st.size() << endl; //输出8
    set <int> ::iterator i;
    for (i = st.begin();i!=st.end();i++) 
        cout << * i << ",";   //输出：1，2，3，5，6，7，8，12，
    cout << endl;
    pair<set<int>::iterator,bool> result = st.insert(2);
    /*
    等价于
    sturct {
        set <int>::iterator first;
        bool second;
    };
    */
    if (!result.second) //条件成立说明插入不成功
        cout << * result.first << " already exists." << endl;
    else 
        cout << * result.first << " inserted." << endl;
    return 0;
    /*
    pair模板的用法
    pair<T1,T2>类型等价于：
    struct {
        T1 first;
        T2 second;
    };
    例如：pair <int, double> a;
    等价于：
    struct {
        int first;
        double second;
    }
    a.fisrt = 1;
    a.second = 93.93;
    */
}