第3章：数据结构
3.1 基本数据结构
在这一小节中，我们讨论了几种最常见的基本数据结构，并介绍了它们的特点、操作方法和应用场景。
3.1.1 线性表 (Linear List)
定义：线性表是由一系列相同类型的元素按顺序排列而成的数据结构。最常见的线性表有数组和链表。 特点：元素之间存在一一对应的关系，可以通过下标访问每个元素。 线性表的两种常见实现：
数组 (Array)：固定大小的连续内存块，支持随机访问，但插入和删除操作效率较低。 链表 (Linked List)：由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表适合插入和删除操作，但访问效率较低。
3.1.2 栈 (Stack)
定义：栈是一种后进先出（LIFO，Last In First Out）的数据结构。栈只有一个操作端，即栈顶，所有操作都在栈顶进行。
基本操作：
push：将一个元素压入栈中。 pop：将栈顶元素移除。 top 或 peek：获取栈顶元素但不移除。 isEmpty：判断栈是否为空。
应用场景：
函数调用：计算机通过栈来保存函数调用的上下文信息（如局部变量、返回地址等）。 表达式求值：栈常用于运算符优先级的管理，例如在计算中缀表达式时使用栈来转换为后缀表达式。
3.1.3 队列 (Queue)
定义：队列是一种先进先出（FIFO，First In First Out）的数据结构。队列有两个操作端，分别是队头和队尾。
基本操作：
enqueue：将元素加入队尾。 dequeue：将队头元素移除。 front：获取队头元素但不移除。 isEmpty：判断队列是否为空。
应用场景：
任务调度：操作系统使用队列来管理等待执行的任务。 广度优先搜索 (BFS)：图算法中，队列用于管理待处理的节点。
3.2 链表 (Linked List)
3.2.1 单链表 (Singly Linked List)
定义：单链表是一种线性数据结构，其中每个节点包含一个数据域和一个指向下一个节点的指针。最后一个节点的指针指向 null，表示链表的结束。
操作：
插入操作：在链表头部、尾部或指定位置插入节点。 删除操作：删除指定位置的节点。 查找操作：查找指定值的节点。
优点：
- 动态内存分配，不需要提前知道元素数量。
- 插入和删除操作效率较高，尤其是在链表头部。
缺点：
- 不支持快速的随机访问。要访问某个节点，需要从头节点开始顺序遍历。
3.2.2 双向链表 (Doubly Linked List)
定义：双向链表是每个节点包含两个指针，一个指向前驱节点，一个指向后继节点。双向链表支持从两个方向进行遍历。 优点：可以在任意位置进行前向或后向遍历，插入和删除操作更加灵活。 缺点：比单链表需要更多的空间来存储前驱指针和后继指针。
3.3 栈的应用
栈有许多经典的应用，尤其在计算机科学中，栈在处理某些类型的递归、表达式计算和内存管理中非常重要。
3.3.1 括号匹配
问题：检查一个字符串中的括号是否正确匹配。 解决方法：通过栈来模拟括号的匹配。当遇到左括号时，将其压入栈中；当遇到右括号时，从栈中弹出对应的左括号。最终栈为空且没有多余的右括号，则括号匹配。
3.3.2 表达式求值
问题：计算算术表达式的值，尤其是后缀表达式。 解决方法：使用栈来保存操作数，当遇到运算符时，从栈中弹出操作数进行运算，再将结果压入栈中。
3.4 队列的应用
队列的应用主要体现在任务调度和图算法中。
3.4.1 任务调度
问题：操作系统中的进程调度常使用队列来管理等待执行的任务。任务按照先进先出的顺序被处理。
3.4.2 广度优先搜索 (BFS)
问题：在图算法中，广度优先搜索（BFS）使用队列来实现。BFS遍历图的每一层，使用队列来维护待访问的节点。
3.5 实现
在这一部分，书中会给出各种数据结构的实现代码。例如：
1. 栈的实现（使用链表）：
struct Node {
int data;
Node* next;
};
class Stack {
private:
Node* top;
public:
Stack() : top(nullptr) {}
void push(int value) {
Node* newNode = new Node{value, top};
top = newNode;
}
int pop() {
if (top == nullptr) throw std::out_of_range("Stack is empty");
int value = top->data;
Node* temp = top;
top = top->next;
delete temp;
return value;
}
bool isEmpty() {
return top == nullptr;
}
};
2. 队列的实现（使用数组）：
class Queue {
private:
int* arr;
int front, rear, capacity;
public:
Queue(int size) : capacity(size), front(0), rear(0) {
arr = new int[size];
}
void enqueue(int value) {
if ((rear + 1) % capacity == front) throw std::overflow_error("Queue is full");
arr[rear] = value;
rear = (rear + 1) % capacity;
}
int dequeue() {
if (front == rear) throw std::underflow_error("Queue is empty");
int value = arr[front];
front = (front + 1) % capacity;
return value;
}
bool isEmpty() {
return front == rear;
}
};
线性表 (Linear List)
线性表是一种非常基础的、重要的数据结构，它由一组元素按照顺序排列而成。在 C++ 中，线性表常见的实现方式有 数组 和 链表 两种形式。每种实现方式有不同的特点和适用场景。
1. 数组实现线性表
数组是线性表的一种实现，它提供了一个固定大小的连续内存空间来存储元素。数组支持随机访问，但插入和删除操作效率较低，尤其是当数组需要动态扩展时。
数组实现线性表
#include <iostream>
#include <stdexcept>
class ArrayList {
private:
int* arr; // 动态数组存储数据
int capacity; // 数组的容量
int size; // 当前存储的元素个数
public:
// 构造函数
ArrayList(int cap = 10) : capacity(cap), size(0) {
arr = new int[capacity]; // 动态分配内存
}
// 析构函数
~ArrayList() {
delete[] arr; // 释放内存
}
// 添加元素到数组末尾
void add(int value) {
if (size >= capacity) {
resize(); // 扩展数组容量
}
arr[size++] = value;
}
// 根据索引访问元素
int get(int index) {
if (index < 0 || index >= size) {
throw std::out_of_range("Index out of bounds");
}
return arr[index];
}
// 删除指定索引位置的元素
void remove(int index) {
if (index < 0 || index >= size) {
throw std::out_of_range("Index out of bounds");
}
for (int i = index; i < size - 1; ++i) {
arr[i] = arr[i + 1]; // 向前移动元素
}
--size;
}
// 扩展数组容量
void resize() {
capacity *= 2; // 容量翻倍
int* newArr = new int[capacity];
for (int i = 0; i < size; ++i) {
newArr[i] = arr[i];
}
delete[] arr; // 释放旧的数组
arr = newArr; // 更新为新的数组
}
// 打印所有元素
void print() {
for (int i = 0; i < size; ++i) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
// 获取数组的当前大小
int getSize() {
return size;
}
// 获取数组的容量
int getCapacity() {
return capacity;
}
};
int main() {
ArrayList list;
list.add(10);
list.add(20);
list.add(30);
list.add(40);
std::cout << "ArrayList after adding elements: ";
list.print();
std::cout << "Element at index 2: " << list.get(2) << std::endl;
list.remove(2);
std::cout << "ArrayList after removing element at index 2: ";
list.print();
std::cout << "Size: " << list.getSize() << ", Capacity: " << list.getCapacity() << std::endl;
return 0;
}
解释：
- 构造函数和析构函数：
ArrayList类通过动态分配内存来创建一个数组，并且在对象销毁时释放内存。 - 增加元素：
add方法在数组末尾添加元素，当数组容量不足时，会调用resize方法扩展容量。 - 删除元素：
remove方法删除指定索引位置的元素，删除时需要移动后面的元素来填补空位。 - 扩展数组容量：当元素个数超过数组容量时，
resize方法会将数组容量翻倍，并将原数组的元素复制到新的更大的数组中。 - 访问元素：通过
get方法访问指定索引位置的元素，索引越界时会抛出异常。
适用场景：
- 当数据量已知或变化较少时，可以使用数组实现线性表，快速随机访问元素。
2. 链表实现线性表
链表是通过指针连接的节点来实现的线性表。每个节点包含一个数据域和一个指向下一个节点的指针。链表的优点是可以动态地增加和删除元素，尤其是在头部或中间操作时，比数组更高效。
单链表实现线性表
#include <iostream>
#include <stdexcept>
class LinkedList {
private:
struct Node {
int data;
Node* next;
};
Node* head; // 链表头
int size; // 当前存储的元素个数
public:
// 构造函数
LinkedList() : head(nullptr), size(0) {}
// 析构函数
~LinkedList() {
while (head != nullptr) {
Node* temp = head;
head = head->next;
delete temp;
}
}
// 添加元素到链表尾部
void add(int value) {
Node* newNode = new Node{value, nullptr};
if (head == nullptr) {
head = newNode;
} else {
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
++size;
}
// 根据索引访问元素
int get(int index) {
if (index < 0 || index >= size) {
throw std::out_of_range("Index out of bounds");
}
Node* temp = head;
for (int i = 0; i < index; ++i) {
temp = temp->next;
}
return temp->data;
}
// 删除指定索引位置的元素
void remove(int index) {
if (index < 0 || index >= size) {
throw std::out_of_range("Index out of bounds");
}
Node* temp = head;
if (index == 0) {
head = head->next;
} else {
for (int i = 0; i < index - 1; ++i) {
temp = temp->next;
}
Node* toDelete = temp->next;
temp->next = temp->next->next;
delete toDelete;
}
--size;
}
// 打印所有元素
void print() {
Node* temp = head;
while (temp != nullptr) {
std::cout << temp->data << " ";
temp = temp->next;
}
std::cout << std::endl;
}
// 获取链表的当前大小
int getSize() {
return size;
}
};
int main() {
LinkedList list;
list.add(10);
list.add(20);
list.add(30);
list.add(40);
std::cout << "LinkedList after adding elements: ";
list.print();
std::cout << "Element at index 2: " << list.get(2) << std::endl;
list.remove(2);
std::cout << "LinkedList after removing element at index 2: ";
list.print();
std::cout << "Size: " << list.getSize() << std::endl;
return 0;
}
解释：
- 链表节点结构：每个节点包含一个数据域和一个指向下一个节点的指针（
next）。 - 添加元素：
add方法通过遍历链表，找到尾节点并将新节点链接到尾节点。 - 删除元素：
remove方法删除指定位置的节点，考虑删除头节点和中间节点的情况。 - 访问元素：通过
get方法遍历链表，返回指定索引位置的元素，若索引越界，抛出异常。
适用场景：
链表适合频繁进行插入和删除操作，特别是在中间或头部操作时比数组更高效。
总结
数组实现线性表：数组通过下标提供快速的随机访问，但插入和删除操作效率较低（尤其是需要扩展数组时）。 链表实现线性表：链表适合频繁的插入和删除操作，特别是在头部或中间部分操作时非常高效，但不支持快速的随机访问。
选择何种实现
数组：适合用于数据量已知且不需要频繁插入或删除元素的场景，如需要快速随机访问的应用。
链表：适合用于需要频繁插入和删除的场景，如任务调度、动态数据存储等。
在 C++ 标准库中，std::array 和 std::list 都是常用的容器类型，它们分别是 静态数组 和 双向链表 的实现。每个容器类型都具有自己独特的特性、优点和应用场景。在这部分，我们将详细介绍这两种容器的相关方法，并提供相应的示例。
1. std::array
std::array 是一个封装固定大小数组的容器，属于 C++11 引入的标准库。与传统的 C 风格数组不同，std::array 提供了更多的功能，例如容器接口和大小信息，能够更方便地操作固定大小的数组。
std::array 的特性
固定大小：一旦定义，std::array 的大小无法改变。
支持迭代器：可以像其他 STL 容器一样使用迭代器进行遍历。
集成 STL 算法：可以直接与 STL 算法（如 std::sort）配合使用。
与 C 风格数组兼容：底层是 C 风格数组，但提供了更多的成员函数来操作数据。
std::array 的常用方法
begin()和end()：返回数组的开始和结束迭代器。size()：返回数组的大小。at(index)：返回指定索引位置的元素，并进行范围检查。front()和back()：分别返回数组的第一个元素和最后一个元素。fill(value)：将所有元素填充为指定的值。swap(other)：交换当前数组与另一个std::array的元素。data()：返回指向数组元素的指针。
std::array 示例代码
#include <iostream>
#include <array>
#include <algorithm>
int main() {
// 创建一个固定大小的 std::array
std::array<int, 5> arr = {1, 2, 3, 4, 5};
// 获取数组大小
std::cout << "Size of array: " << arr.size() << std::endl;
// 使用迭代器遍历数组
std::cout << "Array elements: ";
for (auto it = arr.begin(); it != arr.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// 使用 at() 进行访问（带边界检查）
std::cout << "Element at index 2: " << arr.at(2) << std::endl;
// 获取第一个和最后一个元素
std::cout << "First element: " << arr.front() << std::endl;
std::cout << "Last element: " << arr.back() << std::endl;
// 使用 fill() 填充所有元素
arr.fill(10);
std::cout << "Array after fill: ";
for (int i : arr) {
std::cout << i << " ";
}
std::cout << std::endl;
// 使用 std::sort 对数组排序
std::sort(arr.begin(), arr.end());
std::cout << "Sorted array: ";
for (int i : arr) {
std::cout << i << " ";
}
std::cout << std::endl;
// 交换两个 std::array
std::array<int, 5> arr2 = {1, 1, 1, 1, 1};
arr.swap(arr2);
std::cout << "Array after swap: ";
for (int i : arr) {
std::cout << i << " ";
}
std::cout << std::endl;
return 0;
}
输出：
Size of array: 5
Array elements: 1 2 3 4 5
Element at index 2: 3
First element: 1
Last element: 5
Array after fill: 10 10 10 10 10
Sorted array: 10 10 10 10 10
Array after swap: 1 1 1 1 1
总结：
std::array是固定大小的数组封装，提供了更多的功能来替代传统的 C 风格数组。- 支持 STL 算法和迭代器，且能安全地进行索引操作（通过
at方法）。
2. std::list
std::list 是 C++ STL 提供的双向链表容器。它是一个 动态大小 的容器，允许高效的在头部和中间进行元素的插入和删除操作，但缺点是访问元素的效率较低（需要线性时间遍历链表）。
std::list 的特性
双向链表：每个节点包含数据和指向前一个节点及下一个节点的指针。
动态大小：可以随时向 std::list 中添加或删除元素，大小可以动态变化。
支持迭代器：可以使用迭代器进行遍历操作。
高效的插入和删除操作：尤其是在头部、中间或尾部进行操作时非常高效。
std::list 的常用方法
begin()和end()：返回指向第一个元素和最后一个元素之后的迭代器。size()：返回当前列表的元素个数。push_front()和push_back()：分别在头部和尾部添加元素。pop_front()和pop_back()：分别从头部和尾部删除元素。front()和back()：分别返回头部和尾部的元素。insert()：在指定位置插入元素。erase()：删除指定位置的元素。clear()：删除所有元素。sort()：对列表元素进行排序。remove()：删除指定值的所有元素。
std::list 示例代码
#include <iostream>
#include <list>
#include <algorithm>
int main() {
// 创建一个 std::list
std::list<int> lst = {10, 20, 30, 40, 50};
// 获取列表大小
std::cout << "Size of list: " << lst.size() << std::endl;
// 在列表尾部添加元素
lst.push_back(60);
// 在列表头部添加元素
lst.push_front(5);
std::cout << "List after pushing elements: ";
for (int val : lst) {
std::cout << val << " ";
}
std::cout << std::endl;
// 删除头部元素
lst.pop_front();
// 删除尾部元素
lst.pop_back();
std::cout << "List after popping elements: ";
for (int val : lst) {
std::cout << val << " ";
}
std::cout << std::endl;
// 使用 insert 插入元素到指定位置
auto it = lst.begin();
std::advance(it, 2); // 移动迭代器到索引 2
lst.insert(it, 25);
std::cout << "List after insertion: ";
for (int val : lst) {
std::cout << val << " ";
}
std::cout << std::endl;
// 使用 remove 删除特定元素
lst.remove(30); // 删除所有值为 30 的元素
std::cout << "List after removing 30: ";
for (int val : lst) {
std::cout << val << " ";
}
std::cout << std::endl;
// 对列表进行排序
lst.sort();
std::cout << "Sorted list: ";
for (int val : lst) {
std::cout << val << " ";
}
std::cout << std::endl;
// 清空列表
lst.clear();
std::cout << "List after clear: " << lst.size() << std::endl;
return 0;
}
输出：
Size of list: 5
List after pushing elements: 5 10 20 30 40 50 60
List after popping elements: 10 20 30 40 50
List after insertion: 10 20 25 30 40 50
List after removing 30: 10 20 25 40 50
Sorted list: 10 20 25 40 50
List after clear: 0
总结：
std::list 是一个双向链表，适合频繁进行插入和删除操作。
* 不支持随机访问，所有访问操作的时间复杂度是 O(n)