java数据结构之多维数组实现

多维数组其实就是数组的一种扩展形式。这里介绍几种特殊的多维数组即特殊的矩阵。

1.对称矩阵的压缩存储算法：

矩阵中的所有数据通过一定的规律存储在一维数组中。其中k=j*(j-1)/2+i-1。其中j和i是矩阵中的j和i而k是一维数组的下标号。

2.三角矩阵的压缩存储：

矩阵下标i和j的在一维数组k中对应的公式为：

当i<=j

k=i*(i-1)/2+j-1;

当i>j

k=n*(n+1)/2;

3.对角矩阵的压缩存储：

一种是通过m*n的w对的对角矩阵进行压缩。将原数组压缩到一个m行w列的数组去。映射关系为：t=i; s=j-i+2;（t，s为新数组的行和列）。

第二种是将数组存储到一维数组中去，对应的映射关系为：k=2*i+j-3;（k为一维数组中的下标）。

4.稀疏矩阵的压缩存储：

一种是通过：三元组顺序表实现。

int row,col;//行数，列数
DataType item;//存储的元素
element data[max];//用来存储的数组
int mu,nu,tu//分别是行数，列数，非零元素个数

第二种是通过：十字链表实现。

element//数据域，存储非零元素对应的三元组（包含row,col,item）
down//为指针域，指向同一列中下一个三元组
right//为指针域，指向同一行中下一个三元组