矩阵在数值运算中很常见，本节关注如何存储矩阵的元，从而使矩阵的各种运算能有效进行。

如果矩阵中有许多相同值的元素或者很多零元素。有时为了节省存储空间，可以对这类矩阵进行存储压缩，称为稀疏矩阵。更进一步的，如果稀疏矩阵的相同值或零元素分布还是有规律的，我们可以称他们为特殊矩阵。

对称矩阵

例如：

1 2 4
2 3 5
4 5 6

我们可以为每一对称元分配一个存储空间，即可以将n^2个元压缩存储到n*(n+1)/2个空间中。

假设在线性(一元)数组中存储，下标是k。m[i][j]是矩阵中第i行第j列的元素，则：

当i>=j时，a[k] = m[i][j]，k=i*(i-1)/2 + j -1

当i<j时，a[k] = m[i][j]，k = j*(j-1)/2 +i -1

稀疏矩阵

设在m*n的矩阵中，有t个元素非零，则a=t/(m*n)称为稀疏因子，当a<=0.05，即只有不到5%的元素非零时，称为稀疏矩阵。

在很多问题中，实际都是稀疏矩阵。

压缩存储可以只存储非零元，例如用一个三元组表示：(i, j, val)，i和j是行、列，val是矩阵位置的元素值。

注意：在如下三元组存储中，data是从下标0开始的。但是矩阵的行、列是从1开始的！

下面是数据结构定义、初始化、打印等操作：

#include <stdio.h>
#include <memory.h>

#define MAX 1024

struct Triple
{
	int i,j; // row and column
	int value;
};

struct TMatrix
{
	struct Triple data[MAX]; // Triple
	int ndata; // number of data
	int rows; // row nums
	int cols; // col nums
};

void tmatrix_init(struct TMatrix* matrix)
{
	matrix->ndata = matrix->rows = matrix->cols = 0;
}

void tmatrix_print(struct TMatrix* matrix)
{
	int i,j;
	int k = 0;
	for(i=1;i<=matrix->rows;i++)
	{
		for(j=1;j<=matrix->cols;j++)
		{
			if(k<matrix->ndata && matrix->data[k].i==i && matrix->data[k].j==j)
			{
				printf("%3d ", matrix->data[k].value);
				k++;
			}else
			{
				printf("%3d ", 0);
			}
		}
		printf("\n");
	}
}

int main()
{
	// Init matrix m
	struct TMatrix m, t;
	tmatrix_init(&m);
	// Set m
	m.rows = 6;
	m.cols = 7;
	m.ndata = 8;
	m.data[0].i = 1;
	m.data[0].j = 2;
	m.data[0].value = 12;
	m.data[1].i = 1;
	m.data[1].j = 3;
	m.data[1].value = 9;
	m.data[2].i = 3;
	m.data[2].j = 1;
	m.data[2].value = -3;
	m.data[3].i = 3;
	m.data[3].j = 6;
	m.data[3].value = 14;
	m.data[4].i = 4;
	m.data[4].j = 3;
	m.data[4].value = 24;
	m.data[5].i = 5;
	m.data[5].j = 2;
	m.data[5].value = 18;
	m.data[6].i = 6;
	m.data[6].j = 1;
	m.data[6].value = 15;
	m.data[7].i = 6;
	m.data[7].j = 4;
	m.data[7].value = -7;
	// Fast Trans
	tmatrix_fast_transpose(&m, &t);
	// Print m
	//tmatrix_print(&m);
	tmatrix_print(&t);
	return 0;
}

快速转置算法

这样的存储虽然省了不少空间，但是在一些操作如转置时算法复杂度会上升很多。因为你无法再随机访问m[i][j]了。针对这种情况，有了如下的快速转置算法。它使用两个辅助向量，nrows和frows。这里的rows都是针对转置结果矩阵T而言的。（我们假设从矩阵M转置称为矩阵T）

首先计算nrows，它表示矩阵T中每一行有多少个非空元素即三元组需要存储。实际上也就是M中列j为对应nrows下标的。于是我们扫描一遍M.data的所有元素，对应j在nrows下标中++即可。

然后计算frows，就是T矩阵每一行第一个元素应该位于T的data的哪个位置。初始的第一个frows[1] = 0。这个需要解释下，因为矩阵行列开始都是1,所以frows里面是1,但是data存储是从0开始，所以起始是0。

最后就是快速转置算法，利用上面两个向量就很简单了，直接上代码：

// Transpose m to t
void tmatrix_fast_transpose(struct TMatrix* m, struct TMatrix* t)
{
	// Vars
	int nrows[MAX]; // Number of triple in new matrix t each row(t)
	int frows[MAX]; // First position in new matrix t each row(t)
	int i,j;
	// Basic dat
	t->rows = m->cols;
	t->cols = m->rows;
	t->ndata = m->ndata;
	// Calculate nrows(t), num of data same col in m
	memset(nrows, 0, MAX*sizeof(int));
	j=0;
	for(i=0;i<m->ndata;i++)
	{
		nrows[m->data[i].j]++;
	}
	// Calculate frows
	memset(frows, 0, MAX*sizeof(int));
	frows[1] = 0; // Matrix's row / col is 1/1, but in data, stores begin at [0]
	for(i=2;i<=m->ndata;i++)
	{
		frows[i] = frows[i-1] + nrows[i-1];
	}
	// Transpose
	for(i=0;i<m->ndata;i++)
	{
		t->data[frows[m->data[i].j]].j = m->data[i].i;
		t->data[frows[m->data[i].j]].i = m->data[i].j;
		t->data[frows[m->data[i].j]].value = m->data[i].value;
		frows[m->data[i].j]++;
	}

}