数组和广义表这两个东西放在数据结构的第三章看起来平平无奇。数组嘛天天写代码都在用广义表嘛概念绕得人头疼。但说实话这一章恰恰是从“会写代码的人”过渡到“懂数据结构的人”的第一道门槛。数组背后的存储逻辑、下标为什么会从0开始、矩阵压缩到底在压缩什么、稀疏矩阵的转置算法为什么有个“快速转置”的版本以及广义表那种递归定义的思维方式——这些东西不搞透后面树、图、哈希表你都会学得磕磕绊绊。我当初学这一章的时候有一个很深的感受数组的代码谁都会写但问你“一个二维数组 a[m][n] 里a[i][j] 到底在内存的哪个位置”很多人就答不上来了。而广义表更是劝退神器它不像是前面学的线性表那样“直来直去”元素套着元素一下子就把线性思维给击穿了。所以这篇博文我打算把这一章拆开揉碎把那些教材里一笔带过、但实际理解起来很关键的地方讲清楚。内容不多但这几个点的分量值得你真的坐下来好好推一遍。1. 数组看似简单实则是存储世界的基石1.1 数组的“随机访问”能力靠的是一条公式数组在C语言里的声明很简单int a[10]编译器就给你分配了连续 40 个字节如果int是 4 字节。为什么我们能直接写a[3]就拿到第 4 个元素因为编译器计算的是地址地址(a[i]) 首地址 i * sizeof(int)就这么简单的一条公式构成了“随机访问”的基础——只要给下标就能算出位置不用从头遍历。这就是数组和链表的本质区别链表找第 5 个元素必须从头往后数数组不用直接算。这里有个关键点经常被忽略数组在 C 语言中不是一种“动态结构”它在声明那一刻长度就固定了。这跟 Python 里的列表完全不同Python 的 list 实际上是一个动态数组。很多从 Python 转 C 的同学会在这里踩坑以为可以像 Python 那样往数组里随便塞东西结果就出现了缓冲区溢出问题。C 语言的数组本质上是这块连续内存的“带类型视图”它不会帮你做越界检查也不会自动扩容这就是为什么后来会出现链表、动态数组这些结构——它们解决的都是数组“静态”这个天然约束。1.2 下标从0开始不只是“C语言习惯”这么简单几乎每本教材都会专门讲一下数组下标为什么从 0 开始。很多同学的理解是“惯例”“C 语言就是这样定的”其实真实原因是下标本质上是“偏移量”。如果下标从 1 开始地址公式就变成地址(a[i]) 首地址 (i-1) * sizeof(int)每次访问都要多一次减法运算。听起来不多但在数组大规模访问的场景下比如图遍历、矩阵运算这样一次多余的减法也是额外开销。下标从 0 开始意味着下标本身就是偏移量不用做任何转换。所以教材里说“数组的下标是偏移量”这句话不是随口说的它直接决定了地址计算公式的形式。我当初在学校做实验的时候用二维数组模拟矩阵乘法老师让我们憋编译器优化打开手动写三层循环。当时我就在想如果能把内层循环的下标计算简化一下性能提升会很明显。后来才理解下标表达式写得好不好直接决定了生成的汇编代码质量。虽然现在编译器优化很厉害但理解这层逻辑对你的代码性能直觉很有帮助。1.3 多维数组的存储行优先还是列优先必须搞清楚C 语言里int a[3][4]在内存里是怎么排的答案是按行优先row-major先存完一行再存下一行。具体来说a[0][0], a[0][1], a[0][2], a[0][3], a[1][0], a[1][1], a[1][2], a[1][3], a[2][0], a[2][1], a[2][2], a[2][3]而 Fortran 用的是列优先。这两种存储方式不仅影响内存布局也影响你写循环时的访问模式——a[i][j]和a[j][i]的访问模式完全不同。如果你按列优先的方式去访问一个行优先存储的数组每次访问都会跳着走缓存命中率会惨不忍睹。二维数组的地址公式地址(a[i][j]) 首地址 (i * 列数 j) * sizeof(类型)再推广到三维int a[L][M][N]地址(a[i][j][k]) 首地址 (i * M * N j * N k) * sizeof(类型)这个嵌套公式的模式很明显就是一层一层展开。每次多一维就等于多一个乘积。这个公式最好不要死记而是理解“按照行优先的顺序前面所有完整行/面的元素总数 当前行内的偏移量”。我见过很多考研的朋友在这类“求某个数组元素地址”的题目上反复失分错的从来不是公式是对存储顺序的理解。1.4 C语言实操数组设计里面那些“无声的设计决策”数组的声明在 C 语言里必须是编译期常量这其实是个设计决策不是懒。C 语言设计时面对的是 PDP-11 这类内存极其宝贵的机器动态长度数组需要额外的运行时信息会显著增加实现复杂度。相比之下定长数组的地址计算可以在编译期优化到寄存器运算级别代价就是你必须自己管好内存。当然C99 引入了变长数组VLA允许int a[n]这种写法。但在实际项目里VLA 不受待见——它在栈上分配大小运行时才确定一旦n很大直接就爆栈了。我自己以前写过一个图像处理的 Demo用 VLA 存一张大图的灰度值运行到一半直接段错误排查了很久才发现是栈溢出。后来老老实实用malloc在堆上分配问题解决。这个经历让我记住一件事数组的“静态性”不是缺陷而是一种约束下的最优选择。你后续学栈和堆、学动态内存管理很多套路本质上都是在模拟“动态数组”的能力。而理解数组的静态性是理解这一切的起点。2. 矩阵压缩存储把重复数据关进小黑屋2.1 对称矩阵只需要存一半实际应用中很多矩阵是稀疏的或者有某种规则结构。比如无向图的邻接矩阵一定是对称矩阵。A[i][j] A[j][i]那存储整个矩阵时一半空间存的是同一个数据太浪费了。对称矩阵压缩的思路很简单只存下三角部分含对角线大小从n*n变成n*(n1)/2。关键是下标换算。假设我们用一维数组sa[k]存下三角的数据当i j时k i*(i1)/2 j当i j时利用对称性交换i和j再套同一个公式为什么i*(i1)/2因为前i行第 0 行到第i-1行有1 2 ... i i*(i1)/2个元素加上第i行里第j列之前的j个元素就是当前元素的偏移量。这公式本质上就是等差数列求和。我在实际项目里真用过这个。当时要给某个存储受限的嵌入式环境处理一个 100x100 的对称矩阵原始要 10KB 浮点数压完变成 5050 个浮点数省了差不多一半空间。别小看这在嵌入式上能省下的几百字节有时候就是能塞进去和不能塞进去的区别。2.2 三角矩阵和下三角的边界情况三角矩阵分上三角、下三角两种。下三角矩阵上三角部分全是常数通常为 0存储方案是sa[0..n*(n1)/2] 存下三角元素 sa[n*(n1)/2] 存那个常数下标映射和对称矩阵下三角公式一样。上三角矩阵则反过来k i*(2*n - i 1)/2 (j - i)这个公式看着复杂推一遍就懂了——从最后一行往上推第i行前面有多少个元素列出来数一数比背公式牢靠得多。做这类题目的时候我很推荐一个方法先画一个 3x3 或 4x4 的小矩阵手动把每个位置的下标 K 写出来再看规律。比单纯对着公式套靠谱十倍而且真的遇到考试、面试的时候你可以现场推导不用赌自己有没有记错公式。2.3 带状矩阵的存储方案还有一种比较常见的压缩对象是带状矩阵对角矩阵非零元素只集中在主对角线附近的一两条对角线上。比如三对角矩阵每一行最多只有 3 个非零元素。压缩思路是按对角线存或者按行存但只存这几个非零位置。按行存储时地址公式Loc(a[i][j]) 首地址 (2*(i-1) (j - i 1)) * L这个公式里的2*(i-1)是前i-1行的非零元素个数第一行 2 个之后每行 3 个(j - i 1)是当前行偏移。行业里有大量这类实际存储模型的应用比如有限元分析中的刚度矩阵很多就是带状稀疏矩阵。掌握压缩存储的思路不是为了考试做题而是为了让你真正遇到内存紧张的场景时有个明确的优化方向。3. 稀疏矩阵当数据大部分是零就该换个思路了3.1 怎么能判断它该压缩了稀疏矩阵的定义很简单非零元素个数远远少于零元素。教材里常给一个比例比如非零元素占比小于 5% 就算稀疏。但在实际工程里真正的标准是用三元组表存储后省下的空间是否足够覆盖存储索引的开销。三元组表的结构C 语言定义大致长这样#define MAXSIZE 12500 typedef struct { int i, j; // 行号、列号从1开始 ElemType e; // 非零元素值 } Triple; typedef struct { Triple data[MAXSIZE 1]; int mu, nu, tu; // 行数、列数、非零元个数 } TSMatrix;特别注意编号从 1 开始data[0]经常留作“哨兵”或不用。这种结构下存一个非零元素需要两个 int 和一个 ElemType通常也是 4 字节也就是 12 字节。如果原来的矩阵一个元素占 4 字节那么只有非零元素零零散散分布时三元组表才划算。如果你的矩阵非零元太多三元组表反而比直接存完整矩阵更占空间因为没有省下内存反而新增了索引开销。3.2 三元组表的转置为什么要搞出两个版本转置是稀疏矩阵最经典的操作。原理很简单把(i, j, e)换成(j, i, e)再保证行优先顺序即可。朴素转置的算法逻辑扫描原矩阵的三元组表对列号j从 1 到nu每次都从原三元组表里把列号为j的元素提取出来放到转置后的三元组表里。每个列号要完整扫描一遍原表复杂度为O(nu * tu)。如果nu很大而且tu也很大的时候这个算法完全不能用。举个例子一个 1000 列的矩阵1 万个非零元复杂度就是 1000 * 10000 10^7 量级虽然还不算灾难但明显有更好的方案。快速转置的思路是先数出每一列有多少个非零元算出每一列第一个非零元应该放到新表的哪个位置然后一遍扫描原表把每个元素直接放到正确位置。关键实现int cpot[MAXSIZE]; // 记录每一列第一个非零元在新表中的位置 // 第一遍统计各列非零元个数 num[col] for (int col 1; col S.nu; col) num[col] 0; for (int t 1; t S.tu; t) num[S.data[t].j]; // 第二遍计算每列第一个非零元在新表中的位置 cpot[1] 1; for (int col 2; col S.nu; col) cpot[col] cpot[col-1] num[col-1]; // 第三遍扫描原表边扫边放边更新 cpot for (int t 1; t S.tu; t) { int col S.data[t].j; int pos cpot[col]; M.data[pos].i S.data[t].j; M.data[pos].j S.data[t].i; M.data[pos].e S.data[t].e; cpot[col]; // 同一列的下一个元素顺延 }这个算法的精妙之处在于cpot[col]这一句。每一次放完一个元素就把该列的“下一个可用位置”往后挪一位这样同一列的元素自然就按行号递增的顺序排好了。时间复杂度降到了O(nu tu)。我当初自己写这个算法的时候总觉得cpot数组初始化很绕后来想通了它本质上就是一个“列号 → 新表下标”的映射函数只不过这个函数需要先扫一遍矩阵才能建立起来。建立映射的思路在以后学哈希表、学索引结构时到处都在用。3.3 十字链表当稀疏矩阵需要频繁增删时三元组表适合静态矩阵。如果有一个稀疏矩阵需要不断地插入或删除非零元素用三元组表存储每次增删都要移动后面的元素代价很大。这时候该用十字链表。十字链表每个非零元素是一个结点有 5 个字段typedef struct OLNode { int i, j; ElemType e; struct OLNode *right, *down; // 同行后继、同列后继 } OLNode;所有结点通过right指针串成行链表通过down指针串成列链表。还要额外搞一个行头节点数组和列头节点数组用来记录每一行、每一列链表的起始位置。这样插入、删除一个非零元素只需要调整所在行和所在列的链指针完全不需要搬移数据。不过说实话如果只是应付课程设计十字链表用得不多。但如果你之后学操作系统、学文件系统里面很多组织方式都跟十字链表的思想沾边。如果跟稀疏矩阵打交道的场景是几十万行几十万列的超大型矩阵直接上十字链表往往是最优解。4. 广义表递归的思维听着绕但能一下打开思路4.1 广义表的定义让人第一次见到递归广义表的定义广义表是 nn0个元素的有限序列其中每个元素既可以是原子单个数据元素也可以是子表又是一个广义表。注意这定义里出现了“广义表”自己。这种自指式定义就叫递归定义。之前学的单链表可以叫“递归定义”但它的递归发生在表节点层面没有打破“元素都是同一种数据”的假设。广义表则彻底打破了“表的元素必须是同一类型”的限制——元素可以是不同类型甚至可以嵌套成子表。这就给数据处理带来极大的灵活性。举几个典型例子F ()空表长度为 0。L (a, b)两个原子长度为 2。A (x, (a, b))一个原子 x一个子表 (a, b)长度为 2。D ((a, b), ((c, d)))两个子表第二个子表里又套了一个子表。这些例子的麻烦在于你要区分“长度”和“深度”。长度是看这一层有几个元素是水平方向的概念深度是看嵌套了多少层括号是垂直方向的概念。D的表长为 2深度为 3你们可以数一下括号。4.2 表头表尾理解广义表的钥匙教材里会给出两个重要的操作定义表头Head广义表的第一个元素可能是原子也可能是子表表尾Tail广义表去掉第一个元素后剩下的部分它一定是一个广义表为什么表尾一定还是广义表因为去掉表头后剩下的那部分依然可以看作一个元素序列也就是一个广义表。这一点特别重要因为它是广义表递归处理能够持续的根源。举个例子L (a, b, c) Head(L) a Tail(L) (b, c)注意Tail(L)的结果仍然带括号是(b, c)不是b, c。继续Tail(Tail(L)) (c) Tail(Tail(Tail(L))) ()到空表为止递归结束。这套“取表头、取表尾”的操作就是广义表所有运算的基础。求表长可以一直Tail直到空表求深度也可以递归下去。我学的时候最大的误区是以为Tail(L)等于(a, b)这种是保留括号后来才发现取出表尾必须重新组合成广义表于是对“表尾必为表”这个性质有了真正认识。4.3 广义表的存储结构两种方案都得懂广义表的元素可能是原子也可能是子表所以存储结构要能区分这两类数据。常见的说法是两种方案头尾链表存储结构和扩展线性链表存储结构。头尾链表存储结构把每个广义表结点分成表结点和原子结点。表结点包括一个标记位和一个指针域指向“表头”和“表尾”而原子结点则是标记位加一个值域。经典的 C 语言定义typedef enum { ATOM, LIST } ElemTag; typedef struct GLNode { ElemTag tag; // 当前元素是原子还是子表 union { char atom; // 原子结点的值 struct { struct GLNode *hp; // 表头指针 struct GLNode *tp; // 表尾指针 } ptr; } un; } GLNode;这里用了一个union因为一个结点要么是原子要么是子表不会同时是。这个设计在数据结构的书里是经典案例值得反复研究。union是 C 语言里省内存的手段同一个内存位置可以存不同类型的值只要你自己保证当前读的是正确的那一类型。扩展线性链表存储结构也差不多区别在于表结点里不区分表头和表尾所有子表都按线性链表的“下一个元素”方式串起来。两种方案各有优劣考试可能考画图题或写算法题需要熟练掌握其中一种并且能快速转换成另一种。4.4 求深度、建表和遍历递归一上手就有意义广义表算法里最典型的三个求深度、求长度、复制。求深度的递归定义很明确int GListDepth(GLNode *L) { if (!L) return 1; // 空表深度为1 if (L-tag ATOM) return 0; // 原子深度为0 int max 0; GLNode *p L; while (p) { int d GListDepth(p-un.ptr.hp); // 递归求表头深度 if (d max) max d; p p-un.ptr.tp; // 遍历表尾 } return max 1; }边界条件要理清楚原子结点深度为 0空表深度为 1非空表是“表头深度 1”。这里有几个约定俗成的东西需要按教材口径来定否则很容易算错深浅。建表的算法书里给的是CreateGList实际上就是一个递归建表过程遇到左括号则创建子表结点遇到原子则创建原子结点遇到逗号则继续处理同一个表的下一个元素。整个过程本身就是一个带状态机的递归下降解析我们每个人在毕业设计里遇到嵌套 JSON 解析时这东西会再次出现。看到这里你已经能从广义表里看到一个极其重要的思维转变学树之前先学会“递归描述数据”。广义表比树更容易理解递归它是递归定义的完美入门。如果你把这一章的递归算法真正写明白了后面的二叉树遍历、图的深度优先搜索学起来会丝滑很多。5. 常见问题与排查心得5.1 地址计算题公式记得住一算就错考试里最常出现的坑是这几种第一分不清行列下标是从 0 开始还是从 1 开始。如果题目没有明确说默认“从 0 开始”但它经常不按套路出牌比如“一个 n 阶矩阵下标从 1 到 n”你如果不仔细读题直接套行优先公式就会差一行。第二忘了sizeof。有些题目给的是“每个元素占 4 个字节”有的给“占 L 个存储单元”有的直接问“第几个元素”不乘单位会得出完全不一样的东西。第三多维数组的计算会漏维度。三维数组求元素地址我建议先画小例子比如 2x3x4 的数组手动写出几个元素的位置再对照公式就非常清晰。5.2 C语言数组越界编译不会报错运行时才出问题C 语言数组越界是未定义行为。你写int a[5]; a[5] 1;编译大概率通过但运行时会怎样谁也不知道可能改了一个相邻的变量、可能直接段错误、可能在 debug 模式下崩、在 release 模式下就静静躺着事情更大。排查方法往往是不确定时先检查数组的每个循环边界。我之前调试过一个排序模块数据偶尔会冒出一个超大值花了很长时间排查才发现是冒泡排序里内层循环某个下标多走了一步越界写到了相邻数组的第一个元素上在特定数据规模下才复现。这个问题用 ASANAddressSanitizer一跑就抓出来了。如果你在做 C 项目编译时记得加-fsanitizeaddress这个工具能抓住很多只在运行时才现形的越界。5.3 稀疏矩阵转置效率换空间的取舍快速转置算法的代价是引入辅助数组num[]和cpot[]额外空间开销 O(nu)。如果矩阵列数极大比如 10 万列额外 10 万个 int也就是 400KB在某些单片机环境下可能就撑不住了。所以需要根据实际矩阵规模来判断该用朴素转置还是快速转置。极端情况下如果矩阵非零元数量极小比如 100 个朴素转置O(nu*tu)可能反而更省时间——因为tu太小多扫几遍也没多少开销。数据规模不同最优解就不同这是很多教程不会教你的经验。算法分析课教的是渐近复杂度但实际优化要考虑常数项和存储代价。5.4 广义表递归的边界条件永远是第一优先级写广义表递归算法最常见的报错是无限递归导致栈溢出。根子出在边界没写对或者递归推进写错了。写递归的基本三要素明确终止条件空表、原子明确递归推进方向取表头或表尾表会变小先处理终止再处理推进顺序不能反另外广义表可以根据需要一个元素一个元素地构建但产出顺序跟读取顺序不一定一样。有些考试题目问“构造广义表的过程”本质上就是递归入栈和出栈的过程建议在纸上手动模拟一遍递归调用栈印象会非常深。还有一种情况是广义表里面出现“共享子表”——多个地方引用了同一个子表存储结构用指针的话可能会形成环遍历时就死循环了。如果出现这种现象去查一下是否有人在创建子表时多次调用同一个指针而没有refcount一类的引用计数这个坑在系统设计里很经典。写在最后的几点体会这一章学完之后我自己的感受是数组不难难的是理解它背后的存储逻辑和代价广义表不难难的是第一次接触递归定义时的思维转换。很多时候我们觉得数据结构“难”不是因为代码写不出来而是因为脑子里没有建立起对“数据在内存里如何组织”的直观认识。我建议你把数组的地址公式、对称矩阵的压缩、稀疏矩阵的快速转置、广义表的求深度这四件事都用手工模拟跑一遍——写在纸上画出来拿个小矩阵自己算一遍。这个过程花不了多长时间但它建立的直觉会让后面学习二叉树、图、查找表时受益无穷。实际写代码的时候如果遇到越界、爆栈、内存占用过高回头想一想这一章的存储模型很多问题自然就有排查方向了。