学数据结构的时候串、数组和广义表这一章常常被当成“背概念”的一章——字符串谁不会写数组天天用广义表好像考试完就再也不见。但真到了开发或者刷题你会发现坑全在这章地里埋着数组初始化的默认值、sort排序的字典序陷阱、字符串的不可变性、嵌套数组的递归遍历每一个都让人“啊还能这样”这篇文章我按自己从教材到实战的路径把数组、串、广义表三块重新捋一遍。不仅讲它们是什么更讲代码里的边界条件、底层存储和踩坑记录。适合正在啃数据结构教材的同学、准备面试的候选人以及想弄清楚为什么字符串处理总是慢的开发者。全文不写废话直接上干货。1. 数组连续内存、动态扩容与初始化陷阱1.1 连续存储为什么快数组之所以能在 O(1) 时间内随机访问是因为它在内存里申请的是一段连续空间。编译器只需要知道三个信息起始地址、元素类型、下标就能算出任意元素的地址第 i 个元素的地址 起始地址 i × sizeof(元素类型)这也是为什么数组下标从 0 开始更自然——如果从 1 开始每次寻址都得做一次i - 1的减法。C 语言把这套规则保留得最彻底arr[3]在底层就是*(arr 3)等价于*(3 arr)所以写3[arr]在 C 里都能编译通过只是没人会这么干。连续存储带来的副作用是插入和删除费劲。在数组中间插一个元素得把后面的所有元素整体往后挪一位最坏情况是 O(n)。所以数组适合读多写少的场景频繁增删得用链表或者用动态数组在尾部操作。1.2 初始化三种语言各怀鬼胎数组初始化的坑几乎每个初学者都踩过。C 语言里int arr[5] {0};很多人以为是把所有元素设成 1不对{}里只写了 0编译器会把剩余元素自动补 0所以这个写法确实能把全部元素清 0。但如果你写int arr[5] {1};效果不是五个 1而是{1, 0, 0, 0, 0}。局部变量的数组不初始化值是不确定的谁也不知道里面是什么垃圾数据。全局数组和static数组则自动清零。Java 稍微友好一点int[] arr new int[10];默认全是 0但Integer[] arr new Integer[10];默认全是null用到之前不判空就会空指针。JavaScript 更迷惑new Array(10)产生的是一个长度为 10、但没有任何元素的稀疏数组map、forEach会直接跳过这些空位。想创建真正的 0 数组得写new Array(10).fill(0)或者Array.from({ length: 10 }, () 0)。Python 里[0] * 10倒是好使但[[]] * 3会创建三个指向同一个空列表的引用一改全改这个坑后面细说。1.3 动态数组扩容的实际开销普通数组定长很多时候长度是运行期才知道的于是有了动态数组。Java 的ArrayList、C 的vector、Python 的list本质都是动态数组。它们的策略很简单容量不够时扩容通常扩到原来的 1.5 或 2 倍再把旧数据整体搬过去。有人担心每次扩容都搬数据性能是不是 O(n²)不会。因为扩容是按倍数增长的假设初始容量 1扩容到 2、4、8、16…… 总搬迁次数是 1 2 4 ... n ≈ 2n均摊到 n 次插入里每次接近 O(1)。这也是面试常问的“为什么动态数组末尾插入均摊 O(1)”的答案。注意如果提前知道大概数据量直接给ArrayList或vector一个初始容量能省好几次扩容搬迁。别小看这个优化大数组场景下差距很可观。2. 数组高频操作排序、去重、切片与多维数组2.1 排序默认行为不等于你想要的JavaScript 的sort是翻车重灾区[10, 9, 100].sort()的结果是[10, 100, 9]因为默认按字符串的 UTF-16 码元排序10 和 100 都排在 9 前面。正确写法是arr.sort((a, b) a - b)升序想降序就b - a。C 的sort默认按比较数字没问题但它是快速排序不稳定。如果同时要稳定性和性能用stable_sort。Java 里Arrays.sort对基本类型用双轴快排对对象类型用 TimSort后者是稳定的这点和 C 不一样。实际业务中经常要按对象的某个字段排比如按价格、按时间。JS 写法const items [{ price: 3 }, { price: 10 }, { price: 1 }]; items.sort((a, b) a.price - b.price);注意比较函数里返回的是数值差不是布尔值。返回布尔值会导致排序结果不稳定因为底层不确定怎么解释true/false。2.2 去重Set 之外还有哪些招数组去重的第一反应是Setconst arr [1, 2, 2, 3, 4, 4]; const unique [...new Set(arr)];这套对基本类型好使对象数组就失灵了——两个内容相同的对象在内存里地址不同Set认为它们不相等。按某个唯一键比如 id去重得用Mapconst users [ { id: 1, name: a }, { id: 2, name: b }, { id: 1, name: c } ]; const uniqueUsers [...new Map(users.map(u [u.id, u])).values()];面试不让你用Set时还有一条经典思路有序数组原地去重。两个指针一个慢指针i指向不重复区的末尾一个快指针j负责扫描function removeDuplicates(nums) { if (nums.length 0) return 0; let i 0; for (let j 1; j nums.length; j) { if (nums[j] ! nums[i]) { i; nums[i] nums[j]; } } return i 1; }这个解法的时间 O(n)空间 O(1)是 LeetCode 26 题的标准答案。理解双指针的移动时机比背答案重要。2.3 切片与拷贝浅拷贝的坑Python 的切片语法最爽arr[1:4]取下标 1 到 3左闭右开arr[::-1]直接反转二维数组arr[:, :2]取前两列。但切片是浅拷贝——一维数组没问题里面套列表时外层切片只是复制了引用内层列表还是同一份。深拷贝要copy.deepcopy(arr)或者用[row[:] for row in arr]。JS 的slice()同理只拷贝一层arr.splice(1, 2)则是删除/替换元素会改变原数组和slice完全不同。C 里没有内建切片可以用迭代器区间构造vectorint src {1, 2, 3, 4, 5}; vectorint sub(src.begin() 1, src.begin() 4); // {2, 3, 4}左闭右开这个规则C、Python、Java 的很多 API 都遵循记死它结束下标不包含。2.4 二维数组与矩阵指针、切片与维度C 语言的二维数组最容易把人绕晕。int a[3][4]的类型是int (*)[4]即指向“含 4 个 int 的数组”的指针而不是int**。把二维数组传给函数时必须写明列数void printMatrix(int a[][4], int rows) { for (int i 0; i rows; i) { for (int j 0; j 4; j) { printf(%d , a[i][j]); } } }如果非要动态二维数组常见套路是申请一个指针数组再给每个指针申请一行int** matrix (int**)malloc(rows * sizeof(int*)); for (int i 0; i rows; i) { matrix[i] (int*)malloc(cols * sizeof(int)); }Python 的 NumPy 把多维操作简化了很多比如三维数组相乘需要搞清楚是矩阵乘法还是逐元素乘法。np.matmul做矩阵乘法*做逐元素乘。举个例子三维数组a形状(2, 3, 4)想让它和形状(4, 5)的矩阵相乘用a b会得到(2, 3, 5)。广播机制自动把矩阵应用到第一维的每个“页”这在批量处理图像或时间序列时非常实用。数组还能玩出树形结构比如树状数组和线段树就是用数组存树形区间信息处理“数组区间最大值”这类问题。高频的套路是静态区间最大值用单调栈或 RMQ动态修改用线段树前缀和用于区间和。核心思路是先想清楚查询是静态还是动态再选数据结构。3. 串字符数组之上字符串算法和工程实践3.1 串的存储模型串String本质是受限的线性表元素只能是字符。教材里说三种存储方式定长顺序存储、堆分配存储、块链存储。定长顺序存储就是char str[100]空间固定容易溢出堆分配存储是malloc出来的一段字符空间C 字符串其实就是这样末尾加一个\0标记结束。\0导致很多经典坑sizeof(abc)是 4包含结束符strlen(abc)是 3。用strlen遍历字符串没问题但拿sizeof当长度就错了尤其在函数参数里char arr[]作为参数后自动退化为char*sizeof只会得到指针大小。现代语言基本都封装好了Java 的String不可变底层是byte[]Python 的str也是不可变的。不可变带来一个好处——多个字符串变量可以安全共享底层数组不用复制坏处是拼接时得不断创建新对象。3.2 模式匹配与回文串串最经典的算法是模式匹配。朴素匹配两层循环最坏 O(mn)。KMP 的核心是next数组也叫部分匹配表它记录模式串中每个位置之前的子串最长相等前后缀的长度保证失配时模式串从不匹配的位置往前跳而不是从头再来。KMP 的时间复杂度是 O(m n)。回文串是刷题高发区。判断一个字符串是不是回文用双指针从两端往中间扫function isPalindrome(s) { let left 0, right s.length - 1; while (left right) { if (s[left] ! s[right]) return false; left; right--; } return true; }找最长回文子串更进阶中心扩展法枚举每个中心点向两边扩散注意奇数长度和偶数长度的中心不同Manacher 算法能压到 O(n)面试时能讲清楚中心扩展就够了。3.3 字符串不可变性与拼接性能工程里最常见的性能杀手是循环拼接字符串。Java 里String是 final 的每次都会创建新的字符串对象循环 1 万次就创建 1 万个临时对象。正确做法StringBuilder sb new StringBuilder(); for (String item : list) { sb.append(item); } String result sb.toString();JavaScript 的字符串也是不可变的但 JS 引擎对有一定的优化不过大量拼接时靠谱的做法还是收集到数组然后join()。Python 里join比循环快得多尤其是拼接列表里的片段时。经常有人问“串口”和“串”的关系。串口通信里读到的数据本质上也是一个字节串/字符串处理时同样要注意缓冲区边界、分隔符和半包问题和数据结构串的“顺序访问、边界判断”思路是一致的。串级 PID 里的“串”则是控制回路串联两个词的“串”不是一回事但都跟“有序、按顺序处理”有关。3.4 字符串、字符数组与 JSON 数组的转换字符串和字符数组的互转是标配。Javaabc.toCharArray()和new String(chars)Pythonlist(abc)和.join(chars)JSabc.split()和arr.join()。split和join组合还能做小规模文本清洗比如把一个数组按逗号拼成 CSV 行const row [1, haha, x].join(,); // 1,haha,xJSON 数组的解析和序列化本质也是字符串和结构化数据的转换const jsonStr [{id:1,name:a}]; const arr JSON.parse(jsonStr); const back JSON.stringify(arr);这里要注意JSON.stringify遇到循环引用会抛错对象里有undefined、函数、Symbol时这些字段会被跳过。所以不能把它当万能序列化工具手写深拷贝时尤其要小心。4. 广义表递归定义的“表的表”4.1 广义表到底是什么广义表Generalized List把线性表的定义放宽了元素可以是原子也可以是另一个广义表。比如A (a, (b, c), ((d), e))A的长度是 3因为第一层有三个元素原子a、子表(b, c)、子表((d), e)。深度是括号嵌套的层数A的深度是 3。普通线性表相当于“所有元素都是原子”的广义表特例。广义表还有一个让初学者拧巴的性质表头可以是原子也可以是子表但表尾一定是子表。GetHead(A) aGetTail(A) ((b, c), ((d), e))。想取A的第二个元素得先GetHead(GetTail(A))。这套运算就是 LISP 语言里car和cdr的原型。递归定义导致后面的算法几乎全得用递归写所以这本书把它放在数组后面等于给读者一个递归思维的过渡。4.2 存储结构如何把一个递归概念装进内存存储广义表最常见的是头尾链表表示法。每个结点要么是原子结点要么是表结点。原子结点只需要一个tag标志和值表结点则要两个指针hp指向表头tp指向下一兄弟结点。用 C 的联合体表示typedef enum { ATOM, LIST } ElemTag; typedef struct GLNode { ElemTag tag; union { char atom; struct { struct GLNode* hp; struct GLNode* tp; } ptr; } data; } GLNode;这个结构妙在“递归类型”可以用指针自引用。表结点里的hp指向的可能是原子结点也可能又是一个表结点tp则串起同一层的所有元素。像 JSON 里的嵌套数组解析成树形结构后结点类型、子节点列表本质上和广义表的存储是同一个模型。画图时我习惯把原子结点画成圆形表结点画成矩形hp往下指tp往右指。看不懂代码时把图画出来递归逻辑立刻清楚了。4.3 深度、复制和遍历递归算法三件套求广义表深度的递归公式很直白空表深度为 1原子深度为 0一般表的深度 1 max(所有子表元素的深度)伪代码int depth(GLNode* ls) { if (ls NULL) return 1; if (ls-tag ATOM) return 0; int maxDepth 0; GLNode* p ls; while (p ! NULL) { int d depth(p-data.ptr.hp); maxDepth max(maxDepth, d); p p-data.ptr.tp; } return maxDepth 1; }复制广义表也递归复制一个表就是先复制表头再复制表尾。遍历更简单遇到表结点就往深处走遇到原子就打印。这三个操作写熟练后再看目录树遍历、表达式树求值、JSON 嵌套遍历代码结构都是相似的。难点在于处理共享和递归的广义表比如A (a, A)这种自指定义。直接递归会死循环解决办法是加访问标记或引用计数这已经接近图的遍历了。4.4 广义表就在我们身边很多教材只会出两道题就完了但广义表的思想在日常开发里到处都是。最直观的是 JSON 数组[1, [2, 3], [4, [5]]]就是一个广义表。写递归解析器时遇到[就递归解析子数组遇到数字就返回原子值这个结构就是广义表的解析过程。再比如文件系统的目录树、前端组件树的children字段、语法分析里的 AST 节点都是“元素可以是自己的同类”的递归结构。理解广义表本质上是在理解树形数据在内存里的递归表达。哪怕你以后不写 LISP处理嵌套数据时也会顺手很多。5. 常见问题与实测避坑5.1 高频翻车现场场景典型问题原因解决办法C 数组传参函数里sizeof(arr)不对数组名退化为指针额外传长度或改用std::vectorC 数组越界写arr[5]有时不报错有时崩C/C 不做边界检查严格用i size循环优先用容器JS 数字排序[10,9,100].sort()错默认按字典序arr.sort((a,b)a-b)Python 二维列表[[0]*3]*3一改全改外层乘的是引用[[0]*3 for _ in range(3)]对象数组去重Set去不掉比较的是引用用Map按 id 去重Java 字符串循环拼接慢到怀疑人生不可变对象频繁创建用StringBuilderJSsplice和slice改动了原数组数据全乱了两者语义不同删除/替换用splice取子集用sliceC 二维数组传参int**接不住int a[][4]类型不匹配参数写int (*p)[4]每一条都是我在调试时真实撞过的。有些问题不报错纯粹是“表现正常但结果错误”这种比直接崩溃还难查。比如 JS 数字排序数据量小的时候可能看不出来数据一多就出现 100 排在 9 前面的奇葩顺序。5.2 面试和笔试里怎么用这些知识刷题时数组、串、广义表这些基础结构会反复出现。几个热点题的思路拆解最长回文子串先用中心扩展 O(n²) 保住底再提 Manacher O(n)。面试官更看重你能不能快速写出中心扩展并且正确处理奇偶中心。连续子数组的最大和Kadane 算法维护current max(num, current num)同时更新全局最大。这是“动态规划”最简单的一种。数组区间最大值静态用单调栈/稀疏表动态用线段树。树状数组适合前缀和类问题写起来短但理解成本高。三个数组的最大乘积先排序答案要么是最后三个数相乘要么是两个最小负数×最大正数。这个坑很多人想不到因为默认数组都是正数。2 的幂数组判断位运算(n (n - 1)) 0同时要排除 0。用循环除 2 也能做但位运算更快。数组切片记住区间是左闭右开Python、Go、C 的迭代器区间都遵循这条规则就不会出现“差一错误”。广义表在笔试里更多以“递归遍历嵌套列表”的形式出现比如把[1, [2, 3], [4, [5]]]展平成[1, 2, 3, 4, 5]。写递归时先判断当前元素是原子还是列表列表就继续递归原子就收集代码十几行就够。我个人在实际操作中的体会是数组、串和广义表其实是递进关系——数组是最朴素的顺序存储串加上了字符和匹配的算法广义表则把“元素”扩展到“子表”逼着你用递归去思考。很多人觉得数据结构枯燥是只背了结论没写代码这三章恰恰是需要大量手写练习的内容尤其是广义表画的图越多对递归的理解越扎实。最后再分享一个小技巧遇到嵌套结构的题目先别急着写循环先在草稿纸上把这个结构画成树再决定是递归还是用栈。数组题卡住了检查一下切片边界是不是左闭右开字符串题卡住了先想清楚它是不是不可变对象对象去重卡住了看看是不是该用 Map 而不是 Set。这些细节看起来不起眼但就是它们在决定你代码能不能一次跑对。