C++ Library(1)



  • C++ Library(1)

    0.结构体 struct

    0.1 定义

    有时我们需要定义自己的「数据类型」,比如平面上的点,需要由两个数字来表示. 也就是每一个「点类型」对应两个「整数类型」

    让我们来定义我们自己的数据类型Point:

    struct Point
    {
        int x, y;
    };
    

    这段代码的作用是定义结构体, 或者通俗一点说: 告诉编译器, 我要定义一种类型, 类型名字叫做Point, 其中1个Point由2个名字分别为x,y的整数构成

    structC++中的关键字, 类似于if,else等. 定义语句要注意结尾的分号(第4行).

    Point是要定义的类型的名字, 类似于给变量取名字.

    x,y是结构体的「成员」类型的名字

    0.2 实例化

    定义完Point类型之后, 我们可以来定义一些Point类型的变量

    Point p;
    Point arr_p[10];
    

    基本上就相当于把Point当作int,char这些内置类型来用

    0.3 访问成员

    Point p;
    p.x = 1;
    p.y = 2;
    cout << p.x << ' ' << p.y <<endl;
    

    通过「成员运算符 member operator」.来访问/调用Point类型变量p的成员, p.x,p.y的类型显然是int

    同理也可以输入之类的

    Point arr_p[10];
    for (int i = 1; i < 10; i++)
    {
        cin >> arr_p[i].x >> arr_p[i].y;
    }
    

    0.4 成员函数

    比如我们想用一个函数来算一个点到原点的距离, 但是这个函数显然是和Point这个类型高度「耦合」的, 这个时候我们「最好」定义一个「成员函数」

    struct Point
    {
        int x, y;
        double distance()
        {
            return sqrt (x * x + y * y);
        }
    };
    

    其中第4行到第7行就是「Point类型的成员函数的定义」, 定义基本上和普通的函数一模一样, 不过值得注意的是, distance()函数内可以直接访问「当前结构体内的成员」,比如x,y

    distance()函数被封装在了Point类型里面, 外部不能直接访问, 也只能通过「成员运算符」.

    Point p;
    p.x = 1, p.y = 1;
    cout << p.distance() << endl;
    
    • 到这里, 你有没有什么联想呢?
    struct string
    {
        // declare something
        int size()
        {
            // return something
        }
    };
    
    // when you write your program like this:
    string s = "123asd";
    int l = s.size();
    // do something
    

    1.队列 queue

    队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(back)进行插入操作。

    队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

    #include <iostream>
    #include <queue>//STL容器通常需要包含与其同名的头文件
    using namespace std;//STL:Standard Template Library 标准模板库
    int main()
    {
        queue<int>q;//定义一个'装'int类型,名字为q的队列.初始时q为空队列
        q.push (1); //调用队列q的「成员函数」push,将一个整数1加入队列
        q.push (3); //同上,此时队列中依次为1,3
        q.push (2); //同上,此时队列中依次为1,3,2
        cout << q.size() << endl;//输出3,即当前队列元素个数
        //size()是队列q的一个成员函数,返回q中包含的元素个数,几乎所有STL容器都有size()函数,记得size后面有一对「小括号」
        while (!q.empty()) //同理,empty()也是队列q的一个成员函数,望文生义:如果q当前是空的,就返回true;否则返回false
        {
            //while中的判断条件即为"当q不为空就一直做",在BFS(广度优先搜索)中经常见到
            cout << q.front() << ' '; //front()返回q的队首元素
            q.pop();//队首元素出队,这样可以遍历q中的所有元素
        }
        return 0;
    }
    

    练习1:P1996 约瑟夫问题

    2.栈 stack

    栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。

    向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

    #include <iostream>
    #include <stack>//STL容器通常需要包含与其同名的头文件
    using namespace std;//STL:Standard Template Library 标准模板库
    int main()
    {
        stack<int> s;//定义一个'装'int类型,名字为s的栈.初始时s为空栈
        s.push (1); //调用栈s的「成员函数」push,将一个整数1加入栈
        s.push (3); //同上,此时栈中依次为3,1
        s.push (2); //同上,此时栈中依次为2,3,1
        cout << s.size() << endl;//输出3,即当前栈元素个数
        //size()是栈s的一个成员函数,返回s中包含的元素个数,几乎所有STL容器都有size()函数,记得size后面有一对「小括号」
        while (!s.empty()) //同理,empty()也是栈s的一个成员函数,望文生义:如果s当前是空的,就返回true;否则返回false
        {
            cout << s.top() << ' '; //front()返回s的栈顶元素
            s.pop();//栈顶元素弹栈(退栈),这样可以遍历s中的所有元素
        }
        return 0;
    }
    

    练习2:P1739 表达式括号匹配

    练习3:P1449 后缀表达式

    3.优先队列 priority_queue

    普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。

    在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。

    优先队列通常采用堆数据结构来实现。

    #include <iostream>
    #include <vector>
    #include <queue>
    using namespace std;
    int main()
    {
        priority_queue<int> pq; //默认是越「大」的元素「优先级」越高,也就是越先出队
        //priority_queue<int, vector<int>, greater<int> >pq;
        //如果你想让越「小」的元素「优先级」越高,像被注释的上一行这样做,记得包含<vector>
        pq.push (1);
        pq.push (3);
        pq.push (2);
        while (!pq.empty())
        {
            cout << pq.top() << ' ';//访问队首(堆顶),即最大元素
            pq.pop();//队首(堆顶)出队
        }
        return 0;
    }
    

    练习4:P3378 【模板】堆

    练习5:P1090 合并果子


 

Copyright © 2018 bbs.dian.org.cn All rights reserved.

Looks like your connection to Dian was lost, please wait while we try to reconnect.