C++数据结构实战源码解析与项目实现
·
简介：数据结构是计算机科学的核心概念，涉及如何高效地在内存中组织和管理数据。本资源“C++数据结构实战源码”提供了基于C++语言实现的多种常见数据结构，包括数组、链表、栈、队列、树、图、哈希表和堆等，并结合C++特性如模板和指针操作进行封装设计。通过该源码库，学习者可以深入理解数据结构的底层实现原理，并掌握如何在实际项目中应用这些结构提升程序性能。 
1. 数据结构核心概念与C++编程基础
1.1 数据结构的基本定义与分类
数据结构是计算机中组织和存储数据的方式，其核心目标是提高数据访问和操作的效率。常见的数据结构可分为三类： 线性结构 （如数组、链表、栈、队列）、 树形结构 （如二叉树、平衡树）和 图形结构 （如图的邻接矩阵、邻接表）。不同结构适用于不同场景，例如线性结构适合顺序处理，树结构便于层次化数据管理，图结构则适用于复杂关系建模。
在程序设计中，合理选择数据结构能显著提升算法性能和系统稳定性。
2. 线性结构的C++实现与优化
线性结构是数据结构中最基础、最常见的一类结构，广泛应用于算法设计、系统编程以及实际工程开发中。本章将深入探讨线性结构的实现与优化方式，包括数组、链表、栈与队列等基本线性结构，并结合C++语言特性进行详细分析和实现。
线性结构的核心特点在于数据元素之间存在“一对一”的关系，即每个元素最多有一个前驱和一个后继。常见的线性结构包括数组、链表、栈、队列等。在本章中，我们将从底层原理、实现方式、性能优化等角度出发，逐步深入讲解这些结构的实现与应用。
2.1 数组与动态数组的实现
2.1.1 静态数组的定义与操作
静态数组是一种固定大小的数据结构，其大小在编译时确定，无法动态改变。在C++中，静态数组通过以下方式定义：
int arr[10]; // 定义一个长度为10的整型数组
静态数组的特点：
| 特点 | 描述 |
|---|---|
| 固定容量 | 大小在编译时确定，不能更改 |
| 连续内存 | 所有元素在内存中连续存储 |
| 访问效率高 | 通过下标直接访问，时间复杂度为 O(1) |
| 插入/删除慢 | 插入或删除中间元素需要移动其他元素，时间复杂度为 O(n) |
示例代码：静态数组的初始化与访问
#include <iostream>
using namespace std;
int main() {
int arr[5] = {1, 2, 3, 4, 5}; // 初始化数组
cout << "第3个元素：" << arr[2] << endl; // 输出 3
arr[2] = 10; // 修改元素
cout << "修改后的第3个元素：" << arr[2] << endl; // 输出 10
return 0;
}
代码逻辑分析：
int arr[5] = {1, 2, 3, 4, 5};：定义并初始化一个长度为5的数组。arr[2]：通过下标访问数组中的第3个元素（索引从0开始）。- 修改操作：直接通过下标对元素进行赋值，不会改变数组的大小。
适用场景：
- 数据量较小且大小固定的场景。
- 对访问速度要求高，但不频繁进行插入/删除操作。
2.1.2 动态数组的内存管理与扩容机制
与静态数组不同，动态数组的大小可以在运行时动态调整。在C++中，动态数组通常通过 new 和 delete 运算符来实现内存的动态分配与释放。
动态数组的实现步骤：
- 内存分配 ：使用
new在堆上分配内存。 - 元素操作 ：像静态数组一样通过下标访问。
- 扩容机制 ：当数组满时，重新分配更大的内存空间，并将原数据复制过去。
示例代码：动态数组的实现与扩容
#include <iostream>
using namespace std;
class DynamicArray {
private:
int* data;
int capacity; // 当前容量
int size; // 当前元素个数
public:
DynamicArray() {
capacity = 4;
size = 0;
data = new int[capacity];
}
~DynamicArray() {
delete[] data;
}
void push(int value) {
if (size == capacity) {
resize();
}
data[size++] = value;
}
void resize() {
capacity *= 2;
int* newData = new int[capacity];
for (int i = 0; i < size; ++i) {
newData[i] = data[i];
}
delete[] data;
data = newData;
}
int get(int index) {
if (index >= 0 && index < size) {
return data[index];
}
throw out_of_range("索引超出范围");
}
int getSize() {
return size;
}
};
int main() {
DynamicArray arr;
for (int i = 0; i < 10; ++i) {
arr.push(i);
}
for (int i = 0; i < arr.getSize(); ++i) {
cout << arr.get(i) << " ";
}
return 0;
}
代码逻辑分析：
DynamicArray类封装了动态数组的实现。push(int value)方法负责添加元素，若当前容量不足，则调用resize()扩容。resize()方法将容量翻倍，并将旧数据复制到新内存空间。- 使用
new和delete[]实现动态内存的分配与释放。
扩容流程图（mermaid）：
graph TD
A[push操作] --> B{size == capacity?}
B -->|是| C[调用resize()]
C --> D[分配新内存]
D --> E[复制旧数据]
E --> F[释放旧内存]
F --> G[更新指针]
B -->|否| H[直接添加元素]
参数说明：
capacity：当前数组容量，默认为4。size：当前实际元素数量。- 每次扩容时，容量翻倍，确保平均时间复杂度为 O(1)。
2.1.3 C++中 new/delete 与智能指针的应用
在C++中，手动管理内存容易导致内存泄漏或悬空指针问题。为此，C++11 引入了智能指针（ std::unique_ptr 和 std::shared_ptr ），自动管理内存的生命周期。
示例代码：使用智能指针优化动态数组
#include <iostream>
#include <memory>
using namespace std;
class SmartArray {
private:
unique_ptr<int[]> data;
int capacity;
int size;
public:
SmartArray() : capacity(4), size(0) {
data = make_unique<int[]>(capacity);
}
void push(int value) {
if (size == capacity) {
capacity *= 2;
auto newData = make_unique<int[]>(capacity);
for (int i = 0; i < size; ++i) {
newData[i] = data[i];
}
data = move(newData);
}
data[size++] = value;
}
int get(int index) {
if (index >= 0 && index < size) {
return data[index];
}
throw out_of_range("索引越界");
}
int getSize() {
return size;
}
};
int main() {
SmartArray arr;
for (int i = 0; i < 10; ++i) {
arr.push(i);
}
for (int i = 0; i < arr.getSize(); ++i) {
cout << arr.get(i) << " ";
}
return 0;
}
代码逻辑分析：
- 使用
unique_ptr<int[]>自动管理数组内存。 make_unique<int[]>(capacity)创建动态数组。- 使用
move()转移所有权，避免浅拷贝问题。 - 析构函数不再需要手动释放内存。
参数说明：
unique_ptr：独占式智能指针，确保只有一个指针拥有内存资源。shared_ptr：共享式智能指针，适用于多个对象共享同一块内存的情况。
优化建议：
- 尽量使用智能指针替代原始指针，提高代码安全性。
- 对于需要频繁扩容的数组结构，可以结合
std::vector进行封装，简化开发流程。
2.2 链表的设计与实现
2.2.1 单链表的节点结构与插入/删除操作
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序通过指针链接实现。单链表是最基本的链表结构，每个节点包含一个数据域和一个指针域。
单链表节点结构：
struct Node {
int data;
Node* next;
};
插入与删除操作示意图（mermaid）：
graph LR
A[头节点] --> B[节点1]
B --> C[节点2]
C --> D[节点3]
D --> E[尾节点]
subgraph 插入操作
C --> F[新节点]
F --> D
end
subgraph 删除操作
C --> D
end
示例代码：单链表的基本操作
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
class LinkedList {
private:
Node* head;
public:
LinkedList() : head(nullptr) {}
~LinkedList() {
while (head) {
Node* temp = head;
head = head->next;
delete temp;
}
}
void insert(int value) {
Node* newNode = new Node{value, nullptr};
if (!head) {
head = newNode;
return;
}
Node* current = head;
while (current->next) {
current = current->next;
}
current->next = newNode;
}
void remove(int value) {
if (!head) return;
if (head->data == value) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* current = head;
while (current->next && current->next->data != value) {
current = current->next;
}
if (current->next) {
Node* temp = current->next;
current->next = current->next->next;
delete temp;
}
}
void print() {
Node* current = head;
while (current) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
};
int main() {
LinkedList list;
list.insert(1);
list.insert(2);
list.insert(3);
list.print(); // 输出 1 2 3
list.remove(2);
list.print(); // 输出 1 3
return 0;
}
代码逻辑分析：
insert()方法将节点插入到链表末尾。remove()方法查找并删除指定值的节点。print()方法遍历链表并输出所有节点值。
参数说明：
head：指向链表第一个节点的指针。next：每个节点通过next指针指向下一个节点。- 插入操作时间复杂度为 O(n)，删除操作也为 O(n)，但在已知节点指针时可优化为 O(1)。
优化方向：
- 可以引入哨兵节点（Dummy Node）简化插入/删除逻辑。
- 支持双向链表以提高查找效率。
2.2.2 双链表的实现与双向遍历优化
双链表是在单链表的基础上，每个节点增加一个指向前一个节点的指针，从而支持双向遍历。
双链表节点结构：
struct DoubleNode {
int data;
DoubleNode* prev;
DoubleNode* next;
};
双链表的插入操作流程图（mermaid）：
graph LR
A[prev] --> B[newNode]
B --> C[next]
C --> D[old next]
示例代码：双链表的基本实现
#include <iostream>
using namespace std;
struct DoubleNode {
int data;
DoubleNode* prev;
DoubleNode* next;
};
class DoublyLinkedList {
private:
DoubleNode* head;
DoubleNode* tail;
public:
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
~DoublyLinkedList() {
while (head) {
DoubleNode* temp = head;
head = head->next;
delete temp;
}
}
void append(int value) {
DoubleNode* newNode = new DoubleNode{value, tail, nullptr};
if (!head) {
head = tail = newNode;
return;
}
tail->next = newNode;
tail = newNode;
}
void remove(int value) {
DoubleNode* current = head;
while (current) {
if (current->data == value) {
if (current->prev) {
current->prev->next = current->next;
} else {
head = current->next;
}
if (current->next) {
current->next->prev = current->prev;
} else {
tail = current->prev;
}
delete current;
return;
}
current = current->next;
}
}
void printForward() {
DoubleNode* current = head;
while (current) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
void printBackward() {
DoubleNode* current = tail;
while (current) {
cout << current->data << " ";
current = current->prev;
}
cout << endl;
}
};
int main() {
DoublyLinkedList list;
list.append(1);
list.append(2);
list.append(3);
list.printForward(); // 输出 1 2 3
list.printBackward(); // 输出 3 2 1
list.remove(2);
list.printForward(); // 输出 1 3
return 0;
}
代码逻辑分析：
append()方法在链表末尾添加节点。remove()方法查找并删除指定值的节点。printForward()和printBackward()分别支持正向和反向遍历。
参数说明：
head：指向第一个节点。tail：指向最后一个节点。prev和next指针分别指向前一个和后一个节点。
优化方向：
- 支持双向迭代器（
begin()、end()）以兼容STL算法。 - 使用智能指针管理节点内存，提升安全性。
2.2.3 循环链表与链表的常见问题处理
循环链表是一种首尾相连的链表结构，最后一个节点的 next 指针指向头节点，常用于实现环形缓冲区、任务调度等场景。
循环链表插入操作流程图（mermaid）：
graph LR
A[节点1] --> B[节点2]
B --> C[节点3]
C --> A
常见问题处理：
| 问题类型 | 解决方案 |
|---|---|
| 环检测 | 快慢指针法（Floyd判圈算法） |
| 中间节点查找 | 快慢指针，快指针每次走两步，慢指针每次走一步 |
| 反转链表 | 使用三个指针逐个反转 |
| 合并两个有序链表 | 归并排序思想，使用虚拟头节点辅助合并 |
示例代码：判断链表是否有环
bool hasCycle(Node* head) {
if (!head || !head->next) return false;
Node* slow = head;
Node* fast = head->next;
while (fast && fast->next) {
if (slow == fast) return true;
slow = slow->next;
fast = fast->next->next;
}
return false;
}
代码逻辑分析：
- 使用两个指针，
slow每次移动一步，fast每次移动两步。 - 如果链表中存在环，两个指针最终会相遇。
- 时间复杂度为 O(n)，空间复杂度为 O(1)。
应用场景：
- 数据结构课程教学（链表环检测）
- 系统调度（如操作系统中的任务队列）
- 游戏开发（角色状态循环）
3. 树结构与图结构的原理与编程实现
在计算机科学中，树结构和图结构是两个极其重要的非线性数据结构，它们在实际应用中有着广泛而深远的影响。树结构以层次化的方式组织数据，适用于文件系统、数据库索引、语法分析等场景；而图结构则用于建模复杂的关系网络，如社交网络、路径规划、网络拓扑等。本章将深入讲解二叉树、平衡二叉树（AVL树）以及图结构的原理、实现与优化，通过C++编程语言实现核心操作，并结合代码示例展示其底层逻辑。
3.1 二叉树的基本操作与遍历算法
二叉树是一种每个节点最多有两个子节点的树结构，通常称为左子节点和右子节点。它在搜索、排序、表达式树等领域中有着广泛的应用。本节将介绍二叉树的基本操作，包括构建、插入、删除、查找等，以及深度优先和广度优先的遍历方式。
3.1.1 二叉树的递归与非递归遍历方式
二叉树的遍历方式包括前序遍历（根左右）、中序遍历（左根右）和后序遍历（左右根）。我们可以使用递归或非递归（栈模拟）方式实现这些遍历。
示例代码：递归实现中序遍历
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void inorderTraversal(TreeNode* root) {
if (root == nullptr) return;
inorderTraversal(root->left); // 递归访问左子树
std::cout << root->val << " "; // 访问当前节点
inorderTraversal(root->right); // 递归访问右子树
}
代码逻辑分析：
- inorderTraversal 函数通过递归方式实现中序遍历。
- 首先判断当前节点是否为空，为空则返回。
- 递归调用自身访问左子树，打印当前节点值，再递归访问右子树。
- 这种递归方式简洁直观，但容易导致栈溢出，尤其是在树非常深的情况下。
示例代码：非递归实现中序遍历（栈实现）
void inorderTraversalIterative(TreeNode* root) {
std::stack<TreeNode*> stack;
TreeNode* current = root;
while (current != nullptr || !stack.empty()) {
while (current != nullptr) {
stack.push(current);
current = current->left; // 一直向左压栈
}
current = stack.top(); stack.pop();
std::cout << current->val << " ";
current = current->right; // 转向右子树
}
}
代码逻辑分析：
- 使用栈模拟递归调用过程，实现中序遍历。
- 先将所有左节点压入栈中，然后弹出并访问当前节点，再转向右子树。
- 避免了递归带来的栈溢出问题，适合处理深度较大的二叉树。
3.1.2 二叉搜索树的构建与查找实现
二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，其中每个节点的左子树值都小于该节点值，右子树值都大于该节点值。
示例代码：构建二叉搜索树
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == nullptr) return new TreeNode(val);
if (val < root->val)
root->left = insertIntoBST(root->left, val);
else
root->right = insertIntoBST(root->right, val);
return root;
}
代码逻辑分析：
- 如果当前节点为空，则创建新节点并返回。
- 若插入值小于当前节点值，则递归插入左子树；否则插入右子树。
- 此函数递归构建BST结构，保证插入后仍满足BST性质。
示例代码：BST查找操作
TreeNode* searchBST(TreeNode* root, int val) {
if (root == nullptr || root->val == val)
return root;
if (val < root->val)
return searchBST(root->left, val);
else
return searchBST(root->right, val);
}
代码逻辑分析：
- 查找逻辑基于BST的有序性，比较当前节点值与目标值。
- 若目标值小于当前节点值，则向左子树查找；否则向右子树查找。
- 时间复杂度为 O(h)，其中 h 为树的高度。
3.1.3 二叉树的插入与删除逻辑详解
BST的插入较为简单，但删除操作较为复杂，需要考虑三种情况：
1. 删除节点为叶子节点（无子节点）；
2. 删除节点有一个子节点；
3. 删除节点有两个子节点（需找中序后继或前驱替换）。
示例代码：BST删除操作
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return root;
if (key < root->val)
root->left = deleteNode(root->left, key);
else if (key > root->val)
root->right = deleteNode(root->right, key);
else {
// 找到要删除的节点
if (root->left == nullptr) {
TreeNode* temp = root->right;
delete root;
return temp;
} else if (root->right == nullptr) {
TreeNode* temp = root->left;
delete root;
return temp;
}
// 有两个子节点的情况：找到中序后继（右子树中的最小节点）
TreeNode* temp = minValueNode(root->right);
root->val = temp->val; // 替换值
root->right = deleteNode(root->right, temp->val); // 删除中序后继
}
return root;
}
代码逻辑分析：
- 若当前节点值大于目标值，递归进入左子树。
- 若当前节点值小于目标值，递归进入右子树。
- 若找到目标节点，分情况处理：
- 无子节点或只有一个子节点时，直接替换。
- 有两个子节点时，找到右子树中最小节点作为替代节点，并递归删除该节点。
3.2 平衡二叉树（AVL树）实现
AVL树是一种自平衡的二叉搜索树，通过旋转操作维持树的平衡，从而保证查找、插入和删除操作的时间复杂度始终为 O(log n)。
3.2.1 AVL树的平衡因子与旋转操作
AVL树中每个节点维护一个平衡因子（Balance Factor），其值为左子树高度减去右子树高度。当平衡因子的绝对值超过1时，说明树不平衡，需进行旋转调整。
四种旋转类型：
| 旋转类型 | 描述 |
|---|---|
| LL旋转 | 插入在左子树的左子树导致失衡 |
| RR旋转 | 插入在右子树的右子树导致失衡 |
| LR旋转 | 插入在左子树的右子树导致失衡 |
| RL旋转 | 插入在右子树的左子树导致失衡 |
示例代码：LL旋转实现
struct AVLNode {
int key;
AVLNode* left;
AVLNode* right;
int height;
};
int height(AVLNode* node) {
return node ? node->height : 0;
}
AVLNode* rotateLL(AVLNode* root) {
AVLNode* newRoot = root->left;
root->left = newRoot->right;
newRoot->right = root;
root->height = 1 + std::max(height(root->left), height(root->right));
newRoot->height = 1 + std::max(height(newRoot->left), height(newRoot->right));
return newRoot;
}
代码逻辑分析：
- rotateLL 实现左左旋转，调整树结构。
- 原根节点左子节点成为新的根节点。
- 更新两个节点的高度值，保持AVL树的平衡属性。
3.2.2 插入与删除过程中的平衡调整
AVL树的插入和删除操作都需要进行平衡因子的更新与旋转调整。
示例代码：AVL插入操作
AVLNode* insertAVL(AVLNode* node, int key) {
if (!node) return new AVLNode{key, nullptr, nullptr, 1};
if (key < node->key)
node->left = insertAVL(node->left, key);
else if (key > node->key)
node->right = insertAVL(node->right, key);
else
return node; // 重复值不插入
node->height = 1 + std::max(height(node->left), height(node->right));
int balance = getBalanceFactor(node);
// LL
if (balance > 1 && key < node->left->key)
return rotateLL(node);
// RR
if (balance < -1 && key > node->right->key)
return rotateRR(node);
// LR
if (balance > 1 && key > node->left->key) {
node->left = rotateRR(node->left);
return rotateLL(node);
}
// RL
if (balance < -1 && key < node->right->key) {
node->right = rotateLL(node->right);
return rotateRR(node);
}
return node;
}
代码逻辑分析：
- 插入节点后更新高度。
- 计算平衡因子，判断是否需要旋转。
- 根据不同失衡情况选择对应的旋转方式，恢复AVL树平衡。
3.3 图结构的存储与操作
图结构由顶点（Vertex）和边（Edge）组成，用于表示实体之间的关系。图的常见存储方式包括邻接矩阵和邻接表。
3.3.1 邻接矩阵与邻接表的实现对比
| 存储方式 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| 邻接矩阵 | 快速判断边是否存在 | 空间复杂度高 O(n²) | 边数密集的图 |
| 邻接表 | 空间效率高 O(n + e) | 查询边效率低 | 边数稀疏的图 |
示例代码：邻接矩阵实现图
#define MAX_VERTEX 100
class GraphMatrix {
private:
int vertexNum;
int matrix[MAX_VERTEX][MAX_VERTEX];
public:
GraphMatrix(int n) : vertexNum(n) {
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
matrix[i][j] = 0;
}
void addEdge(int u, int v) {
matrix[u][v] = 1;
matrix[v][u] = 1;
}
void print() {
for (int i = 0; i < vertexNum; ++i) {
for (int j = 0; j < vertexNum; ++j)
std::cout << matrix[i][j] << " ";
std::cout << std::endl;
}
}
};
代码逻辑分析：
- 使用二维数组存储邻接矩阵。
- addEdge 方法添加边，设置对应位置为1。
- print 方法输出邻接矩阵内容。
示例代码：邻接表实现图
#include <vector>
class GraphList {
private:
int vertexNum;
std::vector<int> adjList[MAX_VERTEX];
public:
GraphList(int n) : vertexNum(n) {}
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u);
}
void print() {
for (int i = 0; i < vertexNum; ++i) {
std::cout << "Vertex " << i << ": ";
for (int v : adjList[i])
std::cout << v << " ";
std::cout << std::endl;
}
}
};
代码逻辑分析：
- 使用数组存储邻接表，每个节点对应一个动态数组。
- addEdge 方法将顶点加入对方的邻接表中。
- print 方法输出邻接表内容。
3.3.2 图的深度优先与广度优先遍历
图的遍历方式包括深度优先搜索（DFS）和广度优先搜索（BFS），它们分别使用递归/栈和队列实现。
示例代码：DFS遍历
void DFSUtil(int v, bool visited[], std::vector<int> adjList[]) {
visited[v] = true;
std::cout << v << " ";
for (int neighbor : adjList[v])
if (!visited[neighbor])
DFSUtil(neighbor, visited, adjList);
}
void DFS(int start, int vertexNum, std::vector<int> adjList[]) {
bool visited[MAX_VERTEX] = {false};
DFSUtil(start, visited, adjList);
}
代码逻辑分析：
- 使用递归实现DFS。
- visited 数组记录已访问节点，防止重复访问。
- 每次访问一个节点后，递归访问其未访问的邻接节点。
示例代码：BFS遍历
void BFS(int start, int vertexNum, std::vector<int> adjList[]) {
bool visited[MAX_VERTEX] = {false};
std::queue<int> queue;
visited[start] = true;
queue.push(start);
while (!queue.empty()) {
int v = queue.front();
queue.pop();
std::cout << v << " ";
for (int neighbor : adjList[v]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.push(neighbor);
}
}
}
}
代码逻辑分析：
- 使用队列实现BFS，保证广度优先访问。
- 初始节点入队，访问后将其邻接节点入队，并标记为已访问。
3.3.3 最小生成树与最短路径算法的C++实现
图的两个经典算法：最小生成树（MST）和最短路径算法（如Dijkstra、Floyd）在实际中有广泛应用。
示例代码：Dijkstra算法求最短路径
#include <vector>
#include <queue>
#include <utility>
const int INF = 1e9;
void dijkstra(int start, std::vector<std::vector<std::pair<int, int>>> &adjList) {
int n = adjList.size();
std::vector<int> dist(n, INF);
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
int currentDist = pq.top().first;
int u = pq.top().second;
pq.pop();
if (currentDist > dist[u]) continue;
for (auto edge : adjList[u]) {
int v = edge.first;
int weight = edge.second;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
for (int i = 0; i < n; ++i)
std::cout << "Distance from " << start << " to " << i << " is " << dist[i] << std::endl;
}
代码逻辑分析：
- 使用优先队列（最小堆）实现Dijkstra算法。
- 初始化距离数组为无穷大，起点距离为0。
- 每次取出距离最小的节点，更新其邻接节点的最短路径。
- 最终输出每个节点到起点的最短路径长度。
总结与延伸
本章系统讲解了二叉树、平衡二叉树（AVL树）以及图结构的基本操作与实现方法。通过C++代码示例展示了递归与非递归遍历、BST插入删除、AVL旋转、图的存储方式及遍历算法等内容。这些结构和算法是现代软件开发中解决复杂问题的核心工具，建议读者在理解原理的基础上，结合实际项目进行深入练习与拓展应用。
4. 高效数据结构与泛型编程实践
4.1 哈希表与冲突解决策略
4.1.1 哈希函数的设计与实现
哈希表是一种高效的查找结构，其核心思想是通过哈希函数将键（key）映射到数组的特定位置。哈希函数的设计直接影响哈希表的性能。优秀的哈希函数应满足以下几点：
- 均匀性 ：尽量将键均匀分布在整个数组中，避免冲突。
- 确定性 ：相同输入始终返回相同输出。
- 高效性 ：计算速度快。
在C++中，可以使用 std::hash 作为基础哈希函数，也可以根据具体数据类型自定义。例如，针对字符串的哈希函数可以使用BKDR哈希算法：
size_t bkdrHash(const std::string& key) {
size_t hash = 0;
for (char c : key) {
hash = hash * 131 + c;
}
return hash;
}
逻辑分析：
hash = hash * 131 + c;：通过乘法因子131进行扰动，增强哈希值的随机性。- 该算法时间复杂度为 O(n)，n 为字符串长度。
- 适用于字符串键值的哈希映射。
4.1.2 开放地址法与链地址法的比较
哈希冲突是不可避免的，解决冲突的两种主流方式是 开放地址法 和 链地址法 。
| 方法 | 原理描述 | 优缺点分析 |
|---|---|---|
| 开放地址法 | 当发生冲突时，按某种规则（线性探测、二次探测、双重哈希）寻找下一个空槽。 | 优点：缓存友好，节省空间；缺点：易聚集，扩容成本高。 |
| 链地址法 | 每个槽位维护一个链表，冲突键值添加到对应链表中。 | 优点：插入效率高，易于实现；缺点：链表访问效率低，内存碎片。 |
以链地址法为例，实现一个简易哈希表：
template<typename K, typename V>
class HashMap {
private:
struct Node {
K key;
V value;
Node* next;
Node(K k, V v) : key(k), value(v), next(nullptr) {}
};
std::vector<Node*> table;
size_t size;
size_t hashFunction(const K& key) {
return std::hash<K>()(key) % size;
}
public:
HashMap(size_t s = 100) : size(s) {
table.resize(size, nullptr);
}
void insert(const K& key, const V& value) {
size_t index = hashFunction(key);
Node* newNode = new Node(key, value);
newNode->next = table[index];
table[index] = newNode;
}
V* get(const K& key) {
size_t index = hashFunction(key);
Node* current = table[index];
while (current) {
if (current->key == key) {
return &(current->value);
}
current = current->next;
}
return nullptr;
}
};
代码分析：
table：哈希桶数组，每个元素是一个链表头节点。insert：插入键值对时，使用哈希函数定位索引，插入链表头部。get：查找键值时遍历链表，找到匹配键返回值指针。
4.1.3 哈希表的扩容与性能优化
哈希表随着插入数据的增加，冲突率上升，导致性能下降。因此需要引入 负载因子 （load factor）进行扩容判断：
double loadFactor = (double)count / size;
if (loadFactor > 0.75) rehash();
rehash函数示例：
void rehash() {
size_t newSize = size * 2;
std::vector<Node*> newTable(newSize, nullptr);
for (size_t i = 0; i < size; ++i) {
Node* current = table[i];
while (current) {
Node* next = current->next;
size_t newIndex = std::hash<K>()(current->key) % newSize;
current->next = newTable[newIndex];
newTable[newIndex] = current;
current = next;
}
}
table = newTable;
size = newSize;
}
逻辑说明：
- 扩容为原大小的两倍。
- 遍历旧表，重新计算每个键的哈希值并插入新表。
- 保证哈希均匀分布，降低冲突率。
4.2 堆结构与优先队列实现
4.2.1 最大堆与最小堆的构建与维护
堆是一种完全二叉树结构，分为最大堆（父节点大于等于子节点）和最小堆（父节点小于等于子节点），常用于实现优先队列。
template<typename T>
class MaxHeap {
private:
std::vector<T> heap;
void heapifyUp(int index) {
while (index > 0) {
int parent = (index - 1) / 2;
if (heap[index] > heap[parent]) {
std::swap(heap[index], heap[parent]);
index = parent;
} else break;
}
}
void heapifyDown(int index) {
int left, right, largest;
while ((left = 2 * index + 1) < heap.size()) {
right = 2 * index + 2;
largest = (right < heap.size() && heap[right] > heap[left]) ? right : left;
if (heap[largest] > heap[index]) {
std::swap(heap[largest], heap[index]);
index = largest;
} else break;
}
}
public:
void push(T value) {
heap.push_back(value);
heapifyUp(heap.size() - 1);
}
void pop() {
if (heap.empty()) return;
heap[0] = heap.back();
heap.pop_back();
heapifyDown(0);
}
T top() { return heap[0]; }
bool empty() { return heap.empty(); }
};
逻辑分析：
heapifyUp：插入新元素后向上调整堆结构。heapifyDown：删除根节点后向下调整堆结构。push：将元素添加至末尾并向上调整。pop：替换根节点后向下调整，保持堆性质。
4.2.2 堆排序与Top-K问题的解决方案
堆排序是一种利用堆结构实现的排序算法，其时间复杂度为 O(n log n)，适合大数据量排序。
template<typename T>
void heapSort(std::vector<T>& arr) {
MaxHeap<T> maxHeap;
for (T val : arr) {
maxHeap.push(val);
}
for (int i = arr.size() - 1; i >= 0; --i) {
arr[i] = maxHeap.top();
maxHeap.pop();
}
}
Top-K问题示例（使用最小堆）：
std::vector<int> findTopK(const std::vector<int>& nums, int k) {
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
for (int num : nums) {
if (minHeap.size() < k) {
minHeap.push(num);
} else if (num > minHeap.top()) {
minHeap.pop();
minHeap.push(num);
}
}
std::vector<int> result;
while (!minHeap.empty()) {
result.push_back(minHeap.top());
minHeap.pop();
}
std::reverse(result.begin(), result.end());
return result;
}
逻辑说明：
- 使用最小堆维护前 K 个最大值。
- 若当前数大于堆顶，替换并重新调整堆。
- 最终堆中保存的是前 K 个最大值。
4.2.3 堆在优先队列中的实际应用
优先队列（priority_queue）是堆的典型应用之一。C++ STL 中的 priority_queue 默认实现为最大堆。
#include <queue>
#include <vector>
#include <iostream>
struct Task {
int priority;
std::string description;
bool operator<(const Task& other) const {
return priority < other.priority; // 最大堆
}
};
int main() {
std::priority_queue<Task> taskQueue;
taskQueue.push({3, "Fix bug"});
taskQueue.push({1, "Write doc"});
taskQueue.push({5, "Release version"});
while (!taskQueue.empty()) {
std::cout << taskQueue.top().description << " (Priority: " << taskQueue.top().priority << ")\n";
taskQueue.pop();
}
}
输出示例：
Release version (Priority: 5)
Fix bug (Priority: 3)
Write doc (Priority: 1)
说明：
- 使用优先队列实现任务调度，高优先级任务优先执行。
- 自定义
operator<控制堆排序逻辑。
4.3 C++模板编程与泛型数据结构
4.3.1 模板函数与类模板的定义与使用
模板是C++实现泛型编程的核心机制，允许编写与类型无关的代码。
函数模板示例：
template<typename T>
T max(T a, T b) {
return (a > b) ? a : b;
}
类模板示例：
template<typename T>
class Stack {
private:
std::vector<T> data;
public:
void push(T value) { data.push_back(value); }
void pop() { if (!data.empty()) data.pop_back(); }
T top() { return data.back(); }
bool empty() { return data.empty(); }
};
优势：
- 提高代码复用性。
- 编译期类型检查，类型安全。
- 适用于容器、算法、数据结构等通用模块。
4.3.2 泛型容器的实现与类型安全控制
泛型容器是模板编程的重要应用。通过类型参数化，可以实现任意数据类型的存储与操作。
template<typename T>
class MyVector {
private:
T* data;
size_t capacity, size;
public:
MyVector() : data(nullptr), capacity(0), size(0) {}
~MyVector() { delete[] data; }
void push_back(const T& val) {
if (size == capacity) {
capacity = (capacity == 0) ? 1 : capacity * 2;
T* newData = new T[capacity];
for (size_t i = 0; i < size; ++i) newData[i] = data[i];
delete[] data;
data = newData;
}
data[size++] = val;
}
T& operator[](size_t index) {
if (index >= size) throw std::out_of_range("Index out of range");
return data[index];
}
size_t getSize() { return size; }
};
说明：
push_back：动态扩容逻辑，按指数增长。operator[]：提供安全访问方式，防止越界。- 支持任意类型 T 的存储，如
MyVector<int>,MyVector<std::string>等。
4.3.3 STL容器与自定义数据结构的整合
STL容器如 vector , map , set 提供了丰富的功能，但有时需要自定义结构以满足特定需求。
#include <vector>
#include <iostream>
template<typename T>
class CustomContainer {
private:
std::vector<T> internal;
public:
void add(const T& val) { internal.push_back(val); }
void remove(const T& val) {
internal.erase(std::remove(internal.begin(), internal.end(), val), internal.end());
}
void print() {
for (const T& item : internal) {
std::cout << item << " ";
}
std::cout << std::endl;
}
};
示例用法：
int main() {
CustomContainer<int> container;
container.add(10);
container.add(20);
container.add(10);
container.remove(10);
container.print(); // Output: 20
}
说明：
- 利用 STL 的
vector实现自定义容器功能。 - 可扩展支持排序、搜索、过滤等操作。
- 类型安全、泛型、复用性强。
本章通过哈希表、堆、模板编程等技术，深入探讨了高效数据结构的设计与实现方法，并展示了泛型编程在C++中的应用。这些内容不仅适用于算法设计与系统开发，也为后续章节的实战应用打下坚实基础。
5. 数据结构的实战应用与性能优化
5.1 数据结构在常见算法中的应用
在实际的算法开发中，选择合适的数据结构往往决定了程序的效率与稳定性。不同的数据结构适用于不同类型的算法问题。以下我们将从排序、查找、图算法和高频算法题几个角度，分析数据结构的实际应用场景。
排序与查找算法中的结构选择
排序和查找是最基础的算法问题，它们对数据结构的选择有明确的要求：
| 算法类型 | 推荐数据结构 | 原因说明 |
|---|---|---|
| 冒泡排序 | 数组 | 便于相邻元素比较与交换 |
| 快速排序 | 数组 | 需要快速访问中间元素 |
| 归并排序 | 链表 | 合并两个有序链表效率高 |
| 二分查找 | 有序数组 | 支持随机访问 |
| 插值查找 | 有序数组 | 数据分布均匀时效率更高 |
| 二叉搜索树查找 | 二叉搜索树 | 平均时间复杂度为 O(log n) |
| 哈希查找 | 哈希表 | 平均时间复杂度为 O(1) |
例如，使用哈希表进行快速查找可以极大地提高程序性能，特别是在去重、频率统计等问题中表现突出：
#include <unordered_map>
#include <vector>
std::vector<int> findDuplicates(const std::vector<int>& nums) {
std::unordered_map<int, int> freq;
std::vector<int> result;
for (int num : nums) {
freq[num]++;
}
for (const auto& pair : freq) {
if (pair.second > 1) {
result.push_back(pair.first);
}
}
return result;
}
代码说明：
- 使用 std::unordered_map 作为哈希表统计元素频率；
- 遍历一次原始数组进行频率统计；
- 第二次遍历哈希表，找出频率大于1的元素作为结果。
图算法与树结构在实际问题中的运用
图结构在路径规划、社交网络分析等领域有广泛应用。例如，使用邻接表表示图结构，并结合深度优先搜索（DFS）或广度优先搜索（BFS）解决连通性问题：
#include <vector>
#include <queue>
void bfs(const std::vector<std::vector<int>>& graph, int start) {
std::vector<bool> visited(graph.size(), false);
std::queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int node = q.front();
q.pop();
std::cout << node << " ";
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
代码说明：
- 使用邻接表 graph 存储图结构；
- 使用队列实现广度优先搜索；
- 记录访问状态防止重复访问。
哈希与堆结构在高频算法题中的实践
在 LeetCode 等算法平台中，很多高频题都涉及哈希表和堆结构的结合使用，例如“前 K 个高频元素”问题：
#include <vector>
#include <unordered_map>
#include <queue>
std::vector<int> topKFrequent(const std::vector<int>& nums, int k) {
std::unordered_map<int, int> freq;
for (int num : nums) {
freq[num]++;
}
// 使用最小堆（频率小的排前面），保持堆的大小为k
auto cmp = [](const std::pair<int, int>& a, const std::pair<int, int>& b) {
return a.second > b.second;
};
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, decltype(cmp)> minHeap(cmp);
for (const auto& pair : freq) {
minHeap.push(pair);
if (minHeap.size() > k) {
minHeap.pop();
}
}
std::vector<int> result;
while (!minHeap.empty()) {
result.push_back(minHeap.top().first);
minHeap.pop();
}
return result;
}
代码说明：
- 使用 unordered_map 统计频率；
- 使用最小堆（priority_queue）维护前 K 个高频元素；
- 最终将堆中的元素取出返回结果。
5.2 数据结构的调试与性能分析
在开发过程中，数据结构的调试与性能分析是确保程序稳定性和效率的重要环节。
使用调试工具定位结构异常
使用 GDB（GNU Debugger）可以有效调试 C++ 程序中的结构异常。例如，当链表指针出现空指针访问时，GDB 可以帮助定位错误发生的位置：
g++ -g -o linked_list linked_list.cpp
gdb ./linked_list
run
一旦程序崩溃，使用 bt 查看调用栈，即可定位到具体出错的代码行。
内存泄漏检测与资源释放优化
使用 Valgrind 可以检测内存泄漏问题：
valgrind --leak-check=full ./linked_list
输出示例：
==12345== LEAK SUMMARY:
==12345== definitely lost: 16 bytes in 1 blocks
==12345== indirectly lost: 0 bytes in 0 blocks
==12345== possibly lost: 0 bytes in 0 blocks
==12345== still reachable: 0 bytes in 0 blocks
==12345== suppressed: 0 bytes in 0 blocks
发现内存泄漏后，需检查 new 和 delete 的匹配使用，或改用智能指针如 std::unique_ptr 或 std::shared_ptr 。
时间复杂度与空间复杂度的评估方法
在算法分析中，大 O 表示法是评估复杂度的标准。例如：
- 数组查找：O(1)
- 链表查找：O(n)
- 二叉搜索树查找：O(log n)
- 哈希表查找：O(1)（平均）
使用 std::chrono 可以测量程序运行时间：
#include <chrono>
#include <iostream>
auto start = std::chrono::high_resolution_clock::now();
// 执行算法代码
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> duration = end - start;
std::cout << "Time taken: " << duration.count() << " seconds" << std::endl;
5.3 数据结构项目实战开发流程
在实际项目开发中，数据结构的选择与实现需要遵循完整的开发流程。
需求分析与结构选型
以“学生管理系统”为例，需实现学生信息的增删查改操作。根据需求分析，选择合适的数据结构：
- 学生信息存储：使用
std::vector<Student>或std::map<int, Student>（按学号索引）； - 快速查找：使用哈希表或二叉搜索树；
- 高频插入删除：使用链表结构。
系统模块划分与接口设计
可将系统划分为以下几个模块：
- 学生管理模块（CRUD）
- 查询模块（按姓名、学号、成绩）
- 排序模块（按成绩排序）
- 文件持久化模块
接口设计示例：
class StudentManager {
public:
void addStudent(const Student& student);
void deleteStudent(int id);
Student getStudent(int id);
std::vector<Student> searchStudents(const std::string& name);
std::vector<Student> sortStudentsByScore();
void saveToFile(const std::string& filename);
void loadFromFile(const std::string& filename);
};
单元测试与整体性能调优
使用 Google Test 编写单元测试：
TEST(StudentManagerTest, AddAndGetStudent) {
StudentManager manager;
Student s{1, "Tom", 90};
manager.addStudent(s);
EXPECT_EQ(manager.getStudent(1).name, "Tom");
}
性能调优方面，可通过以下方式提升效率：
- 使用
reserve()预分配 vector 容量； - 使用
std::unordered_map替代std::map提高查找效率； - 使用缓存机制避免重复计算。
5.4 数据结构在实际工程中的高级应用
数据库索引结构的模拟实现
数据库中常用 B+ 树作为索引结构。我们可模拟实现一个简单的索引结构：
struct IndexEntry {
int key;
int offset;
};
class SimpleIndex {
private:
std::vector<IndexEntry> index;
public:
void addEntry(int key, int offset) {
index.push_back({key, offset});
}
int findOffset(int key) {
for (const auto& entry : index) {
if (entry.key == key) {
return entry.offset;
}
}
return -1;
}
};
该结构可用于快速定位磁盘文件中的数据位置。
文件系统中的树结构管理
文件系统本质上是一个树结构，每个目录可以包含子目录和文件。我们可以使用递归结构模拟文件系统的管理：
struct FileSystemNode {
std::string name;
bool isDirectory;
std::vector<FileSystemNode*> children;
};
通过递归遍历可实现目录结构的展示、搜索、删除等功能。
网络通信中的队列与缓存优化
在网络通信中，发送与接收缓冲区常使用队列结构管理数据：
#include <queue>
#include <mutex>
#include <condition_variable>
template<typename T>
class ThreadSafeQueue {
private:
std::queue<T> queue_;
mutable std::mutex mtx_;
std::condition_variable cv_;
public:
void push(T value) {
std::lock_guard<std::mutex> lock(mtx_);
queue_.push(std::move(value));
cv_.notify_one();
}
T pop() {
std::unique_lock<std::mutex> lock(mtx_);
cv_.wait(lock, [this] { return !queue_.empty(); });
T val = queue_.front();
queue_.pop();
return val;
}
};
该结构可应用于多线程下的数据缓存、任务调度等场景。
（本章节内容结束）
简介：数据结构是计算机科学的核心概念，涉及如何高效地在内存中组织和管理数据。本资源“C++数据结构实战源码”提供了基于C++语言实现的多种常见数据结构，包括数组、链表、栈、队列、树、图、哈希表和堆等，并结合C++特性如模板和指针操作进行封装设计。通过该源码库，学习者可以深入理解数据结构的底层实现原理，并掌握如何在实际项目中应用这些结构提升程序性能。
更多推荐
4
0- 0
已为社区贡献30条内容
所有评论(0)