C++基础(十三)-C++ 数据结构

1. 数组（Array）

数组是最基础的数据结构，用于存储一组相同类型的数据。

• 特点：
• 固定大小，一旦声明，大小不能改变。
• 直接访问元素，时间复杂度为 O(1)。
• 适合处理大小已知、元素类型相同的集合。

int arr[5] = {1, 2, 3, 4, 5};
cout << arr[0]; // 输出第一个元素

2. 结构体（Struct）

结构体允许将不同类型的数据组合在一起，形成一种自定义的数据类型。

• 特点：
• 可以包含不同类型的成员变量。
• 提供了对数据的基本封装，但功能有限。

struct Person {
    string name;
    int age;
};
Person p = {"Alice", 25};
cout << p.name << endl; // 输出 Alice

3. 类（Class）

类是 C++ 中用于面向对象编程的核心结构，允许定义成员变量和成员函数。与 struct 类似，但功能更强大，支持继承、封装、多态等特性。

• 特点：
• 可以包含成员变量、成员函数、构造函数、析构函数。
• 支持面向对象特性，如封装、继承、多态。

class Person {
private:
    string name;
    int age;
public:
    Person(string n, int a) : name(n), age(a) {}
    void printInfo() {
        cout << "Name: " << name << ", Age: " << age << endl;
    }
};
Person p("Bob", 30);
p.printInfo(); // 输出: Name: Bob, Age: 30

4. 链表（Linked List)

链表是一种动态数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

• 特点：
• 动态调整大小，不需要提前定义容量。
• 插入和删除操作效率高，时间复杂度为 O(1)（在链表头部或尾部操作）。
• 线性查找，时间复杂度为 O(n)。

struct Node {
    int data;
    Node* next;
};
Node* head = nullptr;
Node* newNode = new Node{10, nullptr};
head = newNode; // 插入新节点

5. 栈（Stack）

列是一种先进先出（FIFO, First In First Out）的数据结构，常用于广度优先搜索、任务调度等场景。

• 特点：
• 插入操作在队尾进行，删除操作在队头进行。
• 时间复杂度为 O(1)。

#include <iostream>  
#include <stack>
using namespace std;  
int main(){
     stack<int> sti;
     sti.push(1);
     sti.push(2);
        cout<<"栈查看栈顶元素："<<sti.top()<<endl;
     sti.pop();
      cout<<"栈查看栈顶元素："<<sti.top()<<endl;
    return 0;
};

7. 双端队列（Deque）

双端队列允许在两端进行插入和删除操作，是栈和队列的结合体。

• 特点：
• 允许在两端进行插入和删除。

deque<int> dq;
dq.push_back(1);
dq.push_front(2);
cout << dq.front(); // 输出 2
dq.pop_front();

8. 哈希表（Hash Table）

哈希表是一种通过键值对存储数据的数据结构，支持快速查找、插入和删除操作。C++ 中的 unordered_map 是哈希表的实现。

• 特点：
• 使用哈希函数快速定位元素，时间复杂度为 O(1)。
• 不保证元素的顺序。

重点

• 插入

 // unordered_map - 哈希表，无序
    unordered_map<int, string> um;
    um.insert({3, "three"});
    um.emplace(1, "one");
    um[2] = "two";  // 顺序不确定

• 删除

void eraseComparison() {
    map<int, string> m = {{1,"a"}, {2,"b"}, {3,"c"}, {4,"d"}};
    unordered_map<int, string> um = {{1,"a"}, {2,"b"}, {3,"c"}, {4,"d"}};
        // 通过键删除 - 语法相同
    m.erase(2);
    um.erase(2);
        // 通过迭代器删除 - 语法相同
    auto it_m = m.find(3);
    if (it_m != m.end()) m.erase(it_m);
        auto it_um = um.find(3);
    if (it_um != um.end()) um.erase(it_um);
        // 范围删除 - 语法相同
    m.erase(m.begin(), m.end());  // 清空
    um.erase(um.begin(), um.end()); // 清空
}

• 修改

void updateComparison() {
    map<int, string> m = {{1, "old1"}, {2, "old2"}};
    unordered_map<int, string> um = {{1, "old1"}, {2, "old2"}};
        // 修改值 - 语法相同
    m[1] = "new1";           // O(log n)
    um[1] = "new1";          // 平均 O(1)
        // 通过迭代器修改值（不能修改键）
    auto it_m = m.find(2);
    if (it_m != m.end()) it_m->second = "new2";  // O(log n)查找
        auto it_um = um.find(2);
    if (it_um != um.end()) it_um->second = "new2"; // 平均 O(1)查找
}

• 查找

#include <map>
#include <unordered_map>
using namespace std;

void searchComparison() {
    map<int, string> m = {{1,"a"}, {2,"b"}, {3,"c"}};
    unordered_map<int, string> um = {{1,"a"}, {2,"b"}, {3,"c"}};
    
    // 使用 find() - 语法相同
    auto it_m = m.find(2);  // O(log n)
    auto it_um = um.find(2); // 平均 O(1)
        if (it_m != m.end()) {
        cout << "map找到: " << it_m->second << endl;
    }
        if (it_um != um.end()) {
        cout << "unordered_map找到: " << it_um->second << endl;
    }
        // 使用 count() - 语法相同
    if (m.count(2)) {  // O(log n)
        cout << "map中存在键2" << endl;
    }
        if (um.count(2)) { // 平均 O(1)
        cout << "unordered_map中存在键2" << endl;
    }
        // 使用 [] 操作符 - 语法相同
    cout << "map[2] = " << m[2] << endl;     // O(log n)
    cout << "um[2] = " << um[2] << endl;     // 平均 O(1)
}

举例

#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
    unordered_map<string, int> map = {
        {"apple", 1},
        {"banana", 2},
        {"cherry", 3}
    };
        // 通过键删除元素
    map.erase("banana");
        // 检查元素是否存在后删除
    if (map.find("apple") != map.end()) {
        map.erase("apple");
    }
        for (auto& pair : map) {
        cout << pair.first << ": " << pair.second << endl;
    }
    // 输出: cherry: 3
}

9. 映射（Map）

map 是一种有序的键值对容器，底层实现是红黑树。与 unordered_map 不同，它保证键的顺序，查找、插入和删除的。

• 特点：
• 保证元素按键的顺序排列。
• 使用二叉搜索树实现。

map<string, int> myMap;
myMap["apple"] = 10;
cout << myMap["apple"]; // 输出 10

10. 集合（Set）

set 是一种用于存储唯一元素的有序集合，底层同样使用红黑树实现。它保证元素不重复且有序。

• 特点：
• 保证元素的唯一性。
• 元素自动按升序排列。

1. 创建和初始化

#include <iostream>
#include <set>
using namespace std;
int main() {
    // 创建空set
    set<int> s1;
        // 初始化列表
    set<int> s2 = {1, 3, 5, 2, 4};
        // 从数组初始化
    int arr[] = {6, 2, 8, 1, 5};
    set<int> s3(arr, arr + 5);
        // 从vector初始化
    vector<int> vec = {9, 7, 3, 1, 5};
    set<int> s4(vec.begin(), vec.end());
        // 自动排序和去重
    set<int> s5 = {3, 1, 4, 1, 5, 9, 2, 6, 5}; 
    // 结果: 1, 2, 3, 4, 5, 6, 9
        for (int num : s5) {
        cout << num << " ";
    }
    // 输出: 1 2 3 4 5 6 9
}

2. 增加/插入操作

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

void insertDemo() {
    set<int> s;
    
    // 方法1: insert(value)
    s.insert(10);
    s.insert(20);
    s.insert(30);
    
    // 方法2: insert(iterator hint, value) - 带提示插入
    auto hint = s.find(20);
    if (hint != s.end()) {
        s.insert(hint, 25);  // 在20附近插入25
    }
    
    // 方法3: emplace (C++11) - 原地构造
    s.emplace(15);
    s.emplace(35);
    
    // 方法4: 插入范围
    vector<int> new_nums = {5, 12, 18};
    s.insert(new_nums.begin(), new_nums.end());
    
    // 检查插入结果
    auto result = s.insert(20);  // 重复插入
    if (!result.second) {
        cout << "插入失败，元素已存在" << endl;
    }
    
    // 输出结果
    cout << "set元素: ";
    for (int num : s) {
        cout << num << " ";
    }
    // 输出: 5 10 12 15 18 20 25 30 35
}

3. 删除操作

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

void eraseDemo() {
    set<int> s = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    cout << "原始set: ";
    for (int num : s) cout << num << " ";
    cout << endl;
    
    // 方法1: 通过值删除
    s.erase(5);  // 删除元素5
    cout << "删除5后: ";
    for (int num : s) cout << num << " ";
    cout << endl;
    
    // 方法2: 通过迭代器删除
    auto it = s.find(3);
    if (it != s.end()) {
        s.erase(it);  // 删除元素3
    }
    cout << "删除3后: ";
    for (int num : s) cout << num << " ";
    cout << endl;
    
    // 方法3: 删除范围 [first, last)
    auto first = s.find(6);
    auto last = s.find(9);
    if (first != s.end() && last != s.end()) {
        s.erase(first, last);  // 删除6,7,8 (不包含9)
    }
    cout << "删除6-8后: ";
    for (int num : s) cout << num << " ";
    cout << endl;
    
    // 遍历时删除
    for (auto it = s.begin(); it != s.end(); ) {
        if (*it % 2 == 0) {  // 删除偶数
            it = s.erase(it);
        } else {
            ++it;
        }
    }
    cout << "删除偶数后: ";
    for (int num : s) cout << num << " ";
    cout << endl;
    
    // 清空set
    s.clear();
    cout << "清空后大小: " << s.size() << endl;
}

4. 查找操作

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

void searchDemo() {
    set<int> s = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    
    // 方法1: find() - 查找元素
    auto it = s.find(50);
    if (it != s.end()) {
        cout << "找到元素: " << *it << endl;
    } else {
        cout << "未找到元素" << endl;
    }
    
    // 方法2: count() - 检查元素是否存在
    if (s.count(30) > 0) {
        cout << "元素30存在" << endl;
    }
    
    // 方法3: lower_bound() - 第一个 >= value 的元素
    auto lb = s.lower_bound(35);
    if (lb != s.end()) {
        cout << "lower_bound(35): " << *lb << endl;  // 输出: 40
    }
    
    // 方法4: upper_bound() - 第一个 > value 的元素
    auto ub = s.upper_bound(35);
    if (ub != s.end()) {
        cout << "upper_bound(35): " << *ub << endl;  // 输出: 40
    }
    
    // 方法5: equal_range() - 返回包含value的范围
    auto range = s.equal_range(50);
    if (range.first != s.end()) {
        cout << "equal_range(50): [" << *range.first;
        if (range.second != s.end()) {
            cout << ", " << *range.second << ")" << endl;
        }
    }
    
    // 检查边界情况
    if (s.find(999) == s.end()) {
        cout << "元素999不存在" << endl;
    }
}

5. 遍历操作

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

void traverseDemo() {
    set<string> fruits = {"apple", "banana", "orange", "grape", "kiwi"};
    
    cout << "=== 遍历方式 ===" << endl;
    
    // 方法1: 迭代器遍历
    cout << "1. 迭代器遍历: ";
    for (auto it = fruits.begin(); it != fruits.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // 方法2: 反向迭代器
    cout << "2. 反向遍历: ";
    for (auto rit = fruits.rbegin(); rit != fruits.rend(); ++rit) {
        cout << *rit << " ";
    }
    cout << endl;
    
    // 方法3: 范围for循环 (C++11)
    cout << "3. 范围for循环: ";
    for (const auto& fruit : fruits) {
        cout << fruit << " ";
    }
    cout << endl;
    
    // 方法4: 使用auto
    cout << "4. 使用auto: ";
    for (auto& fruit : fruits) {
        cout << fruit << " ";
    }
    cout << endl;
}

6. 容量和大小操作

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

void capacityDemo() {
    set<int> s = {1, 2, 3, 4, 5};
    
    cout << "set大小: " << s.size() << endl;
    cout << "最大大小: " << s.max_size() << endl;
    cout << "是否为空: " << (s.empty() ? "是" : "否") << endl;
    
    s.insert(6);
    cout << "插入后大小: " << s.size() << endl;
    
    s.erase(1);
    cout << "删除后大小: " << s.size() << endl;
    
    s.clear();
    cout << "清空后是否为空: " << (s.empty() ? "是" : "否") << endl;
}