数据结构Java实现——④数组——>奇葩矩阵的压缩和还原

作者信息

写在前面

好吧，不得不说在家真的是不在状态，这一转眼都放假小一个月了，才复习了那么点东西，也是没SEI了，闲话少说，进入正题，今天整理奇葩矩阵的压缩和还原。

文字描述

矩阵的压缩：对于某些特殊的矩阵来说，非零元素较少，大部分元素为0，采用某种算法，将非零元素存储在一位数组里以达到节省存储空间的目的的过程，称为矩阵的压缩

矩阵的还原：将压缩后的数组还原成原始矩阵的过程

1、对角矩阵

①矩阵介绍

所谓对角矩阵：

矩阵中的所有非零元素都集中在以主对角线为中心的带状区域中，

即除了主对角线上和直接在主对角线上下若干条对角线上的元素外，其余元素均为零。

这样的矩阵称为半带宽为d的带状矩阵，带宽是2*d+1,d为直接在对角线上下方不为0的对角线数

② 矩阵压缩原理

对于n阶2d+1对角矩阵，只需要存放对角线区域内 n*（2*d+1）-d*(d+1)个非零元素

为了简便运算，认为每一行都有2*d+1个元素，若少于2*d+1个元素，则添零补齐。

因为非零元素都在主对角线元素的左右两侧，

那么只要在矩阵的每一行的主对角线元素的两侧分别  “凑够”  d个元素即可，

如果该元素  “不在"  矩阵内部，则补零，如果“在”矩阵内部，则存储到一维数组中即可

2、对称矩阵

① 矩阵介绍

 对称矩阵  array[ i ][ j ]=array[ j ][ i ]  所以对于相同的元素只保存一个

②矩阵压缩的原理

压缩成一个一维数组后 array [ i ]  [ j]  =array [ j ]  [ i  ]

s [ k ] = i * ( i + 1 ) / 2 + j = j * ( j + 1  ) / 2 + i ;

对于一个n阶的矩阵而言，压缩后一维空间的数目为  n*（n+1）/2;

3、三角矩阵

① 矩阵介绍

所谓三角矩阵：

整个矩阵只有主对角线及主对角线以上（或以下）为非零元素。

下三角形矩阵：主对角线及主对角线以下为非零元素

上三角形矩阵：主对角线及主对角线以上为非零元素

很显然对于一个n阶的矩阵而言，压缩后一维空间的数目为n*（n+1）/2;（等差数列求和）

（以下以下三角为例进行分析）

② 矩阵压缩的原理

根据该矩阵的性质，很容易得出结论

很显然第一行一个元素，第二行两个元素，依次类推。。。

代码实现

1、对角矩阵

import org.Stone6762.Utils.ArrayUtils;

/**
 * @Stone6762
 */
public class DiagonalArray {

	/**
	 * @Title: compress n阶2d+1对角矩阵的压缩
	 * @Description: TODO(n阶2d+1对角矩阵的压缩)
	 * @param oriArray
	 *            原始矩阵
	 * @param d
	 *            半带宽
	 * @return
	 */
	public static double[] compress(double[][] oriArray, int d) {
		int n = oriArray.length;
		double compressedArray[] = new double[n * (2 * d + 1)];
		int col = 0;
		for (int i = 0, k = 0; i < n; i++) {
			for (int j = -d; j <= d; j++, k++) {
				col = i + j;//计算对应的列值
				if (col >=0 && col < n) {//在矩阵内部的就赋值，不在矩阵内部的就直接补零
					compressedArray[k] = oriArray[i][col];
				}
			}
		}
		return compressedArray;
	}

	/**
	 * @Title: recover n阶2d+1对角矩阵的还原
	 * @Description: TODO()
	 * @param compressedArray
	 *            压缩后的矩阵
	 * @param d
	 *            半带宽
	 * @return
	 */
	public static double[][] recover(double[] compressedArray, int d) {
		int sum = compressedArray.length;
		int n = sum / (2 * d + 1);
		double[][] oriArray = new double[n][n];
		int col = 0;
		for (int i = 0, k = 0; i < n; i++) {
			for (int j = -d; j <= d; j++, k++) {
				col = i + j;
				if (col >= 0 && col < n) {
					oriArray[i][col] = compressedArray[k];
				}
			}
		}
		return oriArray;
	}

	public static void main(String[] args) {
		double[][] arr = { 
				{ 1, 2, 0, 0, 0 }, 
				{ 3, 4, 5, 0, 0 },
				{ 0, 6, 7, 8, 0 }, 
				{ 0, 0,9,10,11 }, 
				{ 0, 0, 0,12, 13 }

		};

		double[] tar = compress(arr,1);
//		[0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 0.0]

		ArrayUtils.printOneArray(tar);

		ArrayUtils.printMulArray(recover(tar,1));

	}

}

2、对称矩阵

import org.Stone6762.Utils.ArrayUtils;

/**
 * @Stone6762
 */
public class SymmetricalArray {

	/**
	 * @Title: compressSymmetricalArray 对称矩阵的压缩
	 * @Description: TODO(n阶方阵 对称矩阵（a[i][j]=a[j][i]）的压缩 此处采用的的是行优先顺序储存的方式)
	 * @param <T>
	 * @param oriArray
	 * @return
	 */
	public static double[] compress(double[][] oriArray) {
		int n = oriArray.length;
		double compressedArray[] = new double[n * (n + 1) / 2];
		for (int i = 0; i < oriArray.length; i++) {
			for (int j = 0; j <= i; j++) {
				compressedArray[i * (i + 1) / 2 + j] = oriArray[i][j];
			}
		}
		return compressedArray;
	}

	/**
	 * @Title: recoverSymmetricalArray
	 * @Description: TODO( 将压缩后的对称矩阵进行还原)
	 * @param compressedArray
	 * @return
	 */
	public static double[][] recover(double[] compressedArray) {
		int length = compressedArray.length;
		int n = (int) Math.sqrt(2 * length);
		double[][] oriArray = new double[n][n];
		for (int i = 0, k = 0; i < oriArray.length; i++) {
			for (int j = 0; j <= i; j++, k++) {
				oriArray[j][i] = oriArray[i][j] = compressedArray[k];
			}
		}
		return oriArray;
	}

	public static void main(String[] args) {
		double[][] arr = { 
				{ 1, 2, 3 },
				{ 2, 4, 6 }, 
				{ 3, 6, 5 } };

		double[] tar = compress(arr);
		// [1.0, 2.0, 4.0, 3.0, 6.0, 5.0]

		ArrayUtils.printOneArray(tar);

		ArrayUtils.printMulArray(recover(tar));

	}

}

3、三角矩阵

import org.Stone6762.Utils.ArrayUtils;

/**
 * @Stone6762
 */
public class TriangleArray {

	/**
	 * @Title: compress
	 * @Description: TODO(以下三角形为例压缩)
	 * @param oriArray
	 * @return
	 */
	public static double[] compress(double[][] oriArray) {
		int n = oriArray.length;
		double compressedArray[] = new double[n * (n + 1) / 2];
		for (int i = 0; i < oriArray.length; i++) {
			for (int j = 0; j <= i; j++) {
				compressedArray[i * (i + 1) / 2 + j] = oriArray[i][j];
			}
		}
		return compressedArray;
	}

	/**
	 * @Title: recover
	 * @Description: TODO(以下三角形为例解压)
	 * @param compressedArray
	 * @return
	 */
	public static double[][] recover(double[] compressedArray) {
		int length = compressedArray.length;
		int n = (int) Math.sqrt(2 * length);
		double[][] oriArray = new double[n][n];
		for (int i = 0, k = 0; i < oriArray.length; i++) {
			for (int j = 0; j <= i; j++, k++) {
				oriArray[i][j] = compressedArray[k];
			}
		}
		return oriArray;
	}

	public static void main(String[] args) {
		double[][] arr = { 
				{ 1, 0, 0 }, 
				{ 2, 4, 0 }, 
				{ 3, 6, 5 } };
		double[] tar = compress(arr);
		// [1.0, 2.0, 4.0, 3.0, 6.0, 5.0]

		ArrayUtils.printOneArray(tar);

		ArrayUtils.printMulArray(recover(tar));

	}

}