前几天一个准备秋招的学弟问我说教材里《串、数组和广义表》这一章翻来覆去看了好几遍还是记不住问我当初是怎么啃下来的。我说这一章其实最容易被忽略但你去看各厂笔试和面试很少有人直接问你“广义表是什么”可串的模式匹配、二维数组的存储结构、数组指针和指针数组的区别几乎每场都会变着法考。更关键的是这三类结构在写真实业务代码时天天都在用后端处理文本要搞敏感词过滤数据分析绕不开多维数组的切片和矩阵运算写解析器又离不开递归定义的树形结构。所以我今天换个角度把串、数组和广义表放到一起讲说清楚它们各自的脾气、互通的底层逻辑以及这些年我在编码里亲手踩过的坑。1. 串一切文本处理的底层数据结构很多人觉得串就是字符数组没什么好学的。这个想法在应付考试时还能蒙混一到实际项目就露馅了。串和字符数组的本质区别在于操作粒度字符数组关心的是“每个格子存了什么”串关心的是“连续一段字符的整体行为”。你要在一个长度为几百万的字符串里做子串查找或者在用户输入里做敏感词替换如果只会字符数组级别的操作性能和正确性都很难保证。串要学明白重点是两块存储结构怎么选模式匹配怎么做。这两块学透了后面看各语言字符串库的源码基本就是看它们在这两个维度上做了哪些取舍。1.1 存储结构怎么选定长、堆分配、块链教材里讲串的存储一般给三种方案定长顺序存储、堆分配存储、块链存储。我刚学的时候觉得这三种方案就是三个名词背完就完事直到自己写了一个需要频繁修改字符串的模块才明白每一种方案背后都是一组实实在在的代价。定长顺序存储类似C语言里的char str[MAXSIZE]长度一开始就固定死。优点是实现简单、访问快缺点是“定长”两个字就是天花板一旦字符串长度超过预设值要么截断要么报错。我见过不少老系统里用定长结构存用户备注存到一半内容被无声截断排查半天才发现是这里出了问题。所以定长存储只适合那些长度上限明确、且不会变化的场景比如固定长度的订单号。堆分配存储是现在的主流思路C语言里就是malloc一个动态大小的空间用完了freeC的std::string、Java的String底层虽各有优化本质也是“运行时动态管理字符存储区”。好处是长度不再受限坏处是要自己操心内存的分配和释放以及扩容时的数据搬运。很多线上崩溃、内存泄漏都是在这个环节出了问题。块链存储是把字符串拆成若干块每块存几个字符再用链表串起来。它的价值在理论上避免每个字符都背一个指针提高存储密度。但你要是真去实现一次就知道插入删除要在块间移动数据访问某个下标的字符要沿着链表遍历复杂度极高。现在工程里基本见不到了我建议把它当成“理解存储密度”的练习题别真用到生产代码里。三种方案的选择逻辑可以总结成一句话长度固定选定长长度动态选堆分配极端节省内存再考虑块链。工程上最常见的是堆分配因为业务数据的长度几乎都是动态的。1.2 模式匹配朴素算法、KMP与真实工程的取舍串里最经典的问题是模式匹配在主串里找模式串第一次出现的位置。朴素算法很好理解两个循环逐位比对主串指针和模式串指针一起走不匹配就回退。最坏情况比如主串是aaaaaaaaab模式串是aaaab每趟都要比到最后一个字符才失败然后主串指针回退一格再来时间复杂度退化到O(m*n)。KMP算法解决的就是这个回退问题。它的核心是预处理模式串生成一个next数组记录“如果这一位失配模式串指针应该跳到哪个位置”。因为主串指针永远不回退整体复杂度降到O(mn)。当年第一次自己手写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::vectorint 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))那才是连续内存的数组。我把几种典型初始化的行为整理成了一张表面试前扫一眼很有用语言/写法默认行为注意事项Cint a[5] {0}未列出的元素补0局部未初始化是垃圾值Cvectorint v(5)元素默认构造int为0扩容有额外开销Javaint[] a new int[5]默认0引用类型默认为nullPython[0]*55个0的listlist存的是引用不是连续值NumPynp.zeros((3,4))连续内存全0适合数值计算2.2 多维数组的存储顺序行优先、列优先与指针纠缠一维数组是线性内存二维数组的存储就出现了路线分歧到底是先存完一行再存下一行还是先存完一列再存下一列。C和C是行优先按base (i * 列数 j) * sizeof(type)寻址a[i][j]。MATLAB是列优先所以a(j,i)这种访问方式性能更好。numpy默认也是行优先但创建时传orderF就能按列优先布局。这个差异不只是学术问题当你做矩阵乘法时数据在内存里的排列顺序直接影响缓存命中率进而影响性能好几倍。多维数组和指针搅在一起是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开发时开AddressSanitizerGCC或Clang加-fsanitizeaddress编译运行时报错会直接告诉你哪块内存出了问题比自己用printf猜快得多。第三个是二维数组越界。很多越界不是“大得离谱”的越界而是行列搞反了比如按行优先存储的数组里用a[j][i]去遍历虽然下标都在合法范围内但访问顺序完全反了缓存命中率暴跌性能差好几倍严重时还会访问到不属于本行的内存。这种问题要结合存储公式去理解别只是背“行优先”三个字。第四个是Java字符串拼接。用连续拼接大量字符串每次都会生成新的String对象时间复杂度逼近O(n²)。我在线上代码里见过有人用循环拼SQL拼到几千条就把内存打爆。解决办法很直接用StringBuilder。同理C#用StringBuilderPython建议用列表收集后再join。4.2 多语言数组高频操作对照很多搜索热词集中在“数组去重”“js数组删除指定元素”“js数组排序的几种方法”“数组转字符串”这说明跨语言切换时大家特别容易忘API。这里整理一个高频操作对照表覆盖最常见的四种语言需要的可以直接抄。操作JavaScriptPythonCJava去重[...new Set(arr)]list(dict.fromkeys(arr))sortunique先排序new LinkedHashSet(list)删除指定元素arr.splice(idx, 1)arr.pop(i)或列表推导v.erase(remove(...))list.remove(obj)排序arr.sort((a,b)a-b)sorted(arr)sort(v.begin(), v.end())Collections.sort(list)切片arr.slice(1, 4)arr[1:4]vector的子区间构造list.subList(1, 4)数组转字符串arr.join(,),.join(map(str, arr))手动拼接String.join(,, list)表格里值得展开一句的是排序稳定性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迭代版本才通过这个经验在实际线上环境同样适用。最后再分享一个我自己总结的小经验学串、数组和广义表不要只盯着教材里的“三种存储结构对比”死记硬背。试着把概念映射到身边真实存在的东西上——串的匹配对应你每次按CtrlF的体验数组的存储公式对应你排查内存越界时的直觉广义表的递归定义对应你解析JSON时的递归下降代码。把这些映射想清楚你会发现自己不是背了一堆名词而是真的建立了一套“用数据结构看世界”的思维框架。如果让我给新手一个建议那就是每学完一种结构立刻去翻一门语言里对应API的源码比如看看std::vector的扩容逻辑、String.indexOf的实现思路这比反复刷十道模板题都管用。