C++ 数据结构

前言

这一节内容是C++ 基础教程的最后一部分，对于这一节的内容，看不懂也没关系，等大家学习数据结构以后再来看就能够懂了。说说之后的安排吧，这一节内容结束以后，我将会分享更加深入的知识，也就是C++ 面向对象的相关内容，对于C++ 基础教程这一部分的内容如果你还有不明白的，可以去温习一下之前所学C++基础教程

C++ 数据结构

在 C++ 中，数据结构是用来组织和管理数据的重要工具。C++ 提供了从简单到复杂的多种数据结构，既包括基础的数组、结构体，也包括强大的 STL（Standard Template Library）容器，如 vector、map 等。这些数据结构各有优缺点，适合不同的场景。以下是对这些数据结构的详细介绍。

---

1. 数组（Array）

什么是数组？

数组是一组存储相同类型数据的连续内存块，可以通过索引访问元素。数组的大小在声明时固定，不能动态改变。

特点

• 连续存储：所有元素在内存中是连续分布的。
• 固定大小：声明时确定大小，运行时无法更改。
• 快速访问：通过索引直接访问元素，时间复杂度为 O(1)。
• 适用场景：适合存储已知大小的同类型数据集合。

实例

int arr[5] = {1, 2, 3, 4, 5}; // 定义一个整型数组
cout << arr[0]; // 输出第一个元素 1
arr[2] = 10;    // 修改第三个元素为 10

优缺点

• 优点：
  • 访问速度快（随机访问 O(1)）。
  • 内存紧凑。
• 缺点：
  • 无法动态调整大小。
  • 插入和删除效率低（需要移动元素）。

典型应用

• 数值统计（如存储分数列表）。
• 固定大小的矩阵或表格。

---

2. 结构体（Struct）

什么是结构体？

结构体是一种自定义数据类型，可以将不同类型的数据组合在一起。它可以看作是“迷你数据库”，用来描述某些实体或对象。

特点

• 可以组合多种数据类型。
• 成员变量可以是基本类型或复杂类型。
• 提供基本的封装，但功能有限。

实例

struct Person {
    string name;
    int age;
};

Person p = {"Alice", 25};
cout << p.name << endl; // 输出 "Alice"
p.age = 30; // 修改年龄

优缺点

• 优点：
  • 逻辑清晰，适合组织复杂数据。
• 缺点：
  • 不支持继承和多态，功能比类弱。

典型应用

• 用于表示实体对象，如学生、员工等。

---

3. 类（Class）

什么是类？

类是面向对象编程的核心，可以定义数据（成员变量）和行为（成员函数）。与结构体类似，但功能更强大，支持继承、多态、封装等特性。

特点

• 成员变量默认是私有的（private）。
• 支持方法、构造函数、析构函数等。
• 支持继承和多态。

实例

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）

什么是栈？

栈是一种后进先出（LIFO）的数据结构，像“弹簧盒”，只能从顶部插入和删除。

特点

• 只能操作栈顶元素。
• 插入和删除的时间复杂度为 O(1)。

实例

stack<int> s;
s.push(1);       // 压栈
s.push(2);
cout << s.top(); // 输出 2
s.pop();         // 弹栈

优缺点

• 优点：
  • 操作简单，效率高。
• 缺点：
  • 不能随机访问。

典型应用

• 递归调用栈。
• 表达式求值。

---

6. 队列（Queue）

什么是队列？

队列是一种先进先出（FIFO）的数据结构，像排队的队伍。

特点

• 从队尾插入元素，从队头删除元素。
• 时间复杂度为 O(1)。

实例

queue<int> q;
q.push(1);        // 入队
q.push(2);
cout << q.front(); // 输出 1
q.pop();          // 出队

优缺点

• 优点：
  • 按顺序处理数据，适合任务调度等场景。
• 缺点：
  • 无法随机访问。

典型应用

• 任务调度。
• 广度优先搜索（BFS）。

---

7. 动态数组（Vector）

什么是动态数组？

vector 是 C++ 标准库提供的动态数组实现，可以根据需要自动扩展大小。

特点

• 动态大小：内存不足时会自动扩容。
• 随机访问：支持通过索引访问元素，时间复杂度为 O(1)。

实例

vector<int> v;
v.push_back(1);
v.push_back(2);
cout << v[0]; // 输出 1

优缺点

• 优点：
  • 动态调整大小，使用方便。
• 缺点：
  • 插入/删除中间元素效率较低。

典型应用

• 动态增长的数据集合。

---

8. 哈希表（Hash Table）

什么是哈希表？

哈希表是一种通过键值对存储数据的结构，使用哈希函数快速定位元素。

特点

• 快速操作：查找、插入和删除的时间复杂度为 O(1)。
• 无序存储：元素存储顺序不固定。

实例

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

优缺点

• 优点：
  • 高效查找和操作。
• 缺点：
  • 可能发生哈希冲突。

典型应用

• 实现键值对存储，如字典。

---

总结

数据结构	特点	典型场景
数组（Array）	连续存储，固定大小，快速随机访问	固定大小的数据集合
结构体（Struct）	组合不同类型的数据	实体对象描述
类（Class）	支持面向对象编程，封装数据与行为	复杂对象建模
链表（Linked List）	动态大小，高效插入/删除，但查找效率低	数据流，动态数据集合
栈（Stack）	后进先出，操作简单	表达式求值，递归处理
队列（Queue）	先进先出，适合按顺序处理数据	任务调度