第 6 讲 · 矩阵、广义表与串匹配

我把几类看似不相干的结构放在这一讲：它们都在解决“逻辑上的多层或稀疏关系，怎样用线性内存表达”。

多维数组仍是一段连续内存

二维数组 A[m][n] 按行优先存储时，A[i][j] 前面有 $i\,n+j$ 个元素。因此若首地址为 $B$ 、元素长度为 $L$ ，则

LOC(A[i][j])=B+(i\,n+j)L.

更高维数组也一样：把每个下标乘以后续各维长度的乘积，再求和。

对称矩阵满足 $a_{ij}=a_{ji}$ ，只需保存上三角或下三角。下三角按行存储时，第 $i$ 行之前共有 $i(i-1)/2$ 个元素，再加本行偏移即可定位。

三角矩阵的另一半元素相同，可额外保存一个公共值。带状矩阵只有主对角线附近少量非零元素，也可以把带区映射到一维数组。

压缩存储的关键是写出从逻辑下标 $(i,j)$ 到物理下标 $k$ 的映射，并明确下标从零还是从一开始。

当非零元素远少于总元素数时，完整二维数组浪费空间。三元组表只保存 (row, col, value)，通常还记录矩阵行数、列数和非零元个数。

三元组表适合顺序处理非零元；若要频繁按行或按列访问，可以增加行起始位置，或采用十字链表：每个非零结点同时进入所在行链和列链。

矩阵转置不能只交换三元组的行列字段，还要让结果按新的行列次序排列。快速转置会先统计原矩阵每一列的非零元个数，由此算出它们在转置表中的起始位置。

稠密多项式可以让数组下标表示指数、数组值表示系数；稀疏多项式更适合保存 (系数, 指数) 的有序结点。

多项式相加类似合并有序表；相乘则让两表每对项相乘，再按指数合并同类项。保持结果表按指数有序，是整个过程的不变量。

广义表的元素可以是原子，也可以是另一个广义表。例如

L=(a,(b,c),d).

长度是最外层元素个数，此例长度为 3；深度是括号的最大嵌套层数。空表和原子要分别定义深度约定。

存储时可在结点中放标志位，区分原子结点和子表结点；同层元素用后继指针相连，子表结点再指向下一层。递归遍历最符合这种嵌套定义。

串是字符的有限序列，可以用定长数组、动态数组或分块链表存储。常见操作有求长度、比较、连接、求子串、插入、删除和模式匹配。

朴素匹配在每次失配后把模式串退回开头，主串起点右移一位。若主串和模式串含有长重复前缀，会重复比较已经知道相同的字符。

假设模式串已经匹配了前 $j$ 个字符，却在下一位失配。已经匹配的这一段既是主串当前后缀，也是模式串前缀。若它还有长度为 $k$ 的“相同真前缀和真后缀”，就可以让模式串的第 $k$ 位继续与当前主串字符比较，而主串指针不回退。

例如模式 ABABAC 的前缀 ABABA，最长相同真前后缀是 ABA。下一位失配时，不必重新比较开头的 ABA。

前缀函数 $\pi[j]$ 表示模式串前 $j+1$ 个字符中，最长相同真前缀和真后缀的长度。构造时也使用同样的回退关系，因此预处理 $O(m)$ ，匹配 $O(n)$ ，总复杂度 $O(n+m)$ 。

对模式串每个前缀：

不要把 next 数组当成孤立数字背诵。不同教材可能使用不同下标和 next[0] 约定，但“失配后保留最长可复用前后缀”这一含义完全相同。