总结

这一章的结论可以压缩成一句话:数组的代价在「按下标随机访问」,矩阵的代价在「按结构存得更省」。术语对照表把行优先、对称矩阵、三元组、十字链表这些说法对齐到英文表述,核心要点则把必须记住的地址公式与压缩下标公式集中列出,考前扫一遍就能把这一章的公式串起来。

术语对照表

中文术语英文术语说明
行优先Row-Major按行展开存储
列优先Column-Major按列展开存储
对称矩阵Symmetric Matrix满足 A[i][j]=A[j][i]
压缩存储Compressed Storage只存有效元素
稀疏矩阵Sparse Matrix非零元素很少的矩阵
三元组Triple(行, 列, 值) 表示非零元素
十字链表Orthogonal List行列双向链表存储

核心要点

  • 行优先地址公式:LOC=LOC00+(i×n+j)×LLOC = LOC_{00} + (i \times n + j) \times L
  • 对称矩阵压缩下标:k=i(i+1)2+jk = \frac{i(i+1)}{2} + j(i≥ji \ge j)
  • 三对角矩阵压缩下标:k=2i+jk = 2i + j
  • 稀疏矩阵用三元组或十字链表存储,节省空间但随机访问慢

发现内容有问题?

告诉我们哪里需要改进。