稀疏矩阵的压缩矩阵

        如果一个矩阵中的大部分元素为零，称为稀疏矩阵。对于稀疏矩阵而言，时间存储的数据项很少，如果在程序中使用传统的二维数组方式来存储，则十分浪费存储空间，且矩阵越大，资源浪费越严重。为提内存空间利用率，可利用三项式（3-tuple）的数据结构，即把一个非零项用（i,j,item_value）来表示。其中array(0,0)存储稀疏矩阵的总行数，array(0,1)存储稀疏矩阵的总列数，其中array(0,2)存储稀疏矩阵非零项总数，从第1行开始依次存储稀疏矩阵的非零项所在行、列、非零值，这就是稀疏矩阵的压缩矩阵。

#include <iostream>
#include <cstdlib>
#include <iomanip>
using namespace std;

//稀疏矩阵行数、列数、非零项总数
const int ROWS = 11;
const int COLUMNS = 13;
const int NONZERO = 15;

int main()
{
	int iarrSparse[ROWS][COLUMNS];
	int iarrCompress[NONZERO][3];//压缩矩阵（三项式）
	int iarrCompressRows = 1; 
	int iRandROW,iRandColumn,iRandNonZero,iRandValue;
	int i,j;

	//随机生成稀疏矩阵
	iRandNonZero = NONZERO;
    for(i = 0;i < ROWS;i++)
	{
		for(j = 0;j < COLUMNS;j++)
		{
			iarrSparse[i][j] = 0;
		}
	}
	for(i = 0;i < iRandNonZero;i++)
	{
		iRandROW = rand() % ROWS;
		iRandColumn = rand() % COLUMNS;
		//如果随机生成的元素之前已随机生成过，则此次不算，循环+1，避免同一个元素设置多余1次，导致NONZERO个数不正确。
		if(0 != iarrSparse[iRandROW][iRandColumn])
		{
			iRandNonZero++;
			continue;
		}
		iRandValue = rand() % 100;
		iarrSparse[iRandROW][iRandColumn] = iRandValue > 0 ? iRandValue : 100;
	}
	cout << "稀疏矩阵为：" <<endl;
	for(i = 0;i < ROWS;i++)
	{
		cout << setw(4);
		for(j = 0;j < COLUMNS;j++)
		{
			cout << iarrSparse[i][j] << setw(4);
		}
		cout << endl;
	}

	//压缩稀疏矩阵
	iarrCompress[0][0] = ROWS;
	iarrCompress[0][1] = COLUMNS;
	iarrCompress[0][2] = NONZERO;
	for (i = 0;i < ROWS;i++)
	{
		for(j = 0;j < COLUMNS;j++)
		{
			if(0 != iarrSparse[i][j])
			{
				iarrCompress[iarrCompressRows][0] = i;
				iarrCompress[iarrCompressRows][1] = j;
				iarrCompress[iarrCompressRows][2] = iarrSparse[i][j];
				iarrCompressRows++;
			}
		}
	}
	cout << "压缩矩阵为：" <<endl;
	for(i = 0;i < NONZERO + 1;i++)
	{
		cout << setw(4);
		for(j = 0;j < 3;j++)
		{
			cout << iarrCompress[i][j] << setw(4);
		}
		cout << endl;
	}

	return true;
}