串、数组与广义表：从底层逻辑到工程实践

前几天一个准备秋招的学弟问我，说教材里《串、数组和广义表》这一章翻来覆去看了好几遍还是记不住，问我当初是怎么啃下来的。我说这一章其实最容易被忽略，但你去看各厂笔试和面试，很少有人直接问你“广义表是什么”，可串的模式匹配、二维数组的存储结构、数组指针和指针数组的区别，几乎每场都会变着法考。更关键的是，这三类结构在写真实业务代码时天天都在用：后端处理文本要搞敏感词过滤，数据分析绕不开多维数组的切片和矩阵运算，写解析器又离不开递归定义的树形结构。所以我今天换个角度，把串、数组和广义表放到一起讲，说清楚它们各自的脾气、互通的底层逻辑，以及这些年我在编码里亲手踩过的坑。

1. 串：一切文本处理的底层数据结构

很多人觉得串就是字符数组，没什么好学的。这个想法在应付考试时还能蒙混，一到实际项目就露馅了。串和字符数组的本质区别在于操作粒度：字符数组关心的是“每个格子存了什么”，串关心的是“连续一段字符的整体行为”。你要在一个长度为几百万的字符串里做子串查找，或者在用户输入里做敏感词替换，如果只会字符数组级别的操作，性能和正确性都很难保证。

串要学明白，重点是两块：存储结构怎么选，模式匹配怎么做。这两块学透了，后面看各语言字符串库的源码，基本就是看它们在这两个维度上做了哪些取舍。

1.1 存储结构怎么选：定长、堆分配、块链

教材里讲串的存储，一般给三种方案：定长顺序存储、堆分配存储、块链存储。我刚学的时候觉得这三种方案就是三个名词，背完就完事，直到自己写了一个需要频繁修改字符串的模块，才明白每一种方案背后都是一组实实在在的代价。

定长顺序存储，类似C语言里的char str[MAXSIZE]，长度一开始就固定死。优点是实现简单、访问快，缺点是“定长”两个字就是天花板，一旦字符串长度超过预设值，要么截断要么报错。我见过不少老系统里用定长结构存用户备注，存到一半内容被无声截断，排查半天才发现是这里出了问题。所以定长存储只适合那些长度上限明确、且不会变化的场景，比如固定长度的订单号。

堆分配存储是现在的主流思路，C语言里就是malloc一个动态大小的空间，用完了free；C++的std::string、Java的String底层虽各有优化，本质也是“运行时动态管理字符存储区”。好处是长度不再受限，坏处是要自己操心内存的分配和释放，以及扩容时的数据搬运。很多线上崩溃、内存泄漏，都是在这个环节出了问题。

块链存储是把字符串拆成若干块，每块存几个字符，再用链表串起来。它的价值在理论上：避免每个字符都背一个指针，提高存储密度。但你要是真去实现一次就知道，插入删除要在块间移动数据，访问某个下标的字符要沿着链表遍历，复杂度极高。现在工程里基本见不到了，我建议把它当成“理解存储密度”的练习题，别真用到生产代码里。

三种方案的选择逻辑可以总结成一句话：长度固定选定长，长度动态选堆分配，极端节省内存再考虑块链。工程上最常见的是堆分配，因为业务数据的长度几乎都是动态的。

1.2 模式匹配：朴素算法、KMP与真实工程的取舍

串里最经典的问题是模式匹配：在主串里找模式串第一次出现的位置。朴素算法很好理解，两个循环逐位比对，主串指针和模式串指针一起走，不匹配就回退。最坏情况比如主串是aaaaaaaaab，模式串是aaaab，每趟都要比到最后一个字符才失败，然后主串指针回退一格再来，时间复杂度退化到O(m*n)。

KMP算法解决的就是这个回退问题。它的核心是预处理模式串，生成一个next数组，记录“如果这一位失配，模式串指针应该跳到哪个位置”。因为主串指针永远不回退，整体复杂度降到O(m+n)。当年第一次自己手写next数组时，我花了一整个下午才捋明白，但只要捋明白一次，后面遇到各种“字符串匹配”变体题，思路都会清晰很多。

不过我要泼一盆冷水：真实工程里，KMP并没有把其他算法都干掉。Java的String.indexOf、Python的str.find在实现时都做了自己的优化，有的在朴素匹配基础上加字符跳跃，有的用BM算法的思路从后往前匹配，因为实际文本的匹配失败率很高，朴素加上跳跃优化往往比KMP更快。KMP更适合那些“匹配失败频繁、且模式串有大量重复前缀”的场景，比如DNA序列匹配、基因数据比对这类极端数据。

串处理还会遇到一类高频问题：回文串。判断一个字符串是不是回文，比如“level”“上海自来水来自海上”，最简单的做法是双指针从两端往中间走，遇到不匹配就返回false。这个思路看着简单，但很多人在边界处理上翻车，比如忘记跳过非字母数字字符，或者空字符串直接返回false。LeetCode 125题就是标准例子，建议亲手写一遍。

1.3 字符串处理的常见坑：初始化、返回值与编码

字符串相关的bug，我愿称之为“新手体验卡”。先说初始化。C语言里char s[] = "hello"和char *s = "hello"看起来一样，前者是数组，存在栈上或静态区，可以修改；后者是指针指向字符串字面量，在很多编译器里是只读的，你尝试s[0]='H'就可能段错误。C++里还有char s[][20]这种二维字符数组，第二维必须给，否则编译都过不去。std::string arr[] = {"hello","world"}这种初始化倒是方便，但要注意sizeof(arr)/sizeof(arr[0])在C++里用std::size更安全。

再一个是返回局部数组的坑。如果你在函数里写char buf[64];填了几行数据然后return buf;，跑起来就是一地鸡毛，因为buf是栈上的局部变量，函数一结束就被回收了，调用方拿到的是一个悬垂指针。正确做法是传入输出参数、使用堆分配，或者直接用std::string返回。

还有一个特别容易被忽略的：编码。UTF-8中文一个字符占3个字节，strlen返回的是字节数不是字符数。我见过有人用substr(0, 5)截取用户昵称，结果正好从中文中间切过去，字符串直接乱码。所以在处理多语言文本时，要么按码点操作，要么先用库函数做字符边界判断，别拿字节长度当字符长度。

2. 数组：从一维到多维的内存游戏

数组看着是三种结构里最老实的，其实它是最考验内存功底的一章。教科书里一句话“随机访问时间复杂度O(1)”，背后是“元素连续存放、定长寻址”这个前提。你一旦使用多维数组、动态数组或者指针数组，一个不小心，地址算错一个偏移，轻则读到垃圾值，重则直接越界崩溃。

我自己的感受是，数组题写不对，很多时候不是语法问题，而是没想清楚“这块内存到底长什么样”。所以这一章我打算从初始化、存储布局、动态化三个角度，把数组的“内存视角”讲透。

2.1 数组初始化的语言差异：静态、动态与默认值

数组初始化是个看着简单、细节很多的点。C语言里int a[5] = {1,2,3};，剩下的两个元素自动补0；但如果写int b[5];而不初始化，局部变量的内容是随机垃圾值。这会让很多从Python转过来的同学非常难受，因为Python里根本没有“未初始化”这个概念。

C++的std::vector<int> v(5, 0)会把5个元素全部置0，比原生数组安全。Java里int[] arr = new int[5]默认全0，但Integer[] arr = new Integer[5]默认全是null，给null元素做加减乘除直接空指针。Python的list是对象指针数组，存的不是原始int本身，而是指向int对象的引用，所以看起来“什么都能装”，代价是内存开销大、缓存不友好；要做真正的数值数组，就得用numpy的np.zeros((3,4))，那才是连续内存的数组。

我把几种典型初始化的行为整理成了一张表，面试前扫一眼很有用：

2.2 多维数组的存储顺序：行优先、列优先与指针纠缠

一维数组是线性内存，二维数组的存储就出现了路线分歧：到底是先存完一行再存下一行，还是先存完一列再存下一列。C和C++是行优先，按base + (i * 列数 + j) * sizeof(type)寻址a[i][j]。MATLAB是列优先，所以a(j,i)这种访问方式性能更好。numpy默认也是行优先，但创建时传order='F'就能按列优先布局。这个差异不只是学术问题，当你做矩阵乘法时，数据在内存里的排列顺序直接影响缓存命中率，进而影响性能好几倍。

多维数组和指针搅在一起，是C++里最容易让人怀疑人生的地方。int *p[3]和int (*p)[3]只差一个括号，含义天差地别：前者是“指针数组”，p是一个数组，里面存了3个int*；后者是“数组指针”，p是一个指针，指向一个长度为3的int数组。我面试别人的时候爱问这个，能一口说清楚的人，C语言功底基本不会差。

二维数组作为参数传函数时也有坑。int a[2][3]传给形参，第一维大小会被丢弃，函数里拿到的是int (*)[3]。所以在函数里sizeof(a)/sizeof(a[0][0])是不可靠的，必须额外传行数，或者用模板、std::vector。

再顺带提一个热门场景：numpy三维数组相乘。两个三维数组做np.matmul或@，规则是把最后两维当矩阵、前面的维度当batch并做广播。你要先确认形状能对上，比如(2,3,4)和(2,4,5)可以乘出(2,3,5)；如果batch维分别是2和1，也能广播。很多人报错ValueError: operands could not be broadcast together，就是因为没搞清楚广播的规则，看成“两个三维数组随便乘”了。

2.3 动态数组与数组的进阶应用：扩容、切片、树状数组

静态数组最大的问题是“不可变长”：计算机科学里很多问题的输入规模是运行时才确定的，所以所有主流语言都封装了动态数组。C++的std::vector、Java的ArrayList、Python的list，本质都一样：底层是一段连续内存，元素不够了就申请一块更大的，把旧数据搬过去。扩容加倍是常见的策略，所以平摊下来每次插入的复杂度还是O(1)。这也是为什么面试官爱问“vector的push_back均摊时间复杂度为什么是O(1)”——因为扩容不经常发生。

Python的数组切片也是动态数组的高频操作。arr[1:5]对普通list来说，会生成一个新list，拷贝元素；numpy的切片则默认返回原数组的视图，不拷贝数据。这个区别非常关键，很多人用numpy切片后修改值，发现原数组也变了，一脸懵。如果不想影响原数组，记得显式.copy()。

数组还能玩出很多高级形态。比如竞赛里常用的树状数组，就是拿一个普通数组抽象成“树状的前缀和结构”，用来快速做区间求和、单点更新，代码量比线段树小很多。它本质上是“数组+二进制索引”的组合，虽然名叫树状，底层仍然是那个连续数组。这类应用对初学者来说有点跳跃，但会让你深刻体会到：数组不只是“存数据的盒子”，它还可以承载各种各样的算法结构。

3. 广义表：递归思维的天花板

广义表是线性表的推广，它的定义一上来就带递归味道：广义表是n个元素的有限序列，每个元素可以是原子，也可以是一个广义表。很多人被这个定义绕晕，觉得这是教材发明出来为难人的。其实你每天都在和广义表打交道：JSON里一个对象的值可以是数字、字符串，也可以是一个嵌套的数组或对象，这就是广义表的思维模型。

说句实在话，广义表本身在工程里很少被直接实现成“广义表类”，但它的递归定义方式、存储方式和操作方式，是理解树、图、解析器、LISP的一把钥匙。我甚至觉得，如果你能把广义表的深度计算和复制逻辑吃透，后面学递归下降解析器会顺畅很多。

3.1 广义表的定义：原子、子表与递归结构

先看形式化定义。一个广义表记为LS = (a1, a2, ..., an)，其中每个ai可以是原子，也可以是一个广义表。比如L = (a, (b, c), d)，这个表里有三个元素：原子a、子表(b,c)、原子d。如果进一步(b,c)里b是原子，c也是原子，那整个结构的形状就像一棵深度为2的树。

广义表有两个非常基础的概念：表头和表尾。对非空的广义表，第一个元素叫表头，剩下的元素组成的表叫表尾。注意，表尾永远是一个广义表。比如L = (a, (b,c), d)，表头是a，表尾是((b,c), d)，它仍然是一个广义表，因为表尾必须用括号把剩余元素包起来。曾经有同学把表尾答成((b,c), d)还是((b,c),d)其实无所谓，但脑子里必须清楚它是一个子表，不是原子序列。

广义表的深度，定义为括号嵌套的最大层数。原子的深度是0，空表的深度是1，非空表的深度是1 + max(各元素深度)。所以L = (a, (b, c), d)的深度是2。计算深度是递归操作的入门题，也是面试里高频考的“手写递归”题目之一。

3.2 广义表的存储与经典操作：表头表尾、深度、复制

广义表的存储不能像普通线性表那样用一块连续空间，因为元素类型不一致：原子是一个小的数据节点，子表又是一个独立的广义表。常见的做法是用带tag的结点区分类型，我给出一个C风格的结构体示例：

typedef enum { ATOM, LIST } ElemTag; typedef struct GLNode { ElemTag tag; union { char atom; // 原子结点的值 struct { struct GLNode *head; // 子表的头 struct GLNode *tail; // 下一个元素（表尾） } ptr; } un; } GLNode;

这个结构体里，tag用来区分当前结点是原子还是子表。如果是原子，就用un.atom存值；如果是子表，就用un.ptr.head指向子表的第一个结点，un.ptr.tail指向同层的下一个结点。这种“头尾链表存储法”把广义表变成了一个由结点组成的链表，但某些结点的值又是一个子链表，整体形成了嵌套结构。

实际操作里最常写的两个函数是求深度和复制。求深度用递归：原子深度为0，空表深度为1，非空表深度为1加所有子表深度的最大值。复制广义表则是递归地复制每个结点，遇到子表时进入递归。这些题看起来和平时的线性表操作很不一样，但只要你画一张图，把每个结点的tag、head、tail标清楚，代码思路一下就顺了。

有一个容易踩的坑是共享结构和循环引用。如果两个广义表共享同一个子表，释放内存时你可能会重复释放同一块区域，导致double free。更麻烦的是广义表允许自引用，比如定义L = (a, L)来描述无限结构，这时如果直接递归求深度或复制，会无限递归下去。教材里的定义虽然承认这种表的存在，但工程实现里必须加深度限制或使用显式栈，否则就是栈溢出。

3.3 广义表的真实投影：从JSON到S表达式

广义表教科书味很重，但它的“递归定义+变长结点”思想其实无处不在。

最典型的是JSON。一个JSON对象的值可以是字符串、数字、布尔值、数组、对象，其中数组的元素还可以继续是数组，对象的value还可以继续是对象。这和广义表的定义几乎一一对应：值本身是“原子型数据”或“嵌套结构”。你写一个递归下降的JSON解析器时，遇到{就递归解析对象，遇到[就递归解析数组，这和广义表的递归遍历方式完全一致。

LISP的S表达式就更直接了。LISP里(a (b c) d)既是一段代码，也是一份数据，它的内存表示就是一个广义表：原子对应符号或数字，子表对应括号括起来的表达式。所以很多编译原理课程会把“广义表”和“S表达式”放在一起讲，理解其中一个，另一个基本就通了。

工程上还有一类典型的广义表应用是XML/HTML的DOM树。一个元素节点有文本子节点、元素子节点，元素子节点本身还可以再嵌套。你用DOM API遍历节点时，用到的就是递归地“处理当前节点，然后处理子节点列表”的思路。所以，广义表并非“找工作用不上”的章节，它是你后面学AST、学解释器、学一切嵌套结构时的基础思维。

4. 高频问题与排查经验速查

写到这里，我想把平时被问得最多的、以及我自己在项目里遇到过的典型问题集中整理一下。这些内容不复杂，但每一次都能让新手卡上几个小时，值得记下来。

4.1 串和数组最容易翻车的几个报错

第一个是C数组名退化。数组名在大部分表达式中会退化为指向首元素的指针，所以把数组传给函数后，在函数里写sizeof(arr)/sizeof(arr[0])是拿不到正确长度的，因为arr已经变成了int*。正确做法是额外传长度参数，或者用模板推导，再或者直接用std::array/std::vector。

第二个是返回局部数组。这个我在串的章节提过，但它在数组场景同样高发。函数内部定义的数组在栈上，函数返回后内存就“还回去”了，外部继续读写就是未定义行为。排查这种问题，我推荐在C/C++开发时开AddressSanitizer，GCC或Clang加-fsanitize=address编译，运行时报错会直接告诉你哪块内存出了问题，比自己用printf猜快得多。

第三个是二维数组越界。很多越界不是“大得离谱”的越界，而是行列搞反了，比如按行优先存储的数组里，用a[j][i]去遍历，虽然下标都在合法范围内，但访问顺序完全反了，缓存命中率暴跌，性能差好几倍，严重时还会访问到不属于本行的内存。这种问题要结合存储公式去理解，别只是背“行优先”三个字。

第四个是Java字符串拼接。用+连续拼接大量字符串，每次都会生成新的String对象，时间复杂度逼近O(n²)。我在线上代码里见过有人用循环拼SQL，拼到几千条就把内存打爆。解决办法很直接：用StringBuilder。同理，C#用StringBuilder，Python建议用列表收集后再join。

4.2 多语言数组高频操作对照

很多搜索热词集中在“数组去重”“js数组删除指定元素”“js数组排序的几种方法”“数组转字符串”，这说明跨语言切换时，大家特别容易忘API。这里整理一个高频操作对照表，覆盖最常见的四种语言，需要的可以直接抄。

表格里值得展开一句的是排序稳定性：JS的Array.prototype.sort在ES2019之后强制稳定，Python的sorted稳定，C++的std::sort不是稳定排序，需要稳定场景要改用std::stable_sort。如果面试官问你“排序后相同元素的相对顺序会不会变”，你就要立刻意识到他在考这个点。

4.3 广义表学习与面试避坑指南

广义表在面试里出现频率不高，但只要出现，考的基本就是三件事：求深度、求表头表尾、写递归复制。我建议把这三道题都手写一遍，并且在纸上画出存储结构图。画图的价值是能把“递归”具象化，不然代码写出来也是凭感觉。

求深度时很多人容易把空表的深度搞错。按主流定义，空表也是一个广义表，深度为1，因为你至少有一层括号。原子没有括号，深度为0。这个细节经常被当成扣分点。

复制广义表时要注意内存管理。如果结点是动态分配的，递归复制完成后，要保证新旧表完全独立，不要共享子表，否则释放时可能出现多次释放同一块内存。更保险的做法是预先规定“不共享任何结构”，每个结点都重新分配。

还有一个工程化建议：真要在C++里实现广义表相关的复杂操作，直接用std::variant或std::any来承载原子和子表，会比手写union安全很多。手写union不是不行，但要自己处理构造函数、析构函数和拷贝语义，调试成本不低。数据结构题用来练习没问题，生产代码尽量用语言提供的高级抽象。

另外，广义表相关的题经常是“递归+回溯”的变体，比如把广义表转换成括号字符串、把字符串解析成广义表。这类题建议用显式栈来模拟递归，避免递归深度太大导致栈溢出。我面试时遇到过候选人递归写得好好的，可一跑深层数据就崩，后来换成stack迭代版本才通过，这个经验在实际线上环境同样适用。

最后再分享一个我自己总结的小经验：学串、数组和广义表，不要只盯着教材里的“三种存储结构对比”死记硬背。试着把概念映射到身边真实存在的东西上——串的匹配对应你每次按Ctrl+F的体验，数组的存储公式对应你排查内存越界时的直觉，广义表的递归定义对应你解析JSON时的递归下降代码。把这些映射想清楚，你会发现自己不是背了一堆名词，而是真的建立了一套“用数据结构看世界”的思维框架。如果让我给新手一个建议，那就是每学完一种结构，立刻去翻一门语言里对应API的源码，比如看看std::vector的扩容逻辑、String.indexOf的实现思路，这比反复刷十道模板题都管用。