本文还有配套的精品资源，点击获取 menu-r.4af5f7ec.gif

简介：《殷人昆C++数据结构》是清华大学出版的经典教材，系统讲解了数组、链表、栈、队列、树、图、排序、查找、哈希表和堆等核心数据结构与算法。本书配套代码库包含所有例题的C++实现，内容详实、结构清晰，适合初学者打基础，也适合进阶者提升编程与算法设计能力。通过学习和实践这些代码，读者能够深入理解数据结构原理，并灵活应用于实际开发中。
清华 殷人昆C++数据结构 书中全部代码

1. C++数据结构概述

数据结构是程序设计中组织和管理数据的核心方式，直接影响程序的性能与可维护性。C++作为一门静态类型、面向对象的编程语言，提供了对数据结构的强大支持，如通过类封装、模板泛型编程、运算符重载等机制，使数据结构的设计与实现更加高效和灵活。

从结构分类来看，数据结构主要分为线性结构（如数组、链表、栈、队列）、树形结构（如二叉树、堆、平衡树）和图结构（如邻接矩阵、邻接表）。每种结构适用于不同的数据组织与访问需求。

在本书中，我们采用抽象数据类型（ADT）的设计思想，结合C++的面向对象特性，构建可复用的数据结构类。同时，为保证代码风格统一，我们将采用清晰、规范的命名约定，并在每个类中提供完整的构造、析构及异常处理机制。此外，每章将结合时间复杂度分析，帮助读者理解算法效率与优化方向。

2. 数组实现与操作详解

数组是编程中最基础也是最常用的数据结构之一。在C++中，数组提供了一种连续存储相同类型数据的方式，具备高效的访问和遍历能力。然而，数组的静态特性（长度固定）也带来了一些操作上的限制。本章将深入探讨数组的基本操作、封装设计与安全性增强策略，帮助开发者更全面地理解数组在C++中的实现机制与应用方式。

2.1 静态数组的基本操作

2.1.1 数组的定义与初始化

在C++中，静态数组的定义方式如下： 

int arr[10]; // 定义一个长度为10的整型数组

该数组在栈上分配内存，生命周期由编译器自动管理。数组的初始化可以在定义时完成： 

int arr[5] = {1, 2, 3, 4, 5}; // 完全初始化
int arr2[5] = {1, 2};         // 部分初始化，其余元素默认为0
int arr3[] = {1, 2, 3};       // 编译器自动推导长度

数组的访问通过索引完成，索引从 0 开始。例如： 

std::cout << arr[0]; // 输出第一个元素

需要注意的是，C++不会对数组越界进行检查，因此开发者需自行确保索引的有效性。

2.1.2 元素的访问、插入与删除

元素访问

访问数组元素的时间复杂度为 O(1)，这是数组的一大优势： 

int value = arr[2]; // 访问第三个元素
插入操作

由于静态数组长度固定，插入操作会改变数组结构，需手动实现： 

void insert(int arr[], int& size, int index, int value) {
    if (size >= MAX_SIZE) return; // 防止溢出
    if (index < 0 || index > size) return; // 非法索引

    for (int i = size; i > index; --i) {
        arr[i] = arr[i - 1];
    }
    arr[index] = value;
    ++size;
}

上述函数将指定索引位置插入一个新元素，整体复杂度为 O(n)。

删除操作

删除操作同样需要移动元素： 

void remove(int arr[], int& size, int index) {
    if (index < 0 || index >= size) return;

    for (int i = index; i < size - 1; ++i) {
        arr[i] = arr[i + 1];
    }
    --size;
}

删除操作的时间复杂度也为 O(n)，适用于元素较少的场景。

2.1.3 数组的遍历与查找

遍历操作

遍历数组可使用传统 for 循环或 C++11 的范围 for ： 

for (int i = 0; i < size; ++i) {
    std::cout << arr[i] << " ";
}

for (int val : arr) {
    std::cout << val << " ";
}

第二种方式更简洁，适用于静态数组或容器类型。

查找操作

查找元素可以采用线性搜索或二分查找（前提是数组有序）： 

int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; ++i) {
        if (arr[i] == target) return i;
    }
    return -1;
}

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

线性查找适用于无序数组，复杂度为 O(n)；二分查找适用于有序数组，复杂度为 O(log n)，效率更高。

2.2 数组的封装与类设计

为了增强数组的安全性和可维护性，通常将其封装为类，通过类成员函数管理数组的生命周期与操作。

2.2.1 数组类 MyArray 的封装设计

定义一个 MyArray 类，包含基本属性与操作： 

class MyArray {
private:
    int* data;      // 指向数组的指针
    int capacity;   // 数组容量
    int size;       // 当前元素数量

public:
    MyArray(int cap);
    ~MyArray();

    void insert(int index, int value);
    void remove(int index);
    int get(int index) const;
    int find(int value) const;
    void print() const;
};

此类将数组的访问封装在成员函数中，并提供了边界检查和动态管理的能力。

2.2.2 构造函数与析构函数的实现

构造函数负责分配内存并初始化类成员： 

MyArray::MyArray(int cap) : capacity(cap), size(0) {
    data = new int[capacity];
}

析构函数负责释放内存，防止内存泄漏： 

MyArray::~MyArray() {
    delete[] data;
}

构造与析构函数的设计是类安全性的基础，尤其是在动态内存分配的场景下。

2.2.3 运算符重载实现数组操作

重载 [] 运算符，实现安全的元素访问： 

int& MyArray::operator[](int index) {
    if (index < 0 || index >= size) {
        throw std::out_of_range("Index out of bounds");
    }
    return data[index];
}

使用时可如下： 

MyArray arr(10);
arr[0] = 100;
std::cout << arr[0];

该设计结合了运算符重载与异常处理，提升了代码的可读性和健壮性。

2.3 数组的边界检查与异常处理

2.3.1 越界访问的风险与检测机制

数组越界是C++中常见的错误来源之一，可能导致程序崩溃或数据损坏。例如： 

int arr[5] = {1, 2, 3, 4, 5};
std::cout << arr[10]; // 未定义行为

为防止此类问题，应在访问前进行边界检查： 

if (index >= 0 && index < size) {
    return data[index];
} else {
    // 错误处理
}

2.3.2 使用异常类 throw out_of_range 处理错误

C++标准库提供了 std::out_of_range 异常类用于处理越界访问： 

int MyArray::get(int index) const {
    if (index < 0 || index >= size) {
        throw std::out_of_range("Index is out of range");
    }
    return data[index];
}

调用时使用 try-catch 块捕获异常： 

try {
    std::cout << arr.get(10);
} catch (const std::out_of_range& e) {
    std::cerr << "Error: " << e.what() << std::endl;
}

此机制增强了程序的健壮性，使错误处理更加清晰可控。

2.3.3 数组类的安全性增强策略

除了边界检查和异常处理，还可以通过以下方式增强数组类的安全性：

  1. 访问封装 ：禁止直接访问内部数据，仅通过接口操作。
  2. 常量成员函数 ：为不修改对象状态的方法加上 const 限定符。
  3. 复制控制 ：实现拷贝构造函数和赋值运算符，防止浅拷贝问题。
  4. RAII机制 ：利用构造与析构自动管理资源。

例如，添加 const 成员函数： 

int MyArray::get(int index) const {
    // 只读操作
}

该函数确保不会修改对象状态，适用于常量对象。

本章总结

本章从静态数组的基本操作出发，深入讲解了数组的定义、访问、插入、删除、查找等核心操作，并通过类封装的方式提升了数组的可维护性与安全性。进一步地，我们探讨了边界检查与异常处理机制，确保程序在越界访问等错误情况下仍能保持稳定性。通过本章的学习，开发者不仅掌握了数组的基本使用方法，也理解了如何将其封装为更高级的数据结构，为后续动态数组与复杂数据结构的实现打下坚实基础。

3. 动态数组设计与扩展机制

在现代软件开发中，数据量的动态变化是常态。传统的静态数组虽然在内存连续性和访问效率上表现优异，但由于其容量固定，难以满足程序运行过程中对内存需求的实时变化。为了解决这一问题， 动态数组（Dynamic Array） 应运而生。动态数组通过 动态内存分配 和 自动扩容机制 ，在运行时按需调整内存大小，兼顾了性能与灵活性。本章将从动态内存分配的基本操作开始，逐步深入讲解动态数组的扩容机制，并最终实现一个完整的动态数组类。

3.1 动态内存分配基础

动态数组之所以能够实现容量的动态调整，核心在于 动态内存管理机制 。C++ 提供了 new 和 delete 操作符用于在堆（heap）上动态分配和释放内存，这使得我们可以在程序运行时灵活地管理数据结构的大小。

3.1.1 new与delete操作符的使用

在 C++ 中， new 用于在堆上分配内存， delete 用于释放由 new 分配的内存。对于数组来说，我们需要使用 new[] 和 delete[] 。 

int* arr = new int[5];  // 动态分配5个整型元素的数组
for(int i = 0; i < 5; ++i) {
    arr[i] = i;
}
// 使用完成后释放
delete[] arr;

逐行分析：
- 第1行：使用 new int[5] 在堆上分配一个长度为5的整型数组，返回指向首元素的指针。
- 第2~4行：对数组进行初始化赋值。
- 第6行：使用 delete[] 释放数组内存，防止内存泄漏。

3.1.2 动态数组与静态数组的对比

特性 静态数组 动态数组
内存位置 栈上 堆上
容量 固定不可变 动态可扩展
性能 快，访问效率高 略慢于静态数组
生命周期管理 自动释放 需手动管理释放
适用场景 已知大小、生命周期短 未知大小、需扩展、生命周期长

逻辑分析：
- 静态数组适合小型、固定大小的数据存储，动态数组则适合处理未知大小或需频繁扩展的场景。
- 动态数组的灵活性是以牺牲部分性能和增加内存管理复杂度为代价的。

3.1.3 内存泄漏与深拷贝问题

动态数组在使用过程中最常遇到的问题是 内存泄漏 （memory leak）和 浅拷贝问题 （shallow copy）。

示例：浅拷贝引发的内存泄漏 
class MyArray {
private:
    int* data;
    int size;
public:
    MyArray(int s) {
        size = s;
        data = new int[size];
    }
    ~MyArray() {
        delete[] data;
    }
};

int main() {
    MyArray a(5);
    MyArray b = a; // 默认拷贝构造函数，浅拷贝
    return 0;
}

问题分析：
- 默认拷贝构造函数进行的是浅拷贝， a 和 b 的 data 指向同一块内存。
- 当 b 析构时释放了这块内存，之后 a 析构时再次释放同一块内存，导致 重复释放（double free） ，程序崩溃。
- 若程序中某块内存未被释放，则造成 内存泄漏 。

解决方法：
- 实现 深拷贝构造函数 ，即为新对象重新分配内存并复制数据。
- 实现 赋值运算符重载 （operator=），避免浅拷贝问题。

3.2 动态数组的自动扩容机制

动态数组的核心优势在于其 自动扩容机制 。当数组中已无多余空间时，动态数组会自动申请更大的内存块，并将原数据复制过去，释放旧内存。这一过程对用户透明，是实现高效动态数组的关键。

3.2.1 容量与大小的概念区分

在动态数组中，“ 容量（capacity） ”与“ 大小（size） ”是两个重要概念。

概念 含义 示例说明
size 当前数组中已存储的元素数量 如数组中已存入3个元素
capacity 数组当前所分配的内存能容纳的最大元素数量 若分配了10个空间，capacity=10

逻辑分析：
- size 是逻辑上的元素数量， capacity 是物理上的内存空间。
- 只有当 size == capacity 时，才需要进行扩容。

3.2.2 扩容策略与实现逻辑

常见的扩容策略包括：
- 固定增量策略 ：每次扩容固定大小（如 +10）
- 倍增策略 ：每次扩容为当前容量的两倍（常见做法）

示例：动态扩容函数实现 
void expandCapacity() {
    capacity *= 2;
    int* newData = new int[capacity];
    for(int i = 0; i < size; ++i) {
        newData[i] = data[i];
    }
    delete[] data;
    data = newData;
}

逐行分析：
- 第1行：将当前容量翻倍。
- 第2行：申请新内存空间。
- 第3~5行：将旧数组内容复制到新数组。
- 第6~7行：释放旧内存，更新指针指向新内存。

流程图：扩容逻辑 
graph TD
    A[数组已满？] -->|是| B[申请新内存]
    B --> C[复制原数据]
    C --> D[释放旧内存]
    D --> E[更新指针与容量]
    A -->|否| F[无需扩容]

3.2.3 时间复杂度分析与优化建议

假设每次扩容为当前容量的两倍：

  • 插入操作的均摊时间复杂度 ：O(1)
  • 单次扩容的时间复杂度 ：O(n)

分析过程：
- 扩容时需要复制全部元素，因此单次操作为 O(n)
- 但扩容不是每次插入都发生，而是呈指数级增长，因此均摊后每次插入为 O(1)

优化建议：
- 可根据使用场景调整扩容系数（如 1.5 倍）
- 引入 缩容机制 （如当 size < capacity/4 时，capacity 减半）
- 提供 reserve() 接口让用户主动预留空间，减少频繁扩容

3.3 动态数组类的完整实现

本节将实现一个完整的动态数组类 DynamicArray ，包括构造函数、析构函数、深拷贝、扩容机制等关键部分。

3.3.1 类成员变量与函数接口设计 

class DynamicArray {
private:
    int* data;
    int size;
    int capacity;

    void expandCapacity();
public:
    DynamicArray(int cap = 10); // 构造函数
    ~DynamicArray();             // 析构函数
    DynamicArray(const DynamicArray& other); // 拷贝构造
    DynamicArray& operator=(const DynamicArray& other); // 赋值运算符
    void push_back(int value);
    int get(int index) const;
    int getSize() const { return size; }
    int getCapacity() const { return capacity; }
};

接口说明：
- push_back() ：在数组末尾添加元素，触发扩容逻辑。
- get() ：按索引获取元素，用于封装访问逻辑。
- 拷贝构造函数和赋值运算符重载用于解决浅拷贝问题。

3.3.2 拷贝构造函数与赋值运算符重载 

DynamicArray::DynamicArray(const DynamicArray& other) {
    size = other.size;
    capacity = other.capacity;
    data = new int[capacity];
    for(int i = 0; i < size; ++i) {
        data[i] = other.data[i];
    }
}

DynamicArray& DynamicArray::operator=(const DynamicArray& other) {
    if (this == &other) return *this;
    delete[] data;
    size = other.size;
    capacity = other.capacity;
    data = new int[capacity];
    for(int i = 0; i < size; ++i) {
        data[i] = other.data[i];
    }
    return *this;
}

逐行分析：
- 拷贝构造函数中，为新对象分配新内存并复制数据，实现深拷贝。
- 赋值运算符中，先释放旧内存，再分配新内存并复制数据，防止内存泄漏。
- 判断 this == &other 避免自赋值问题。

3.3.3 实际应用案例：动态数组在数据缓存中的使用

动态数组在实际开发中常用于实现 数据缓存（Data Buffer） 。例如在网络通信中，接收端需要不断接收数据包，但数据长度未知，使用动态数组可以实现自动扩容的数据缓存。

示例：数据缓存模拟 
DynamicArray buffer;
for(int i = 0; i < 100; ++i) {
    buffer.push_back(i);
    std::cout << "Size: " << buffer.getSize()
              << ", Capacity: " << buffer.getCapacity() << std::endl;
}

输出示例： 

Size: 1, Capacity: 10
Size: 2, Capacity: 10
Size: 10, Capacity: 10
Size: 11, Capacity: 20
Size: 20, Capacity: 20
Size: 21, Capacity: 40

分析：
- 初始容量为10，当插入第11个元素时，容量翻倍为20。
- 插入第21个元素时，容量再次翻倍为40。
- 动态数组自动扩容，适应数据增长需求。

总结：
动态数组通过 new / delete 进行内存管理，结合自动扩容机制，实现了高效、灵活的数据结构。在实际开发中，合理设计扩容策略、实现深拷贝与赋值操作，是确保动态数组稳定运行的关键。后续章节中我们将基于动态数组的思想，深入探讨链表、栈、队列等更复杂的数据结构实现。

4. 链表（单链表、双链表、循环链表）实现

链表是一种基础而重要的线性数据结构，与数组不同，链表通过指针连接各个节点，具有动态分配内存、插入和删除效率高等特点。本章将深入讲解链表的结构设计、实现方式及其操作逻辑，涵盖单链表、双链表和循环链表三种常见形式，并结合类封装、操作实现和统一接口设计进行系统阐述。

4.1 链表的基本概念与结构设计

链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表与数组最大的不同在于其非连续存储的特性，这使得它在插入和删除操作上具有显著优势。

4.1.1 节点结构与指针操作

链表的基本单位是节点（Node），其结构通常如下： 

struct Node {
    int data;       // 数据域
    Node* next;     // 指针域，指向下一个节点
};
  • data 用于存储数据；
  • next 是指向下一个节点的指针，构成链式结构。
指针操作的逻辑分析

在链表中，通过指针访问节点，例如创建节点并连接： 

Node* head = new Node();   // 创建头节点
head->data = 10;
head->next = nullptr;      // 初始化为空

Node* second = new Node();
second->data = 20;
second->next = nullptr;

head->next = second;       // 将头节点与第二个节点连接

上述代码中， new 操作符用于动态分配内存， -> 用于访问指针所指向对象的成员。 nullptr 表示链表的结束。

内存管理注意事项
  • 使用 new 分配的内存需在适当时候使用 delete 释放，避免内存泄漏；
  • 避免野指针：释放后应将指针设为 nullptr 。

4.1.2 单链表、双链表与循环链表的区别

类型 节点结构 特点
单链表 每个节点只有一个 next 指针 只能从前往后遍历，插入/删除效率高
双链表 每个节点有两个指针： prev 和 next 可双向遍历，但占用更多内存
循环链表 尾节点指向头节点 构成环形结构，适合循环任务或队列管理
结构对比图（Mermaid 流程图） 
graph LR
    A[单链表] --> B[节点A]
    B --> C[节点B]
    C --> D[节点C]
    D --> E[NULL]

    F[双链表] --> G[节点A]
    G --> H[节点B]
    H --> I[节点C]
    H -->|prev| G
    I -->|prev| H

    J[循环链表] --> K[节点A]
    K --> L[节点B]
    L --> M[节点C]
    M --> K

4.1.3 链表的插入与删除操作

链表的插入和删除是其最核心的操作之一，它们的时间复杂度为 O(1)（已知插入位置），优于数组。

插入操作示例（单链表） 
// 在节点 prev 后插入新节点
void insertAfter(Node* prev, int newData) {
    if (prev == nullptr) return; // 空指针检查

    Node* newNode = new Node();
    newNode->data = newData;
    newNode->next = prev->next;
    prev->next = newNode;
}
  • newNode->next = prev->next ：将新节点的指针指向原 prev 的下一个节点；
  • prev->next = newNode ：将 prev 的指针指向新节点。
删除操作示例（单链表） 
// 删除节点 prev 后的节点
void deleteAfter(Node* prev) {
    if (prev == nullptr || prev->next == nullptr) return;

    Node* delNode = prev->next;
    prev->next = delNode->next;
    delete delNode;
    delNode = nullptr;
}
  • 检查 prev 是否为空，或者 prev 的下一个节点是否存在；
  • delNode 是待删除节点；
  • 释放内存并设置为 nullptr 防止野指针。

4.2 单链表的实现与操作

单链表是最基础的链表形式，理解其实现有助于掌握链表操作的核心逻辑。

4.2.1 头插法与尾插法实现

头插法

头插法将新节点插入链表头部，时间复杂度为 O(1)。 

class SingleLinkedList {
private:
    Node* head;
public:
    SingleLinkedList() : head(nullptr) {}

    void insertAtHead(int data) {
        Node* newNode = new Node();
        newNode->data = data;
        newNode->next = head;
        head = newNode;
    }
};
  • newNode->next = head ：新节点指向原头节点；
  • head = newNode ：更新头指针。
尾插法

尾插法将新节点插入链表尾部，时间复杂度为 O(n)，除非维护一个尾指针。 

void insertAtTail(int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = nullptr;

    if (head == nullptr) {
        head = newNode;
        return;
    }

    Node* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = newNode;
}
  • 若链表为空，则新节点为头节点；
  • 否则遍历链表找到尾节点，并将尾节点的 next 指向新节点。

4.2.2 查找、删除与逆序操作

查找操作 
Node* find(int data) {
    Node* current = head;
    while (current != nullptr) {
        if (current->data == data)
            return current;
        current = current->next;
    }
    return nullptr;
}
  • 遍历链表，查找数据匹配的节点；
  • 若未找到，返回 nullptr 。
删除指定节点 
void deleteNode(int data) {
    Node* current = head;
    Node* prev = nullptr;

    while (current != nullptr && current->data != data) {
        prev = current;
        current = current->next;
    }

    if (current == nullptr) return; // 未找到节点

    if (prev == nullptr) {
        head = current->next; // 删除头节点
    } else {
        prev->next = current->next; // 删除中间或尾节点
    }
    delete current;
}
  • 使用两个指针记录当前节点和前驱节点；
  • 若删除头节点，则更新 head ；
  • 否则修改前驱节点的 next 指针。
逆序操作 
void reverse() {
    Node* prev = nullptr;
    Node* current = head;
    Node* next = nullptr;

    while (current != nullptr) {
        next = current->next; // 保存下一个节点
        current->next = prev; // 反转当前节点
        prev = current;       // 移动指针
        current = next;
    }
    head = prev; // 更新头指针
}
  • 使用三个指针完成链表反转；
  • 每次循环将当前节点的 next 指向前一个节点；
  • 最后更新 head 指向原尾节点。

4.2.3 单链表的类封装与接口设计

接口设计示例 
class SingleLinkedList {
private:
    struct Node {
        int data;
        Node* next;
    };
    Node* head;

public:
    SingleLinkedList() : head(nullptr) {}
    ~SingleLinkedList();

    void insertAtHead(int data);
    void insertAtTail(int data);
    void deleteNode(int data);
    void reverse();
    void printList() const;
};
  • 使用结构体 Node 定义节点；
  • 提供基本操作：插入、删除、逆序、打印；
  • 析构函数需释放所有节点内存。
打印链表函数实现 
void SingleLinkedList::printList() const {
    Node* current = head;
    while (current != nullptr) {
        std::cout << current->data << " -> ";
        current = current->next;
    }
    std::cout << "NULL" << std::endl;
}
  • 遍历链表输出每个节点数据；
  • 以 -> NULL 结束表示链表末尾。

4.3 双链表与循环链表的实现

4.3.1 双链表节点结构与操作实现

双链表每个节点包含两个指针： prev 和 next ，可实现双向遍历。

节点结构定义 
struct DoubleNode {
    int data;
    DoubleNode* prev;
    DoubleNode* next;
};
插入操作（在节点后插入） 
void insertAfter(DoubleNode* prevNode, int data) {
    if (prevNode == nullptr) return;

    DoubleNode* newNode = new DoubleNode();
    newNode->data = data;

    newNode->next = prevNode->next;
    prevNode->next = newNode;
    newNode->prev = prevNode;

    if (newNode->next != nullptr)
        newNode->next->prev = newNode;
}
  • newNode->next = prevNode->next ：将新节点指向原节点的下一个；
  • newNode->prev = prevNode ：设置新节点的前驱；
  • 若新节点不是尾节点，则设置其后继的 prev 。
删除操作 
void deleteNode(DoubleNode* delNode) {
    if (delNode == nullptr) return;

    if (delNode->prev != nullptr)
        delNode->prev->next = delNode->next;
    if (delNode->next != nullptr)
        delNode->next->prev = delNode->prev;

    delete delNode;
    delNode = nullptr;
}
  • 更新前驱和后继节点的指针；
  • 释放内存并置空指针。

4.3.2 循环链表的判断与遍历方式

循环链表的尾节点指向头节点，形成环形结构。

判断是否为循环链表 
bool isCircular(DoubleNode* head) {
    if (head == nullptr) return false;

    DoubleNode* slow = head;
    DoubleNode* fast = head;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast)
            return true;
    }
    return false;
}
  • 使用快慢指针法判断是否有环；
  • 若快指针追上慢指针，则存在环。
遍历循环链表 
void printCircularList(DoubleNode* head) {
    if (head == nullptr) return;

    DoubleNode* current = head;
    do {
        std::cout << current->data << " -> ";
        current = current->next;
    } while (current != head);

    std::cout << "(回到头节点)" << std::endl;
}
  • 使用 do-while 循环，确保至少执行一次；
  • 当 current == head 时结束遍历。

4.3.3 链表类的统一接口设计与多态应用

为了实现单链表、双链表和循环链表的统一接口，可以使用继承和多态。

基类定义 
class LinkedList {
public:
    virtual void insert(int data) = 0;
    virtual void remove(int data) = 0;
    virtual void print() const = 0;
    virtual ~LinkedList() {}
};
单链表子类实现 
class SingleLinkedList : public LinkedList {
private:
    struct Node {
        int data;
        Node* next;
    };
    Node* head;
public:
    SingleLinkedList() : head(nullptr) {}
    void insert(int data) override;
    void remove(int data) override;
    void print() const override;
};
统一接口的使用示例 
int main() {
    LinkedList* list = new SingleLinkedList();
    list->insert(10);
    list->insert(20);
    list->print(); // 输出 10 -> 20 -> NULL

    delete list;
    return 0;
}
  • 通过基类指针调用子类实现，实现多态；
  • 可扩展支持双链表、循环链表等子类，统一接口调用。

本章系统讲解了链表的结构设计、实现方式与操作逻辑，涵盖了单链表、双链表和循环链表的具体实现，并通过类封装和接口统一设计，展示了链表在实际开发中的应用模式。

5. 栈的数组与链表实现（LIFO）

5.1 栈的抽象数据类型与应用场景

5.1.1 栈的基本操作（Push、Pop、Top）

栈（Stack）是一种后进先出（LIFO, Last In First Out）的数据结构，它的操作主要包括以下几种：

  • Push ：将元素压入栈顶。
  • Pop ：将栈顶元素弹出。
  • Top （或 Peek ）：获取栈顶元素，但不弹出。
  • IsEmpty ：判断栈是否为空。
  • Size ：获取栈中当前元素的数量。

这些操作的时间复杂度均为 O(1)，因为栈的访问和修改仅发生在栈顶。

为了更清晰地理解栈的操作逻辑，我们可以用一个简单的类图来表示其抽象数据类型结构： 

classDiagram
    class Stack {
        <<interface>>
        +push(element T)
        +pop() T
        +top() T
        +isEmpty() bool
        +size() int
    }

5.1.2 栈在表达式求值、括号匹配中的应用

栈在实际应用中非常广泛，尤其在以下两个经典场景中发挥着重要作用：

1. 表达式求值

在中缀表达式转后缀表达式（逆波兰表达式）以及后缀表达式的计算过程中，栈用于保存操作符和操作数。

示例代码：后缀表达式求值 
#include <iostream>
#include <stack>
#include <sstream>
#include <cctype>

int evaluatePostfix(const std::string& expression) {
    std::stack<int> s;
    std::istringstream iss(expression);
    std::string token;

    while (iss >> token) {
        if (isdigit(token[0])) {
            s.push(std::stoi(token));
        } else {
            int b = s.top(); s.pop();
            int a = s.top(); s.pop();
            switch (token[0]) {
                case '+': s.push(a + b); break;
                case '-': s.push(a - b); break;
                case '*': s.push(a * b); break;
                case '/': s.push(a / b); break;
            }
        }
    }
    return s.top();
}

逐行解析：

  • std::stack<int> s; ：定义一个整型栈，用于存储操作数。
  • std::istringstream ：将字符串拆分为多个 token。
  • isdigit(token[0]) ：判断当前 token 是否为数字。
  • 如果是操作符，取出栈顶两个操作数进行计算，并将结果压入栈中。
  • 最终栈顶的值即为表达式结果。
2. 括号匹配检查

在编译器设计中，括号匹配是语法分析的一部分。使用栈可以轻松实现这一功能。

示例代码：括号匹配检查 
bool isBalanced(const std::string& expr) {
    std::stack<char> s;
    for (char ch : expr) {
        if (ch == '(' || ch == '{' || ch == '[')
            s.push(ch);
        else if (ch == ')' || ch == '}' || ch == ']') {
            if (s.empty()) return false;
            char top = s.top(); s.pop();
            if ((ch == ')' && top != '(') ||
                (ch == '}' && top != '{') ||
                (ch == ']' && top != '[')) {
                return false;
            }
        }
    }
    return s.empty();
}

逐行解析：

  • 遇到左括号就入栈。
  • 遇到右括号时，判断栈是否为空，若为空说明不匹配。
  • 若栈不为空，取出栈顶元素判断是否匹配。
  • 最后栈为空则说明括号全部匹配。

5.1.3 栈的STL实现与自定义实现对比

C++ STL 提供了 <stack> 容器适配器，其底层默认使用 deque 实现。我们可以直接使用： 

#include <stack>
std::stack<int> st;
st.push(10);
st.pop();

STL 栈优点：

  • 稳定性强，经过大量测试。
  • 使用简单，封装良好。
  • 可替换底层容器（如 vector 、 list ）。

自定义栈优点：

  • 更灵活，可添加自定义功能（如容量限制、日志记录）。
  • 可以根据需求优化性能。
  • 有助于理解栈的底层实现机制。

表格对比：STL 栈与自定义栈

特性 STL 栈 自定义栈
实现复杂度 极低，直接调用接口 较高，需手动实现类结构
可扩展性 一般，依赖底层容器 高，可根据需求添加任意功能
性能控制能力 低，封装好不可更改 高，可自行优化内存管理、扩容策略
调试与日志支持 有限 可加入日志、断言等调试信息
应用场景 快速开发、通用需求 高性能、特定业务需求、教学实践

5.2 数组实现的顺序栈

5.2.1 栈的结构定义与初始化

顺序栈是基于数组实现的栈结构。我们使用固定大小的数组来存储栈元素，并维护一个栈顶指针 top 来指示当前栈顶位置。

栈类定义示例： 
#define MAX_SIZE 100

class ArrayStack {
private:
    int arr[MAX_SIZE];
    int topIndex;
public:
    ArrayStack() : topIndex(-1) {}
    bool isEmpty() const;
    bool isFull() const;
    void push(int value);
    int pop();
    int top() const;
};

参数说明：

  • arr[MAX_SIZE] ：固定大小的数组，用于存储栈元素。
  • topIndex ：表示栈顶元素的索引，初始为 -1，表示栈空。

5.2.2 栈满与栈空的判断条件

  • 栈空条件 ： topIndex == -1
  • 栈满条件 ： topIndex == MAX_SIZE - 1

这两个条件决定了是否可以进行 push 或 pop 操作。

实现判断函数： 
bool ArrayStack::isEmpty() const {
    return topIndex == -1;
}

bool ArrayStack::isFull() const {
    return topIndex == MAX_SIZE - 1;
}

5.2.3 栈操作的实现与异常处理

Push 操作： 
void ArrayStack::push(int value) {
    if (isFull()) {
        throw std::overflow_error("Stack overflow");
    }
    arr[++topIndex] = value;
}
Pop 操作： 
int ArrayStack::pop() {
    if (isEmpty()) {
        throw std::underflow_error("Stack underflow");
    }
    return arr[topIndex--];
}
Top 操作： 
int ArrayStack::top() const {
    if (isEmpty()) {
        throw std::underflow_error("Stack is empty");
    }
    return arr[topIndex];
}

异常处理说明：

  • 使用 C++ 的标准异常类 std::overflow_error 和 std::underflow_error 来处理栈满和栈空的情况。
  • 在实际应用中，可以结合 try-catch 机制进行错误处理。
示例使用： 
int main() {
    ArrayStack stack;
    try {
        stack.push(10);
        stack.push(20);
        std::cout << "Top: " << stack.top() << std::endl;
        std::cout << "Pop: " << stack.pop() << std::endl;
        std::cout << "Top: " << stack.top() << std::endl;
    } catch (const std::exception& e) {
        std::cerr << "Error: " << e.what() << std::endl;
    }
    return 0;
}

输出： 

Top: 20
Pop: 20
Top: 10

5.3 链表实现的链式栈

5.3.1 链栈的节点结构与操作

链式栈使用链表实现栈结构，每个节点包含一个数据域和一个指向下一个节点的指针。这种实现方式没有固定大小限制，动态分配内存。

节点结构定义： 
struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};
链栈类定义： 
class LinkedStack {
private:
    Node* topNode;
public:
    LinkedStack() : topNode(nullptr) {}
    ~LinkedStack();
    bool isEmpty() const;
    void push(int value);
    int pop();
    int top() const;
};

5.3.2 插入与删除操作的时间复杂度分析

链式栈的插入和删除操作都在链表头部进行，时间复杂度为 O(1) 。

Push 操作： 
void LinkedStack::push(int value) {
    Node* newNode = new Node(value);
    newNode->next = topNode;
    topNode = newNode;
}
Pop 操作： 
int LinkedStack::pop() {
    if (isEmpty()) {
        throw std::underflow_error("Stack underflow");
    }
    Node* temp = topNode;
    int val = temp->data;
    topNode = topNode->next;
    delete temp;
    return val;
}
Top 操作： 
int LinkedStack::top() const {
    if (isEmpty()) {
        throw std::underflow_error("Stack is empty");
    }
    return topNode->data;
}

5.3.3 链栈类的设计与实现

析构函数实现： 
LinkedStack::~LinkedStack() {
    while (!isEmpty()) {
        pop();
    }
}
示例使用： 
int main() {
    LinkedStack stack;
    try {
        stack.push(10);
        stack.push(20);
        std::cout << "Top: " << stack.top() << std::endl;
        std::cout << "Pop: " << stack.pop() << std::endl;
        std::cout << "Top: " << stack.top() << std::endl;
    } catch (const std::exception& e) {
        std::cerr << "Error: " << e.what() << std::endl;
    }
    return 0;
}

输出： 

Top: 20
Pop: 20
Top: 10

表格对比：顺序栈与链式栈

特性 顺序栈 链式栈
存储方式 固定大小数组 动态链表
扩展性 不可扩展 可无限扩展
时间复杂度 所有操作 O(1) 所有操作 O(1)
内存效率 高，一次性分配 低，频繁分配释放
异常处理 栈满异常 不会栈满，只有内存不足异常
实现复杂度 简单 稍复杂，需处理指针
适用场景 数据量固定、内存敏感场景 数据量不确定、频繁变化场景

总结对比

顺序栈适合在已知最大容量、对内存访问速度有要求的场景中使用，而链式栈则适合数据量动态变化、需要灵活扩展的场景。两者在核心操作的时间复杂度上一致，但实现机制和适用场景各有侧重。

6. 队列的数组与链表实现（FIFO）

6.1 队列的基本概念与操作

6.1.1 队列的定义与基本操作（Enqueue、Dequeue）

队列（Queue）是一种 先进先出 （FIFO, First-In-First-Out）的线性数据结构，它只允许在 队尾 （rear）进行插入操作，在 队头 （front）进行删除操作。这种结构非常适用于需要按顺序处理任务的场景，如任务调度、打印队列、缓冲池等。

常见的基本操作包括：

  • Enqueue ：在队列尾部插入一个元素。
  • Dequeue ：从队列头部移除一个元素。
  • Front/Peek ：获取队列头部元素而不移除。
  • IsEmpty ：判断队列是否为空。
  • Size ：获取队列中元素的数量。

6.1.2 队列的循环队列与链式队列对比

特性 顺序队列（数组实现） 循环队列（数组优化） 链式队列（链表实现）
内存分配 固定大小 固定大小 动态分配
插入效率 O(1) O(1) O(1)
删除效率 O(1) O(1) O(1)
扩容能力 不支持 不支持 支持
空间利用率 低（存在假溢出） 高 高
实现复杂度 简单 中等 较高

6.1.3 队列在任务调度与缓冲中的应用

队列在系统设计中有广泛的应用，例如：

  • 操作系统任务调度 ：将等待执行的进程按顺序放入队列，CPU按队列顺序执行。
  • 消息队列系统 ：生产者将任务放入队列，消费者从队列取出任务处理。
  • 网络通信缓冲 ：在网络数据包传输中，接收端使用队列缓存数据包。
  • 打印机队列 ：多个打印任务按顺序排队等待打印。

下面以一个简单的任务调度模型为例，展示队列的使用场景： 

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

int main() {
    queue<string> taskQueue;

    // 模拟添加任务
    taskQueue.push("Task 1");
    taskQueue.push("Task 2");
    taskQueue.push("Task 3");

    cout << "Processing tasks in order:" << endl;

    // 处理任务（FIFO）
    while (!taskQueue.empty()) {
        cout << "Processing: " << taskQueue.front() << endl;
        taskQueue.pop();
    }

    return 0;
}

执行说明：

  • 使用 push() 向队列中添加任务；
  • 使用 front() 获取队列头部任务；
  • 使用 pop() 移除已处理的任务；
  • 输出结果将严格按照插入顺序处理任务。

6.2 数组实现的顺序队列与循环队列

6.2.1 队列的数组结构与状态判断

顺序队列使用数组来实现队列结构。通常需要维护两个指针：

  • front ：指向队列的第一个元素；
  • rear ：指向队列最后一个元素的下一个位置。

初始状态下， front = 0 ， rear = 0 。当 front == rear 时，队列为空；当 rear == capacity 时，队列为满（但此时前面可能有空位，造成“假溢出”）。

以下是一个简单的顺序队列实现： 

class ArrayQueue {
private:
    int* data;
    int front;      // 队头指针
    int rear;       // 队尾指针
    int capacity;   // 队列容量

public:
    ArrayQueue(int size) {
        capacity = size;
        data = new int[capacity];
        front = rear = 0;
    }

    ~ArrayQueue() {
        delete[] data;
    }

    bool isEmpty() {
        return front == rear;
    }

    bool isFull() {
        return rear == capacity;
    }

    void enqueue(int value) {
        if (isFull()) {
            cout << "Queue overflow!" << endl;
            return;
        }
        data[rear++] = value;
    }

    int dequeue() {
        if (isEmpty()) {
            cout << "Queue underflow!" << endl;
            return -1;
        }
        return data[front++];
    }
};

6.2.2 循环队列的设计与实现

为了避免“假溢出”问题，我们使用 循环队列 。其核心思想是将数组的首尾相连，当 rear 或 front 到达数组末尾时，可以回到数组开头继续操作。

此时，判断队列满的条件不再是 rear == capacity ，而是 (rear + 1) % capacity == front 。

下面是循环队列的实现： 

class CircularQueue {
private:
    int* data;
    int front;
    int rear;
    int capacity;

public:
    CircularQueue(int size) {
        capacity = size + 1;  // 多留一个空间用于判断队列满
        data = new int[capacity];
        front = rear = 0;
    }

    ~CircularQueue() {
        delete[] data;
    }

    bool isEmpty() {
        return front == rear;
    }

    bool isFull() {
        return (rear + 1) % capacity == front;
    }

    void enqueue(int value) {
        if (isFull()) {
            cout << "Queue overflow!" << endl;
            return;
        }
        data[rear] = value;
        rear = (rear + 1) % capacity;
    }

    int dequeue() {
        if (isEmpty()) {
            cout << "Queue underflow!" << endl;
            return -1;
        }
        int value = data[front];
        front = (front + 1) % capacity;
        return value;
    }
};

6.2.3 队列的扩容与效率优化

对于循环队列来说，固定大小可能限制了其灵活性。为了实现动态扩容，可以在队列满时重新分配更大的数组空间，并将原有数据复制过去。

扩容策略建议使用 两倍扩容 （或1.5倍），以减少频繁扩容带来的性能损耗。 

void resize(int newCapacity) {
    int* newData = new int[newCapacity];
    int i = 0;
    while (front != rear) {
        newData[i++] = data[front];
        front = (front + 1) % capacity;
    }
    front = 0;
    rear = i;
    capacity = newCapacity;
    delete[] data;
    data = newData;
}

在 enqueue() 中加入扩容逻辑： 

void enqueue(int value) {
    if (isFull()) {
        resize(capacity * 2);  // 自动扩容
    }
    data[rear] = value;
    rear = (rear + 1) % capacity;
}

（以下为下一章节的开头，便于章节衔接）

6.3 链表实现的链式队列

6.3.1 队列节点结构与操作实现

链式队列使用链表来实现队列，每个节点包含一个数据域和一个指向下一个节点的指针。链式队列无需预先分配固定大小，适合元素数量变化较大的场景。

定义节点结构如下： 

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

接下来定义链式队列类： 

class LinkedQueue {
private:
    Node* front;
    Node* rear;
    int size;

public:
    LinkedQueue() : front(nullptr), rear(nullptr), size(0) {}

    ~LinkedQueue() {
        while (front) {
            Node* temp = front;
            front = front->next;
            delete temp;
        }
    }

    bool isEmpty() {
        return size == 0;
    }

    void enqueue(int value) {
        Node* newNode = new Node(value);
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear->next = newNode;
            rear = newNode;
        }
        size++;
    }

    int dequeue() {
        if (isEmpty()) {
            cout << "Queue underflow!" << endl;
            return -1;
        }
        Node* temp = front;
        int value = temp->data;
        front = front->next;
        delete temp;
        size--;
        return value;
    }

    int peek() {
        if (isEmpty()) {
            cout << "Queue is empty!" << endl;
            return -1;
        }
        return front->data;
    }

    int getSize() {
        return size;
    }
};

操作说明：

  • enqueue() ：在队尾插入节点；
  • dequeue() ：删除队头节点并返回其值；
  • peek() ：查看队头节点值；
  • 析构函数负责释放所有动态分配的节点。

链式队列的实现避免了数组队列的容量限制，适合不确定数据量大小的场景。在下一节中，我们将进一步讨论链式队列的类封装与接口设计。

本文还有配套的精品资源，点击获取 menu-r.4af5f7ec.gif

简介：《殷人昆C++数据结构》是清华大学出版的经典教材，系统讲解了数组、链表、栈、队列、树、图、排序、查找、哈希表和堆等核心数据结构与算法。本书配套代码库包含所有例题的C++实现，内容详实、结构清晰，适合初学者打基础，也适合进阶者提升编程与算法设计能力。通过学习和实践这些代码，读者能够深入理解数据结构原理，并灵活应用于实际开发中。


本文还有配套的精品资源，点击获取
menu-r.4af5f7ec.gif

Logo
乐奇 Rokid 开放社区

更多推荐

cover

国庆文旅安保上新！AR智能眼镜守护景区，黑科技护航假期出游

avatar 乐奇 Rokid 开放社区
cover

2027中国深圳智能穿戴产业链展览会

avatar 乐奇 Rokid 开放社区
cover

化工行业AR巡检找哪家公司比较好

avatar 乐奇 Rokid 开放社区