基础知识-数组

二维数组

行下标[0,h₁]

列下标[0,h₂]

按行优先Loc(a_{i,j})=Loc(a_{0,0})+[i\times(h_{2}+1)+j]\times L

按列优先Loc(a_{i,j})=Loc(a_{0,0})+[i\times(h_{1}+1)+i]\times L

特殊矩阵压缩存储(数组下标从0开始)

对称矩阵

元素存储在数组中的下标k对应关系

上三角

行优先

k= \begin{cases} \frac{(i-1)(2n-i+2)}{2}+(j-i),\quad i\leqslant j\text{(上三角区和主对角线元素)} \\ \frac{(j-1)(2n-j+2)}{2}+(i-j),\quad i>j\text{(下三角区)} & \end{cases}

列优先

k= \begin{cases} \frac{j(j-1)}{2}+i-1,\quad i\leqslant j\text{(上三角区和主对角线元素)} \\ \frac{i(i-1)}{2}+j-1,\quad i>j\text{(下三角区)} \end{cases}

下三角

行优先

k= \begin{cases} \frac{i(i-1)}{2}+j-1,\quad i\geqslant j\text{(下三角区和主对角线元素)} \\ \frac{j(j-1)}{2}+i-1,\quad i<j\text{(上三角区)} \end{cases}

列优先

k= \begin{cases} \frac{(j-1)(2n-j+2)}{2}+(i-j),\quad i\geqslant j\text{(下三角区和主对角线元素)} \\ \frac{(i-1)(2n-i+2)}{2}+(j-i),\quad i<j\text{(上三角区)} & \end{cases}

三角矩阵

上三角

行优先

k= \begin{cases} \frac{(i-1)(2n-i+2)}{2}+(j-i), & \quad i\leqslant j\text{(上三角区和主对角线元素)} \\ \frac{n(n+1)}{2}, & \quad i>j\text{(下三角区元素)} \end{cases}

列优先

k= \begin{cases} \frac{j(j-1)}{2}+i-1,& \quad i\leqslant j\text{(上三角区和主对角线元素)} \\ \frac{n(n+1)}{2}, & \quad i>j\text{(下三角区元素)} \end{cases}

下三角

行优先

k= \begin{cases} \frac{i(i-1)}{2}+j-1, & \quad i\leqslant j\text{(下三角区和主对角线元素)} \\ \frac{n(n+1)}{2}, & \quad i>j\text{(上三角区元素)} & \end{cases}

列优先

k= \begin{cases} \frac{(j-1)(2n-j+2)}{2}+(i-j), & \quad i\leqslant j\text{(下三角区和主对角线元素)} \\ \frac{n(n+1)}{2}, & \quad i>j\text{(上三角区元素)} & \end{cases}

三对角矩阵

k=2i+j-3

稀疏矩阵(三元组)

1. 存储非零元素值

2. 所在行

3. 所在列