数组

i

本文的内容还不完整

概念

数组和线性表的关系：数组由线性表推广而来。数组都可以看作一个线性表

数组一旦被定义，大小不再改变，维数也不再改变。

多维数组有两种映射方法，一种是按行优先，一种是按列优先。一般都是按行优先，因为这符合声明符的解析顺序。

特殊矩阵的压缩存储

存储矩阵用二维数组。有些矩阵具有特殊性质，可以用技巧压缩其存储空间。

对称矩阵

n阶对称矩阵。右上左下的数据其实是一样的，所以可以只存一份，比如存一个左下三角加主对角线，共$\frac{n(n+1)}{2}$个。按照一行一行的顺序，存储到一维数组里。这样左下三角和主对角线里的i,j处的元素在数组里就是第$1+2+\cdots +(i-1)+j$ 个，即第$\frac{i(i-1)}{2}+j$个，下标为$\frac{i(i-1)}{2}+j-1$。对于右上的元素，按照主对角线对称过来，i,j处的元素相对于下面的j,i处的元素。所以右上三角的i,j处元素等于下标为$\frac{j(j-1)}{2}+i-1$的元素。

三角矩阵

上三角矩阵和下三角矩阵。线性代数里，这种矩阵通常指另外一个三角里的元素全是0,具有求行列式只需要主对角线乘起来的特性。但是对于数据结构，另外一个三角里的元素是多少都可以，只要都相同就可以，因为数据结构关注的是需要多少存储空间，存0或存任何其他的数都是一样的。

这就是一个数据结构里的下三角矩阵。和对称矩阵一样，按照一行一行的顺序。多出来那个常数放到最后一位。也就是前$\frac{n(n+1)}{2}$个元素和对称矩阵完全一样。

对称矩阵还能使用左下存储方式避开右上，但是上三角矩阵避不开。对于上三角的元素，存储是倒过来的,i,j处的元素处于$k=n+(n-1)+\cdots +(n-i+2)+(j-i+1)-1=(i-1)(2n-i+2)/2+(j-i)$位置。

TODO:带状矩阵

这个其实不重要，先放着

稀疏矩阵

意思是矩阵里面非0的元素比较少，剩下的全是0.如果采用普通的方式存储，存了一堆0,浪费空间。所以我们只要存储非0值就行了。

稀疏矩阵的非0值分布没有规律。方法是把i，j和值组成一个三元组，然后存储三元组线性表。这样存了以后矩阵将失去随机存储的优势。
以下是图片内容的 Markdown 文本表示，包含 LaTeX 公式和表格：

M对应的三元组如下表所示：