1. 项目概述为什么需要自己实现串的链式存储与匹配在C的标准库STL里std::string已经为我们封装好了字符串的几乎所有操作包括查找、匹配。那么为什么我们还要“多此一举”自己动手用链式存储来实现一个字符串并为其编写匹配算法呢这绝不是为了重复造轮子而是为了深入理解两个核心的计算机科学概念数据结构与算法的底层实现逻辑。串也就是字符串是编程中最基础、最常用的数据类型之一。它的存储方式主要有两种顺序存储比如C风格字符数组或std::string的典型实现和链式存储。顺序存储大家接触得多连续的内存块随机访问快但插入、删除可能涉及大量数据移动。链式存储则相反它由一系列分散的节点通过指针链接而成每个节点存放一个或几个字符。这种结构在频繁进行局部修改如文本编辑器的早期实现的场景下有其优势但随机访问效率低匹配算法也需要相应调整。自己动手实现一个链式串我们暂且叫它LinkedString并为其编写一个朴素的模式匹配算法就像汽车爱好者亲手拆解、组装一台发动机。你知道了std::string的find()方法很快但通过这个项目你将彻底明白“快”的背后内存是如何组织的指针是如何跳转的以及当数据不连续时算法应该如何设计。这对于理解更复杂的链表结构如区块链、文件系统块链、以及应对一些特殊的面试场景面试官就爱问底层实现至关重要。接下来我将带你从零开始构建一个CharNode节点串联成LinkedString并实现一个简单但完整的模式匹配功能。我们会深入每个步骤的“为什么”并分享我在实现过程中踩过的坑和总结的技巧。最终你会得到一套可以直接编译、运行和学习的完整源码。2. 核心数据结构设计链式串的节点与类任何链式结构的第一步都是设计节点。我们的链式串也不例外。2.1 字符节点CharNode的设计考量一个最直观的想法是一个节点只存一个字符。这样做概念清晰但缺点也明显——内存开销巨大。在64位系统上一个char占1字节但一个节点至少包含数据域和一个next指针8字节内存利用率极低且遍历效率差。因此更实用的设计是让一个节点存储一个定长的小字符串比如4个、8个或16个字符。这能显著减少节点数量提高内存局部性和遍历效率。这里我们选择一个折中且常见的方案每个节点存储一个固定大小的字符块例如char data[BLOCK_SIZE]。当字符串长度不是块大小的整数倍时最后一个节点未使用的部分可以填充空字符\0。为什么选择固定块大小而不是像std::string那样动态数组因为这是链表的特性。链表擅长处理不连续的内存块固定块大小简化了内存管理和节点间的数据迁移逻辑。如果块内动态就变成了“链表套动态数组”复杂度会急剧上升违背了我们学习底层实现的初衷。基于以上思路我们设计CharNode结构体struct CharNode { static const int BLOCK_SIZE 4; // 每个节点存储4个字符 char data[BLOCK_SIZE]; // 字符数据块 CharNode* next; // 指向下一个节点的指针 int length; // 当前节点实际存储的字符数 BLOCK_SIZE // 构造函数 CharNode() : next(nullptr), length(0) { std::fill_n(data, BLOCK_SIZE, \0); // 初始化为空字符 } // 从C风格字符串初始化的构造函数辅助用 CharNode(const char* str, int len) : next(nullptr) { int copyLen std::min(len, BLOCK_SIZE); std::copy_n(str, copyLen, data); length copyLen; if (copyLen BLOCK_SIZE) { std::fill(data copyLen, data BLOCK_SIZE, \0); } } };关键点解析static const int BLOCK_SIZE 4; 将块大小定义为静态常量。选择4是为了演示方便在实际应用中8或16可能是更好的选择以匹配内存对齐和缓存行大小。这里用4可以让链表示例更短便于调试和观察。length成员 这是必须的。因为最后一个节点可能未存满我们需要知道节点内有效字符的个数以正确判断字符串结尾和进行匹配。构造函数中的初始化 使用std::fill_n确保整个data数组被初始化为\0避免未初始化内存带来的不可预测行为。第二个构造函数 这是一个工具函数方便我们从一段字符直接创建节点在后续的字符串赋值或拼接操作中会很有用。注意这里没有使用new char[BLOCK_SIZE]动态分配data数组而是使用了固定大小的字符数组作为成员。这是因为BLOCK_SIZE是编译期常量作为成员数组分配在栈上当节点在栈上时或堆上当节点通过new在堆上创建时管理更简单内存碎片更少。如果BLOCK_SIZE需要运行时决定则必须使用动态数组。2.2 链式串类LinkedString的框架有了节点我们就可以构建串类了。LinkedString需要管理整个节点链表并提供基本的接口。class LinkedString { private: CharNode* head; // 链表头指针 CharNode* tail; // 链表尾指针方便追加操作 int totalLength; // 字符串总长度 // 内部工具函数释放所有节点内存 void clear() { CharNode* curr head; while (curr) { CharNode* toDelete curr; curr curr-next; delete toDelete; } head tail nullptr; totalLength 0; } // 内部工具函数从C风格字符串构建链表 void buildFromCString(const char* str) { clear(); if (!str) return; int len std::strlen(str); totalLength len; int pos 0; while (pos len) { int blockLen std::min(CharNode::BLOCK_SIZE, len - pos); CharNode* newNode new CharNode(str pos, blockLen); pos blockLen; if (!head) { head tail newNode; } else { tail-next newNode; tail newNode; } } } public: // 构造函数 LinkedString() : head(nullptr), tail(nullptr), totalLength(0) {} // 从C风格字符串构造 LinkedString(const char* str) : head(nullptr), tail(nullptr), totalLength(0) { buildFromCString(str); } // 拷贝构造函数深拷贝 LinkedString(const LinkedString other) : head(nullptr), tail(nullptr), totalLength(0) { *this other; // 利用赋值运算符重载 } // 析构函数 ~LinkedString() { clear(); } // 赋值运算符重载 LinkedString operator(const LinkedString other) { if (this other) return *this; // 防止自赋值 clear(); if (other.head) { CharNode* otherCurr other.head; CharNode* prevNewNode nullptr; while (otherCurr) { CharNode* newNode new CharNode(); std::copy_n(otherCurr-data, CharNode::BLOCK_SIZE, newNode-data); newNode-length otherCurr-length; newNode-next nullptr; if (!head) { head newNode; } else { prevNewNode-next newNode; } prevNewNode newNode; otherCurr otherCurr-next; } tail prevNewNode; totalLength other.totalLength; } return *this; } // 获取字符串总长度 int length() const { return totalLength; } // 判断是否为空 bool empty() const { return totalLength 0; } // 转换为C风格字符串动态分配内存调用者需负责释放 char* c_str() const { if (totalLength 0) { char* result new char[1]; result[0] \0; return result; } char* result new char[totalLength 1]; int idx 0; CharNode* curr head; while (curr) { for (int i 0; i curr-length; i) { result[idx] curr-data[i]; } curr curr-next; } result[totalLength] \0; return result; } // 简单匹配算法将在下一章实现 int find(const LinkedString pattern) const; // 为了方便测试添加一个追加字符的函数非核心但有用 void append(char ch) { // 如果尾节点已满或不存在需要创建新节点 if (!tail || tail-length CharNode::BLOCK_SIZE) { CharNode* newNode new CharNode(); if (!head) { head tail newNode; } else { tail-next newNode; tail newNode; } } // 将字符放入尾节点的当前空位 tail-data[tail-length] ch; tail-length; totalLength; } };设计思路与避坑指南head,tail,totalLength 这是管理链表的经典“三件套”。head用于遍历tail用于在末尾高效追加时间复杂度O(1)totalLength用于常数时间获取长度避免每次都要遍历链表统计。深拷贝的必要性 拷贝构造函数和赋值运算符必须实现深拷贝。默认的拷贝是浅拷贝只会复制指针导致两个LinkedString对象共享同一节点链表析构时会发生重复释放内存的致命错误。我们的实现中operator遍历原链表为每个节点创建一份全新的副本。内存管理clear()函数是内存安全的核心。在析构函数、赋值前、以及重新构建时都必须调用它来释放旧内存防止内存泄漏。这是C手动管理内存的经典模式。c_str()的职责 这个函数动态分配了new char[totalLength 1]的内存来返回一个连续的C字符串。调用者必须使用delete[]来释放这块内存。这是一种常见的妥协因为链式结构本身不提供连续存储。更好的工业级设计可能会返回一个std::string或使用智能指针但这里为了突出链式特性采用了传统方式。append函数 这是一个辅助函数方便我们逐步构建字符串。它体现了链式结构的优势当尾部节点有空间时插入是O(1)的只有当节点满了才需要分配新节点。3. 匹配算法实现在链式结构上模拟朴素匹配字符串匹配的经典算法很多如KMP、Boyer-Moore等。但对于学习数据结构而言朴素匹配算法Brute-Force是最直观的起点。它的思想很简单在主串中从每一个可能的位置开始尝试与模式串逐个字符比较直到完全匹配或发现不匹配。在顺序存储数组中这个算法用两个整数索引i和j循环即可。但在我们的链式存储中字符分散在各个节点的块里索引变得复杂。我们需要同时追踪当前在主串的哪个节点mainNode、节点内的哪个位置mainPos以及当前在模式串的哪个节点patNode、节点内的哪个位置patPos。3.1 算法步骤与双指针跳转逻辑算法原型如下在主串上从第一个字符开始作为本次匹配的起始点。记录下这个起始点的位置startNode,startPos。从该起始点开始同时遍历主串和模式串比较每一个字符。如果所有字符都相等则匹配成功返回起始点在整个主串中的线性索引位置。如果在某处字符不相等则主串的匹配起始点向后移动一个字符这可能需要跨节点然后回到步骤2重新开始。如果主串剩余长度已小于模式串长度则匹配失败返回-1。核心难点在于“移动一个字符”和“同时遍历”的指针操作。下面我们用代码来具体实现这个逻辑。int LinkedString::find(const LinkedString pattern) const { // 边界条件处理 if (pattern.empty()) return 0; // 空模式串约定为在位置0找到 if (this-empty() || pattern.length() this-length()) return -1; // 主串遍历指针记录当前匹配的起始位置 CharNode* mainStartNode head; int mainStartPos 0; int currentMainIndex 0; // 当前起始点对应的全局线性索引 // 外层循环移动主串的起始点 while (currentMainIndex this-totalLength - pattern.length()) { // 初始化本次匹配的遍历指针 CharNode* mainNode mainStartNode; int mainPos mainStartPos; CharNode* patNode pattern.head; int patPos 0; bool match true; // 内层循环逐个字符比较 while (patNode ! nullptr) { // 如果主串已遍历完但模式串还有剩余则不匹配理论上不会发生因为外层循环保证了长度 if (mainNode nullptr) { match false; break; } // 比较当前字符 if (mainNode-data[mainPos] ! patNode-data[patPos]) { match false; break; } // 指针向前移动一个字符主串和模式串 // 移动模式串指针 patPos; if (patPos patNode-length) { patNode patNode-next; patPos 0; } // 移动主串指针 mainPos; if (mainPos mainNode-length) { mainNode mainNode-next; mainPos 0; } } // 检查本次匹配结果 if (match) { return currentMainIndex; } // 匹配失败主串起始点向后移动一个字符 // 移动主串起始点指针 mainStartPos; currentMainIndex; if (mainStartPos mainStartNode-length) { mainStartNode mainStartNode-next; mainStartPos 0; // 注意如果mainStartNode移动到nullptr说明主串已遍历完外层循环条件会结束 } } // 所有起始点都尝试过未找到匹配 return -1; }3.2 指针移动的细节与边界处理这段代码是算法的核心有几个关键细节需要厘清线性索引currentMainIndex 我们维护了这个变量它代表了当前匹配起始点在整个主串中的位置从0开始。这是函数的返回值。我们通过移动mainStartNode和mainStartPos来间接更新它每次移动起始点currentMainIndex就加1。内层循环的终止条件while (patNode ! nullptr)。只要模式串的遍历指针patNode不是空就说明还有字符需要比较。当patNode移动到模式串链表末尾的下一个即nullptr时说明模式串的所有字符都已比较完毕且全部相等匹配成功。指针移动的“双检” 移动mainPos和patPos后需要立即检查是否超过了当前节点的有效长度(length)。如果超过就将节点指针指向下一个节点(next)并将节点内位置(pos)重置为0。这是链式结构遍历的通用模式。外层循环的条件currentMainIndex this-totalLength - pattern.length()。这是朴素算法的优化当主串剩余长度不足以容纳模式串时就没有必要再尝试了。这避免了不必要的比较。一个容易出错的点 在内层循环开始前我们将mainNode和mainPos设置为本次匹配的起始点(mainStartNode,mainStartPos)。但在内层循环中mainNode和mainPos是随着比较不断向前移动的。这不会影响外层的mainStartNode和mainStartPos它们只在本次匹配失败后才移动。这种“快慢指针”的思想在这里得到了应用。4. 从理论到实践完整源码、测试与性能分析理解了原理和算法现在让我们把所有的代码片段组合起来形成一个完整的、可编译运行的程序并通过测试来验证其正确性。4.1 完整项目源码将之前的所有代码整合到一个.cpp文件中。为了便于测试我们添加一个main函数。#include iostream #include cstring #include algorithm struct CharNode { static const int BLOCK_SIZE 4; char data[BLOCK_SIZE]; CharNode* next; int length; CharNode() : next(nullptr), length(0) { std::fill_n(data, BLOCK_SIZE, \0); } CharNode(const char* str, int len) : next(nullptr) { int copyLen std::min(len, BLOCK_SIZE); std::copy_n(str, copyLen, data); length copyLen; if (copyLen BLOCK_SIZE) { std::fill(data copyLen, data BLOCK_SIZE, \0); } } }; class LinkedString { private: CharNode* head; CharNode* tail; int totalLength; void clear() { CharNode* curr head; while (curr) { CharNode* toDelete curr; curr curr-next; delete toDelete; } head tail nullptr; totalLength 0; } void buildFromCString(const char* str) { clear(); if (!str) return; int len std::strlen(str); totalLength len; int pos 0; while (pos len) { int blockLen std::min(CharNode::BLOCK_SIZE, len - pos); CharNode* newNode new CharNode(str pos, blockLen); pos blockLen; if (!head) { head tail newNode; } else { tail-next newNode; tail newNode; } } } public: LinkedString() : head(nullptr), tail(nullptr), totalLength(0) {} LinkedString(const char* str) : head(nullptr), tail(nullptr), totalLength(0) { buildFromCString(str); } LinkedString(const LinkedString other) : head(nullptr), tail(nullptr), totalLength(0) { *this other; } ~LinkedString() { clear(); } LinkedString operator(const LinkedString other) { if (this other) return *this; clear(); if (other.head) { CharNode* otherCurr other.head; CharNode* prevNewNode nullptr; while (otherCurr) { CharNode* newNode new CharNode(); std::copy_n(otherCurr-data, CharNode::BLOCK_SIZE, newNode-data); newNode-length otherCurr-length; newNode-next nullptr; if (!head) { head newNode; } else { prevNewNode-next newNode; } prevNewNode newNode; otherCurr otherCurr-next; } tail prevNewNode; totalLength other.totalLength; } return *this; } int length() const { return totalLength; } bool empty() const { return totalLength 0; } char* c_str() const { if (totalLength 0) { char* result new char[1]; result[0] \0; return result; } char* result new char[totalLength 1]; int idx 0; CharNode* curr head; while (curr) { for (int i 0; i curr-length; i) { result[idx] curr-data[i]; } curr curr-next; } result[totalLength] \0; return result; } void append(char ch) { if (!tail || tail-length CharNode::BLOCK_SIZE) { CharNode* newNode new CharNode(); if (!head) { head tail newNode; } else { tail-next newNode; tail newNode; } } tail-data[tail-length] ch; tail-length; totalLength; } int find(const LinkedString pattern) const { if (pattern.empty()) return 0; if (this-empty() || pattern.length() this-length()) return -1; CharNode* mainStartNode head; int mainStartPos 0; int currentMainIndex 0; while (currentMainIndex this-totalLength - pattern.length()) { CharNode* mainNode mainStartNode; int mainPos mainStartPos; CharNode* patNode pattern.head; int patPos 0; bool match true; while (patNode ! nullptr) { if (mainNode nullptr) { match false; break; } if (mainNode-data[mainPos] ! patNode-data[patPos]) { match false; break; } patPos; if (patPos patNode-length) { patNode patNode-next; patPos 0; } mainPos; if (mainPos mainNode-length) { mainNode mainNode-next; mainPos 0; } } if (match) { return currentMainIndex; } mainStartPos; currentMainIndex; if (mainStartPos mainStartNode-length) { mainStartNode mainStartNode-next; mainStartPos 0; } } return -1; } }; // 测试函数 void testLinkedString() { std::cout 测试链式串基本功能 std::endl; // 测试1: 构造与转换 LinkedString str1(Hello, World!); char* cstr1 str1.c_str(); std::cout str1: cstr1 (长度: str1.length() ) std::endl; delete[] cstr1; // 测试2: 追加功能 LinkedString str2; str2.append(H); str2.append(i); str2.append(!); char* cstr2 str2.c_str(); std::cout str2: cstr2 std::endl; delete[] cstr2; // 测试3: 拷贝构造与赋值 LinkedString str3 str1; char* cstr3 str3.c_str(); std::cout str3(拷贝自str1): cstr3 std::endl; delete[] cstr3; LinkedString str4; str4 str2; char* cstr4 str4.c_str(); std::cout str4(赋值自str2): cstr4 std::endl; delete[] cstr4; std::cout \n 测试匹配算法 std::endl; // 测试4: 简单匹配 LinkedString mainStr(ABABABABC); LinkedString pattern1(ABC); int pos1 mainStr.find(pattern1); std::cout 在主串 \; char* mainCStr mainStr.c_str(); std::cout mainCStr; delete[] mainCStr; std::cout \ 中查找模式串 \; char* pat1CStr pattern1.c_str(); std::cout pat1CStr; delete[] pat1CStr; std::cout \, 位置: pos1 (预期: 6) std::endl; // 测试5: 头部匹配 LinkedString pattern2(AB); int pos2 mainStr.find(pattern2); std::cout 查找模式串 \; char* pat2CStr pattern2.c_str(); std::cout pat2CStr; delete[] pat2CStr; std::cout \, 位置: pos2 (预期: 0) std::endl; // 测试6: 不存在匹配 LinkedString pattern3(XYZ); int pos3 mainStr.find(pattern3); std::cout 查找模式串 \; char* pat3CStr pattern3.c_str(); std::cout pat3CStr; delete[] pat3CStr; std::cout \, 位置: pos3 (预期: -1) std::endl; // 测试7: 空串和长串 LinkedString emptyStr(); LinkedString pattern4(); int pos4 mainStr.find(emptyStr); // 空模式串 int pos5 emptyStr.find(pattern4); // 空主串找空模式 int pos6 emptyStr.find(pattern1); // 空主串找非空模式 std::cout 空模式串匹配结果: pos4 (预期: 0) std::endl; std::cout 空主串找空模式: pos5 (预期: 0) std::endl; std::cout 空主串找非空模式: pos6 (预期: -1) std::endl; // 测试8: 跨节点匹配验证链式结构 // 构造一个字符串确保模式串跨越节点边界 LinkedString complexMain; for(int i0; i10; i) { complexMain.append(A (i % 3)); // 生成ABCABCABCA } LinkedString complexPattern(CAB); // 这个模式串应该能在中间找到 int pos7 complexMain.find(complexPattern); std::cout \n跨节点匹配测试: std::endl; char* cmc complexMain.c_str(); std::cout 主串: cmc; delete[] cmc; char* cpc complexPattern.c_str(); std::cout , 模式串: cpc; delete[] cpc; std::cout , 位置: pos7 (预期: 2) std::endl; } int main() { testLinkedString(); return 0; }4.2 编译与运行测试你可以使用任何C编译器来编译运行这段代码。例如在Linux/macOS的终端或Windows的VS Code中配置好GCC/MinGW环境后g -stdc11 -o linked_string linked_string.cpp ./linked_string如果一切正确你将看到类似以下的输出 测试链式串基本功能 str1: Hello, World! (长度: 13) str2: Hi! str3(拷贝自str1): Hello, World! str4(赋值自str2): Hi! 测试匹配算法 在主串 ABABABABC 中查找模式串 ABC, 位置: 6 (预期: 6) 查找模式串 AB, 位置: 0 (预期: 0) 查找模式串 XYZ, 位置: -1 (预期: -1) 空模式串匹配结果: 0 (预期: 0) 空主串找空模式: 0 (预期: 0) 空主串找非空模式: -1 (预期: -1) 跨节点匹配测试: 主串: ABCABCABCA, 模式串: CAB, 位置: 2 (预期: 2)所有测试用例通过证明我们的链式串和匹配算法实现基本正确。4.3 性能分析与思考实现完成后我们必须理性地分析这个设计的优缺点这是从“实现功能”到“理解本质”的关键一步。时间复杂度分析朴素匹配算法 在最坏情况下对于长度为n的主串和长度为m的模式串需要比较约(n-m1) * m次字符。时间复杂度为O(n*m)。我们的链式实现并没有改变这个理论复杂度。指针操作开销 每次字符比较我们都需要通过节点指针和节点内索引来访问字符这比数组的直接索引访问str[i]多了一次或两次内存解引用常数时间更大。此外指针移动时的边界检查if (pos length)也增加了开销。内存访问模式 链式存储是非连续的。当字符串较长时节点分散在内存各处对CPU缓存Cache不友好。顺序遍历链表可能导致大量的缓存未命中Cache Miss而顺序存储的数组则具有良好的空间局部性可以被高效地预取到缓存中。这是链式结构在遍历和匹配操作上性能低于顺序结构的最主要原因。空间复杂度分析每个CharNode除了存储有效字符还有next指针和length的 overhead。我们设定的BLOCK_SIZE4假设在64位系统上指针8字节int4字节加上4字节字符数组和可能的内存对齐填充一个节点的实际内存开销远大于4字节。内存利用率较低。提高BLOCK_SIZE例如到16或32可以显著提高内存利用率减少节点数量从而改善缓存局部性但会使得短字符串的节点内部产生浪费并且在节点内插入/删除字符时如果支持该操作移动数据的开销变大。适用场景反思这个链式串的实现其教育意义远大于实用价值。它完美地展示了链表数据结构的典型操作 插入、遍历、深拷贝、内存管理。算法与数据结构的适配 如何在非连续存储上实现经典的字符串匹配算法。指针操作的复杂性 处理多级指针节点指针和节点内索引是C/C底层编程的必备技能。在实际项目中除非有极特殊的、需要频繁在字符串中间插入删除大段文本的场景如某些特定文本编辑器否则std::string或其类似物如QString,folly::fbstring都是更优的选择。它们经过高度优化综合了动态数组、短字符串优化SSO等技术在绝大多数情况下都提供了最佳的性能。5. 常见问题与深度扩展探讨在实现和测试过程中你可能会遇到一些问题或者对这个设计有进一步的思考。这里我总结几个关键点和扩展方向。5.1 调试与问题排查技巧内存泄漏检测 这是手动管理内存最容易出错的地方。确保每一个new都有对应的delete。在clear()和析构函数中仔细检查遍历删除的逻辑。可以使用工具如Valgrind(Linux) 或Dr. Memory(Windows) 来检测程序运行后是否有内存泄漏。空指针解引用 在find函数的内层循环中我们检查了if (mainNode nullptr)。这是一个重要的防御性编程。尽管外层循环理论上保证了主串剩余长度足够但在指针移动过程中如果链表连接有误比如某个节点的next指针意外为nullptr而length却不为0这个检查能防止程序崩溃。边界条件测试 我们的测试用例覆盖了空串、头部匹配、尾部匹配、跨节点匹配、无匹配等情况。务必重视边界测试这是算法鲁棒性的保证。特别是对于append函数当tail为nullptr或tail-length BLOCK_SIZE时的处理是否正确。可视化调试 对于链表问题在纸上或白板上画出节点的链接图标出head,tail,next指针以及每个节点的data和length然后单步执行代码手动更新指针状态。这是理解链表操作最有效的方法。5.2 功能扩展与优化思路如果你学有余力可以尝试基于这个基础框架进行扩展这能极大加深理解实现更多的字符串操作insert(int pos, const LinkedString str): 在指定位置插入另一个串。这需要先找到位置对应的节点和节点内偏移然后可能涉及拆分节点、创建新节点、重新连接链表是链表操作的集大成者。erase(int pos, int count): 删除从指定位置开始的若干个字符。同样涉及节点拆分、合并和内存释放。substr(int pos, int count): 获取子串。需要创建新的LinkedString对象并从原串对应位置开始复制节点数据。实现更高效的匹配算法KMP算法 这是面试常客。在链式结构上实现KMP的难点在于计算next数组时模式串是链式存储在实际匹配时主串和模式串的“回退”逻辑需要适配我们的双指针节点节点内位置模型。这是一个绝佳的挑战。Boyer-Moore算法 思路是从后向前匹配并利用“坏字符”和“好后缀”规则跳过不可能匹配的位置。在链式结构上从后向前遍历本身就很困难除非实现双向链表因此实现起来更具挑战性。优化数据结构设计双向链表 将CharNode增加一个prev指针可以支持反向遍历和更高效的尾部附近操作但内存开销更大。块大小自适应 能否让BLOCK_SIZE不固定例如第一个节点存8个字符后续节点根据实际情况动态分配大小这需要更复杂的内存管理策略。实现迭代器 为LinkedString设计一个迭代器类重载,*,等运算符。这样你就可以使用for (auto it str.begin(); it ! str.end(); it)这样的标准C循环来遍历字符串极大地提升代码的优雅性和可复用性。迭代器内部需要封装当前节点和节点内位置这两个状态。5.3 从链式串到更广阔的数据结构这个项目虽然围绕“串”展开但其核心是链表。链式串可以看作是一种“块状链表”的特例。理解它就为理解以下更复杂的数据结构打下了坚实基础广义表 链表节点不仅可以存储字符还可以存储指向另一个子表的指针形成递归结构。邻接表 在图论中用于表示稀疏图每个顶点对应一个链表存储其所有邻接顶点。文件系统的块链 早期文件系统如FAT使用链表来记录文件占用的磁盘块号。区块链 每个区块包含数据和指向前一个区块的哈希指针形成一条不可篡改的链。当你下次看到这些结构时你会意识到它们和我们刚刚实现的LinkedString在“通过指针将离散单元组织起来”这个核心思想上是相通的。通过这个从零实现的过程指针、内存、节点、链接这些概念已经从书本上的图例变成了你指尖下确确实实的代码逻辑。这才是本项目最大的价值所在。