今天这一篇是“数据结构day05”的学习笔记。按照我自己的节奏前四天分别是绪论、线性表、栈和队列正好今天进入“数组、矩阵压缩存储与广义表”这一章。这一章不会写太长的代码但非常烧脑子因为里面全是公式推导和下标的边界问题。如果你也在准备期末复习或者考研408这一篇应该对你有参考价值我不只把结论列出来还把我踩过的坑、当时怎么一步步把公式推出来、以及为什么这些内容会和后面的图、排序算法纠缠在一起都写出来。1. 数组不是“把元素存起来”地址公式背后是整片连续内存的布局1.1 一维数组为什么非要连续很多人初学数组的时候觉得它就是“一堆放在一起的元素”这种理解不能说错但会漏掉最关键的部分数组在内存里是一段连续的存储空间它之所以能实现O(1)的随机访问靠的不是“元素排在一起”这个直觉而是“我可以直接从首地址算出来第i个元素在哪里”。比如你在C语言里写一句int a[5]假设系统给了你一个基地址1000每个int占4个字节那么a[0]在1000a[1]在1004a[2]在1008a[3]在1012a[4]在1016。也就是说地址公式是Loc(a[i]) Loc(a[0]) i * sizeof(类型)这个公式简单到看起来像废话但它是整个数组地址计算的出发点。之后所有高维数组、矩阵压缩存储的推导都是在“数元素个数”的基础上套用这个公式。我第一天自学的时候没当回事结果等到对称矩阵的下标映射直接卡住——因为我一上来就在背公式根本没有回到“前面有几个元素”这个最基本的思维模型上。1.2 二维数组按行优先/列优先公式千万不能混二维数组和一维数组的差别只在于逻辑上把它看成了“一个表格”。在内存里它还是要拉直成一维来存。有两种拉直方式按行优先先装第一行再装第二行逐行连续存放。C语言的数组就是按行优先存储。按列优先先装第一列再装第二列。Fortran / MATLAB默认按列优先。对于按行优先的二维数组int a[m][n]如果用0-based下标a[i][j]的地址是Loc(a[i][j]) Loc(a[0][0]) (i * n j) * sizeof(元素)这里i * n表示第i行前面的所有行一共有i * n个元素再加j个本行前面的元素然后乘以类型大小。按列优先则反过来Loc(a[i][j]) Loc(a[0][0]) (j * m i) * sizeof(元素)注意这里的m是总行数j * m表示第j列前面的所有列一共占了j * m个元素。这一段的坑在题目里经常出现。有些题目不告诉你按行还是按列而是直接说明“m行n列、首地址是1000、每个元素4字节”然后问某个元素地址。那时候你必须先看它指定的存储顺序再选用对应的公式。我见过不少人把行数和列数乘反就是因为没有注意到默认语言是C还是其他语言。再补充一个重要细节课本里经常用1-based下标来推公式。如果你使用C语言下标从0开始那么“前面有几行”就要数成i而不是i-1。我在下面会反复遇到这个1和0的边界建议你自己推导的时候也先约定好。1.3 我记公式的方法只记“前面有多少个元素”地址计算本质上是“数元素个数”。这是一个我后来才意识到非常好用的原则确定这个元素前面有几行/几列。确定同一行/同一列里它前面还有几个。把前面的元素个数加起来乘以每个元素的大小再加上首地址。不需要背(i*n j)这种长得差不多的公式。需要的时候现推30秒就能算出来而且不容易把行列搞混。我在刷题时用这个思路解决过不少二维数组的坑题包括后面矩阵压缩的下标映射也完全是同样的逻辑先数前面总共有多少个元素。2. 对称矩阵、三角矩阵、三对角矩阵压缩存储的公式到底怎么推2.1 为什么要把矩阵“压扁”成一维数组现实中的矩阵不都是满的。比如带权图的邻接矩阵、网络的关联矩阵很多元素要么是0要么和别的位置重复。如果我老老实实用一个int matrix[n][n]来存那就要开 n*n 个空间但很多地方完全是浪费的。这里讨论三类常见矩阵对称矩阵满足a[i][j] a[j][i]下三角完全冗余。三角矩阵上三角或者下三角全是某个常数通常为0只存一边加一个常数位。三对角矩阵只有主对角线、主对角线上面那一条、下面那一条上有非零值其他地方全是0。压缩存储的思路就是把“必要元素”按一定顺序存进一维数组然后把二维下标(i, j)映射成一维下标k。难点全在映射公式上。2.2 对称矩阵只用一半空间k值的完整推导以对称矩阵为例我只存下三角区包含主对角线和主对角线以下的部分。若矩阵大小为 n x n那需要存储的元素个数是1 2 3 ... n n(n1)/2现在要回答的问题给定a[i][j]假设下标从1开始它在一维数组里的下标k是多少因为只存下三角所以i j时才直接存储如果i j由于对称性用a[j][i]来代替。假设按行优先存放我站在a[i][j]的位置往前数第1行1个元素第2行2个元素...第i-1行i-1个元素。所以它前面所有行的元素总数为1 2 ... (i-1) i(i-1)/2然后同一行第i行里a[i][j]前面还有j-1个元素。于是k i(i-1)/2 j - 1这里k如果是数组下标且从0开始那这个公式正好是它在一维数组中的位置如果一维数组下标从1开始那就再1。很多教材直接把这个公式写在结论区但如果你不理解“前面几行共有几个元素”这一层考试换个行列编号或换个存储方向从0开始计数你立刻傻眼。我当时就是傻眼之后才决定自己推一遍。推完之后去验证几个已知位置比如a[1][1]对应k1*0/21-10a[2][1]对应k2*1/21-11确实是按行把下三角存进一维数组的正确位置。2.3 三角矩阵和三对角矩阵的公式区别如果还按上述对称矩阵的思路三角矩阵其实只是少了一部分对称的重复元素但常数区是实实在在存在的所以数组长度要额外加1下三角矩阵实际存下三角的n(n1)/2个元素加上一个空间存放上三角的公共常数。一维数组总长度n(n1)/2 1。在下三角区域内a[i][j]的映射和对称矩阵一样在上三角区域即i j且非公共常数的情况一般直接跳到最后一个位置取常数。三对角矩阵更考验推导。三对角矩阵的非零元素集中在三条对角线上主对角线ij上对角线ji1下对角线ji-1。按行优先存放这些带内元素时第一行只有2个元素中间各行有3个元素最后一行也是2个元素。假设下标从1开始第i行带内元素的位置当i1本行有两个元素a[1][1]、a[1][2]当2 i n-1每行有3个元素。对于带内元素a[i][j]它在下一维数组的下标可以这样推前i-1行总元素数第一行2个之后i-2行每行3个。所以前面总数是2 3*(i-2) 3i - 4。本行中列号j相对行号多偏移当j i-1是0偏移j i是1偏移j i1是2偏移。因此k 3i - 4 (j - (i-1)) 2i j - 3。这个公式很常见但它只适用于带内元素。如果题目给你一个a[i][j]但|i-j| 1答案就是“该位置为0不存储”。这个条件别漏掉我在做题时曾经老老实实套公式算出个错误数值就是因为没先判断它是不是带内元素。2.4 避坑经验公式的两种下标体系我在这部分踩过两次坑总结出来就是一句话所有公式都和题目的下标约定强绑定。题目说“数组下标从0开始”公式里就没有那么多的偏移题目说“下标从1开始”公式里就会出现i-1、j-1。我给个可以照做的自查流程先看矩阵下标是0-based还是1-based。再看一维数组下标是0-based还是1-based。先按“前面有多少行每行存多少个”数出来总数。再加上本行前面的偏移量。最后根据一维数组的起始下标决定要不要加1。用这个流程无论题目怎么变都不会慌。真正理解了之后你会觉得那些看起来很吓人的“k值公式”其实就是数数题。3. 稀疏矩阵的三元组表示从普通转置到快速转置3.1 稀疏矩阵的判定和三元组结构如果矩阵中非零元素的分布非常零散达到“稀疏”标准用二维数组硬存就太亏了。衡量标准是稀疏因子稀疏因子 非零元素个数 / (行数 * 列数)一般小于等于0.05就可以认为矩阵是稀疏矩阵。稀疏矩阵的压缩存储不固定最常用的是三元组顺序表每个非零元素用一个三元组(row, col, value)表示然后按某种顺序把这些三元组存进数组。C语言结构体可以这么定义#define MAXSIZE 1000 typedef struct { int row; // 该非零元素所在行 int col; // 该非零元素所在列 int value; // 该非零元素的值 } Triple; typedef struct { Triple data[MAXSIZE]; // data[0] 留作特殊用途实际从1开始存放 int rows; // 总行数 int cols; // 总列数 int nums; // 非零元素个数 } TSMatrix;这里把data[0]空出来或者当作特殊位置存矩阵行数列数信息是比较常见的做法主要为了和后面的快速转置算法保持“1-based下标”一致。如果你初学也可以一切从0开始但要注意算法里的边界也要改成从0起算。3.2 普通转置把每一列挑出来转置就是把矩阵的(i, j)换成(j, i)。三元组存的是稀疏矩阵的非零元素所以转置的一个朴素思路是依次处理原三元组中的每一列也就是新矩阵的每一行把所有该列的元素按顺序写入新的三元组。算法核心伪代码如下for (col 1; col cols; col) { for (p 1; p nums; p) { if (data[p].col col) { newData[q].row data[p].col; newData[q].col data[p].row; newData[q].value data[p].value; q; } } }这个方法实现简单但最坏情况下要扫描原三元组cols * nums次。如果列数很多、非零元素也很多代价会明显变大。所以我一般都选择下面这种更快的方式。3.3 快速转置num和cpot两个辅助数组解决“放哪”的问题快速转置的核心是不再反复扫描而是提前知道“原三元组中第p个元素转置后应该放到新三元组的哪个位置”。操作分成三步统计每一列有多少个非零元素。设num[col]为原矩阵第col列的非零元素个数。计算每一列第一个非零元素转置后的存放位置。设cpot[col]表示第col列中第一个非零元素应该存放在新三元组的下标。扫描原三元组每遇到一个元素就放到newData[cpot[col]]然后把这个列的cpot[col]加1。第二步的递推公式特别重要cpot[1] 1; cpot[col] cpot[col - 1] num[col - 1]; // col 2翻译成人话第col列第一个元素存放的位置是第col-1列第一个元素的起始位置加上第col-1列的元素个数。这就像排队你前面一列的人全进去之后才轮到你这一列。完整代码我用C写了一段void FastTranspose(TSMatrix M, TSMatrix *T) { int num[MAXSIZE] {0}; int cpot[MAXSIZE] {0}; int col, p, q; T-rows M.cols; T-cols M.rows; T-nums M.nums; if (M.nums 0) { return; } for (p 1; p M.nums; p) { num[M.data[p].col]; } cpot[1] 1; for (col 2; col M.cols; col) { cpot[col] cpot[col - 1] num[col - 1]; } for (p 1; p M.nums; p) { col M.data[p].col; q cpot[col]; T-data[q].row M.data[p].col; T-data[q].col M.data[p].row; T-data[q].value M.data[p].value; } }注意这里列号从1开始计数所以数组num和cpot的长度要开到cols 1不然访问会有越界风险。时间复杂度上普通转置一般接近O(cols * nums)快速转置把统计和放置分开做整体是O(cols nums)在处理大矩阵时差别会很明显。3.4 我今天在这个代码里踩的坑第一个坑是cpot[col]写成了cpot[col] 1——少了自增导致每列第一个元素放完后下一个同列元素会覆盖到同一个位置结果转置完非零元素个数没错但内容和位置全乱。调试时我打印num和cpot数组发现数值都对最后才看到是这个自增丢了。这个错误很隐蔽建议写完之后手动检查一下“同一列第二个元素会放在哪”。第二个坑是边界条件。如果M.nums 0我一开始没有提前返回后面cpot[1] 1虽然不报错但空转置逻辑上是不对的。加一个空矩阵判断之后逻辑才完整。十字链表这种链式存储也可以解决稀疏矩阵但它的优势主要体现在矩阵运算会动态改变非零元素个数时。如果你现在只是在学基础、应付考试先把三元组和快速转置吃透十字链表先了解概念就够了。4. 广义表带递归结构的“列表”不该死记表头表尾4.1 广义表定义的“打破常规”数组和矩阵基本都是“同质元素”的集合但广义表不一样。广义表LS (a1, a2, ..., an)中的数据元素既可以是单个原子也可以是一个子表。它允许一个表直接套在另一个表里面。举几个例子A ()空表长度为0。B (a, b, c)长度为3三个元素都是原子。C (a, (b, c))长度为2第一个是原子a第二个是子表(b,c)。D (x, y, z, (u, (v)))长度为4最后一个元素是递归嵌套的子表。这里定义要注意长度是外层元素的个数不是整体元素的个数深度是括号嵌套的最大层数。比如D的长度是4不是6深度是3而不是1因为最内层的(v)外面还套了(u, (v))这一层。学这一节的时候我老把长度和深度搞混后来就记一句话长度看逗号分隔的最外层有几个深度数最深的括号套了几层。广义表和前面学的线性表最大的区别就是递归性。线性表里递归主要体现在“表尾可以是表”但通常我们忽略这一点广义表则彻底允许任意层的嵌套。4.2 表头、表尾和题目里的Head/Tail连招考试里最常考的一类问题就是给定一个广义表让你连续进行Head(Tail(Head(...)))运算最后看结果是什么。定义只有两条表头 Head(LS)取广义表的第一个元素它可以是原子也可以是子表。表尾 Tail(LS)取广义表中除第一个元素外由其余元素组成的表。注意这里的“表”字很重要。举例说明对LS (a, (b, c), d)Head(LS) a结果是原子。Tail(LS) ((b, c), d)结果仍然是一个广义表外层括号不能省。继续操作Head(Tail(LS)) Head(((b,c), d)) (b,c)结果是子表。Tail(Head(Tail(LS))) Tail((b,c)) (c)结果是只有一个元素c的表。最容易犯的错误就是把Tail的结果和中括号混在一起。你记住一条Tail返回的一定是表所以没括号也要加上外层括号再表示。比如Tail((a)) ()不是“空原子”而是空表。4.3 代码怎么描述这种递归结构广义表的存储结构和树类似本质上是一种“有方向的递归结构”。C语言里可以用标签结构体加上联合体来实现typedef enum { ATOM, LIST } ElemTag; typedef struct GLNode { ElemTag tag; // ATOM表示原子LIST表示子表 union { char atom; // 原子节点的值 struct GLNode *hp; // 子表的表头指针 } val; struct GLNode *next; // 指向同一层下一个节点 } GLNode;这种结构其实就是“原子节点 表节点”的混合链表。你在遍历时要先判断当前节点的标签是原子还是子表如果是原子就直接读值如果是子表就递归进去访问。我一开始对这段代码的理解停留在“会背结构体”的层面直到做了一道求广义表深度的题目才真正学会用递归来看待它求深度要从最外层开始遇到子表就把子表深度加1遇到原子就是0最后取最大值再加当前这一层。4.4 为什么说广义表是后面学树的“预课”广义表最大的价值是帮你建立“递归结构”的思维这是学习树和二叉树之前非常重要的一道坎。树本身就是一个递归定义树的子树还是树。如果你在广义表这里想不通“怎么一个表还可以包含自己同类型的表”到了树那里大概率也会卡住。所以我自己的学习顺序建议是先把广义表的递归结构在纸上画清楚哪怕只是画嵌套括号能画明白后面学二叉树的前中后序遍历会顺很多。这一节教材里往往篇幅不多但值得慢慢磨。5. day05之后的衔接数组、图、排序算法怎么连成一条线5.1 排序算法里到处是数组的身影学完数组之后再回头看排序算法会清晰很多。快速排序里反复操作的partition本质就是在数组的一段连续区间上移动元素让基准值放到正确位置归并排序需要一个临时数组在合并两个有序段时来回拷贝堆排序更是直接建立在一维数组的下标关系上。如果你把数组的地址公式和下标关系搞明白了这些算法实现起来会顺手很多。我在自习时写过一个快速排序的小程序经常因为“low/high移动时越界”崩溃后来才发现这是我数组边界感没建立好。只要你清楚low和high始终要在合法下标范围内移动排序算法里的很多小bug都可以提前避免。5.2 图的邻接矩阵就是二维数组的现实应用到了“图”这一章二维数组会再次成为主角。无向图的邻接矩阵是对称矩阵如果图规模不大完全可以利用前面压缩存储里“对称矩阵只用一半空间”的思路去节省内存哪怕不压缩A[i][j] 1表示i和j之间有一条边这本质上就是一个二维数组的快速定位问题。图的深度优先遍历、广度优先遍历在邻接矩阵表示下很多操作都会退化为数组的扫描。这也是为什么408题库里“图和数组”经常放在一起出题图存储那块就是数组知识的下游应用。5.3 给不同目标的复习建议如果你正在期末复习这一章的复习重点是教材上的公式推导题、数组地址计算题、快速转置算法流程把这些手工推一遍比刷十道题更有用。如果你准备考研408建议把数组和图的邻接矩阵、排序算法联系起来看因为真题里经常让你在数组上做排序或者给你一个邻接矩阵让你求度。如果你用的是Java或者平时写业务代码不一定需要死抠C语言语法但“连续存储随机访问”这个底层思维仍然值得懂《大话数据结构》对新手很友好入门阶段读起来不累《数据结构与算法分析》则适合想在工程和理论之间建立更扎实连接的人。我的个人体会是day05这一章不是“数组那么简单”它是整个数据结构里一次很重要的思维升级从顺序结构的直观操作逐步转向压缩存储、下标映射和递归结构。把这些概念真正啃下来后面学树、学图都会轻松很多。今天这份笔记就分享到这里公式一定要自己推一遍代码也要自己跑一遍只看是记不住的。