数据结构-多维数组

???? 关于多维数据的存储有一些公式需要记忆,其实可以很容易推理出来,但是感觉有时候脑子不知道怎么那么笨,容易一下子就走神,记录一下.

?

特殊矩阵

??? 　所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。常见的有对称矩阵、三角矩阵和对角矩阵等。
②元素a_ij的存放位置
??? a_ij元素前有i行(从第0行到第i-1行)，一共有：
???????? 1+2+…+i=i?(i+1)／2个元素；
??? 在第i行上，aij之前恰有j个元素(即a_i0，a_il，…，a_i,j-1)，因此有：
?????????? sa[i?(i+1)／2+j]= a_ij?
③a_ij和sa[k]之间的对应关系：
??? 若i≥j，k=i?(i+1)／2+j?? 0≤k<n(n+1)／2<br> ??? 若i＜j，k=j?(j+1)／2+i?? 0≤k<n(n+1)／2<br> ??? 令I=max(i，j)，J=min(i，j)，则k和i，j的对应关系可统一为：
???????? k=i?(i+1)／2+j 0≤k<n(n+1)／2?<br>
（3）对称矩阵的地址计算公式
? LOC(a_ij)=LOC(sa[k])
????????? =LOC(sa[0])+k?d=LOC(sa[0])+[I?(I+1)／2+J]?d
??? 通过下标变换公式，能立即找到矩阵元素a_ij在其压缩存储表示sa中的对应位置k。因此是随机存取结构。
? 【例】a₂₁和a₁₂均存储在sa[4]中，这是因为
?????????? k=I?(I+1)／2+J=2?(2+1)／2+1=4

2、三角矩阵??
（1）三角矩阵的划分
??? 　以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。
①上三角矩阵
??? 　如下图(a)所示，它的下三角(不包括主角线)中的元素均为常数c。
②下三角矩阵
??? 　与上三角矩阵相反，它的主对角线上方均为常数c，如下图(b)所示。
? 注意：
　??? 在多数情况下，三角矩阵的常数c为零。

　　　

（2）三角矩阵的压缩存储
??? 三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n?(n+1)／2个，因此，三角矩阵可压缩存储到向量sa[0．．n(n+1)／2]中，其中c存放在向量的最后一个分量中。
??
① 上三角矩阵中a_ij和sa[k]之间的对应关系
??? 　上三角矩阵中，主对角线之上的第p行(0≤p<n)恰有n-p个元素，按行优先顺序存放上三角矩阵中的元素a<sub>ij时：
???? a_ij元素前有i行(从第0行到第i-1行)，一共有：
??????? (n-0)+(n-1)+(n-2)+…+(n-i)=i?(2n-i+1)／2个元素；
??? 　在第i行上，a_ij之前恰有j-i个元素(即a_ij，a_i,j+l，…，a_i,j-1)，因此有：
????????? sa[i?(2n-i+1)／2+j-i]= a_ij?
所以：
? ?　?┌i?(2n-i+1)／2+j-i 当i≤j
??　k=│
????? └n?(n+1)/2 当i＞j

②下三角矩阵中a_ij和sa[k]之间的对应关系
??　 ? ┌i?(i+1)／2+j 当i≥j
　?? k=│
??? 　 └n?(n+1)/2 当i＜j

? 注意：
??? 　三角矩阵的压缩存储结构是随机存取结构。

3．对角矩阵
??? 　所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零的矩阵为对角矩阵。
　　【例】下图给出了一个三对角矩阵。
???????????
???? 其中：
??? 非零元素仅出现在主对角上(a_ii，0≤i≤n-1)，紧邻主对角线上面的那条对角线上(a_i，i+1 ，0≤i≤n-2)和紧邻主对角线下面的那条对角线上(a _i+1，i，0≤i≤n-2)。当|i-j|>1时，元素a_ij=0。
??? 　由此可知，一个k对角线矩阵(k为奇数)A是满足下述条件的矩阵：
??????????? 若|i-j|>(k-1)／2，则元素a_ij=0。
??? 　对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。具体【参见练习】