数据结构、算法与应用：C++语言描述（第2版） 前言 《数据结构、算法与应用：C++语言描述》是一本经典的计算机科学教材，由 Sartaj Sahni 教授编写。本书以C++为实现工具，系统阐述了数据结构的设计原理、算法分析方法及实际应用场景，是学习数据结构与算法的权威参考资料。本笔记基于第2版内容，对核心知识点、关键算法的C++实现、时间复杂度分析及应用场景进行详细梳理，旨在为读者提供全面且深入的学习参考。
目标读者 本笔记适合以下读者群体：
计算机科学专业学生 ：深入理解数据结构与算法的理论基础和C++实现软件工程师 ：需要在实际项目中应用高效的数据结构和算法算法竞赛参与者 ：提升算法设计和分析能力技术面试官 ：掌握数据结构与算法的核心概念和C++实现细节C++在数据结构与算法中的优势 C++作为实现数据结构和算法的首选语言之一，具有以下优势：
模板系统 ：通过模板实现泛型数据结构，提高代码复用性和类型安全性STL库 ：提供丰富的标准容器和算法，为数据结构和算法的实现提供基础内存管理 ：支持手动内存管理，允许更精细的内存控制和优化性能优势 ：编译型语言，执行效率高，适合对性能要求严格的算法面向对象 ：支持封装、继承和多态，便于设计模块化的数据结构操作符重载 ：允许为自定义数据类型定义操作符，提高代码可读性异常处理 ：提供异常机制，增强代码的健壮性本笔记的核心价值 C++高级特性的深度应用 ：
模板特化和偏特化 右值引用和移动语义 智能指针的使用 类型萃取（type traits） 表达式模板 算法分析的深入 ：
均摊分析 势能法分析 amortized analysis 最坏情况、平均情况和最好情况分析 空间复杂度的详细分析 性能优化策略 ：
缓存优化 内存布局优化 分支预测优化 并行化策略 编译器优化提示 实际应用场景 ：
大规模数据处理 实时系统中的算法选择 分布式系统中的数据结构 嵌入式系统中的内存受限场景 高性能计算中的算法优化 完整的C++实现 ：
符合现代C++标准（C++11/14/17/20） 包含完整的错误处理和边界检查 提供详细的性能测试和分析 代码风格统一，可读性强 本笔记不仅关注理论知识的讲解，更注重实际应用能力的培养，通过丰富的代码示例和详细的性能分析，帮助读者掌握数据结构与算法的核心原理和C++实现技巧，为解决实际问题提供有力的工具和方法。
1. 算法分析基础 1.1 基本概念 数据结构 ：数据元素及其相互关系的集合，如数组、链表、树、图等。数据结构的选择直接影响算法的效率。算法 ：解决特定问题的有限步骤集合，需满足有穷性、确定性、可行性、输入和输出五大特征。时间复杂度 ：衡量算法执行时间随输入规模 n 增长的变化趋势，使用大O记号表示。空间复杂度 ：衡量算法所需额外空间随输入规模增长的变化趋势，同样使用大O记号表示。渐近复杂度 ：当输入规模趋近于无穷大时的复杂度行为，是算法分析的重点。算法效率 ：包括时间效率和空间效率，通常需要在两者之间进行权衡。1.2 复杂度记号 1.2.1 大O记号（O-notation） 若存在正常数 c 和 n_0 ，使得当 n eq n_0 时，有 T(n) eq c dot f(n) ，则称 T(n) = O(f(n)) 。大O记号描述了算法时间复杂度的上界 。
1.2.2 大Ω记号（Ω-notation） 若存在正常数 c 和 n_0 ，使得当 n eq n_0 时，有 T(n) ge c dot f(n) ，则称 T(n) = Ω(f(n)) 。大Ω记号描述了算法时间复杂度的下界 。
1.2.3 大Θ记号（Θ-notation） 若存在正常数 c_1, c_2 和 n_0 ，使得当 n eq n_0 时，有 c_1 dot f(n) eq T(n) eq c_2 dot f(n) ，则称 T(n) = Θ(f(n)) 。大Θ记号描述了算法时间复杂度的紧确界 。
1.2.4 小o记号（o-notation） 若对于任意正常数 c ，存在 n_0 ，使得当 n eq n_0 时，有 T(n) < c dot f(n) ，则称 T(n) = o(f(n)) 。小o记号描述了算法时间复杂度的非紧上界 。
1.3 常见时间复杂度比较 按增长率从小到大排序：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
复杂度类别分析 ：
常数时间 O(1)：操作时间与输入规模无关，如数组随机访问、哈希表查找对数时间 O(log n)：操作时间随输入规模对数增长，如二分查找、平衡二叉树操作线性时间 O(n)：操作时间与输入规模线性相关，如线性搜索、数组遍历线性对数时间 O(n log n)：操作时间与输入规模成线性对数关系，如高效排序算法（归并排序、快速排序平均情况）多项式时间 O(nᵏ)：操作时间与输入规模成多项式关系，如冒泡排序、选择排序指数时间 O(2ⁿ)：操作时间随输入规模指数增长，如子集生成、汉诺塔问题阶乘时间 O(n!)：操作时间随输入规模阶乘增长，如旅行商问题的暴力解法1.4 算法分析方法 1.4.1 循环分析 单循环 ：循环次数乘以循环体时间复杂度嵌套循环 ：各层循环次数的乘积并列循环 ：各循环时间复杂度的总和复杂循环 ：需要分析循环变量的变化规律1.4.2 递归分析 递归树法 ：将递归过程分解为树结构，计算每一层的时间复杂度主定理（Master Theorem） ：用于分析分治算法的时间复杂度代入法 ：假设递归式的解，然后通过数学归纳法证明递推关系式 ：建立递归调用的时间复杂度递推关系，然后求解1.4.3 均摊分析 聚合分析 ：考虑所有操作的总时间，然后平均到每个操作记账法 ：为不同操作分配不同的时间成本，确保总时间不超过上限势能法 ：定义势能函数，将操作的时间复杂度与势能变化相关联1.4.4 最坏情况、平均情况和最好情况分析 最坏情况 ：算法在所有可能输入下的最大运行时间平均情况 ：算法在所有可能输入下的期望运行时间最好情况 ：算法在所有可能输入下的最小运行时间1.5 空间复杂度分析 输入空间 ：存储输入数据所需的空间暂存空间 ：算法运行过程中临时使用的空间输出空间 ：存储输出结果所需的空间空间复杂度分析通常关注额外空间 ，即除输入和输出外的暂存空间。
1.6 C++中的时间复杂度分析示例 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 template <typename T>T sum (const vector<T>& arr) { T total = 0 ; for (size_t i = 0 ; i < arr.size (); i++) { total += arr[i]; } return total; } template <typename T>void printPairs (const vector<T>& arr) for (size_t i = 0 ; i < arr.size (); i++) { for (size_t j = 0 ; j < arr.size (); j++) { cout << arr[i] << " " << arr[j] << endl; } } } template <typename T>int binarySearch (const vector<T>& arr, const T& target) int left = 0 ; int right = arr.size () - 1 ; 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 ; } template <typename T>void merge (vector<T>& arr, int left, int mid, int right) vector<T> temp (right - left + 1 ) ; int i = left, j = mid + 1 , k = 0 ; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } while (i <= mid) { temp[k++] = arr[i++]; } while (j <= right) { temp[k++] = arr[j++]; } for (int p = 0 ; p < temp.size (); p++) { arr[left + p] = temp[p]; } } template <typename T>void mergeSort (vector<T>& arr, int left, int right) if (left < right) { int mid = left + (right - left) / 2 ; mergeSort (arr, left, mid); mergeSort (arr, mid + 1 , right); merge (arr, left, mid, right); } }
1.7 主定理（Master Theorem） 对于形如 T(n) = aT(n/b) + f(n) 的递归式，其中 a ≥ 1, b > 1 是常数， f(n) 是渐近正函数，则：
情况1 ：若 f(n) = O(n^(log_b a - ε)) 对某个 ε > 0 成立，则 T(n) = Θ(n^(log_b a))情况2 ：若 f(n) = Θ(n^(log_b a) log^k n) 对某个 k ≥ 0 成立，则 T(n) = Θ(n^(log_b a) log^(k+1) n)情况3 ：若 f(n) = Ω(n^(log_b a + ε)) 对某个 ε > 0 成立，且对某个常数 c < 1 和所有足够大的 n 有 a f(n/b) ≤ c f(n) ，则 T(n) = Θ(f(n))主定理应用示例 ：
二分查找： T(n) = T(n/2) + Θ(1) ，属于情况2，结果为 Θ(log n) 归并排序： T(n) = 2T(n/2) + Θ(n) ，属于情况2，结果为 Θ(n log n) 快速排序（平均情况）： T(n) = 2T(n/2) + Θ(n) ，属于情况2，结果为 Θ(n log n) 快速排序（最坏情况）： T(n) = T(n-1) + Θ(n) ，不属于主定理适用范围，结果为 Θ(n²) 1.8 实际应用中的复杂度考虑 1.8.1 常数因子的重要性 在实际应用中，当两个算法的渐近复杂度相同时，常数因子成为决定性能的关键因素。例如，插入排序在小规模数据上可能比归并排序更快，尽管其渐近复杂度更高。
1.8.2 缓存优化 现代计算机系统中，缓存对算法性能有显著影响。具有良好空间局部性的算法通常表现更好。
1.8.3 并行化潜力 某些算法比其他算法更容易并行化，这在多核系统中是一个重要考虑因素。
1.8.4 内存层次结构 算法的内存访问模式应考虑计算机的内存层次结构（寄存器、L1/L2/L3缓存、主存、磁盘），以最大化数据局部性。
1.9 C++中的性能优化技巧 使用适当的容器 ：根据操作特点选择合适的STL容器避免不必要的复制 ：使用引用传递和移动语义预分配内存 ：对于vector等容器，使用reserve()预分配内存减少动态内存分配 ：使用对象池或内存池使用inline函数 ：减少函数调用开销避免虚函数 ：在性能关键路径上避免使用虚函数使用constexpr ：在编译时计算常量表达式使用SIMD指令 ：对于向量运算，利用SIMD指令集1.10 复杂度分析的局限性 渐近分析 ：只关注输入规模很大时的情况，可能不适合小规模数据硬件差异 ：不同硬件平台的性能特性不同实现细节 ：算法的具体实现方式会影响实际性能输入特性 ：某些算法对特定类型的输入表现更好尽管存在这些局限性，复杂度分析仍然是评估算法效率的重要工具，为算法设计和选择提供了理论基础。
2. 线性表 2.1 数组 静态数组 ：编译时固定大小，内存连续分配，访问时间 O(1) ，插入/删除时间 O(n) 。动态数组 ：C++中使用 vector 实现，支持动态扩容（通常扩容为原大小的2倍）。智能数组 ：结合静态数组和动态数组的优点，提供更灵活的内存管理。2.1.1 静态数组的C++实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 template <typename T, size_t N>class StaticArray {private : T data[N]; size_t size; public : StaticArray () : size (0 ) {} T& operator [](size_t index) { if (index >= size) { throw out_of_range ("Index out of bounds" ); } return data[index]; } const T& operator [](size_t index) const { if (index >= size) { throw out_of_range ("Index out of bounds" ); } return data[index]; } void push_back (const T& value) if (size >= N) { throw overflow_error ("Array capacity exceeded" ); } data[size++] = value; } void pop_back () if (size == 0 ) { throw underflow_error ("Array is empty" ); } size--; } size_t getSize () const return size; } constexpr size_t getCapacity () const return N; } bool isEmpty () const return size == 0 ; } bool isFull () const return size == N; } void clear () size = 0 ; } T* begin () { return data; } T* end () { return data + size; } const T* begin () const return data; } const T* end () const return data + size; } };
2.1.2 动态数组（vector）的深入分析 核心特性 随机访问 ：vector 支持通过索引快速访问元素，时间复杂度 O(1) 。动态扩容 ：当元素个数超过容量时，vector 会自动分配更大的内存空间并复制元素。尾部操作高效 ：在尾部插入/删除元素的时间复杂度均为 O(1) （均摊时间复杂度）。连续内存 ：元素存储在连续的内存空间中，具有良好的空间局部性。可移植性 ：跨平台兼容，是C++标准库的一部分。扩容机制 扩容策略 ：通常扩容为原容量的1.5倍或2倍扩容过程 ：分配新的更大内存块 将现有元素复制到新内存块 释放旧内存块 更新内部指针和容量 均摊分析 ：扩容操作的均摊时间复杂度为 O(1)性能优化技巧 预分配内存 ：
1 2 vector<int > v; v.reserve (1000 );
避免频繁扩容 ：
估算所需空间并提前reserve 使用emplace_back代替push_back（避免额外拷贝） 内存管理 ：
使用shrink_to_fit释放多余内存 注意vector的内存布局和对齐方式 移动语义 ：
1 2 3 vector<string> v; string s = "hello" ; v.push_back (move (s));
批量操作 ：
1 2 3 vector<int > v1 = {1 , 2 , 3 }; vector<int > v2; v2. insert (v2. end (), v1. begin (), v1. end ());
vector的实现细节 2.1.3 数组的性能优化 缓存优化 空间局部性 ：数组元素在内存中连续存储，访问时具有良好的空间局部性预取优化 ：现代CPU会自动预取连续的内存数据到缓存中缓存行对齐 ：合理安排数组大小，避免缓存行冲突内存布局优化 数据对齐 ：确保数组元素按硬件要求对齐，提高访问速度内存填充 ：对于某些数据结构，适当填充以避免伪共享编译优化 编译器向量化 ：使用#pragma omp simd或编译器内置函数启用SIMD指令循环展开 ：编译器会自动展开小循环，提高指令级并行性分支预测 ：减少数组访问中的分支，提高分支预测准确率2.2 链表 单链表 ：每个节点包含数据和指向下一节点的指针，插入/删除时间 O(1) （已知前驱节点时）。双链表 ：每个节点额外包含指向前一节点的指针，支持双向遍历。循环链表 ：尾节点指向头节点，形成环结构。双向循环链表 ：结合双链表和循环链表的特点，支持双向遍历和环形操作。2.2.1 单链表的C++实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 template <typename T>class Node {public : T data; Node<T>* next; Node (const T& value) : data (value), next (nullptr ) {} Node (T&& value) : data (std::move (value)), next (nullptr ) {} }; template <typename T>class LinkedList {private : Node<T>* head; Node<T>* tail; size_t size; public : LinkedList () : head (nullptr ), tail (nullptr ), size (0 ) {} ~LinkedList () { clear (); } void insertAtHead (const T& value) Node<T>* newNode = new Node <T>(value); newNode->next = head; head = newNode; if (tail == nullptr ) { tail = newNode; } size++; } void insertAtHead (T&& value) Node<T>* newNode = new Node <T>(std::move (value)); newNode->next = head; head = newNode; if (tail == nullptr ) { tail = newNode; } size++; } void insertAtTail (const T& value) Node<T>* newNode = new Node <T>(value); if (head == nullptr ) { head = newNode; tail = newNode; } else { tail->next = newNode; tail = newNode; } size++; } void insertAtTail (T&& value) Node<T>* newNode = new Node <T>(std::move (value)); if (head == nullptr ) { head = newNode; tail = newNode; } else { tail->next = newNode; tail = newNode; } size++; } void insertAtPosition (size_t position, const T& value) if (position == 0 ) { insertAtHead (value); return ; } if (position == size) { insertAtTail (value); return ; } if (position > size) { throw out_of_range ("Position out of bounds" ); } Node<T>* current = head; for (size_t i = 0 ; i < position - 1 ; i++) { current = current->next; } Node<T>* newNode = new Node <T>(value); newNode->next = current->next; current->next = newNode; size++; } void deleteAtHead () if (head == nullptr ) { throw runtime_error ("List is empty" ); } Node<T>* temp = head; head = head->next; delete temp; size--; if (head == nullptr ) { tail = nullptr ; } } void deleteAtTail () if (head == nullptr ) { throw runtime_error ("List is empty" ); } if (head == tail) { delete head; head = nullptr ; tail = nullptr ; } else { Node<T>* current = head; while (current->next != tail) { current = current->next; } delete tail; tail = current; tail->next = nullptr ; } size--; } void deleteByValue (const T& value) if (head == nullptr ) { throw runtime_error ("List is empty" ); } if (head->data == value) { deleteAtHead (); return ; } Node<T>* current = head; while (current->next != nullptr && current->next->data != value) { current = current->next; } if (current->next == nullptr ) { throw runtime_error ("Value not found" ); } Node<T>* temp = current->next; if (temp == tail) { tail = current; } current->next = current->next->next; delete temp; size--; } int search (const T& value) const Node<T>* current = head; size_t index = 0 ; while (current != nullptr ) { if (current->data == value) { return static_cast <int >(index); } current = current->next; index++; } return -1 ; } void print () const if (head == nullptr ) { cout << "List is empty" << endl; return ; } Node<T>* current = head; while (current != nullptr ) { cout << current->data << " -> " ; current = current->next; } cout << "nullptr" << endl; } void clear () while (head != nullptr ) { Node<T>* temp = head; head = head->next; delete temp; } tail = nullptr ; size = 0 ; } size_t getSize () const return size; } bool isEmpty () const return size == 0 ; } Node<T>* getHead () const { return head; } Node<T>* getTail () const { return tail; } };
2.2.2 双链表的C++实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 template <typename T>class DNode {public : T data; DNode<T>* prev; DNode<T>* next; DNode (const T& value) : data (value), prev (nullptr ), next (nullptr ) {} DNode (T&& value) : data (std::move (value)), prev (nullptr ), next (nullptr ) {} }; template <typename T>class DoublyLinkedList {private : DNode<T>* head; DNode<T>* tail; size_t size; public : DoublyLinkedList () : head (nullptr ), tail (nullptr ), size (0 ) {} ~DoublyLinkedList () { clear (); } void insertAtHead (const T& value) DNode<T>* newNode = new DNode <T>(value); newNode->next = head; if (head != nullptr ) { head->prev = newNode; } head = newNode; if (tail == nullptr ) { tail = newNode; } size++; } void insertAtTail (const T& value) DNode<T>* newNode = new DNode <T>(value); newNode->prev = tail; if (tail != nullptr ) { tail->next = newNode; } tail = newNode; if (head == nullptr ) { head = newNode; } size++; } void insertAtPosition (size_t position, const T& value) if (position == 0 ) { insertAtHead (value); return ; } if (position == size) { insertAtTail (value); return ; } if (position > size) { throw out_of_range ("Position out of bounds" ); } DNode<T>* current; if (position < size / 2 ) { current = head; for (size_t i = 0 ; i < position - 1 ; i++) { current = current->next; } } else { current = tail; for (size_t i = 0 ; i < size - position; i++) { current = current->prev; } } DNode<T>* newNode = new DNode <T>(value); newNode->next = current->next; newNode->prev = current; if (current->next != nullptr ) { current->next->prev = newNode; } current->next = newNode; size++; } void deleteAtHead () if (head == nullptr ) { throw runtime_error ("List is empty" ); } DNode<T>* temp = head; head = head->next; if (head != nullptr ) { head->prev = nullptr ; } else { tail = nullptr ; } delete temp; size--; } void deleteAtTail () if (tail == nullptr ) { throw runtime_error ("List is empty" ); } DNode<T>* temp = tail; tail = tail->prev; if (tail != nullptr ) { tail->next = nullptr ; } else { head = nullptr ; } delete temp; size--; } void deleteByValue (const T& value) if (head == nullptr ) { throw runtime_error ("List is empty" ); } if (head->data == value) { deleteAtHead (); return ; } if (tail->data == value) { deleteAtTail (); return ; } DNode<T>* current = head->next; while (current != tail && current->data != value) { current = current->next; } if (current == tail) { throw runtime_error ("Value not found" ); } current->prev->next = current->next; current->next->prev = current->prev; delete current; size--; } int search (const T& value) const DNode<T>* current = head; size_t index = 0 ; while (current != nullptr ) { if (current->data == value) { return static_cast <int >(index); } current = current->next; index++; } return -1 ; } void printForward () const if (head == nullptr ) { cout << "List is empty" << endl; return ; } DNode<T>* current = head; while (current != nullptr ) { cout << current->data << " <-> " ; current = current->next; } cout << "nullptr" << endl; } void printBackward () const if (tail == nullptr ) { cout << "List is empty" << endl; return ; } DNode<T>* current = tail; while (current != nullptr ) { cout << current->data << " <-> " ; current = current->prev; } cout << "nullptr" << endl; } void clear () while (head != nullptr ) { DNode<T>* temp = head; head = head->next; delete temp; } tail = nullptr ; size = 0 ; } size_t getSize () const return size; } bool isEmpty () const return size == 0 ; } };
2.2.3 循环链表的C++实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 template <typename T>class CircularLinkedList {private : Node<T>* head; size_t size; public : CircularLinkedList () : head (nullptr ), size (0 ) {} ~CircularLinkedList () { clear (); } void insertAtHead (const T& value) Node<T>* newNode = new Node <T>(value); if (head == nullptr ) { newNode->next = newNode; head = newNode; } else { Node<T>* tail = head; while (tail->next != head) { tail = tail->next; } newNode->next = head; tail->next = newNode; head = newNode; } size++; } void insertAtTail (const T& value) Node<T>* newNode = new Node <T>(value); if (head == nullptr ) { newNode->next = newNode; head = newNode; } else { Node<T>* tail = head; while (tail->next != head) { tail = tail->next; } newNode->next = head; tail->next = newNode; } size++; } void deleteAtHead () if (head == nullptr ) { throw runtime_error ("List is empty" ); } if (head->next == head) { delete head; head = nullptr ; } else { Node<T>* tail = head; while (tail->next != head) { tail = tail->next; } Node<T>* temp = head; head = head->next; tail->next = head; delete temp; } size--; } void deleteAtTail () if (head == nullptr ) { throw runtime_error ("List is empty" ); } if (head->next == head) { delete head; head = nullptr ; } else { Node<T>* prev = nullptr ; Node<T>* current = head; while (current->next != head) { prev = current; current = current->next; } prev->next = head; delete current; } size--; } void print () const if (head == nullptr ) { cout << "List is empty" << endl; return ; } Node<T>* current = head; do { cout << current->data << " -> " ; current = current->next; } while (current != head); cout << "head" << endl; } void clear () if (head == nullptr ) { return ; } Node<T>* current = head->next; while (current != head) { Node<T>* temp = current; current = current->next; delete temp; } delete head; head = nullptr ; size = 0 ; } size_t getSize () const return size; } bool isEmpty () const return size == 0 ; } };
2.2.4 链表的性能优化 内存管理优化 内存池 ：
为链表节点预分配内存池，减少频繁的动态内存分配 实现自定义分配器，提高内存分配效率 节点复用 ：
实现空闲节点列表，复用被删除的节点 减少内存分配和释放的开销 内存对齐 ：
确保链表节点按硬件要求对齐，提高访问速度 使用alignas关键字或编译器指令 访问性能优化 缓存优化 ：
链表节点在内存中不连续，缓存局部性差 考虑使用数组模拟链表，提高缓存命中率 遍历优化 ：
对于长链表，考虑使用跳跃链表（Skip List） 实现双向遍历，根据位置选择从头部或尾部开始 分支预测 ：
减少链表操作中的分支，提高分支预测准确率 使用条件移动指令代替分支指令 C++特有的优化 移动语义 ：
实现移动构造函数和移动赋值运算符 减少节点创建和插入时的拷贝开销 智能指针 ：
使用std::unique_ptr管理节点内存，避免内存泄漏 注意循环引用问题，必要时使用std::weak_ptr 模板特化 ：
为常见类型提供模板特化，提高性能 例如，为内置类型优化内存布局 内联函数 ：
将频繁调用的链表操作声明为inline 减少函数调用开销 应用场景优化 选择合适的链表类型 ：
单链表：插入删除操作频繁，只需单向遍历 双链表：需要双向遍历，频繁在中间插入删除 循环链表：需要环形操作，如约瑟夫问题 结合其他数据结构 ：
链表 + 哈希表：提高查找性能 链表 + 二叉搜索树：实现有序链表 批量操作 ：
2.2.5 链表与数组的比较 操作 数组 单链表 双链表 随机访问 O(1) O(n) O(n) 头部插入 O(n) O(1) O(1) 尾部插入 O(1) (均摊) O(n) O(1) 中间插入 O(n) O(1) (已知前驱) O(1) (已知位置) 头部删除 O(n) O(1) O(1) 尾部删除 O(1) O(n) O(1) 中间删除 O(n) O(1) (已知前驱) O(1) (已知位置) 内存开销 低 中 (额外指针) 高 (两个额外指针) 缓存局部性 好 差 差
选择建议 ：
当需要频繁随机访问时，选择数组 当需要频繁插入删除且位置不确定时，选择链表 当内存空间有限时，选择数组 当需要在两端频繁操作时，选择双链表 2.3 栈（Stack） 定义 ：后进先出（LIFO）的数据结构，仅允许在栈顶进行插入（push）和删除（pop）操作。C++实现 ：可使用 vector 或链表实现。应用场景 ：函数调用栈、表达式求值、括号匹配、深度优先搜索等。2.3.1 栈的C++实现 基于vector的栈实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 template <typename T, typename Container = std::vector<T>>class Stack {private : Container c; public : bool empty () const return c.empty (); } size_t size () const return c.size (); } T& top () { if (empty ()) { throw std::underflow_error ("Stack is empty" ); } return c.back (); } const T& top () const if (empty ()) { throw std::underflow_error ("Stack is empty" ); } return c.back (); } void push (const T& value) c.push_back (value); } void push (T&& value) c.push_back (std::move (value)); } template <typename ... Args> void emplace (Args&&... args) c.emplace_back (std::forward<Args>(args)...); } void pop () if (empty ()) { throw std::underflow_error ("Stack is empty" ); } c.pop_back (); } void swap (Stack& other) noexcept using std::swap; swap (c, other.c); } }; template <typename T, typename Container>void swap (Stack<T, Container>& lhs, Stack<T, Container>& rhs) noexcept lhs.swap (rhs); }
基于链表的栈实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 template <typename T>class LinkedStack {private : struct Node { T data; Node* next; Node (const T& value) : data (value), next (nullptr ) {} Node (T&& value) : data (std::move (value)), next (nullptr ) {} }; Node* topNode; size_t size; public : LinkedStack () : topNode (nullptr ), size (0 ) {} ~LinkedStack () { clear (); } bool empty () const return size == 0 ; } size_t size () const return size; } T& top () { if (empty ()) { throw std::underflow_error ("Stack is empty" ); } return topNode->data; } const T& top () const if (empty ()) { throw std::underflow_error ("Stack is empty" ); } return topNode->data; } void push (const T& value) Node* newNode = new Node (value); newNode->next = topNode; topNode = newNode; size++; } void push (T&& value) Node* newNode = new Node (std::move (value)); newNode->next = topNode; topNode = newNode; size++; } void pop () if (empty ()) { throw std::underflow_error ("Stack is empty" ); } Node* temp = topNode; topNode = topNode->next; delete temp; size--; } void clear () while (!empty ()) { pop (); } } };
2.3.2 栈的性能优化 内存管理优化 预分配内存 ：
对于基于vector的栈，使用reserve()预分配足够的空间 减少频繁扩容的开销 内存池 ：
对于基于链表的栈，实现内存池管理节点内存 减少动态内存分配的开销 移动语义 ：
利用C++11的移动语义，避免不必要的拷贝 对于大对象，使用std::move()提高性能 操作优化 原地构造 ：
使用emplace()方法原地构造元素，避免中间拷贝 减少构造和拷贝的开销 异常安全性 ：
提供强异常安全保证，确保栈操作的原子性 避免在异常发生时栈处于不一致状态 内联函数 ：
将频繁调用的栈操作声明为inline 减少函数调用开销 线程安全性 无锁设计 ：
对于并发场景，考虑使用无锁栈实现 提高多线程环境下的性能 原子操作 ：
使用std::atomic实现线程安全的栈操作 避免使用重量级的互斥锁 2.3.3 栈的应用案例 表达式求值 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 int evaluateExpression (const std::string& expr) Stack<int > values; Stack<char > operators; for (size_t i = 0 ; i < expr.size (); i++) { char c = expr[i]; if (std::isspace (c)) { continue ; } if (std::isdigit (c)) { int num = 0 ; while (i < expr.size () && std::isdigit (expr[i])) { num = num * 10 + (expr[i] - '0' ); i++; } values.push (num); i--; } else if (c == '(' ) { operators.push (c); } else if (c == ')' ) { while (!operators.empty () && operators.top () != '(' ) { int val2 = values.top (); values.pop (); int val1 = values.top (); values.pop (); char op = operators.top (); operators.pop (); switch (op) { case '+' : values.push (val1 + val2); break ; case '-' : values.push (val1 - val2); break ; case '*' : values.push (val1 * val2); break ; case '/' : values.push (val1 / val2); break ; } } if (!operators.empty ()) { operators.pop (); } } else if (c == '+' || c == '-' || c == '*' || c == '/' ) { while (!operators.empty () && hasHigherPrecedence (operators.top (), c)) { int val2 = values.top (); values.pop (); int val1 = values.top (); values.pop (); char op = operators.top (); operators.pop (); switch (op) { case '+' : values.push (val1 + val2); break ; case '-' : values.push (val1 - val2); break ; case '*' : values.push (val1 * val2); break ; case '/' : values.push (val1 / val2); break ; } } operators.push (c); } } while (!operators.empty ()) { int val2 = values.top (); values.pop (); int val1 = values.top (); values.pop (); char op = operators.top (); operators.pop (); switch (op) { case '+' : values.push (val1 + val2); break ; case '-' : values.push (val1 - val2); break ; case '*' : values.push (val1 * val2); break ; case '/' : values.push (val1 / val2); break ; } } return values.top (); } bool hasHigherPrecedence (char op1, char op2) if ((op1 == '*' || op1 == '/' ) && (op2 == '+' || op2 == '-' )) { return true ; } return false ; }
括号匹配 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 bool isBalanced (const std::string& expr) Stack<char > stack; for (char c : expr) { if (c == '(' || c == '{' || c == '[' ) { stack.push (c); continue ; } if (c == ')' || c == '}' || c == ']' ) { if (stack.empty ()) { return false ; } char top = stack.top (); stack.pop (); if ((c == ')' && top != '(' ) || (c == '}' && top != '{' ) || (c == ']' && top != '[' )) { return false ; } } } return stack.empty (); }
2.3.4 栈与其他数据结构的比较 数据结构 插入操作 删除操作 随机访问 应用场景 栈 O(1) O(1) O(n) 函数调用、表达式求值 队列 O(1) O(1) O(n) 任务调度、消息队列 数组 O(1) (尾部) O(1) (尾部) O(1) 随机访问频繁 链表 O(1) (头部) O(1) (头部) O(n) 插入删除频繁
2.3.5 现代C++中的栈 std::stack C++标准库提供了std::stack容器适配器，它可以基于不同的底层容器实现：
1 2 3 4 5 6 7 8 9 10 11 12 13 #include <stack> #include <vector> #include <deque> #include <list> std::stack<int > stack1; std::stack<int , std::vector<int >> stack2; std::stack<int , std::list<int >> stack3;
性能特点 基于deque ：默认实现，兼顾了随机访问和插入删除性能基于vector ：随机访问性能好，但扩容时可能需要拷贝数据基于list ：插入删除性能稳定，但内存开销较大扩展功能 最大容量限制 ：
实现带容量限制的栈，防止栈溢出 适用于资源受限的环境 迭代器支持 ：
为栈添加迭代器支持，方便遍历栈中的元素 扩展栈的使用场景 序列化支持 ：
2.4 队列（Queue） 定义 ：先进先出（FIFO）的数据结构，仅允许在队尾插入（enqueue）和队头删除（dequeue）操作。C++实现 ：可使用 deque 或链表实现。应用场景 ：任务调度、消息队列、广度优先搜索等。2.4.1 队列的C++实现 基于deque的队列实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 template <typename T, typename Container = std::deque<T>>class Queue {private : Container c; public : bool empty () const return c.empty (); } size_t size () const return c.size (); } T& front () { if (empty ()) { throw std::underflow_error ("Queue is empty" ); } return c.front (); } const T& front () const if (empty ()) { throw std::underflow_error ("Queue is empty" ); } return c.front (); } T& back () { if (empty ()) { throw std::underflow_error ("Queue is empty" ); } return c.back (); } const T& back () const if (empty ()) { throw std::underflow_error ("Queue is empty" ); } return c.back (); } void push (const T& value) c.push_back (value); } void push (T&& value) c.push_back (std::move (value)); } template <typename ... Args> void emplace (Args&&... args) c.emplace_back (std::forward<Args>(args)...); } void pop () if (empty ()) { throw std::underflow_error ("Queue is empty" ); } c.pop_front (); } void swap (Queue& other) noexcept using std::swap; swap (c, other.c); } }; template <typename T, typename Container>void swap (Queue<T, Container>& lhs, Queue<T, Container>& rhs) noexcept lhs.swap (rhs); }
基于链表的队列实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 template <typename T>class LinkedQueue {private : struct Node { T data; Node* next; Node (const T& value) : data (value), next (nullptr ) {} Node (T&& value) : data (std::move (value)), next (nullptr ) {} }; Node* frontNode; Node* rearNode; size_t size; public : LinkedQueue () : frontNode (nullptr ), rearNode (nullptr ), size (0 ) {} ~LinkedQueue () { clear (); } bool empty () const return size == 0 ; } size_t size () const return size; } T& front () { if (empty ()) { throw std::underflow_error ("Queue is empty" ); } return frontNode->data; } const T& front () const if (empty ()) { throw std::underflow_error ("Queue is empty" ); } return frontNode->data; } T& back () { if (empty ()) { throw std::underflow_error ("Queue is empty" ); } return rearNode->data; } const T& back () const if (empty ()) { throw std::underflow_error ("Queue is empty" ); } return rearNode->data; } void push (const T& value) Node* newNode = new Node (value); if (empty ()) { frontNode = newNode; rearNode = newNode; } else { rearNode->next = newNode; rearNode = newNode; } size++; } void push (T&& value) Node* newNode = new Node (std::move (value)); if (empty ()) { frontNode = newNode; rearNode = newNode; } else { rearNode->next = newNode; rearNode = newNode; } size++; } void pop () if (empty ()) { throw std::underflow_error ("Queue is empty" ); } Node* temp = frontNode; frontNode = frontNode->next; if (frontNode == nullptr ) { rearNode = nullptr ; } delete temp; size--; } void clear () while (!empty ()) { pop (); } } };
2.4.2 队列的性能优化 内存管理优化 预分配内存 ：
对于基于deque的队列，预分配足够的空间 减少频繁扩容的开销 内存池 ：
对于基于链表的队列，实现内存池管理节点内存 减少动态内存分配的开销 移动语义 ：
利用C++11的移动语义，避免不必要的拷贝 对于大对象，使用std::move()提高性能 操作优化 原地构造 ：
使用emplace()方法原地构造元素，避免中间拷贝 减少构造和拷贝的开销 批量操作 ：
异常安全性 ：
提供强异常安全保证，确保队列操作的原子性 避免在异常发生时队列处于不一致状态 2.4.3 队列的应用案例 广度优先搜索 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 void bfs (const std::vector<std::vector<int >>& graph, int start) std::vector<bool > visited (graph.size(), false ) ; Queue<int > queue; visited[start] = true ; queue.push (start); while (!queue.empty ()) { int current = queue.front (); queue.pop (); std::cout << current << " " ; for (int neighbor : graph[current]) { if (!visited[neighbor]) { visited[neighbor] = true ; queue.push (neighbor); } } } std::cout << std::endl; }
任务调度 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 class TaskScheduler {private : Queue<std::function<void ()>> taskQueue; std::mutex mutex; std::condition_variable cv; bool running; std::thread workerThread; public : TaskScheduler () : running (true ) { workerThread = std::thread ([this ]() { while (running) { std::function<void ()> task; { std::unique_lock<std::mutex> lock (mutex); cv.wait (lock, [this ]() { return !taskQueue.empty () || !running; }); if (!running && taskQueue.empty ()) { return ; } task = std::move (taskQueue.front ()); taskQueue.pop (); } task (); } }); } ~TaskScheduler () { { std::unique_lock<std::mutex> lock (mutex) ; running = false ; } cv.notify_one (); workerThread.join (); } void addTask (std::function<void ()> task) std::unique_lock<std::mutex> lock (mutex) ; taskQueue.push (std::move (task)); cv.notify_one (); } };
2.4.4 特殊类型的队列 优先队列 优先队列是一种特殊的队列，其中元素按照优先级排序：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <queue> #include <vector> #include <functional> std::priority_queue<int > maxHeap; std::priority_queue<int , std::vector<int >, std::greater<int >> minHeap; struct Task { int priority; std::string name; bool operator <(const Task& other) const { return priority < other.priority; } }; std::priority_queue<Task> taskQueue;
双端队列 双端队列允许在两端进行插入和删除操作：
1 2 3 4 5 6 7 #include <deque> std::deque<int > dq; dq.push_back (1 ); dq.push_front (2 ); dq.pop_back (); dq.pop_front ();
循环队列 循环队列是一种使用固定大小数组实现的队列，通过模运算实现循环：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 template <typename T, size_t Capacity>class CircularQueue {private : T data[Capacity]; size_t front; size_t rear; size_t size; public : CircularQueue () : front (0 ), rear (0 ), size (0 ) {} bool empty () const return size == 0 ; } bool full () const return size == Capacity; } size_t getSize () const return size; } T& front () { if (empty ()) { throw std::underflow_error ("Queue is empty" ); } return data[front]; } const T& front () const if (empty ()) { throw std::underflow_error ("Queue is empty" ); } return data[front]; } void push (const T& value) if (full ()) { throw std::overflow_error ("Queue is full" ); } data[rear] = value; rear = (rear + 1 ) % Capacity; size++; } void pop () if (empty ()) { throw std::underflow_error ("Queue is empty" ); } front = (front + 1 ) % Capacity; size--; } };
2.4.5 队列的性能分析 队列类型 插入操作 删除操作 随机访问 内存开销 适用场景 基于deque的队列 O(1) O(1) O(n) 中 一般场景 基于链表的队列 O(1) O(1) O(n) 高 频繁插入删除 循环队列 O(1) O(1) O(1) 低 固定大小场景 优先队列 O(log n) O(log n) O(1) 中 优先级调度
2.5 总结 线性表是最基础的数据结构，包括数组、链表、栈和队列等。在C++中，我们可以根据具体的应用场景选择合适的实现方式：
数组 ：适用于需要频繁随机访问的场景，具有良好的缓存局部性。链表 ：适用于需要频繁插入删除的场景，具有灵活的内存管理。栈 ：适用于后进先出的场景，如函数调用、表达式求值。队列 ：适用于先进先出的场景，如任务调度、广度优先搜索。通过合理选择和优化这些数据结构，我们可以显著提高程序的性能和可靠性。在实际应用中，我们还可以结合这些基础数据结构，构建更复杂的数据结构，如树、图等。
templateelements;
// 出栈
void pop() {
if (isEmpty()) {
throw runtime_error("Stack underflow");
}
elements.pop_back();
}
// 获取栈顶元素
T& top() {
if (isEmpty()) {
throw runtime_error("Stack is empty");
}
return elements.back();
}
// 检查栈是否为空
bool isEmpty() const {
return elements.empty();
}
// 获取栈大小
size_t size() const {
return elements.size();
}
// 打印栈
void print() const {
if (isEmpty()) {
cout << "Stack is empty" << endl;
return;
}
cout << "Stack: ";
for (const auto& elem : elements) {
cout << elem << " ";
}
cout << endl;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 ### 2.4 队列（Queue） - **定义**：先进先出（FIFO）的数据结构，允许在队尾插入（enqueue），在队头删除（dequeue）。 - **C++实现**：可使用 `vector`、链表或STL的 `queue` 实现。 - **应用场景**：广度优先搜索（BFS）、任务调度、打印机队列、缓冲区管理。 #### 循环队列的C++实现 ```cpp template <typename T> class CircularQueue { private: vector<T> elements; size_t front; // 队头索引 size_t rear; // 队尾索引（下一个插入位置） size_t capacity; size_t size; public: CircularQueue(size_t cap) : capacity(cap), front(0), rear(0), size(0) { elements.resize(capacity); } // 入队 void enqueue(const T& value) { if (isFull()) { throw runtime_error("Queue overflow"); } elements[rear] = value; rear = (rear + 1) % capacity; size++; } // 出队 void dequeue() { if (isEmpty()) { throw runtime_error("Queue underflow"); } front = (front + 1) % capacity; size--; } // 获取队头元素 T& getFront() { if (isEmpty()) { throw runtime_error("Queue is empty"); } return elements[front]; } // 检查队列是否为空 bool isEmpty() const { return size == 0; } // 检查队列是否已满 bool isFull() const { return size == capacity; } // 获取队列大小 size_t getSize() const { return size; } // 打印队列 void print() const { if (isEmpty()) { cout << "Queue is empty" << endl; return; } cout << "Queue: "; for (size_t i = 0; i < size; i++) { size_t index = (front + i) % capacity; cout << elements[index] << " "; } cout << endl; } };
3. 树结构 3.1 二叉树 定义 ：每个节点最多有两个子节点（左子树和右子树）的树结构。遍历方式 ：前序（根→左→右）、中序（左→根→右）、后序（左→右→根）、层序（BFS）。二叉树的C++实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 template <typename T>class TreeNode {public : T data; TreeNode<T>* left; TreeNode<T>* right; TreeNode (const T& value) : data (value), left (nullptr ), right (nullptr ) {} }; template <typename T>class BinaryTree {private : TreeNode<T>* root; void destroyTree (TreeNode<T>* node) if (node != nullptr ) { destroyTree (node->left); destroyTree (node->right); delete node; } } void preorderTraversal (TreeNode<T>* node) const if (node != nullptr ) { cout << node->data << " " ; preorderTraversal (node->left); preorderTraversal (node->right); } } void inorderTraversal (TreeNode<T>* node) const if (node != nullptr ) { inorderTraversal (node->left); cout << node->data << " " ; inorderTraversal (node->right); } } void postorderTraversal (TreeNode<T>* node) const if (node != nullptr ) { postorderTraversal (node->left); postorderTraversal (node->right); cout << node->data << " " ; } } public : BinaryTree () : root (nullptr ) {} ~BinaryTree () { destroyTree (root); } void setRoot (TreeNode<T>* node) root = node; } TreeNode<T>* getRoot () const { return root; } void preorder () const cout << "Preorder traversal: " ; preorderTraversal (root); cout << endl; } void inorder () const cout << "Inorder traversal: " ; inorderTraversal (root); cout << endl; } void postorder () const cout << "Postorder traversal: " ; postorderTraversal (root); cout << endl; } void levelOrder () const if (root == nullptr ) { cout << "Tree is empty" << endl; return ; } cout << "Level order traversal: " ; queue<TreeNode<T>*> q; q.push (root); while (!q.empty ()) { TreeNode<T>* current = q.front (); q.pop (); cout << current->data << " " ; if (current->left != nullptr ) { q.push (current->left); } if (current->right != nullptr ) { q.push (current->right); } } cout << endl; } };
3.2 二叉搜索树（BST） 性质 ：左子树所有节点值小于根节点，右子树所有节点值大于根节点（无重复值）。操作 ：查找、插入、删除，时间复杂度平均 O(og n) ，最坏 O(n) （退化为链表）。二叉搜索树的C++实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 template <typename T>class BST {private : TreeNode<T>* root; TreeNode<T>* insertHelper (TreeNode<T>* node, const T& value) { if (node == nullptr ) { return new TreeNode <T>(value); } if (value < node->data) { node->left = insertHelper (node->left, value); } else if (value > node->data) { node->right = insertHelper (node->right, value); } return node; } TreeNode<T>* searchHelper (TreeNode<T>* node, const T& value) const { if (node == nullptr || node->data == value) { return node; } if (value < node->data) { return searchHelper (node->left, value); } else { return searchHelper (node->right, value); } } TreeNode<T>* findMin (TreeNode<T>* node) const { while (node->left != nullptr ) { node = node->left; } return node; } TreeNode<T>* deleteHelper (TreeNode<T>* node, const T& value) { if (node == nullptr ) { return node; } if (value < node->data) { node->left = deleteHelper (node->left, value); } else if (value > node->data) { node->right = deleteHelper (node->right, value); } else { if (node->left == nullptr && node->right == nullptr ) { delete node; return nullptr ; } else if (node->left == nullptr ) { TreeNode<T>* temp = node->right; delete node; return temp; } else if (node->right == nullptr ) { TreeNode<T>* temp = node->left; delete node; return temp; } TreeNode<T>* temp = findMin (node->right); node->data = temp->data; node->right = deleteHelper (node->right, temp->data); } return node; } void inorderHelper (TreeNode<T>* node) const if (node != nullptr ) { inorderHelper (node->left); cout << node->data << " " ; inorderHelper (node->right); } } void destroyTree (TreeNode<T>* node) if (node != nullptr ) { destroyTree (node->left); destroyTree (node->right); delete node; } } public : BST () : root (nullptr ) {} ~BST () { destroyTree (root); } void insert (const T& value) root = insertHelper (root, value); } bool search (const T& value) const return searchHelper (root, value) != nullptr ; } void remove (const T& value) root = deleteHelper (root, value); } void inorder () const cout << "Inorder traversal: " ; inorderHelper (root); cout << endl; } };
3.3 平衡树（AVL树） 定义 ：左右子树高度差（平衡因子）的绝对值不超过1的二叉搜索树。平衡因子 ：左子树高度 - 右子树高度（范围：-1, 0, 1）。平衡调整 ：通过旋转操作（左旋、右旋、左右旋、右左旋）维持平衡。AVL树的C++实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 template <typename T>class AVLNode {public : T data; AVLNode<T>* left; AVLNode<T>* right; int height; AVLNode (const T& value) : data (value), left (nullptr ), right (nullptr ), height (1 ) {} }; template <typename T>class AVLTree {private : AVLNode<T>* root; int getHeight (AVLNode<T>* node) const if (node == nullptr ) { return 0 ; } return node->height; } int getBalanceFactor (AVLNode<T>* node) const if (node == nullptr ) { return 0 ; } return getHeight (node->left) - getHeight (node->right); } void updateHeight (AVLNode<T>* node) if (node == nullptr ) { return ; } node->height = 1 + max (getHeight (node->left), getHeight (node->right)); } AVLNode<T>* rightRotate (AVLNode<T>* y) { AVLNode<T>* x = y->left; AVLNode<T>* T2 = x->right; x->right = y; y->left = T2; updateHeight (y); updateHeight (x); return x; } AVLNode<T>* leftRotate (AVLNode<T>* x) { AVLNode<T>* y = x->right; AVLNode<T>* T2 = y->left; y->left = x; x->right = T2; updateHeight (x); updateHeight (y); return y; } AVLNode<T>* insertHelper (AVLNode<T>* node, const T& value) { if (node == nullptr ) { return new AVLNode <T>(value); } if (value < node->data) { node->left = insertHelper (node->left, value); } else if (value > node->data) { node->right = insertHelper (node->right, value); } else { return node; } updateHeight (node); int balance = getBalanceFactor (node); if (balance > 1 && value < node->left->data) { return rightRotate (node); } if (balance < -1 && value > node->right->data) { return leftRotate (node); } if (balance > 1 && value > node->left->data) { node->left = leftRotate (node->left); return rightRotate (node); } if (balance < -1 && value < node->right->data) { node->right = rightRotate (node->right); return leftRotate (node); } return node; } AVLNode<T>* findMin (AVLNode<T>* node) const { while (node->left != nullptr ) { node = node->left; } return node; } AVLNode<T>* deleteHelper (AVLNode<T>* node, const T& value) { if (node == nullptr ) { return node; } if (value < node->data) { node->left = deleteHelper (node->left, value); } else if (value > node->data) { node->right = deleteHelper (node->right, value); } else { if (node->left == nullptr && node->right == nullptr ) { delete node; return nullptr ; } else if (node->left == nullptr ) { AVLNode<T>* temp = node->right; delete node; return temp; } else if (node->right == nullptr ) { AVLNode<T>* temp = node->left; delete node; return temp; } AVLNode<T>* temp = findMin (node->right); node->data = temp->data; node->right = deleteHelper (node->right, temp->data); } updateHeight (node); int balance = getBalanceFactor (node); if (balance > 1 && getBalanceFactor (node->left) >= 0 ) { return rightRotate (node); } if (balance > 1 && getBalanceFactor (node->left) < 0 ) { node->left = leftRotate (node->left); return rightRotate (node); } if (balance < -1 && getBalanceFactor (node->right) <= 0 ) { return leftRotate (node); } if (balance < -1 && getBalanceFactor (node->right) > 0 ) { node->right = rightRotate (node->right); return leftRotate (node); } return node; } void inorderHelper (AVLNode<T>* node) const if (node != nullptr ) { inorderHelper (node->left); cout << node->data << " " ; inorderHelper (node->right); } } void destroyTree (AVLNode<T>* node) if (node != nullptr ) { destroyTree (node->left); destroyTree (node->right); delete node; } } public : AVLTree () : root (nullptr ) {} ~AVLTree () { destroyTree (root); } void insert (const T& value) root = insertHelper (root, value); } void remove (const T& value) root = deleteHelper (root, value); } void inorder () const cout << "Inorder traversal: " ; inorderHelper (root); cout << endl; } };
3.4 红黑树 性质 ：每个节点为红色或黑色。 根节点为黑色。 叶节点（NIL）为黑色。 红色节点的子节点为黑色。 从根到叶节点的黑色节点数相同（黑高相同）。 操作 ：插入和删除时通过旋转和变色维持平衡，时间复杂度 O(og n) 。应用 ：C++ STL中的 map、set、multimap、multiset。红黑树的C++实现（简化版） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 template <typename T>class RBNode {public : T data; RBNode<T>* left; RBNode<T>* right; RBNode<T>* parent; bool isRed; RBNode (const T& value) : data (value), left (nullptr ), right (nullptr ), parent (nullptr ), isRed (true ) {} }; template <typename T>class RedBlackTree {private : RBNode<T>* root; RBNode<T>* nil; void leftRotate (RBNode<T>* x) RBNode<T>* y = x->right; x->right = y->left; if (y->left != nil) { y->left->parent = x; } y->parent = x->parent; if (x->parent == nil) { root = y; } else if (x == x->parent->left) { x->parent->left = y; } else { x->parent->right = y; } y->left = x; x->parent = y; } void rightRotate (RBNode<T>* y) RBNode<T>* x = y->left; y->left = x->right; if (x->right != nil) { x->right->parent = y; } x->parent = y->parent; if (y->parent == nil) { root = x; } else if (y == y->parent->left) { y->parent->left = x; } else { y->parent->right = x; } x->right = y; y->parent = x; } void insertFixup (RBNode<T>* z) while (z->parent->isRed) { if (z->parent == z->parent->parent->left) { RBNode<T>* y = z->parent->parent->right; if (y->isRed) { z->parent->isRed = false ; y->isRed = false ; z->parent->parent->isRed = true ; z = z->parent->parent; } else { if (z == z->parent->right) { z = z->parent; leftRotate (z); } z->parent->isRed = false ; z->parent->parent->isRed = true ; rightRotate (z->parent->parent); } } else { RBNode<T>* y = z->parent->parent->left; if (y->isRed) { z->parent->isRed = false ; y->isRed = false ; z->parent->parent->isRed = true ; z = z->parent->parent; } else { if (z == z->parent->left) { z = z->parent; rightRotate (z); } z->parent->isRed = false ; z->parent->parent->isRed = true ; leftRotate (z->parent->parent); } } } root->isRed = false ; } void insertNode (const T& value) RBNode<T>* z = new RBNode <T>(value); RBNode<T>* y = nil; RBNode<T>* x = root; while (x != nil) { y = x; if (z->data < x->data) { x = x->left; } else if (z->data > x->data) { x = x->right; } else { delete z; return ; } } z->parent = y; if (y == nil) { root = z; } else if (z->data < y->data) { y->left = z; } else { y->right = z; } z->left = nil; z->right = nil; insertFixup (z); } void inorderHelper (RBNode<T>* node) const if (node != nil) { inorderHelper (node->left); cout << node->data << (node->isRed ? "(R) " : "(B) " ); inorderHelper (node->right); } } void destroyTree (RBNode<T>* node) if (node != nil) { destroyTree (node->left); destroyTree (node->right); if (node != this ->nil) { delete node; } } } public : RedBlackTree () { nil = new RBNode <T>(T ()); nil->isRed = false ; root = nil; } ~RedBlackTree () { destroyTree (root); delete nil; } void insert (const T& value) insertNode (value); } void inorder () const cout << "Inorder traversal: " ; inorderHelper (root); cout << endl; } };
4. 图结构 4.1 图的表示 邻接矩阵 ：二维数组 adj[i][j] 表示顶点 i 到顶点 j 的边（有权值则存储权值，否则存储0/1）。适合稠密图，空间复杂度 O(V^2) 。邻接表 ：数组 adj，其中 adj[i] 是顶点 i 的邻接顶点链表。适合稀疏图，空间复杂度 O(V+E) 。邻接表的C++实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 template <typename T>class Edge {public : int dest; T weight; Edge (int d, const T& w) : dest (d), weight (w) {} }; template <typename T>class Graph {private : int V; vector<vector<Edge<T>>> adj; public : Graph (int vertices) : V (vertices), adj (vertices) {} void addEdge (int src, int dest, const T& weight) adj[src].emplace_back (dest, weight); } void addUndirectedEdge (int src, int dest, const T& weight) addEdge (src, dest, weight); addEdge (dest, src, weight); } int getVertices () const return V; } const vector<vector<Edge<T>>>& getAdj () const { return adj; } void print () const for (int i = 0 ; i < V; i++) { cout << "Vertex " << i << ": " ; for (const auto & edge : adj[i]) { cout << "(" << edge.dest << ", " << edge.weight << ") -> " ; } cout << "nullptr" << endl; } } };
4.2 图的遍历 深度优先搜索（DFS） ：递归或栈实现，探索路径到底后回溯。广度优先搜索（BFS） ：队列实现，按层访问节点。DFS与BFS的C++实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 template <typename T>class GraphTraversal {private : const Graph<T>& graph; void dfsHelper (int start, vector<bool >& visited) const visited[start] = true ; cout << start << " " ; const auto & adj = graph.getAdj (); for (const auto & edge : adj[start]) { int dest = edge.dest; if (!visited[dest]) { dfsHelper (dest, visited); } } } public : GraphTraversal (const Graph<T>& g) : graph (g) {} void dfs (int start) const int V = graph.getVertices (); vector<bool > visited (V, false ) ; cout << "DFS traversal starting from " << start << ": " ; dfsHelper (start, visited); cout << endl; } void bfs (int start) const int V = graph.getVertices (); vector<bool > visited (V, false ) ; queue<int > q; visited[start] = true ; q.push (start); cout << "BFS traversal starting from " << start << ": " ; while (!q.empty ()) { int current = q.front (); q.pop (); cout << current << " " ; const auto & adj = graph.getAdj (); for (const auto & edge : adj[current]) { int dest = edge.dest; if (!visited[dest]) { visited[dest] = true ; q.push (dest); } } } cout << endl; } };
4.3 最短路径算法 Dijkstra算法 ：单源最短路径算法，适用于边权为正的图。使用优先队列优化，时间复杂度 O(E og V) 。Floyd-Warshall算法 ：多源最短路径算法，使用动态规划实现，时间复杂度 O(V^3) 。Dijkstra算法的C++实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 template <typename T>class Dijkstra {private : const Graph<T>& graph; public : Dijkstra (const Graph<T>& g) : graph (g) {} vector<T> shortestPath (int start) const { int V = graph.getVertices (); vector<T> dist (V, numeric_limits<T>::max()) ; vector<bool > visited (V, false ) ; priority_queue<pair<T, int >, vector<pair<T, int >>, greater<pair<T, int >>> pq; dist[start] = 0 ; pq.emplace (0 , start); while (!pq.empty ()) { auto [currentDist, u] = pq.top (); pq.pop (); if (visited[u]) { continue ; } visited[u] = true ; const auto & adj = graph.getAdj (); for (const auto & edge : adj[u]) { int v = edge.dest; T weight = edge.weight; if (!visited[v] && dist[u] != numeric_limits<T>::max () && dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; pq.emplace (dist[v], v); } } } return dist; } void printShortestPath (int start) const vector<T> dist = shortestPath (start); cout << "Shortest paths from " << start << ":" << endl; for (int i = 0 ; i < dist.size (); i++) { if (dist[i] == numeric_limits<T>::max ()) { cout << "Vertex " << i << ": unreachable" << endl; } else { cout << "Vertex " << i << ": " << dist[i] << endl; } } } };
4.4 最小生成树（MST） Prim算法 ：从单个顶点开始，逐步添加连接树与非树顶点的最小边，时间复杂度 O(E og V) 。Kruskal算法 ：按边权排序，依次添加边，使用并查集避免环，时间复杂度 O(E og E) 。Kruskal算法的C++实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 template <typename T>class Kruskal {private : const Graph<T>& graph; struct UnionFind { vector<int > parent; vector<int > rank; UnionFind (int size) { parent.resize (size); rank.resize (size, 0 ); for (int i = 0 ; i < size; i++) { parent[i] = i; } } int find (int x) if (parent[x] != x) { parent[x] = find (parent[x]); } return parent[x]; } void unite (int x, int y) int xRoot = find (x); int yRoot = find (y); if (xRoot == yRoot) { return ; } if (rank[xRoot] < rank[yRoot]) { parent[xRoot] = yRoot; } else if (rank[xRoot] > rank[yRoot]) { parent[yRoot] = xRoot; } else { parent[yRoot] = xRoot; rank[xRoot]++; } } }; public : Kruskal (const Graph<T>& g) : graph (g) {} vector<pair<pair<int , int >, T>> computeMST () const { int V = graph.getVertices (); const auto & adj = graph.getAdj (); vector<pair<T, pair<int , int >>> edges; for (int u = 0 ; u < V; u++) { for (const auto & edge : adj[u]) { int v = edge.dest; T weight = edge.weight; edges.emplace_back (weight, make_pair (u, v)); } } sort (edges.begin (), edges.end ()); UnionFind uf (V) ; vector<pair<pair<int , int >, T>> mst; T totalWeight = 0 ; for (const auto & edge : edges) { T weight = edge.first; int u = edge.second.first; int v = edge.second.second; if (uf.find (u) != uf.find (v)) { uf.unite (u, v); mst.emplace_back (make_pair (u, v), weight); totalWeight += weight; } } cout << "Minimum Spanning Tree edges:" << endl; for (const auto & edge : mst) { int u = edge.first.first; int v = edge.first.second; T weight = edge.second; cout << u << " - " << v << " (weight: " << weight << ")" << endl; } cout << "Total weight of MST: " << totalWeight << endl; return mst; } };
5. 排序算法 5.1 插入排序 思想 ：将元素插入到已排序部分的正确位置，时间复杂度 O(n^2) ，适合小规模或基本有序数据。插入排序的C++实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 template <typename T>void insertionSort (vector<T>& arr) int n = arr.size (); for (int i = 1 ; i < n; i++) { T key = arr[i]; int j = i - 1 ; while (j >= 0 && arr[j] > key) { arr[j + 1 ] = arr[j]; j--; } arr[j + 1 ] = key; } }
5.2 归并排序 思想 ：分治，将数组分为两半递归排序，再合并，时间复杂度 O(n og n) ，稳定排序。归并排序的C++实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 template <typename T>void merge (vector<T>& arr, int left, int mid, int right) int n1 = mid - left + 1 ; int n2 = right - mid; vector<T> L (n1) ; vector<T> R (n2) ; for (int i = 0 ; i < n1; i++) { L[i] = arr[left + i]; } for (int j = 0 ; j < n2; j++) { R[j] = arr[mid + 1 + j]; } int i = 0 , j = 0 , k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k++] = L[i++]; } else { arr[k++] = R[j++]; } } while (i < n1) { arr[k++] = L[i++]; } while (j < n2) { arr[k++] = R[j++]; } } template <typename T>void mergeSort (vector<T>& arr, int left, int right) if (left < right) { int mid = left + (right - left) / 2 ; mergeSort (arr, left, mid); mergeSort (arr, mid + 1 , right); merge (arr, left, mid, right); } } template <typename T>void mergeSort (vector<T>& arr) mergeSort (arr, 0 , arr.size () - 1 ); }
5.3 快速排序 思想 ：选择pivot划分数组为两部分，递归排序，时间复杂度平均 O(n og n) ，最坏 O(n^2) ，非稳定排序。快速排序的C++实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 template <typename T>int partition (vector<T>& arr, int low, int high) T pivot = arr[high]; int i = low - 1 ; for (int j = low; j < high; j++) { if (arr[j] <= pivot) { i++; swap (arr[i], arr[j]); } } swap (arr[i + 1 ], arr[high]); return i + 1 ; } template <typename T>void quickSort (vector<T>& arr, int low, int high) if (low < high) { int pi = partition (arr, low, high); quickSort (arr, low, pi - 1 ); quickSort (arr, pi + 1 , high); } } template <typename T>void quickSort (vector<T>& arr) quickSort (arr, 0 , arr.size () - 1 ); }
5.4 堆排序 思想 ：利用大顶堆特性，依次取出堆顶元素，时间复杂度 O(n og n) ，非稳定排序。堆排序的C++实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 template <typename T>void heapify (vector<T>& arr, int n, int i) int largest = i; int left = 2 * i + 1 ; int right = 2 * i + 2 ; if (left < n && arr[left] > arr[largest]) { largest = left; } if (right < n && arr[right] > arr[largest]) { largest = right; } if (largest != i) { swap (arr[i], arr[largest]); heapify (arr, n, largest); } } template <typename T>void heapSort (vector<T>& arr) int n = arr.size (); for (int i = n / 2 - 1 ; i >= 0 ; i--) { heapify (arr, n, i); } for (int i = n - 1 ; i > 0 ; i--) { swap (arr[0 ], arr[i]); heapify (arr, i, 0 ); } }
5.5 排序算法比较 排序算法 最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度 稳定性 插入排序 O(n) O(n^2) O(n^2) O(1) 稳定 归并排序 O(n og n) O(n og n) O(n og n) O(n) 稳定 快速排序 O(n og n) O(n^2) O(n og n) O(og n) 不稳定 堆排序 O(n og n) O(n og n) O(n og n) O(1) 不稳定 冒泡排序 O(n) O(n^2) O(n^2) O(1) 稳定 选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定
6. 查找算法 6.1 二分查找 二分查找的C++实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 template <typename T>int binarySearch (const vector<T>& arr, const T& target) int left = 0 ; int right = arr.size () - 1 ; 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 ; } template <typename T>int binarySearchRecursive (const vector<T>& arr, int left, int right, const T& target) if (left <= right) { int mid = left + (right - left) / 2 ; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { return binarySearchRecursive (arr, mid + 1 , right, target); } else { return binarySearchRecursive (arr, left, mid - 1 , target); } } return -1 ; } template <typename T>int binarySearchRecursive (const vector<T>& arr, const T& target) return binarySearchRecursive (arr, 0 , arr.size () - 1 , target); }
6.2 哈希表 思想 ：使用哈希函数将键映射到哈希表索引，时间复杂度平均 O(1) ，最坏 O(n) 。冲突处理 ：链地址法、开放定址法。哈希表的C++实现（链地址法） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 template <typename K, typename V>class HashNode {public : K key; V value; HashNode<K, V>* next; HashNode (const K& k, const V& v) : key (k), value (v), next (nullptr ) {} }; template <typename K, typename V>class HashTable {private : vector<HashNode<K, V>*> table; size_t size; size_t capacity; size_t hash (const K& key) const return hash <K>()(key) % capacity; } void resize () size_t newCapacity = capacity * 2 ; vector<HashNode<K, V>*> newTable (newCapacity, nullptr ); for (size_t i = 0 ; i < capacity; i++) { HashNode<K, V>* current = table[i]; while (current != nullptr ) { HashNode<K, V>* next = current->next; size_t index = hash <K>()(current->key) % newCapacity; current->next = newTable[index]; newTable[index] = current; current = next; } } table.swap (newTable); capacity = newCapacity; } public : HashTable (size_t initialCapacity = 16 ) : size (0 ), capacity (initialCapacity) { table.resize (capacity, nullptr ); } ~HashTable () { clear (); } void insert (const K& key, const V& value) if (size >= capacity * 0.7 ) { resize (); } size_t index = hash (key); HashNode<K, V>* current = table[index]; while (current != nullptr ) { if (current->key == key) { current->value = value; return ; } current = current->next; } HashNode<K, V>* newNode = new HashNode <K, V>(key, value); newNode->next = table[index]; table[index] = newNode; size++; } V get (const K& key) const { size_t index = hash (key); HashNode<K, V>* current = table[index]; while (current != nullptr ) { if (current->key == key) { return current->value; } current = current->next; } throw runtime_error ("Key not found" ); } void remove (const K& key) size_t index = hash (key); HashNode<K, V>* current = table[index]; HashNode<K, V>* prev = nullptr ; while (current != nullptr ) { if (current->key == key) { if (prev == nullptr ) { table[index] = current->next; } else { prev->next = current->next; } delete current; size--; return ; } prev = current; current = current->next; } throw runtime_error ("Key not found" ); } bool contains (const K& key) const size_t index = hash (key); HashNode<K, V>* current = table[index]; while (current != nullptr ) { if (current->key == key) { return true ; } current = current->next; } return false ; } void clear () for (size_t i = 0 ; i < capacity; i++) { HashNode<K, V>* current = table[i]; while (current != nullptr ) { HashNode<K, V>* temp = current; current = current->next; delete temp; } table[i] = nullptr ; } size = 0 ; } size_t getSize () const return size; } bool isEmpty () const return size == 0 ; } };
7. 高级数据结构 7.1 B树 定义 ：多路搜索树，每个节点包含多个键和子节点指针，适用于磁盘等外部存储。性质 ：根节点至少有2个子节点，非根节点至少有 m/2 个子节点（ m 为阶数），所有叶节点在同一层。B树的C++实现（简化版） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 template <typename T>class BTreeNode {public : vector<T> keys; vector<BTreeNode<T>*> children; bool isLeaf; BTreeNode (bool leaf) : isLeaf (leaf) {} }; template <typename T>class BTree {private : BTreeNode<T>* root; int order; void splitChild (BTreeNode<T>* parent, int index, BTreeNode<T>* child) BTreeNode<T>* newChild = new BTreeNode <T>(child->isLeaf); int mid = order / 2 ; for (int i = mid + 1 ; i < child->keys.size (); i++) { newChild->keys.push_back (child->keys[i]); } if (!child->isLeaf) { for (int i = mid + 1 ; i < child->children.size (); i++) { newChild->children.push_back (child->children[i]); } } child->keys.resize (mid); if (!child->isLeaf) { child->children.resize (mid + 1 ); } parent->keys.insert (parent->keys.begin () + index, child->keys[mid]); parent->children.insert (parent->children.begin () + index + 1 , newChild); } void insertNonFull (BTreeNode<T>* node, const T& key) int i = node->keys.size () - 1 ; if (node->isLeaf) { node->keys.push_back (key); while (i >= 0 && node->keys[i] > key) { node->keys[i + 1 ] = node->keys[i]; i--; } node->keys[i + 1 ] = key; } else { while (i >= 0 && node->keys[i] > key) { i--; } i++; if (node->children[i]->keys.size () == order - 1 ) { splitChild (node, i, node->children[i]); if (key > node->keys[i]) { i++; } } insertNonFull (node->children[i], key); } } bool searchHelper (BTreeNode<T>* node, const T& key) const int i = 0 ; while (i < node->keys.size () && key > node->keys[i]) { i++; } if (i < node->keys.size () && key == node->keys[i]) { return true ; } if (node->isLeaf) { return false ; } return searchHelper (node->children[i], key); } void destroyTree (BTreeNode<T>* node) if (node != nullptr ) { if (!node->isLeaf) { for (auto child : node->children) { destroyTree (child); } } delete node; } } public : BTree (int ord) : order (ord), root (nullptr ) {} ~BTree () { destroyTree (root); } void insert (const T& key) if (root == nullptr ) { root = new BTreeNode <T>(true ); root->keys.push_back (key); } else { if (root->keys.size () == order - 1 ) { BTreeNode<T>* newRoot = new BTreeNode <T>(false ); newRoot->children.push_back (root); splitChild (newRoot, 0 , root); int i = 0 ; if (key > newRoot->keys[0 ]) { i++; } insertNonFull (newRoot->children[i], key); root = newRoot; } else { insertNonFull (root, key); } } } bool search (const T& key) const if (root == nullptr ) { return false ; } return searchHelper (root, key); } };
7.2 B+树 定义 ：B树变种，所有数据存储在叶节点，叶节点形成链表，适合范围查询。优势 ：叶节点链表支持顺序访问，查询效率更高，适合数据库索引。7.3 斐波那契堆 定义 ：由多个最小堆组成的森林，支持合并、插入、删除最小值等操作，均摊时间复杂度优于二叉堆。优势 ：插入和合并操作的均摊时间复杂度为 O(1) ，删除最小值为 O(og n) 。应用 ：图算法（如Prim和Dijkstra的优化）。7.4 并查集 定义 ：用于管理元素所属集合的数据结构，支持查找和合并操作。优化 ：路径压缩和按秩合并，使时间复杂度接近 O(1) 。应用 ：Kruskal最小生成树算法、连通分量问题。并查集的C++实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 class UnionFind {private : vector<int > parent; vector<int > rank; public : UnionFind (int size) { parent.resize (size); rank.resize (size, 0 ); for (int i = 0 ; i < size; i++) { parent[i] = i; } } int find (int x) if (parent[x] != x) { parent[x] = find (parent[x]); } return parent[x]; } void unite (int x, int y) int xRoot = find (x); int yRoot = find (y); if (xRoot == yRoot) { return ; } if (rank[xRoot] < rank[yRoot]) { parent[xRoot] = yRoot; } else if (rank[xRoot] > rank[yRoot]) { parent[yRoot] = xRoot; } else { parent[yRoot] = xRoot; rank[xRoot]++; } } bool isConnected (int x, int y) return find (x) == find (y); } };
8. 算法设计技术 8.1 贪心算法 策略 ：每一步选择当前最优解，希望全局最优。适用条件 ：贪心选择性质和最优子结构。示例 ：活动选择问题、霍夫曼编码、最小生成树（Kruskal和Prim算法）。活动选择问题的C++实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 struct Activity { int start; int finish; Activity (int s, int f) : start (s), finish (f) {} }; bool compareActivities (const Activity& a, const Activity& b) return a.finish < b.finish; } vector<Activity> selectActivities (vector<Activity>& activities) { vector<Activity> selected; sort (activities.begin (), activities.end (), compareActivities); selected.push_back (activities[0 ]); int lastFinish = activities[0 ].finish; for (size_t i = 1 ; i < activities.size (); i++) { if (activities[i].start >= lastFinish) { selected.push_back (activities[i]); lastFinish = activities[i].finish; } } return selected; }
8.2 动态规划 策略 ：将问题分解为子问题，存储子问题解避免重复计算。适用条件 ：重叠子问题和最优子结构。示例 ：0-1背包问题、最长公共子序列（LCS）、最短路径（Floyd-Warshall算法）。0-1背包问题的C++实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 int knapsack (int W, const vector<int >& weights, const vector<int >& values, int n) vector<vector<int >> dp (n + 1 , vector <int >(W + 1 , 0 )); for (int i = 1 ; i <= n; i++) { for (int w = 0 ; w <= W; w++) { if (weights[i - 1 ] <= w) { dp[i][w] = max (values[i - 1 ] + dp[i - 1 ][w - weights[i - 1 ]], dp[i - 1 ][w]); } else { dp[i][w] = dp[i - 1 ][w]; } } } return dp[n][W]; }
8.3 分治算法 策略 ：将问题分解为独立子问题，递归解决后合并结果。适用条件 ：问题可分解为规模更小的子问题，子问题解可合并为原问题解。示例 ：归并排序、快速排序、大整数乘法、Strassen矩阵乘法。8.4 回溯算法 策略 ：尝试所有可能的解，通过剪枝避免无效路径。适用条件 ：组合优化问题，解空间较大但可通过剪枝减少搜索空间。示例 ：八皇后问题、迷宫问题、子集和问题。八皇后问题的C++实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 class NQueens {private : int n; vector<vector<string>> solutions; bool isSafe (const vector<string>& board, int row, int col) for (int i = 0 ; i < row; i++) { if (board[i][col] == 'Q' ) { return false ; } } for (int i = row - 1 , j = col - 1 ; i >= 0 && j >= 0 ; i--, j--) { if (board[i][j] == 'Q' ) { return false ; } } for (int i = row - 1 , j = col + 1 ; i >= 0 && j < n; i--, j++) { if (board[i][j] == 'Q' ) { return false ; } } return true ; } void backtrack (vector<string>& board, int row) if (row == n) { solutions.push_back (board); return ; } for (int col = 0 ; col < n; col++) { if (isSafe (board, row, col)) { board[row][col] = 'Q' ; backtrack (board, row + 1 ); board[row][col] = '.' ; } } } public : NQueens (int size) : n (size) {} vector<vector<string>> solve () { vector<string> board (n, string(n, '.' )) ; backtrack (board, 0 ); return solutions; } void printSolutions () for (size_t i = 0 ; i < solutions.size (); i++) { cout << "Solution " << i + 1 << ":" << endl; for (const string& row : solutions[i]) { cout << row << endl; } cout << endl; } } };
9. 实际应用与性能优化 9.1 数据结构选择原则 根据操作频率 ：频繁查找：哈希表、平衡树（红黑树、AVL树）。 频繁插入/删除：链表、二叉搜索树。 频繁顺序访问：数组、链表。 根据数据规模 ：小数据：数组（空间效率高）。 大数据：链表、动态数组（无容量限制）。 根据内存限制 ：空间紧张：紧凑结构（数组）。 空间充足：操作高效结构（哈希表）。 9.2 性能优化技巧 缓存优化 ：时间局部性 ：最近访问的数据可能再次被访问，使用缓存。空间局部性 ：连续访问的数据应存储在连续内存（如数组）。代码优化 ：内联函数：减少函数调用开销。 循环展开：减少循环控制开销。 避免不必要的计算：预处理、缓存中间结果。 并行计算 ：多线程：利用多核CPU。 GPU加速：适合并行度高的计算（如矩阵乘法）。 9.3 C++特性的利用 模板 ：实现通用数据结构和算法，如 vector、map、set 等。STL ：标准模板库提供了丰富的数据结构和算法，如排序、查找、容器等。智能指针 ：自动管理内存，避免内存泄漏，如 unique_ptr、shared_ptr。移动语义 ：减少不必要的拷贝，提高性能，如 std::move。10. 总结 《数据结构、算法与应用：C++语言描述》第2版是一本系统讲解数据结构与算法的经典教材，通过C++实现，帮助读者理解数据结构的设计原理和算法分析方法。本书的核心价值在于：
C++特性的充分利用 ：通过模板、STL等C++特性，实现通用且高效的数据结构和算法。理论与实践结合 ：不仅讲解概念，还提供完整的C++实现示例，便于理解与应用。算法分析的深入 ：详细的时间复杂度和空间复杂度分析，帮助读者评估算法性能。应用场景的丰富 ：结合实际问题，展示数据结构和算法的应用价值。通过学习本书，读者可以掌握数据结构与算法的核心原理，提高代码效率，为解决复杂问题打下坚实基础。在实际编程中，应根据具体场景选择合适的数据结构和算法，平衡时间复杂度与空间复杂度，编写高效、可维护的代码。
数据结构与算法是计算机科学的基础，无论编程语言如何变化，其核心原理始终不变。掌握好数据结构与算法，不仅可以提高编程能力，还可以培养逻辑思维能力，为未来的职业发展奠定坚实基础。
参考资料 《数据结构、算法与应用：C++语言描述》（第2版），Sartaj Sahni 著 C++标准库文档 算法可视化工具：Visualgo（https://visualgo.net/） 数据结构与算法在线课程：Coursera、edX 
