考研笔记 | 数据结构 §4. 矩阵的压缩存储 广义表

发表于 分类于 阅读次数： 本文字数： 747 阅读时长 ≈ 1 分钟

  1. 数组是由 n (n≥1) 个相同类型的数据元素构成的有限序列。

  2. 数组与线性表：数组是线性表的推广。除了结构初始化与销毁外，数组只会存取元素和修改元素的操作。

  3. 矩阵的压缩存储，对 n 阶方阵 $\begin {equation} A= \left [ \begin {matrix} 1&……&n&\\……&……&……&\\n&……&n&\end {matrix}\right]\end {equation}$ 中元素 $a_{ij} $ 存储于 B，B 下标从 0 开始，下同。

  4. 对称矩阵
    $$K=\left\{\begin {aligned}\frac {i (i-1)}{2}+j-1& &i≥j&(下三角区及对角线) \\ \frac {j (j-1)}{2}+i-1 & &i＜j&(上三角区及 a_{ij}=a {ji})\end {aligned}\right.$$

  5. 三角矩阵

    1. 下三角阵：$$k=\left\{\begin {aligned}\frac {i (i-1)}{2}+j-1& &i≥j&(下三角区及主对角线) \\ \frac {n (n+1)}{2} & &i＜j&(上三角区)\end {aligned}\right.$$
    2. 下三角阵：$$k=\left\{\begin {aligned}\frac {(i-1)(2n-i+2)}{2}+(j-i)& &i≤j&(上三角区及主对角线) \\ \frac {n (n+1)}{2} & &i＞j&(下三角区)\end {aligned}\right.$$

  6. 三对称矩阵 行优先存储 $k=2i+j-3$

  7. 三元组结构

$i$$j$$v$
行列值