串数据结构详解：存储结构、运算实现与KMP算法实战

写在前头串这章看着简单考起来全是细节。很多人在链表和树上面花了大把时间结果在字符串上栽了跟头——其实不是不懂操作而是没把类型定义存储结构运算这三层关系理清楚。这篇文章就拿串的类型定义、存储结构及其运算当主线把原理、代码和那些踩过的坑一次讲透。1. 先搞清楚串到底是个啥东西1.1 从逻辑结构理解串的定义串String就是零个或多个字符组成的有限序列一般记作S a1a2...an其中 S 是串名n 叫串长。n 等于 0 的时候是空串记作。这个定义看起来比线性表多了个字符约束但恰恰是这个约束决定了后面所有存储结构的选择逻辑。字符在计算机里本质是整数ASCII 或 Unicode 编码所以串可以看作元素类型受限的线性表——但实际操作上完全不是一回事因为字符串的赋值、比较、拼接、子串提取和模式匹配都是连续内存操作直接决定性能瓶颈。还需要区分三个概念串、子串和主串。子串是串中任意连续字符组成的子序列比如ell是hello的子串而hlo不是因为不连续。这个连续二字就是后面匹配算法的核心约束之一。另外还要区分串变量和串常量。串常量是用双引号括起来的字符序列比如123串变量则是赋值后的内存对象。这个区别在 C 语言里体现最明显——123是静态存储区的 const char*而你定义的char[] arr 123;是栈上数组它们的内存行为和生命周期完全不同。1.2 串的基本操作到底有哪些数据结构的类型定义不只是给出一组字段更重要的是确定在这个类型上允许哪些操作。串的 ADT抽象数据类型一般包含这些操作操作作用关键点StrAssign(T, chars)把 chars 赋值给 T注意覆盖旧值StrCopy(T, S)把 S 复制给 T深拷贝还是浅拷贝要看存储StrEmpty(S)判断 S 是否空串实际是判断长度是否为 0StrCompare(S, T)比较 S 和 T 大小先比长度还是先比内容StrLength(S)返回串长取决于存储方式定义ClearString(S)清空串注意释放内存Concat(T, S1, S2)连接两个串常用但容易溢出SubString(Sub, S, pos, len)取子串参数合法性检验Index(S, T, pos)模式匹配定位核心算法所在Replace(S, T, V)替换子串可能改变串长StrInsert(S, pos, T)插入子串移动大量字符StrDelete(S, pos, len)删除子串同上很多初学者一上来就钻进 KMP 算法里以为串这章考的就是匹配。实际上大部分考试和面试的基础题反而集中在接续部分——比如定长顺序存储里 Concat 之后怎么处理截断、SubString 的 pos 参数越界怎么报错、Index 的返回位置是从 1 开始还是从 0 开始。这些细节才是区分会背书和真懂的分水岭。2. 三种存储结构怎么选定长、堆分配、块链2.1 定长顺序存储简单但自带枷锁定长顺序存储就是用一段固定长度的字符数组来存放串C 语言里最直观的结构体长这样#define MAXLEN 255 typedef struct { char ch[MAXLEN 1]; // 多留一个位置放 \0 或作下标统一 int length; // 当前串长 } SString;为什么要MAXLEN 1这里有一个历史包袱和一个实用性考量。历史包袱是 C 字符串以\0结尾如果定义一个char ch[MAXLEN]那么实际能存的字符最多是MAXLEN - 1个最后一个位置要给结束符。如果不想要\0这套逻辑就多开一个位置、用独立的length字段管理长度那么实际存储上限就是MAXLEN下标也从 1 开始更自然——这是教材里传统定义法的思路。定长存储最大的问题就是长度不可变。你定义 255就只能存 255 个字符。连接两个串的时候尤其危险Status Concat(SString *T, SString S1, SString S2) { int i; if (S1.length S2.length MAXLEN) { // 未截断完整连接 for (i 1; i S1.length; i) T-ch[i] S1.ch[i]; for (i 1; i S2.length; i) T-ch[S1.length i] S2.ch[i]; T-length S1.length S2.length; return OK; } else if (S1.length MAXLEN) { // 截断S2 只能存一部分 for (i 1; i S1.length; i) T-ch[i] S1.ch[i]; for (i 1; i MAXLEN - S1.length; i) T-ch[S1.length i] S2.ch[i]; T-length MAXLEN; return TRUNCATE; // 返回截断标志 } else { // S1 本身就满了S2 完全装不下 T-length 0; return ERROR; } }这段代码里最容易被忽略的是TRUNCATE这个返回值。很多人的实现里要么直接丢弃这个状态要么用了一个不恰当的ERROR。实际业务中串被截断往往是灾难性的——比如拼 SQL、拼文件路径截断了就是另一条语句。定长存储逐步被淘汰不是因为速度慢而是这种半成功半失败的状态让上层逻辑很难处理。另外注意下标问题这里我用ch[i]从 1 开始是因为length字段本身不包含位置 0。如果你从 0 开始存那么length和下标的关系是str[length - 1]才是最后一个字符。很多人在写 SubString 时出越界问题根源就在这里——不同教科书下标习惯不一致。2.2 堆分配存储灵活的主流选择堆分配存储的核心思路是串的存储空间不再固定死而是按需用malloc和free动态分配。结构体非常简单typedef struct { char *ch; // 指向动态分配的存储区 int length; // 串长 } HString;关键操作是赋值时的空间管理逻辑。我们拿 StrAssign 举例完整写出来是这样的Status StrAssign(HString *T, const char *chars) { int len strlen(chars); if (T-ch) free(T-ch); // 先释放旧空间 T-ch (char *)malloc(len * sizeof(char)); if (!T-ch) return ERROR; // 分配失败 for (int i 0; i len; i) T-ch[i] chars[i]; T-length len; return OK; }最容易被忽略的两点第一if (T-ch) free(T-ch);不是可选的如果没有这个判断和释放连续两次 StrAssign 就会内存泄漏。第二这里不拷贝\0因为length已经明确表示了串长不需要用结束符来判断边界。这里我给一个从业者的直接建议代码里一定要先释放旧空间再分配新空间否则第二次赋值时原来那块内存根本没有指针指向它——这就是经典的内存泄漏场景。面试官问堆分配的优势不只是可以存任意长度的串还包括可以反复赋值而不需要预先知道最大长度但前提是你要把释放逻辑写对。和定长存储相比堆分配的空间效率由实际内容决定不存在定义 1KB 但只用了 30 字节的浪费。但代价是 malloc/free 本身的系统开销以及那 4 或 8 字节的指针加 4 字节的 length 字段。对中小规模字符串来说完全值得。2.3 块链存储空间换时间的边角料块链存储是链表在串上的应用。每个节点可以存 1~N 个字符外加一个 next 指针#define CHUNKSIZE 4 typedef struct Chunk { char ch[CHUNKSIZE]; // 一块内存存 4 个字符 struct Chunk *next; // 下一块 } Chunk; typedef struct { Chunk *head; // 头指针 Chunk *tail; // 尾指针 int length; // 总串长 } LString;注意这里同时存了 head 和 tail。为什么要 tail因为串的很多操作比如 Concat需要快速找到链尾。如果没有 tail连接一个串要遍历整条链 O(n)有了 tail 就是 O(1)。链表里加尾指针是常见优化尤其适合尾部追加频繁的串操作场景。还有一个指标叫存储密度存储密度 数据本身占用的存储量 / 实际分配的存储量一个节点存 4 个字符、4 字节指针假设 int 4 字节、char 1 字节那么存储密度是 4 / (4 指针大小)。1 字节字符加 4 字节指针密度只有 4/(44) 0.5——一半空间都拿来存指针了。CHUNKSIZE 越大密度越高但插入删除的代价也越大因为每个节点持有的字符多操作范围扩大。这是个经典的时间空间取舍。实际开发中你几乎不会用块链来存字符串因为 O(n) 的随机访问实在难接受——字符串的核心操作之一是取第 i 个字符链表只能遍历。但块链的思路在文件系统、大对象存储里有价值把大数据切块链起来每块带校验信息断点续传、随机分块读都有用。所以弄清它不只是为了考试填空而是理解分块思想的第一站。有些教材会说块链还有一个变种每个节点只存 1 个字符此时存储密度最低但操作最灵活。实际上这就是普通的字符链表基本只能当作业题没有实用价值。3. 运算实操落地从最基本的函数到 KMP3.1 基本运算的代码实现与边界处理我在这里统一用堆分配结构体HString展开因为定长与块链的运算本质相同区别只在存储访问方式。先看最核心的取子串操作这是最容易写错的一个Status SubString(HString *Sub, HString S, int pos, int len) { if (pos 1 || pos S.length || len 0 || pos len - 1 S.length) { return ERROR; } if (Sub-ch) free(Sub-ch); if (len 0) { // 空子串 Sub-ch NULL; Sub-length 0; return OK; } Sub-ch (char *)malloc(len * sizeof(char)); if (!Sub-ch) return ERROR; for (int i 0; i len; i) { Sub-ch[i] S.ch[pos - 1 i]; // pos 是 1 起始数组是 0 起始 } Sub-length len; return OK; }重点是pos len - 1 S.length这个条件不是随便写的。举例验证S 长度为 10pos8len3那么要取的是第 8、9、10 个字符最后一个位置是 10pos len - 1 8 3 - 1 10没越界合法。如果 pos9len29 2 - 1 10仍然合法。如果 pos9len39 3 - 1 11 10越界报错。这个公式用数学语言描述就是子串在 S 中起始于 pos、长度为 len最后一个字符下标是 (pos-1) (len-1) pos len - 2数组 0 起始转换成串位置1 起始就是 pos len - 1。这里是对位置从 1 开始还是从 0 开始极度敏感的典型场景。如果你把 pos 定义成 0 起始条件就会变成pos len S.length。两种写法都对错的是混着用。再来看比较操作 StrCompare。比较规则不是先比长度而是先比第一个不同的字符字符小者所在的串小如果所有对应字符都相同则长度短者小如果完全一样则相等。这个规则和 C 语言的strcmp完全一致。也就是说在实现 StrCompare 时你不需要先判断长度而是先逐字符比较遇到不同即返回大小关系最后用length1 - length2决定Status StrCompare(HString S, HString T) { for (int i 0; i S.length i T.length; i) { if (S.ch[i] ! T.ch[i]) return S.ch[i] - T.ch[i]; } return S.length - T.length; }这里返回的可以是负数、0 或正数省去了多余的分类讨论。这个写法也是实际开发里 strcmp 的标准实现思路。3.2 朴素模式匹配先从最朴素的思路开始定位操作 Index通俗讲就是找子串。朴素匹配的思路超级简单从主串的每个位置出发依次尝试匹配子串的每个字符直到完全匹配或主串被遍历完。int Index(HString S, HString T, int pos) { // pos 是主串中开始匹配的位置1 起始 if (pos 1 || pos S.length) return 0; if (T.length 0) return 0; // 空串按约定返回 0表示不存在或不匹配 int i pos; // 主串当前位置 int j 1; // 子串当前位置 while (i S.length j T.length) { if (S.ch[i - 1] T.ch[j - 1]) { i; j; } else { i i - j 2; // 主串回溯到下一个位置 j 1; // 子串从头开始 } } if (j T.length) return i - T.length; // 子串匹配成功 return 0; }最让人懵的就是i i - j 2这个回溯公式。我们拆解一下当某个字符不匹配时主串当前处于位置 i而子串已经匹配了 j-1 个字符。这次匹配的起点是i - (j - 1)为了从下一个位置重新开始尝试所以新起点应该是i - (j - 1) 1 i - j 2。举个例子S helloT ll第一轮 i1 时h ! lj 从 1 变 1那么新 i 就是1 - 1 2 2从第 2 个字符e开始继续。这个公式是朴素匹配里最容易写错的地方背下来不如理解推导过程。朴素匹配的时间复杂度是 O(n*m)n 是主串长度m 是模式串长度。最坏情况下比如主串是 aaaaaaaaab模式串是 aaab每次都在最后一个字符失败整体近乎 O(n*m)。对小型文本足够但对大文本显然不行。3.3 KMP 算法next 数组到底在算什么KMP 的核心不是优化匹配过程而是优化失败后主串回溯的距离。朴素匹配失败时i 要回退到本次起点的下一个位置KMP 的改进是让 i 尽量不动只让 j 回退到某个位置利用已经匹配过的信息跳过一些必然失败的比较。next 数组的定义不复杂但极易混淆。标准的定义是对于模式串 Tnext[j]表示当第 j 个字符失配时j 应该回退到的位置。更本质的说法next[j]等于 T[1..j-1] 这个子串中最长的相等前缀后缀的长度加 1。手动求解 next[1] 到 next[5] 时一般这样处理j123456模式串ababaanext[j]011234解释一下 next[4] 为什么是 2T[1..3] aba它的前缀有 a、ab后缀有 ba、a最长公共前后缀是 a长度是 1所以 next[4] 1 1 2。next[6] 的来源T[1..5] ababa最长公共前后缀是 aba长度是 3所以 next[6] 3 1 4。有些教材把 next 数组定义为最长相等前缀后缀的长度不加 1也没有那个特殊的 next[1] 0于是就出现了两个版本的 next。考试和面试时务必先确认定义否则直接套算法会差一位。KMP 匹配的核心代码和朴素匹配的差别只在一行int Index_KMP(HString S, HString T, int pos) { int i pos, j 1; while (i S.length j T.length) { if (j 0 || S.ch[i - 1] T.ch[j - 1]) { i; j; } else { j next[j]; // i 不动j 跳转 } } if (j T.length) return i - T.length; return 0; }注意到多了j 0这个分支当 next[j] 0 时j 被置为 0下一次循环 j 为 0此时无法比较 S.ch[i-1] 和 T.ch[-1]所以必须把 j 加回 1、i 前进一步。这是 KMP 实现里很刁钻的细节。next 数组的递推求法比手动求解重要得多因为考试不一定只考 next 求值还会考为什么这个递推是对的。递推代码void get_next(HString T, int next[]) { int i 1, j 0; next[1] 0; while (i T.length) { if (j 0 || T.ch[i] T.ch[j]) { i; j; next[i] j; } else { j next[j]; } } }这里有个让很多人绕进去的点T.ch[i] T.ch[j]中 i 和 j 的含义。i 不是主串下标而是模式串本次要计算的扩展位置j 是已匹配的前缀长度。如果 T.ch[i] T.ch[j]说明前缀可以继续延长一位于是 next[i1] j1。如果不等j 回退到 next[j]继续对比直到 j 为 0说明没有公共前后缀next[i1] 1。nextval 是 next 的优化版把T.ch[i] T.ch[next[i]]的情况压缩掉避免无效跳转。对 aaaaaaab 这种重复串next 数组会退化成和朴素匹配差不多的效果nextval 才能真正体现 KMP 的优势。注意区分nextval 的求法是在 next 求出之后再扫一遍如果 T.ch[i] T.ch[next[i]]则 nextval[i] nextval[next[i]]否则 nextval[i] next[i]。一个实际测试感受对模式串 ababaa朴素匹配在某些主串上每一步都几乎白走KMP 能直接利用 next 跳过大量位置。数据量大了之后这个差距不是常数级别的而是多项式级别的——O(n*m) 对比 O(nm)当 m 和 n 都在十万量级时朴素匹配基本跑不动。4. 实战中的坑与排查技巧4.1 常见问题速查表我在实际写代码和改别人代码的过程中总结出串运算里最常出问题的几个点放在一个表里方便你排查症状可能原因排查方向取子串结果乱码pos 和数组下标的换算混用确认 pos 是 1 起始还是 0 起始SubString 内部统一用pos - 1连接后长度不对忘了更新 length 或没有释放旧空间Concat 里必须重算 lengthStrAssign 必须先 free赋值后原串数据被改浅拷贝共享内存确认结构体的 ch 指针是否被多个实例共享赋值要深拷贝KMP 死循环next 数组中 j 没有回退到 0检查 j0 分支是否缺失以及 get_next 的边界条件字符串比较结果反了返回值符号理解错误记住返回值小于 0 说明第一个串小内存泄漏StrAssign 连续调用没先释放旧空间每个赋值函数开头先if (T-ch) free(T-ch)模式串为空时报错未处理 T.length 0约定空串匹配返回 0 或不匹配4.2 字节、字符与编码的隐藏陷阱教材里讲串的时候默认一个字符占一个字节用 ASCII。现实中这个假设几乎不成立——UTF-8 编码下中文字符占 3 个字节emoji 占 4 个字节串长到底以字节计还是以字符计接口必须明确。比如 UTF-8 下中的长度如果是 3 字节SubString 按字节截断可能把一个多字节字符劈成两半产生非法 UTF-8 序列显示成乱码。有的语言像 Python 的len()返回字符数但文件流读取按字节两者很容易搞混。处理建议是如果在存储层用字节计长所有操作都以字节为单位保持一致性字符边界问题交给编码层处理。如果要在字符层面操作需要先把字节流解码成字符数组。不要试图在字节数组里直接数中文字符的个数然后猜边界——那是踩坑的开始。4.3 我在实际项目中踩过的几个坑第一个坑是 Concat 拼接动态字符串时的性能问题。循环里反复调用 Concat每次都重新 malloc、free、拷贝量一上来就卡顿。后来我改成先计算总长度、一次性分配、两次拷贝性能提升非常明显。这不是算法的问题是工程习惯问题。第二个坑是堆分配里忘记处理T-ch NULL的情况。有些函数把 ch NULL 当作空串处理但 S.length 又是 0看起来没问题。可是当你要对空串做 SubString 时Sub-ch被 malloc(0) 或者直接赋值 NULL后续 free 的操作要另外判断。干脆约定空串的 ch 永远是 NULL长度永远是 0所有操作都先查 length。第三个坑很细节在读外部配置的时候字符串是null和值为 NULL 不是一回事。前者是一个长度为 4 的串后者是空指针或空串。很多线上问题都是因为没有区分这两个状态造成配置文件解析时把null当成没有字段来处理。建议在数据结构的操作上去安全地处理这类情况而不只是靠调用方约定。4.4 几个实操经验分享自己写串运算有几个习惯我建议早点养成。下标从 1 开始就全程 1 开始从 0 开始就全程 0 开始不要在同一个函数里混用。统一之后pos、length 和数组下标之间的关系可以用一个公式表达出错概率直线下降。凡是修改串内容的地方先确认原来内存是否要释放再确认新内存分配是否成功。顺序是分配新空间、检查 NULL、拷贝数据、更新 length、最后释放旧空间。这个顺序能避免The process was terminated due to a problem这类崩溃。拿着别人封装好的串库用也要关注 API 的边界约定。返回值代表什么、下标从几开始、有没有截断行为这些信息在文档里写得再短也要看完再动工。尤其注意Index这种函数的返回约定不同库的返回规则差异很大。KMP 的 next 数组求法多练几遍。不只是求 next还要知道 nextval 相比 next 到底优化了什么场景。面试挂在这一块的人很多不是因为算法难而是定义版本太多、混淆了概念。动手写代码时我是先写一个求 next 的辅助函数再把具体模式串摆到数组里逐步调试遇到问题打印 i、j 和 next[j] 的值——比瞎猜快得多。最后分享一个顺手的测试小技巧自己实现完 Index 或 KMP 之后不要只测匹配成功的情况。用模式串比主串长的情况测、用空串测、用模式串开头匹配但中段失配的情况测、用多个重叠匹配目标的情况测——比如主串是 abababa、模式串是 aba检查返回的位置是 1 而不是 3 或 5 的时候你就能快速判断匹配逻辑到底是从前往后找第一个还是有别的行为。这些边界用例才是代码里最容易埋雷的地方。