[数据结构与算法]数据结构4-多维数组-特殊矩阵的压缩

一.对称矩阵

1.分析

这种矩阵的上三角矩阵和下三角矩阵是完全一样的，重复的存储会造成将近一倍的空间浪费，我们希望找到一种方案只存储上三角矩阵或下三角矩阵来节约内存空间。

2.映射到一维数组

用一维数组按照行优先存储下三角元素
注意：由于一维数组的下标由0开始，所以原矩阵中的$a_{i,j}$在一维数组中对应的索引为$$i\times (i+1)/2+j$$

二.稀疏矩阵

1.分析

稀疏矩阵指的是含有较多为‘0’的元素，且分布没有规律的矩阵。一般系数因子小于0.05的矩阵被称为稀疏矩阵。因为很多0元素并没有意义，反而占据了很多内存空间。所以我们希望对矩阵进行压缩。

2.三元组顺序表&带行地址的二元组顺序表法

采用三元组顺序表，即将每一非零的元素单独拎出来，并记录下他们各自的行列坐标。

#define MAXSIZE 10000
typedef struct {//这个结构体用于存储非0的数据
	int i, j;//表示非零元素的行下标和列下标
	int element;//非零元素的值
}Datas;
typedef struct {
	Datas data[MAXSIZE];
	int rows, cols, num_of_elements;
}Matrix;

这种最原始的三元组数序表在进行操作时很不方便。比如，矩阵以二维数组存储时，可以根据行列坐标索引直接访问元素，但是按照三元组数序表存储时，仅有将整个顺序表遍历一遍找到对应的行列坐标，才能找到这个元素，效率大幅降低。
因此，我们可以采用带行地址数组的二元组顺序表。将行rows单独列出来，开一个一维数组，数组下标代表行数，对应的值代表这一行元素在二元组顺序表中的起始位置。

左图为三元组顺序表，右图为带行地址的二元组顺序表

3.快速转置算法

很容易发现，对于三元组数序表来说，如果要做转置操作，处理效率极低。

void trans(Matrix& source, Matrix& target) {//source是原矩阵，target空矩阵用于返回是转置后的矩阵
	target.cols = source.rows;
	target.rows = source.cols;
	target.num_of_elements = source.num_of_elements;
	int pos = 0;
	for (int i = 0; i < source.cols; i++) {
		for (int j = 0; j < source.num_of_elements; j++) {
			if (source.data[j].j == i) {
				target.data[pos].i = source.data[j].j;
				target.data[pos].j = source.data[j].i;
				target.data[pos++].element = source.data[j].element;
			}
		}
	}
}

为了提高转置的效率，我们需要设计一种能够快速转置的算法。其基本思想为：用空间换时间。通过引入辅助数组，做一些预先处理。

• rowSize[n]存放稀疏矩阵（source）第n列非零元素的个数。
• rowStart[n]存放转置后的矩阵（target）中，各行非零元素存储的起始位置。

void FastTran(Matrix& source, Matrix& target) {//source是原矩阵，target空矩阵用于返回是转置后的矩阵
	//开辟辅助数组并处理
	int rowSize[100] = {0,};
	for (int k = 0; k < source.num_of_elements; k++) {
		rowSize[source.data[k].j]++;
	}
	int rowStart[100] = {0,};
	for (int k = 1; k < source.cols; k++) {
		rowStart[k] = rowStart[k - 1] + rowSize[k - 1];
	}

	target.cols = source.rows;
	target.rows = source.cols;
	target.num_of_elements = source.num_of_elements;

	for (int k = 0; k < source.num_of_elements; k++) {
		int pos = rowStart[source.data[k].j]++;
		//rowStart自增是为了保证元素指向该下标(代表行)下一次应填入的位置
		target.data[pos].i = source.data[k].j;
		target.data[pos].j = source.data[k].i;
		target.data[pos].element = source.data[k].element;
	}
}