[数据结构·C++语法] string 成员函数详解
C++ std::string 成员函数详解std::string 是 C++ 标准库中用于处理字符串的类。它提供了丰富的成员函数，使其操作既方便又高效。本文档整理了 std::string 的常用成员函数，并提供了使用实例。 1. 构造函数 (Constructors)用于创建 std::string 对象。 默认构造函数创建一个空字符串。12345678#include <iostream>#include <string>int main() { std::string s; std::cout << "空字符串: \"" << s << "\"" << std::endl; return 0;} 拷贝构造函数用一个已有的 std::string 对象创建新对象。 123456789#include <iostream>#include <string>int main()...
[数据结构·C++语法] STL list 详解
C++ STL std::list 详解与应用指南std::list 是 C++ 标准模板库（STL）中的双向链表容器。与 std::vector（动态数组）不同，它的内存是不连续的。 1. 核心特性与迭代器1.1 迭代器类型：双向迭代器 (Bidirectional Iterator)这是 list 最需要注意的地方，它的迭代器不像 vector 那样支持随机访问。 不支持的操作： it + 5, it - 3 (算术加减) it[2] (下标访问) it1 < it2 (大小比较，只能判断 != 或 ==) std::sort(list.begin(), list.end()) (标准库的通用排序无法处理它) 支持的操作： it++, ++it, it--, --it *it (解引用) it1 == it2, it1 != it2 1.2 辅助函数 (移动迭代器)由于不能直接 +n，如果需要移动多步，必须使用 <iterator> 头文件中的函数： std::next(it, n): 返回向前移动 $n$ 步后的迭代器（$O(n)$...
[数据结构·C++语法] cout 使用方法详解
std::cout 是 C++ I/O 流库中用于标准输出（通常是控制台/终端）的对象。要使用它，必须包含 <iostream> 头文件。 C++ std::cout 使用方法详解1. 基础：包含头文件和命名空间在使用 cout 之前，必须包含 <iostream> 头文件。cout 位于 std 命名空间中。 123456789101112131415161718#include <iostream>int main() { // 必须使用 std:: 前缀 std::cout << "Hello, world!" << std::endl; // 或者使用 using 声明 using std::cout; using std::endl; cout << "Hello again!" << endl; // 或者使用 using namespace...
[数据结构·C++语法] 文件IO核心指南
C++ 通过 <fstream> 头文件提供强大的文件输入/输出功能。它将文件视为一种“流”（stream），允许你像使用 cin 和 cout 一样方便地读写文件。 核心头文件：12345678910111213141516171819202122232425262728293031323334353637383940414243#include <fstream>````---## 1. 核心类 (文件流对象)在 `<fstream>` 中，你主要会用到三个类，它们是文件操作的“变量”：- **`std::ifstream`** (Input File Stream) - **用途：** 用于从文件中**读取**数据。 - **类比：** 就像 `cin`，但数据源是文件。 - **`std::ofstream`** (Output File Stream) - **用途：** 用于向文件中**写入**数据。 - **类比：** 就像...
[数据结构·C++语法] 模板用法详解
C++ 中的模板（Template）是泛型编程的基石。它允许我们编写与类型无关的代码，即编写一个函数或一个类，让它们能够处理任何数据类型，而无需为每一种类型都重写一次代码。这大大提高了代码的可重用性和灵活性。 1. 什么是 template <typename T>？这是一个模板声明，它告诉编译器接下来的代码（无论是函数还是类）是一个“蓝图”或“模板”，而不是一个具体的实现。 template: C++ 的关键字，表示这是一个模板。 <...>: 尖括号内是模板参数列表。 typename: 关键字，用来声明后面的标识符是一个类型参数。在模板参数列表中，typename 和 class 关键字是等价的，可以互换使用。但通常推荐使用 typename，因为它更明确地表示 T 是一个类型名称。 T: 这是一个模板参数，它是一个占位符，代表一个尚未确定的数据类型。你可以使用任何合法的标识符来代替 T（例如 U, MyType 等），但 T 是最常用的惯例。 当你在代码中使用这个模板时（比如 max<int>(a,...
[数据结构·C++语法] 常见序列容器对比
简介在 C++ STL (标准模板库) 中，序列容器（Sequence Containers）是这样一类容器，它们中的元素都按严格的线性顺序排列。每个元素都有其固定的位置，你可以访问“第一个”元素、“最后一个”元素或“第n个”元素。 最常见的序列容器包括： std::vector std::deque std::list std::array (C++11) std::forward_list (C++11) std::string (专门的字符序列容器) 下面我们将详细介绍前五个通用容器，并简要对比 std::string。 1. std::vector头文件: <vector>底层实现: 动态数组（连续内存）。 vector 是 C++ 中最常用、最灵活的序列容器。它将元素存储在一段连续的内存中，这使得它具有极高的随机访问（通过索引 []）性能。 核心特点: 优点: 随机访问速度最快 (O(1))。尾部插入/删除速度快（均摊 O(1)）。 缺点: 在中间或头部插入/删除元素非常慢 (O(n))，因为它需要移动之后的所有元素。 内存:...
[数据结构·链表] 链表
这是一个非常棒的复习方向。链表（Linked List）是数据结构期末考试中必考且分值较高的模块，通常出现在选择题（考察复杂度）、代码填空题（考察指针操作）和算法大题（手写完整逻辑）中。 数据结构期末复习笔记：链表 (Linked List)一、 核心考点梳理1. 链表 vs 数组 (核心理论)这是选择题和简答题的高频考点，必须熟记两者的区别。 特性 数组 (Array) 链表 (Linked List) 内存存储 连续内存空间 离散内存空间，通过指针连接 随机访问 支持，$O(1)$ 不支持，需要遍历，$O(n)$ 插入/删除 效率低，需移动元素，$O(n)$ 效率高，仅需修改指针，$O(1)$ (前提是已知位置) 空间利用 可能有碎片或预分配浪费 动态分配，但每个节点需额外存储指针 2. 常见链表类型 单链表 (Singly Linked List): 节点包含 data 和 next。 双向链表 (Doubly Linked List): 节点包含 data、prev 和 next。删除节点更方便（因为能找到前驱）。 循环链表...
[数据结构·排序] 快速选择算法
针对从乱序数组中找到第 $k$ 小元素的问题，最经典且高效的算法是 快速选择算法 (Quick Select)。 虽然普通的排序（如快速排序、归并排序）可以将数组全排好后取第 $k$ 个，时间复杂度是 $O(N \log N)$，但如果只要第 $k$ 个，其实没必要把所有人都有序排列。 以下是几种针对该场景的方法，按推荐程度排序： 1. 快速选择算法 (Quick Select) —— 最推荐这是基于快速排序 (Quick Sort) 思想的变种算法。 核心思想： 在快排中，我们每次选取一个基准值 (Pivot)，执行 Partition 操作，将小于 Pivot 的放左边，大于 Pivot 的放右边。 快排：需要递归处理左右两边。 快选：Partition 后，我们可以知道 Pivot 最终所在的下标 index。 如果 index == k-1，那 Pivot 就是我们要找的目标，直接返回。 如果 index > k-1，说明目标在左半区，我们只递归左边。 如果 index <...
[数据结构·排序] 快速排序
快速排序 (Quicksort)快速排序（Quicksort）是一种非常高效的、基于比较的、就地（in-place）排序算法。它由东尼·霍尔（Tony Hoare）在1959年发明，是目前使用最广泛的排序算法之一。 核心思想：分治 (Divide and Conquer)快速排序的核心思想是“分治法”。它将一个大数组不断地分割成越来越小的子数组，然后分别对子数组进行排序，最终使得整个数组有序。 这个过程主要分为三步： 选择基准 (Pivot): 从数组中挑选一个元素，这个元素被称为“基准”或“枢轴”。 分区 (Partition): 重新排列数组。将所有小于基准的元素移动到基准的左侧，所有大于基准的元素移动到基准的右侧（等于的可以放在任意一侧）。完成分区后，这个基准元素就处在它在排序后数组中的最终位置。 递归 (Recurse): 递归地对基准左侧的子数组和基准右侧的子数组重复上述过程。 当一个子数组的大小为 0 或 1 时，它自然就是有序的，递归就停止了。 算法步骤详解假设我们要对数组 arr 从索引 low 到 high 的部分进行排序： 选择基准...
[数据结构·排序] 堆排序
数据结构与算法：堆排序 (Heap Sort) 详解堆排序（Heap Sort）是一种基于比较的排序算法，它利用了堆（Heap）这种数据结构来设计。它的主要特点是时间复杂度稳定在 $O(n \log n)$，并且只需要 $O(1)$ 的额外空间（原地排序）。 1. 堆排序的原理1.1 什么是“堆”？堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。 大顶堆 (Max Heap)：每个节点的值都大于或等于其子节点的值。堆顶（根节点）是整个堆中最大的元素。（升序排序使用大顶堆） 小顶堆 (Min Heap)：每个节点的值都小于或等于其子节点的值。堆顶是最小的元素。（降序排序使用小顶堆） 1.2 数组与堆的映射在实际代码中，我们通常使用数组来存储堆，而不是建立链式二叉树。对于数组中下标为 $i$ 的节点： 父节点索引：\lfloor \frac{i-1}{2} \rfloor 左孩子索引：2i + 1 右孩子索引：2i + 2 1.3 排序流程 (以升序为例)堆排序主要分为两个阶段： 建堆 (Build...