对称矩阵的压缩存储可能是数据结构里最容易出现“背了公式还做错”的考点。同一个求A[i][j]存储下标的题换个下标起点、换一种三角区域答案就完全不同甚至有的题目还故意把“下标”和“第几个元素”混着问。这篇文章把对称矩阵压缩存储的下标计算完整拆一遍覆盖 0 基和 1 基、下三角和上三角、正向求下标、反向由一维下标求二维下标最后加上地址计算和常见坑点适合考研、期末复习和数据结构面试前突击。1. 先搞清楚题目到底在考什么别急着套公式对称矩阵的压缩存储核心思想很简单因为A[i][j] A[j][i]矩阵里有一半数据是重复的所以没必要把完整的n × n矩阵全部存下来。通常只存储下三角或上三角部分包括主对角线空间从n × n降到n(n1)/2。对于大规模矩阵这个优化是很明显的例如一个 1000 × 1000 的对称矩阵完整存储需要 100 万个单元压缩后只需要 500500 个单元。1.1 对称矩阵压缩存储后元素是怎么排列的以下三角按行优先存储为例假设二维矩阵是A[0..n-1][0..n-1]一维数组是SA[0..n(n1)/2 - 1]那么存储顺序是第 0 行A[0][0]第 1 行A[1][0]、A[1][1]第 2 行A[2][0]、A[2][1]、A[2][2]第 i 行A[i][0]、A[i][1]、……、A[i][i]所以每一行的元素个数是递增的1、2、3、……、n。这就是为什么下标计算公式里会出现等差数列求和。很多同学记不住公式是因为没有理解前面这个“每一行有几个元素”的规律。一旦你把压缩后的存储顺序写出来公式其实可以现场推出来。1.2 做题前必须确认的三件事我在看题的时候不管题目多简单都会先做三个确认二维矩阵的下标从 0 开始还是从 1 开始压缩存储的是下三角还是上三角含不含主对角线一维数组的下标从 0 开始还是从 1 开始这三件事只要有一个判断错公式就全错。特别是考研题和期末考试题里经常默认给“矩阵 A[1..n][1..n]”或者默认给“一维数组下标从 1 开始”这些都会影响最终结果。判断项常见题目写法对公式的影响二维矩阵下标A[0..n-1][0..n-1]或A[1..n][1..n]决定前面有多少整行存储区域下三角、上三角、是否含对角线决定每行元素个数一维数组下标0 基或 1 基决定是否要 1问法求一维下标、求第几个元素、求存储地址决定最后要不要换算有时候题目还会问“存放在一维数组的第几个位置”这个和第几个元素是同一件事但和“一维数组下标”不同。如果一维数组下标从 1 开始那么“第几个元素”等于“下标”如果下标从 0 开始那么“第几个元素”等于“下标 1”。这个细节看起来简单但非常容易丢分。注意如果题目问的是“一维数组下标”默认下标从 0 开始如果问的是“第几个位置”或“第几个元素”默认从 1 开始。做题时先把这个明确下来再往下计算。2. 最常考的“下三角按行存储”从零基开始推导公式2.1 二维下标从 0 开始、一维下标从 0 开始这是最标准的情况。假设对称矩阵A[0..n-1][0..n-1]按行优先存储下三角含主对角线一维数组SA的下标从 0 开始。现在求A[i][j]其中i j。它的存储位置分两部分前面已经存了完整的 i 行。第 0 行有 1 个元素第 1 行有 2 个元素……第i-1行有 i 个元素。所以前 i 行一共是1 2 3 ... i i(i1)/2当前第 i 行中A[i][j]前面有 j 个元素因为第 i 行的元素从A[i][0]开始。所以一维下标为k i(i1)/2 j举个例子。有一个 10 × 10 的对称矩阵按行优先压缩存储下三角一维数组下标从 0 开始。求A[5][3]对应的一维下标。代入公式k 5 × 6 / 2 3 15 3 18所以A[5][3]存在SA[18]。这个例子验证起来很容易第 0 行存 1 个第 1 行存 2 个第 2 行存 3 个第 3 行存 4 个第 4 行存 5 个这五组加起来是 15 个元素对应下标 0 到 14。第 5 行的元素是A[5][0]、A[5][1]、A[5][2]、A[5][3]分别对应SA[15]、SA[16]、SA[17]、SA[18]。和公式结果一致。2.2 二维下标从 1 开始、一维下标从 1 开始很多教材和高频考题喜欢用A[1..n][1..n]表示矩阵一维数组也习惯从 1 开始编号。这时候公式要重新推不能直接套用上面的i(i1)/2 j。假设矩阵下标从 1 开始一维数组下标也从 1 开始仍按行优先存储下三角含主对角线。求A[i][j]其中i j。前面已经存了完整的i-1行。第 1 行有 1 个元素第 2 行有 2 个元素……第i-1行有i-1个元素。所以前面一共是1 2 ... (i-1) i(i-1)/2当前第 i 行中A[i][j]前面有j-1个元素因为第 i 行从A[i][1]开始到A[i][j-1]都属于下三角。因为一维数组下标从 1 开始所以最终下标k i(i-1)/2 (j-1) 1 i(i-1)/2 j看例子。有一个 10 × 10 的对称矩阵A[1..10][1..10]按行优先压缩存储下三角一维数组下标从 1 开始。求A[6][4]对应的一维下标。代入公式k 6 × 5 / 2 4 15 4 19所以A[6][4]存在一维数组的第 19 个位置。注意一下之前 0 基情况下A[5][3]对应下标 18现在 1 基情况下A[6][4]对应下标 19。其实A[6][4]1 基就是A[5][3]0 基所以下标从 18 变成 19正好是因为一维数组整体从 0 基变成了 1 基差 1。2.3 为什么很多人会把这两个公式记混我自己以前也犯过这个错误把 0 基的公式i(i1)/2 j用在了 1 基题目里结果多算或少算 1。后来我的做法是不背两个公式只背一个统一的推导逻辑先看二维下标前面有多少行再看当前行前面有多少个元素最后看一维数组下标从几开始。这个逻辑可以应对所有下三角题目。考试的时候如果怕出错可以先用小矩阵验证。比如假设n 4手写一个 4 × 4 下三角序列把A[2][1]或A[3][2]代进去很快就能发现公式写没写对。题目基准二维下标范围一维下标范围下三角公式都从 0 开始0 j i n-10..n(n1)/2-1k i(i1)/2 j都从 1 开始1 j i n1..n(n1)/2k i(i-1)/2 j二维 0 基一维 1 基同上同上k i(i1)/2 j 1二维 1 基一维 0 基同上同上k i(i-1)/2 j - 1最后两行是组合情况题目里偶尔会出现。比如二维矩阵是 0 基但一维数组从 1 开始计数那么先算 0 基下标再整体加 1。3. 遇到“上三角按行存储”时为什么不能直接套下三角公式3.1 上三角每一行的元素个数是递减的下三角的每一行元素个数是递增的上三角则相反。如果按行优先存储上三角含主对角线那么第 1 行有 n 个元素第 2 行有 n-1 个元素第 3 行有 n-2 个元素越往下越少。这个变化是很多同学在做上三角题目时翻车的原因。因为一直习惯了“前面 i 行是 12…i”遇到上三角时还在用递增求和结果自然不对。先看标准情况。假设矩阵下标从 1 开始A[i][j]中i j按行优先存储上三角一维数组下标从 1 开始。第 r 行的上三角元素个数是n - r 1。那么前i-1行的元素总数为n (n-1) ... (n-i2)这是一个首项为 n、末项为n-i2、项数为i-1的等差数列。求和(i-1)(n n-i2) / 2 (i-1)(2n - i 2) / 2当前第 i 行中A[i][j]是该行从A[i][i]开始往后数的第j-i1个元素前面有j-i个元素。所以一维数组下标从 1 开始为k (i-1)(2n - i 2) / 2 (j-i) 1如果一维数组下标从 0 开始那么再去掉末尾的 1k (i-1)(2n - i 2) / 2 (j-i)3.2 完整推导和验证例子假设有一个 10 × 10 的对称矩阵A[1..10][1..10]按行优先存储上三角一维数组下标从 1 开始。求A[4][8]的一维下标。先算前 3 行的元素个数第 1 行10 个 第 2 行9 个 第 3 行8 个 总共27 个当前第 4 行从A[4][4]开始元素依次是A[4][4]、A[4][5]、A[4][6]、A[4][7]、A[4][8]……所以A[4][8]前面有 4 个元素。由于一维数组下标从 1 开始A[4][8]的下标是27 4 1 32代入公式验证(4-1)(20 - 4 2) / 2 (8-4) 1 3 × 18 / 2 4 1 27 4 1 32结果一致。再举一个 0 基例子。假设A[0..9][0..9]按行优先存储上三角一维数组下标从 0 开始。求A[3][7]的一维下标。第 r 行的上三角元素个数是10-r。前 3 行元素个数第 0 行10 个 第 1 行9 个 第 2 行8 个 总共27 个当前第 3 行从A[3][3]开始A[3][7]前面有 4 个元素。因为一维下标从 0 开始所以k 27 4 31用公式验证k 3 × (20 - 3 1) / 2 (7-3) 3 × 18 / 2 4 27 4 31正确。提示上三角公式本身不难难的是不要惯性思维。看到“上三角”三个字第一反应应该是“每行元素个数递减”而不是继续用递增求和。4. 给定一维下标怎么反推二维下标4.1 正向会了反向也要会考试和面试里还有一个常见变形给出一维数组下标 k反推它是矩阵里的哪个元素A[i][j]。这个问题的本质是解不等式。以下三角为例假设二维矩阵和一维数组都从 0 开始。已知k i(i1)/2 j其中0 j i。求i和j。思路是先找到最大的 i使得i(i1)/2 k。这个 i 就是行号。因为前 i 行已经占了i(i1)/2个元素剩下的部分就是当前行的列偏移j k - i(i1)/2比如k 13假设矩阵足够大。从小到大枚举i00×1/20i11×2/21i22×3/23i33×4/26i44×5/210i55×6/21515 已经大于 13 了所以 i 最大取 4此时前 4 行有 10 个元素。j 13 - 10 3所以k 13对应A[4][3]。验证一下A[4][3]的一维下标应该是4×5/2 3 10 3 13正确。4.2 手算和代码里两种常用做法手算时可以先把i(i1)/2的序列列出来0, 1, 3, 6, 10, 15, 21, 28, 36, ...然后看 k 落在哪两个数之间。注意这个序列就是三角形数序列对应对角线元素的位置。如果用代码实现可以直接解一元二次方程i(i1)/2 k展开i^2 i - 2k 0取正根附近的值i 约等于 (sqrt(8k1) - 1) / 2然后向下取整。不过求完以后要验证一下因为开方取整可能会有误差特别是当8k1恰好是完全平方数时。稳妥做法是取整后重新算i(i1)/2如果大于 k就减 1。反推上下三角的题目只要正向公式理解到位基本就是倒过来解不等式。不要怕这种题它比正向题更固定。5. 地址计算与考试陷阱基地址、第几个元素、下标要分开5.1 地址计算的完整例子下标计算的题目最后通常会落到地址计算。核心公式是存储地址 基地址 一维下标偏移 × 每个元素占用的字节数这里的“一维下标偏移”必须和基地址的基准一致。举个例子。对称矩阵A[0..9][0..9]每个元素占 4 字节A[0][0]的存储地址是 2000按行优先存储下三角含对角线。求A[6][2]的存储地址。先求一维下标k 6 × 7 / 2 2 21 2 23因为基地址是A[0][0]的地址也就是压缩数组第 0 个元素的地址所以偏移量直接用 k地址 2000 23 × 4 2000 92 2092如果题目改成A[1..10][1..10]一维数组下标从 1 开始基地址是A[1][1]的地址同样是 2000求A[7][3]的地址。先求一维下标k 7 × 6 / 2 3 21 3 24这里要注意SA[1]存的是A[1][1]基地址 2000 对应SA[1]不是SA[0]。所以SA[24]的地址应该是地址 2000 (24 - 1) × 4 2000 92 2092为什么这里要减 1因为基地址是SA[1]的地址而SA[24]相对SA[1]偏移了 23 个元素位置。如果直接用 24 乘上 4就会多算一个元素。这两个例子最终地址都是 2092说明两种写法虽然公式表示不同但物理存储位置一样。关键就在于基地址对应哪个元素偏移就按哪个基准算。5.2 对称矩阵、三角矩阵和列优先的边界有些参考书会把对称矩阵和三角矩阵放在一起讲但它们是不同的东西。对称矩阵只存下三角或上三角访问另一半元素时通过下标交换实现。例如要访问A[i][j]且i j就等价于访问A[j][i]直接查下三角。三角矩阵除了存下三角或上三角还要额外存一个常数 C代表另一半所有元素的值。所以三角矩阵的一维数组大小是n(n1)/2 1多出来的那一个位置专门存 C。如果考试题写的是“三角矩阵”你还在用对称矩阵的公式最后会漏掉常数 C 的位置。特别是反推题里如果 k 等于n(n1)/2对应的是常数 C而不是某个正常矩阵元素。列优先存储的情况偶尔也会出现。做法和行优先完全对称只是“前面有多少行”变成“前面有多少列”求和方式一样但行和列的关系要反过来。遇到列优先时我建议先画一个小矩阵在草稿纸上按列写一遍存储顺序再推公式不要凭感觉改公式。5.3 最容易丢分的三个地方基地址对应的是A[0][0]还是A[1][1]决定了偏移量要不要减 1。题目问的是“下标”还是“第几个元素”。下标从 0 开始和第几个元素差 1。下三角和上三角的公式不能混用。特别是题目如果给的是上三角但要求用对称性转成下三角计算这时要注意查询的下标是否已经交换。6. 刷题复习建议不要背公式把矩阵画出来推一遍6.1 五分钟自测法每复习到这个知识点我都建议做一次快速自测拿一个 4×4 或 5×5 的对称矩阵自己用手写出下三角压缩到一维数组后的顺序然后随机抽两个位置按公式算下标再对着序列验证。如果连续几次都能算对再练习上三角。上三角自测时可以故意把“第 r 行有 n-r1 个元素”这个规律抄在纸上一步一步代入。这个自测法看起来简单但比单纯背公式有效得多。因为下标计算的本质是“数清楚这个元素前面已经存了多少元素”而不是机械套公式。只要把“数元素”的逻辑搞清楚换什么基准都不怕。6.2 常见错误汇总错误类型具体表现解决办法公式基准错0 基题目用了 i(i-1)/2j1 基题目用了 i(i1)/2j做题前先标出矩阵和一维数组的下标起点三角区域错上三角题直接用下三角公式先判断每行元素个数是递增还是递减“下标”和“第几个元素”混淆一维数组从 1 开始求下标时没有去重算先明确问法必要时换算地址偏移错基地址对应 SA[1]却直接用 k 乘字节数先确认基地址对应哪个元素再算偏移忽略常数项三角矩阵题没有处理常数 C 的存储位置看到“三角矩阵”四个字先检查数组大小列优先套行优先公式题目说按列存储还在用行优先求和按列重写序列再推公式6.3 结合考研和期末复习的落地建议如果你是考研复习王道的《数据结构》和严蔚敏教材的课后题里对称矩阵压缩存储一般只会考一两道小题分值不高但出错率极高。因为它太简单简单到大家不愿意花时间推导结果考试时一紧张就写错基准。复习时不要追求做很多难题只要把下面几类题各练两三道就够了给出A[i][j]求一维下标给出一维下标反推A[i][j]给出A[i][j]和一个元素的地址求另一个元素的地址上三角和下三角各练一遍三角矩阵的常数 C 存储位置单独练一遍练完以后你会发现这种题的核心不只是公式而是你能不能快速判断出题人用的下标基准。判断对了公式怎么推都通。最后说一个实操经验考试时不要只写最终下标把“前几行共多少个元素”这个中间结果写在草稿上。这样一旦算错还能顺着步骤检查是行数错了还是列数错了。平时做题时也保持这个习惯考试才不会慌。