C++数据结构1

博主： Xherlock
发布时间：2023 年 06 月 10 日
343 次浏览
暂无评论
3532字数
分类： C/C++&机试

# C++数据结构1

## 向量

### 相关知识

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

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

~~~c++
#include <vector>
~~~

**vector的状态**：

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

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

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

**vector元素操作**：见词如面

* insert
* erase
* clear

**vector迭代器操作**

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

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

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

### 题目

#### 完数VS盈数

[完数VS盈数_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/ccc3d1e78014486fb7eed3c50e05c99d?tpId=60&tqId=29492&tPage=1&ru=/kaoyan/retest/1001&qru=/ta/tsing-kaoyan/question-ranking)

**描述**

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

**输入描述**：

题目没有任何输入。

**输出描述**：

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

~~~c++
#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 引用头文件如下

~~~c++
#include <queque>
~~~

**定义方法**：

~~~c++
queue<typename> name
~~~

**queue状态**：同vector

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

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

### 题目

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

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

## 栈

### 知识

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

### 题目

#### Zero-complexity Transposition

[Zero-complexity Transposition_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/c54775799f634c72b447ef31eb36e975?tpId=40&tqId=21440&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking)

**描述**

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接收数据，防止溢出

~~~c++
#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;
}
~~~

#### 括号匹配

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

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

~~~c++
#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)](https://www.nowcoder.com/practice/e91982a145944ceab6bb9a4a508e0e26?tpId=40&tqId=21511&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking)

**描述**

堆栈是一种基本的数据结构。堆栈具有两种基本操作方式，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'。

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

~~~c++
#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用来判断符号优先级

~~~c++
#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)](https://www.nowcoder.com/practice/7b18aa6b7cc14f8eaae6b8acdebf890b?tpId=62&tqId=29459&tPage=1&ru=/kaoyan/retest/2002&qru=/ta/sju-kaoyan/question-ranking)

**描述**

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

**输入描述**：

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

**输出描述**：

输出结果

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

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

~~~c++
#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;
}

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;
}
~~~

最后修改：2023 年 06 月 23 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

Reverse（十一）
浏览次数: 2629
Win11新机鼓捣记录
浏览次数: 2382
栈~数制转换
浏览次数: 1604
C++学习
浏览次数: 1603
Python实现文件管理系统（重命名和删除）
浏览次数: 1575

顶点软件
你写得非常清晰明了，让我很容易理解你的观点。
mars
博主你好，请问怎么知道的alloc函数属于Buffer下的方法...
lj
该评论仅登录用户及评论双方可见
Mr.Guan
:@(赞一个)
Typecho
欢迎加入 Typecho 大家族

C++数据结构1

发表评论取消回复

Reverse（十一）

Win11新机鼓捣记录

栈~数制转换

C++学习

Python实现文件管理系统（重命名和删除）

输入/输出和存储系统

XSS-labs Less 11-16

信息与网络空间安全保障

数据库学习（二）

汇编语言学习（四）~寄存器（内存访问）

C++数据结构1

发表评论 取消回复

C++数据结构1

发表评论取消回复