C++ 学习笔记(四)——字符串、二叉树、排序、类与结构体
- 2026-04-23 18:52:17
C++ 学习笔记
四、字符串操作完整速查
4.1 string 核心方法
string s = "Hello, World!"; // ── 长度 ────────────────────────────────────────────── s.size(); // 13（等价 s.length()） s.empty(); // false // ── 访问 ────────────────────────────────────────────── s[0]; // 'H'（char 类型） s.front(); // 'H' s.back(); // '!' // ── 截取子串 ─────────────────────────────────────────── s.substr(7, 5); // "World"（从下标7起，截5个字符） s.substr(7); // "World!"（从下标7到末尾） // ── 查找 ────────────────────────────────────────────── s.find('o'); // 4（第一个 'o' 的下标） s.find("World"); // 7 s.find('z'); // string::npos（不存在时的返回值） // 判断是否找到 if (s.find("llo") != string::npos) { /* 存在 */ } // ── 修改 ────────────────────────────────────────────── s += "!!!"; // 追加字符串 s += '?'; // 追加单个字符 s.pop_back(); // 删除最后一个字符（原地，无返回值） // ── 反转 ────────────────────────────────────────────── reverse(s.begin(), s.end()); // 原地反转，无返回值！ // 注意：reverse 不返回新字符串，s 本身已被修改 |
4.2 类型转换速查表
转换方向 | 方法 | 示例与说明 |
数字→ 字符串 | to_string(val) | to_string(42) → "42" |
字符串→ 整数 | stoi(str) | stoi("007") → 7（忽略前导零） |
字符串→ 长整数 | stol(str) / stoll(str) | 处理大数时用 |
字符串→ 浮点 | stod(str) / stof(str) | stod("3.14") → 3.14 |
字符→ 数字 | ch - '0' | '7' - '0' → 7（仅适用'0'~'9'） |
字符→ 字符串 | string(1, ch) | string(1,'A') → "A" |
字符→ 整数（通用） | stoi(string(1,ch)) | 适用任意字符，但略繁琐 |
整数→ 字符 | '0' + val | '0'+5 → '5'（仅0~9有效） |
char* → string | string s = cstr; | 直接赋值即可 |
string → char* | s.c_str() | 返回 const char*，配合 strcpy 用 |
// 字符转数字的完整示例 char ch = '7'; int n1 = ch - '0'; // = 7，最简洁，仅适合 '0'~'9' int n2 = stoi(string(1, ch)); // = 7，更通用 // 逐字符构建数字（字符串转数字的手动实现） string s = "1.0.3"; int num = 0; int i = 0; while (i < s.size() && s[i] != '.') { num = num * 10 + (s[i] - '0'); i++; } // num = 1 | |
��提示string(1, ch) 中第一个参数是"重复次数"，第二个是字符。若传入的是整数（如 val），需先转字符：string(1, '0'+val)。 |
4.3 字符串拼接与 C 风格字符串的返回
string 支持 += 运算符直接拼接字符、字符串或转换后的数字。当函数要求返回 char* 时，需手动分配内存并拷贝：
// 字符串构建示例（如序列化二叉树） string res = "{"; res += "abc"; // 拼接字符串 res += ','; // 拼接单个字符 res += to_string(node->val); // 拼接数字（必须先转字符串） res += "}"; res.pop_back(); // 删除末尾多余的逗号 // 函数返回类型要求 char* 时 char* toCharPtr(string res) { char* buf = new char[res.size() + 1]; // +1 留给 \0 终止符 strcpy(buf, res.c_str()); // 把 string 内容拷贝进去 return buf; // 调用方需要 delete[] buf } // 把传入的 char* 转为 string 以便操作 char* toCharPtr2(char* str) { string s = str; // char* → string，直接赋值 // 现在可以用 string 的所有方法 s.size(); s.find('.'); s.substr(1,3); } |
五、二叉树 DFS 模板
二叉树的深度优先搜索（DFS）通常用递归实现。有两种最常见的形式，注意判断顺序非常关键。
5.1 判断节点 b 是否在以 a 为根的子树中
传入两个节点指针，返回 bool。思路：若当前节点就是目标则返回 true；若已到空节点则返回 false；否则递归左右子树。
bool dfs(TreeNode* a, TreeNode* b) { if (a == b) return true; // 找到目标 if (a == nullptr) return false; // 到达空节点 return dfs(a->left, b) || dfs(a->right, b); } // 注意：这里先判断 a==b 再判断 a==nullptr // 原因：b 不可能是 nullptr（题目保证目标节点存在） // 若 b 可能为 nullptr，则需先判 a==nullptr |
5.2 按值查找节点，返回节点指针
TreeNode* dfs(TreeNode* a, int b) { if (a == nullptr) return nullptr; // ✅ 必须先判空 if (a->val == b) return a; // ✅ 再访问 val TreeNode* left = dfs(a->left, b); return left ? left : dfs(a->right, b); // 左子树找到了就直接返回；否则尝试右子树 } | |
��说明DFS 递归的"先判空"原则：任何通过指针访问成员（->val / ->left）之前，都必须先确认指针不为 nullptr。这是防止空指针崩溃的基本规范。 |
六、排序
6.1 为什么推荐 std::sort
手写快速排序（Quick Sort）在最坏情况（如已排序数组）时间复杂度退化为 O(n²)，可能在 OJ 上超时。std::sort 使用 IntroSort（快排 + 堆排 + 插入排序的混合算法），最坏 O(n log n)，实际性能极好。
基本用法
#include <algorithm> // 默认升序 sort(v.begin(), v.end()); // 降序 sort(v.begin(), v.end(), greater<int>()); // 部分排序（只排下标 [1, 4) 的部分） sort(v.begin() + 1, v.begin() + 4); |
自定义比较函数的三种写法
给 sort 传类的成员函数作比较器有限制。以下三种方式均可，任选其一：
struct Interval { int start, end; }; vector<Interval> intervals; // ── 方式 1：全局函数（最传统）──────────────────────── bool cmp(Interval a, Interval b) { return a.start < b.start; // 按 start 升序 } sort(intervals.begin(), intervals.end(), cmp); // ── 方式 2：类内 static 成员函数 ───────────────────── class Solution { public: static bool cmp(Interval a, Interval b) { return a.start < b.start; } void solve() { sort(intervals.begin(), intervals.end(), cmp); } }; // ── 方式 3：Lambda 表达式（最现代，推荐）────────────── sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) { return a.start < b.start; }); | |
⚠️ 注意 普通（非 static）成员函数不能直接传给 sort，因为它有隐式的 this 参数，类型不匹配。必须用上面三种方式之一。 | |
��说明类内函数自己递归调用自己（如 dfs 调用 dfs）完全没有问题，没有任何限制。这个约束只针对把函数作为参数传递的场景。 |
七、类与结构体
7.1 类定义体内不能有执行语句
class / struct 的大括号 {} 定义的是类型的"蓝图"，它告诉编译器内存布局和对外接口，不产生任何运行时代码。因此只能放：成员变量声明（含内联初始化）、成员函数声明/定义、嵌套类型等。赋值、函数调用、循环等执行语句必须放在函数体（构造函数或其他成员函数）内。
// ❌ 错误：类体内直接写执行语句 struct Bad { int x = 0; x = 10; // ❌ 赋值语句，编译错误 cout << x; // ❌ 函数调用，编译错误 }; // ✅ 正确：执行语句放入构造函数 struct Node { int key, val; Node* pre; Node* next; // 构造函数：用初始化列表赋初值 Node(int k, int v) : key(k), val(v), pre(nullptr), next(nullptr) {} }; class LRUCache { public: Node* head = new Node(0, 0); // ✅ 内联初始化 Node* tail = new Node(0, 0); // ✅ 内联初始化 LRUCache(int capacity) { head->next = tail; // ✅ 执行语句在构造函数里 tail->pre = head; // ✅ } }; | |
��提示构造函数的初始化列表（: key(k), val(v)）比在函数体内赋值效率更高，因为它直接初始化成员而非先默认构造再赋值。 |
END
