IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 程序设计与算法(一)C语言程序设计 -> 正文阅读

[数据结构与算法]程序设计与算法(一)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中的最后一个元素后面的迭代器
对迭代器++,其就指向容器中下一个元素,--则令其指向上一个元素。
*/
  1. 自定义排序规则的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;
    */
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-08-11 12:40:50  更:2021-08-11 12:42:06 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 20:53:26-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码