C++数据结构1

向量

相关知识

数组存在一个限制：创建数组时必须规定大小，因此可能出现开的太大导致内存浪费的现象，或太小导致数组访问越界

因此引入向量：可以改变大小的线性序列容器，与数组相同的是可以通过下标来访问。头文件如下

#include <vector>

vector的状态：

• empty()：返回向量是否为空
• size()：返回向量元素个数

vector尾部元素的添加或删除：

• push_back：尾部添加一个元素，string也有
• pop_back：尾部删除一个元素，string也有

vector元素操作：见词如面

• insert
• erase
• clear

vector迭代器操作

• begin()：返回向量中的首元素的迭代器begin
• end()：返回向量中尾元素后一个位置的迭代器

下面为使用迭代器获取向量的循环方法

vector<int>::iterator it;    // 定义迭代器
for (it = myVector.begin(); it != myVector.end(); it++) {
    printf("%d ", *it);
}

题目

完数VS盈数

完数VS盈数_牛客题霸_牛客网 (nowcoder.com)

描述

一个数如果恰好等于它的各因子(该数本身除外)子和，如：6=3+2+1。则称其为“完数”；若因子之和大于该数，则称其为“盈数”。 求出2到60之间所有“完数”和“盈数”。

输入描述：

题目没有任何输入。

输出描述：

输出2到60之间所有“完数”和“盈数”，并以如下形式输出： E: e1 e2 e3 ......(ei为完数) G: g1 g2 g3 ......(gi为盈数) 其中两个数之间要有空格，行尾不加空格。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> yingshu;
    int num;
    printf("E:");
    for (int i = 2; i < 61; i++) {
        num = 0;
        for (int j = 1; j <= i / 2; j++) {
            if (i % j == 0) {
                num += j;
            }
            if (num > i) {
                yingshu.push_back(i);
                break;
            }
        }
        if (num == i) {
            printf(" %d", i);
        }
    }
    printf("\nG:");
    for (int i = 0; i < yingshu.size(); i++) {
        printf(" %d", yingshu[i]);
    }
}

vector在图论中邻接表还有应用

队列

知识

队列（Queue）是一种线性的序列结构，其存放的元素按照现行的逻辑次序排列，但操作仅限于序列的两端【先进先出】

STL-queue 引用头文件如下

#include <queque>

定义方法：

queue<typename> name

queue状态：同vector

queue元素添加或删除：push()、pop()

queue元素的访问：front()、back()

题目

约瑟夫问题，猫狗收留领养

队列经常用于宽度优先的搜索

栈

知识

和队列一样，栈也是一种线性序列结构，但操作仅限于特定的一端，和queue的区别在于只能用top()来访问栈顶元素

题目

Zero-complexity Transposition

Zero-complexity Transposition_牛客题霸_牛客网 (nowcoder.com)

描述

You are given a sequence of integer numbers. Zero-complexity transposition of the sequence is the reverse of this sequence. Your task is to write a program that prints zero-complexity transposition of the given sequence.

输入描述：

For each case, the first line of the input file contains one integer n-length of the sequence (0 ＜ n ≤ 10 000). The second line contains n integers numbers-a1, a2, …, an (-1 000 000 000 000 000 ≤ ai ≤ 1 000 000 000 000 000).

输出描述：

For each case, on the first line of the output file print the sequence in the reverse order.

题目大意就是逆向一组数，需要注意使用long long接收数据，防止溢出

#include <iostream>
#include <stack>
using namespace std;

int main() {
    int n;
    while (scanf("%d", &n)!=EOF) {
        stack<long long> a;
        long long b;
        for (int i = 0; i < n; i++) {
            scanf("%lld", &b);
            a.push(b);
        }
        while (!a.empty()) {
            printf("%lld ", a.top());
            a.pop();
        }
        printf("\n");
    }
    return 0;
}

括号匹配

题目大意是不匹配的左括号输出问号，不匹配的右括号输出美元号

思路：定义一个栈装左括号下标，每匹配一对弹出一个左括号下标，栈空时右括号无法匹配输出美元号，遍历字符串完后栈里还有没匹配的左括号输出问号，剩下的输出空格【预先定义一个和字符串长度的空格字符串】

#include <iostream>
#include <stack>
using namespace std;

int main()
{
    string str;
    while (cin >> str)
    {
        cout << str << endl;
        stack<int> bracket;
        string r(str.size(), ' ');
        for (int i = 0; i < str.size(); i++)
        {
            if (str[i] == ')' && bracket.empty())
                r[i] = '?';
            else if (str[i] == '(') 
                bracket.push(i);
            else if (str[i] == ')' && !bracket.empty())
                bracket.pop();
        }
        while(!bracket.empty())
        {
            r[bracket.top()] = '$';
            bracket.pop();
        }
        cout << r << endl;
    }
    return 0;
}

堆栈使用

堆栈的使用_牛客题霸_牛客网 (nowcoder.com)

描述

堆栈是一种基本的数据结构。堆栈具有两种基本操作方式，push 和 pop。其中 push一个值会将其压入栈顶，而 pop 则会将栈顶的值弹出。现在我们就来验证一下堆栈的使用。（注：本题有多组输入，可以参考该网址：https://www.nowcoder.com/discuss/276）

输入描述：

对于每组测试数据，第一行是一个正整数 n（0 < n <= 10000）。而后的 n 行，每行的第一个字符可能是'P'或者'O'或者'A'；如果是'P'，后面还会跟着一个整数，表示把这个数据压入堆栈；如果是'O'，表示将栈顶的值 pop 出来，如果堆栈中没有元素时，忽略本次操作；如果是'A'，表示询问当前栈顶的值，如果当时栈为空，则输出'E'。堆栈开始为空。

输出描述：

对于每组测试数据，根据其中的命令字符来处理堆栈；并对所有的'A'操作，输出当时栈顶的值，每个占据一行，如果当时栈为空，则输出'E'。

需要注意：可以边输入边输出的

#include <iostream>
#include <stack>
using namespace std;

int main() {
    int n, num;
    string c;
    while (scanf("%d", &n)!=EOF) {
        stack<int> s;
        for (int i  = 0; i < n; i++) {
            cin >> c;
            if (c == "P") {
                scanf("%d", &num);
                s.push(num);
            } else if (c == "O" && !s.empty()) {
                s.pop();
            } else if (c == "A") {
                if (s.empty())
                    printf("E\n");
                else
                    printf("%d\n", s.top());
            }
        }
    }
}

简单计算器

描述

读入一个只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。

输入描述：

测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。

输出描述：

对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。

输入：
1 + 2
4 + 2 * 5 - 7 / 11
0
输出：
3.00
13.36

思路：设计两个栈，分别装数字和计算符号；同时is_prior用来判断符号优先级

#include <iostream>
#include <stack>
#include <math.h>
#include <string>
using namespace std;

float calc(float num1, float num2, char op) {
    if (op == '+')
        return num1 + num2;
    else if (op == '-')
        return num1- num2;
    else if (op == '*')
        return num1 * num2;
    else
        return num1 / num2 * 1.0;
}

int op2num(char op) {
    if (op == '+')
        return 0;
    else if (op == '-')
        return 1;
    else if (op == '*')
        return 2;
    else
        return 3;
}

bool is_prior(char op1, char op2) {    //思路是同级或小的，可以计算；优先级大的等下一个在计算
    bool cp[4][4] = {{false, false, true, true}, {false, false, true, true}, {false, false, false, false}, {false, false, false, false}};
    return cp[op2num(op1)][op2num(op2)];
}

int main() {
    string exp;
    while (getline(cin, exp)) {
        stack<float> num;
        stack<char> ops;
        exp = exp + " ";
        int n = 0;
        if (exp == "0 ")
            break;
        else {
            for (int i = 0; i < exp.size(); i++) {
                if (exp[i] == ' ' && (exp[i-1] <= '9' && exp[i-1] >= '0')) {
                    num.push(n);    // 只有当前字符为空格且上一个为数字才push数字
                    n = 0;
                } else if (exp[i] <= '9' && exp[i] >= '0') {
                    n = n * 10 + (exp[i] - '0');    // 字符转数字
                } else if (exp[i] == '+' || exp[i] == '-' || exp[i]== '*' || exp[i] == '/') {
                    while (!ops.empty() && !is_prior(ops.top(), exp[i])) {    //直到同优先级的计算完再填入当前计算符
                        float num1 = num.top();
                        num.pop();
                        float num2 = num.top();
                        num.pop();
                        num.push(calc(num2, num1, ops.top()));
                        ops.pop();
                    }
                    ops.push(exp[i]);
                }
            }
            while (!ops.empty()) {    // 计算字符全部装完，遍历即可
                float num1 = num.top();
                num.pop();
                float num2 = num.top();
                num.pop();
                num.push(calc(num2, num1, ops.top()));
                ops.pop();
            }
        }
        printf("%.2f\n", num.top());    // 保留两位小数
    }
    return 0;
}

计算表达式

计算表达式_牛客题霸_牛客网 (nowcoder.com)

描述

对于一个不存在括号的表达式进行计算

输入描述：

存在多组数据，每组数据一行，表达式不存在空格

输出描述：

输出结果

输入：
6/2+3+3*4
输出：
18

思路：本题和上一题几乎一样，唯一需要注意的本题不严谨，输出格式有的是int有的是float，所以最好使用c++标准输出cout来输出，这样不用printf里规定%d还是%f了；同时本题没有空格，因此最后结束遍历表达式需要再push一次数字

#include <iostream>
#include <stack>
#include <math.h>
#include <string>
using namespace std;

float calc(float num1, float num2, char op) {
    if (op == '+')
        return num1 + num2;
    else if (op == '-')
        return num1- num2;
    else if (op == '*')
        return num1 * num2;
    else
        return num1 / num2;
}

int op2num(char op) {
    if (op == '+')
        return 0;
    else if (op == '-')
        return 1;
    else if (op == '*')
        return 2;
    else
        return 3;
}

bool is_prior(char op1, char op2) {    //思路是同级或小的，可以计算；优先级大的等下一个在计算
    bool cp[4][4] = {{false, false, true, true}, {false, false, true, true}, {false, false, false, false}, {false, false, false, false}};
    return cp[op2num(op1)][op2num(op2)];
}

int main() {
    string exp;
    while (getline(cin, exp)) {
        stack<float> num;
        stack<char> ops;
        int n = 0;
        for (int i = 0; i < exp.size(); i++) {
            if (exp[i] <= '9' && exp[i] >= '0') {
                n = n * 10 + (exp[i] - '0');    // 字符转数字
            } else {
                num.push(n);    // 只有当前字符为空格且上一个为数字才push数字
                n = 0;
                while (!ops.empty() && !is_prior(ops.top(), exp[i])) {
                    float num1 = num.top();
                    num.pop();
                    float num2 = num.top();
                    num.pop();
                    num.push(calc(num2, num1, ops.top()));
                    ops.pop();
                }
                ops.push(exp[i]);
            }
        }
        num.push(n);
        while (!ops.empty()) {    // 计算字符全部装完，遍历即可
            float num1 = num.top();
            num.pop();
            float num2 = num.top();
            num.pop();
            num.push(calc(num2, num1, ops.top()));
            ops.pop();
        }
        cout << num.top() << endl;    // 保留两位小数
    }
    return 0;
}