CS
登录

Introduction to Data Structures

一、数据结构基础概念

数据结构的核心作用是组织数据，以实现高效的信息使用。不同数据结构对操作的支持效率差异显著（部分操作可能不支持），因此需根据具体问题场景选择合适的数据结构。

C++ 标准库数据结构支持存储任意数据类型，声明时需在 <> 中指定目标类型，例如 vector<string> v 表示创建一个仅存储 string 类型的向量（动态数组）。

此外，几乎所有标准库数据结构都支持两个基础方法：

  • size()：返回数据结构中元素的数量。

  • empty()：返回布尔值，true 表示数据结构为空，false 表示非空。

二、核心数据结构详解

1. 数组（Arrays）

数组是最简单的数据结构，USACO 青铜级题目可仅用数组解决，其他数据结构为推荐扩展内容。

（1）STL 数组声明

C++11 及以上提供 std::array 类（STL 数组），声明格式为 array<数据类型, 元素个数> 数组名，例如：

array<int, 25> arr; // 声明一个存储25个int类型元素的STL数组

（2）核心特性

  • 支持 STL 方法：empty()（判断空）、size()（获取元素数）。

  • 支持下标访问：与普通数组一致，如 arr[5] 访问第 5 个索引（从 0 开始）的元素。

（3）初始化注意事项

C++ 局部数组（普通数组或 STL 数组）默认初始化为随机值，若需初始化为 0，有 4 种常用方式：

1. 使用 for 循环（或嵌套循环）手动赋值。

2. 声明为全局数组（全局变量默认初始化为 0）。

3. 用空初始化列表：int arr[25]{};。

4. 调用内置函数：std::fill_n(arr, 25, 0) 或 std::fill(arr, arr+25, 0)。

（4）警告：memset 函数的局限

memset(arr, 0, sizeof arr) 可实现数组零初始化，但需注意其原理是将每个字节设为指定值：

  • 若用 memset(arr, 1, sizeof arr) 初始化 32 位 int 数组，每个元素会被设为 0x01010101（十进制 16843009），而非 1。

  • 若用 memset(arr, -1, sizeof arr)，每个字节设为 0xFF，32 位 int 元素会变为 0xFFFFFFFF（对应有符号 int 的 -1，或无符号 int 的 4294967295）。

2. 动态数组（Dynamic Arrays）

动态数组即 C++ 中的 vector，支持普通数组的所有功能，且可自动调整大小，核心优势是在末尾添加/删除元素的时间复杂度为 O(1)。

（1）参考资源

资源标识

章节/内容

说明

IUSACO

4.1, 4.2 - Dynamic Arrays

本模块内容基于此

CPH

4.1 - Dynamic Arrays

涵盖向量、字符串

PAPS

3.1 - Vectors

向量基础

LCPP

11.17 - Intro to std::vector

STL向量入门

（2）基础用法

① 创建与赋值

// 示例1：创建空向量，添加1-10的元素
vector<int> v;
for (int i = 1; i <= 10; i++) { 
    v.push_back(i); // 末尾添加元素，向量自动扩容
}

// 示例2：指定大小的向量（两种方式）
vector<int> v1(n); // 初始化含n个默认值（int为0）的向量
vector<int> v2;
v2.resize(n); // 先创建空向量，再调整为n个元素的大小

② 注意：变长数组（VLA）的非标准性

g++ 编译器支持 int n; cin >> n; int v[n]; 这种变长数组，但不属于 C++ 标准，推荐用 vector 替代以保证代码可移植性。

③ 多维动态数组

支持多种组合形式，例如：

  • 动态数组的动态数组：vector<vector<int>>（常用，如二维矩阵）。

  • 静态数组的动态数组：array<vector<int>, 5>（固定 5 行，每行长度可变）。

  • 动态数组的静态数组：vector<array<int, 5>>（行数可变，每行固定 5 个元素）。

3. 遍历（Iterating）

提供 3 种遍历静态/动态数组的方式，以 vector<int> v{1, 7, 4, 5, 2} 为例：

（1）普通 for 循环

通过下标访问，需注意 size() 返回值为无符号类型，需强制转换为 int 避免类型不匹配：

for (int i = 0; i < int(size(v)); i++) { 
    cout << v[i] << " "; // 输出：1 7 4 5 2 
}

（2）迭代器（Iterator）

迭代器是指向容器元素的“指针类似物”，支持遍历容器：

// 方式1：显式声明迭代器类型
for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
    cout << *it << " "; // *it 访问迭代器指向的元素
}

// 方式2：用 auto 自动推断类型（C++11及以上）
for (auto it = begin(v); it != end(v); it = next(it)) {
    cout << *it << " ";
}

（3）for-each 循环（简洁版）

直接遍历每个元素，无需关注下标：

for (int element : v) {
    cout << element << " ";
}

（4）可选特性：边界检查访问

vector 支持 v.at(i) 访问下标 i 的元素，与 v[i] 不同的是，若 i 越界，at(i) 会抛出异常，便于调试（普通下标访问越界无提示，可能导致崩溃）。

4. 插入与删除（Inserting and Erasing）

注意：vector 中间位置的插入/删除操作时间复杂度为 <math>O(n)</math>（需移动后续元素），应尽量避免频繁使用。

vector<int> v;
v.push_back(2);          // [2]（末尾添加，O(1)）
v.push_back(3);          // [2, 3]
v.push_back(7);          // [2, 3, 7]
v.push_back(5);          // [2, 3, 7, 5]
v[1] = 4;                // [2, 4, 7, 5]（修改下标1的元素）
v.erase(v.begin() + 1);  // [2, 7, 5]（删除下标1的元素，O(n)）
v.push_back(8);          // [2, 7, 5, 8]
v.erase(v.end() - 1);    // [2, 7, 5]（删除末尾元素，O(1)）

5. 字符串（Strings）

（1）参考资源

资源标识

章节/内容

说明

LCPP

4.17 - An introduction to std::string

字符串基础

CPP Reference

std::string

C++字符串官方参考

（2）核心操作（入门级）

  • 输入：用 cin 读取单个字符串（空格分隔），或 getline 读取整行（含空格）。

  • 排序：sort(s.begin(), s.end())（需包含 <algorithm> 头文件）。

  • 拼接：用 + 运算符，如 string s = "a" + "b";（结果为 "ab"）。

  • 字符访问：s[i] 或 s.at(i)（获取第 i 个字符）。

  • 子串：s.substr(pos, len)，从下标 pos 开始，截取长度为 len 的子串（若 len 省略，截取到字符串末尾）。

6. 对组（Pairs）

用于存储两个元素（可不同类型），比 vector<vector<int>> 或 array<int,2> 更灵活（支持不同类型）。

（1）核心语法

  • 声明：pair<类型1, 类型2> 变量名，如 pair<int, string> p;。

  • 创建：

1. make_pair(a, b)：返回含值 a（类型1）和 b（类型2）的 pair，如 make_pair(1, "abc")。

2. 花括号（C++11+）：{a, b}，比 make_pair 更简洁，如 {1, "abc"}。

  • 访问：p.first（第一个元素）、p.second（第二个元素）。

（2）示例代码

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

int main() {
    pair<int, string> p = {123, "Testing "};
    cout << p.second << p.first << endl; // 输出：Testing 123
    
    p.first = 456; // 修改第一个元素
    cout << "It is possible to edit pairs after declaring them " << p.first << endl; 
    // 输出：It is possible to edit pairs after declaring them 456
    
    // 向量存储pair（如2D平面点：int坐标 + string标签）
    vector<pair<int, string>> points;
    points.push_back({0, "origin"});
    cout << "Point: (" << points[0].first << ", " << points[0].second << ")" << endl;
    // 输出：Point: (0, origin)
    return 0;
}

7. 元组（Tuples）

用于存储两个以上元素（可不同类型），避免 pair<int, pair<int, int>> 这种嵌套 pair 的繁琐写法。

（1）核心语法

  • 声明：tuple<类型1, 类型2, ..., 类型N> 变量名，如 tuple<int, string, double> t;。

    • 警告：i 必须是常量，不能用变量（如 int i=1; get<i>(t); 非法）。

  • 创建：make_tuple(a, b, c, ...)，如 make_tuple(3, "Hello", 3.14)。

  • 访问与修改：get<i>(t)（i 为常量索引，从 0 开始），如 get<0>(t) = 7;（修改第一个元素）。

  • 解包：tie(a, b, c, ...) = t，将 tuple 的元素依次赋值给变量 a, b, c...（变量数量需与 tuple 元素数一致）。

（2）示例代码

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

int main() {
    tuple<int, int, int> t = {3, 4, 5};
    cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << endl; 
    // 输出：3 4 5
    
    get<0>(t) = 7; // 修改第一个元素
    cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << endl; 
    // 输出：7 4 5
    
    // 解包tuple
    string s;
    int num;
    tie(s, num) = make_tuple("Hello world", 100);
    cout << s << " " << num << endl; 
    // 输出：Hello world 100
    return 0;
}

三、内存分配（Memory Allocation）

USACO 题目通常限制内存为 256 MB，需估算数据存储上限：

1. 转换内存单位：256 MB = 256 × 10⁶ 字节。

2. 按数据类型计算最大元素数：

  • int（4 字节）：最大存储量 ≈ (256×10⁶) / 4 = 64×10⁶ 个。

  • long long（8 字节）：最大存储量 ≈ (256×10⁶) / 8 = 32×10⁶ 个。

3. 注意：程序开销（如递归函数栈、其他变量）会减少可用内存，实际存储量需低于理论值。

四、测验（Quiz）

五、总结

  • 青铜级题目核心：固定大小数组可解决几乎所有问题。

  • 扩展建议：动态数组（vector）、对组（pair）、元组（tuple）能简化代码实现，推荐掌握以提升效率。

CS
登录