企业官网建设流程全解析

数组和广义表，这两个东西放在数据结构的第三章，看起来平平无奇。数组嘛，天天写代码都在用，广义表嘛，概念绕得人头疼。但说实话，这一章恰恰是从“会写代码的人”过渡到“懂数据结构的人”的第一道门槛。数组背后的存储逻辑、下标为什么会从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*(n+1)/2。关键是下标换算。假设我们用一维数组sa[k]存下三角的数据：

• 当i >= j时：k = i*(i+1)/2 + j
• 当i < j时：利用对称性，交换i和j，再套同一个公式

为什么i*(i+1)/2？因为前i行（第 0 行到第i-1行）有1 + 2 + ... + i = i*(i+1)/2个元素，加上第i行里第j列之前的j个元素，就是当前元素的偏移量。这公式本质上就是等差数列求和。

我在实际项目里真用过这个。当时要给某个存储受限的嵌入式环境处理一个 100x100 的对称矩阵，原始要 10KB 浮点数，压完变成 5050 个浮点数，省了差不多一半空间。别小看这在嵌入式上能省下的几百字节，有时候就是能塞进去和不能塞进去的区别。

2.2 三角矩阵和下三角的边界情况

三角矩阵分上三角、下三角两种。下三角矩阵，上三角部分全是常数（通常为 0），存储方案是：

sa[0..n*(n+1)/2] 存下三角元素 sa[n*(n+1)/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 广义表的定义，让人第一次见到递归

广义表的定义：

广义表是 n（n>=0）个元素的有限序列，其中每个元素既可以是原子（单个数据元素），也可以是子表（又是一个广义表）。

注意这定义里出现了“广义表”自己。这种自指式定义就叫递归定义。之前学的单链表可以叫“递归定义”，但它的递归发生在表节点层面，没有打破“元素都是同一种数据”的假设。广义表则彻底打破了“表的元素必须是同一类型”的限制——元素可以是不同类型，甚至可以嵌套成子表。这就给数据处理带来极大的灵活性。

举几个典型例子：

• 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 模式下就静静躺着，事情更大。

排查方法，往往是不确定时先检查数组的每个循环边界。我之前调试过一个排序模块，数据偶尔会冒出一个超大值，花了很长时间排查才发现是冒泡排序里内层循环某个下标多走了一步，越界写到了相邻数组的第一个元素上，在特定数据规模下才复现。这个问题用 ASAN（AddressSanitizer）一跑就抓出来了。如果你在做 C 项目，编译时记得加-fsanitize=address，这个工具能抓住很多只在运行时才现形的越界。

5.3 稀疏矩阵转置：效率换空间的取舍

快速转置算法的代价是引入辅助数组num[]和cpot[]，额外空间开销 O(nu)。如果矩阵列数极大，比如 10 万列，额外 10 万个 int，也就是 400KB，在某些单片机环境下可能就撑不住了。

所以需要根据实际矩阵规模来判断该用朴素转置还是快速转置。极端情况下，如果矩阵非零元数量极小（比如 100 个），朴素转置O(nu*tu)可能反而更省时间——因为tu太小，多扫几遍也没多少开销。数据规模不同，最优解就不同，这是很多教程不会教你的经验。算法分析课教的是渐近复杂度，但实际优化要考虑常数项和存储代价。

5.4 广义表递归的边界条件永远是第一优先级

写广义表递归算法，最常见的报错是无限递归导致栈溢出。根子出在边界没写对或者递归推进写错了。写递归的基本三要素：

• 明确终止条件（空表、原子）
• 明确递归推进方向（取表头或表尾，表会变小）
• 先处理终止，再处理推进，顺序不能反

另外，广义表可以根据需要一个元素一个元素地构建，但产出顺序跟读取顺序不一定一样。有些考试题目问“构造广义表的过程”，本质上就是递归入栈和出栈的过程，建议在纸上手动模拟一遍递归调用栈，印象会非常深。

还有一种情况是广义表里面出现“共享子表”——多个地方引用了同一个子表，存储结构用指针的话可能会形成环，遍历时就死循环了。如果出现这种现象，去查一下是否有人在创建子表时多次调用同一个指针而没有refcount一类的引用计数，这个坑在系统设计里很经典。

写在最后的几点体会

这一章学完之后，我自己的感受是：数组不难，难的是理解它背后的存储逻辑和代价；广义表不难，难的是第一次接触递归定义时的思维转换。很多时候我们觉得数据结构“难”，不是因为代码写不出来，而是因为脑子里没有建立起对“数据在内存里如何组织”的直观认识。

我建议你把数组的地址公式、对称矩阵的压缩、稀疏矩阵的快速转置、广义表的求深度这四件事，都用手工模拟跑一遍——写在纸上画出来，拿个小矩阵自己算一遍。这个过程花不了多长时间，但它建立的直觉，会让后面学习二叉树、图、查找表时受益无穷。实际写代码的时候，如果遇到越界、爆栈、内存占用过高，回头想一想这一章的存储模型，很多问题自然就有排查方向了。