C++ 特殊矩阵的压缩存储算法

#include <iostream>
using namespace std;
int main(int argc, char** argv) {
	//对称矩阵
	int nums[4][4]= { {3,5,6,8},{5,4,7,9},{6,7,12,10},{8,9,10,13} };
	//一维数组，根据上述公式，一维数组长度为 4*(4+1)/2=10
	int zipNums[10]= {0};
	for(int i=0; i<4; i++) {
		for(int j=0; j<4; j++) {
			if (i>=j) {
				zipNums[ i*(i+1)/2+j]=nums[i][j];
			} else {
				zipNums[ j*(j+1)/2+i]=nums[i][j];
			}
		}
	}
	for(int i=0; i<10; i++) {
		cout<<zipNums[i]<<"\t";
	}
	return 0;
}

//原矩阵
int aArray[4][5]= {{0,5,0,1,0},{0,0,3,0,0},{0,7,0,0,0},{0,0,9,0,0}};
//转置后矩阵
int bArray[5][4];
//转置算法 
for(int row=0; row<4; row++) {
	for(int col=0; col<5; col++) {
		bArray[col][row]=aArray[row][col];
	}
}

#include <iostream>
using namespace std;
typedef int DataType;
#define maxSize 100
//三元组结构
struct Node {
	//行号
	int row=-1;
	//列号
	int col=-1;
	//非零元素的值
	DataType val=0;
} ;

//维护三元组表的类
class Matrix {
	private:
		//位置编号
		int idx=0;
		//压缩前稀疏矩阵的行数
		int rows;
		//压缩前稀疏矩阵的列数
		int cols;
		//原稀疏矩阵中非零数据的个数
		int terms;
		//压缩存储的一维数组，初始化
		Node node;
		Node data[maxSize]= {node};
	public:
		//构造函数
		Matrix(int row,int col) {
			this->rows=row;
			this->cols=col;
             this->terms=0;
		}
		//存储三元结点
		void setData(int row ,int col,int val) {
			Node n;
			n.row=row;
			n.col=col;
			n.val=val;
			this->data[idx++]=n;
             //记录非零数据的数量
             this->terms++;
		}
        //重载上面函数
    	void setData(int index,int row ,int col,int val) {
			Node n;
			n.row=row;
			n.col=col;
			n.val=val;
			this->data[index]=n;
			this->terms++;
		}
		//显示三无组表中的数据
		void showInfo() {
			for(int i=0; i<maxSize; i++ ) {
				if(data[i].val==0)break;
				cout<<data[i].row<<"\t"<<data[i].col<<"\t"<<data[i].val<<endl;
			}
		}
		//基于三元组表的转置算法
		Matrix transMatrix();
};

int main(int argc, char** argv) {
	//原稀疏矩阵
	int aArray[4][5]= {{0,5,0,1,0},{0,0,3,0,0},{0,7,0,0,0},{0,0,9,0,0}};
	//实例化
	Matrix matrix(4,5);
	//压缩矩阵
	for(int row=0; row<4; row++) {
		for(int col=0; col<5; col++) {
			if (aArray[row][col]!=0) {
                 //转存至三元组表中
				matrix.setData(row,col,aArray[row][col]);
			}
		}
	}
	matrix.showInfo();
	return 0;
}

Matrix Matrix::transMatrix(){
	//转置后的三元组表对象
	Matrix bMatrix(this->cols,this->rows);
	//对原稀疏矩阵以列优先搜索
	for(int c=0;c<this->cols;c++){
		//在对应的三元组表上查找此列上是否有非零数据
	 	for(int j=0;j<this->terms;j++ ){
	 		if(this->data[j].col==c){
	 			//如果此列上有数据，则转置并保存
				bMatrix.setData(this->data[j].col,this->data[j].row,this->data[j].val);  
			 }
		 } 
	}
	return  bMatrix;
}

int main(int argc, char** argv) {
//原稀疏矩阵
int aArray[4][5]= {{0,5,0,1,0},{0,0,3,0,0},{0,7,0,0,0},{0,0,9,0,0}};
//实例化压缩矩阵
Matrix matrix(4,5);
//压缩矩阵
for(int row=0; row<4; row++) {
	for(int col=0; col<5; col++) {
		if (aArray[row][col]!=0) {
			matrix.setData(row,col,aArray[row][col]);
		}
	}
}
cout<<"显示 A 稀疏矩阵压缩后的结果："<<endl; 
matrix.showInfo();
cout<<"在A的三元组表的基础上转置后的结果："<<endl;
Matrix bMatrix= matrix.transMatrix();
bMatrix.showInfo(); 	 
return 0;
}

Matrix Matrix::transMatrix() {
	//保存转置后数据的压缩矩阵
	Matrix bMatrix(this->cols,this->rows);
	//初始化数组，用来保存A稀疏矩阵中第一列中非零数据的个数
	int counts[this->cols]= {0};
	//计算每一列中非零数据个数
	for(int i=0; i<this->terms; i++)
		counts[this->data[i].col]++;
	//初始化数组，用来保存A稀疏矩阵每列中非零数据在B三元组表中的起始位置
	int position[this->cols]= {0};	
	for(int i=1;i<this->cols;i++ ){
        //上一列的起始位置加上上一列非零数据的个数
		position[i]=position[i-1]+counts[i-1];
	}
    //转置A三元组表
    for(int i=0;i<this->terms;i++){ 
    	int col=this->data[i].col;
    	int row=this->data[i].row;
    	int val=this->data[i].val;
    	//找到在B三元组中的起始存储位置
		int pos=position[col];
		bMatrix.setData(pos,col,row,val);
		position[col]++;	
	} 
	return  bMatrix;
}

int main(int argc, char** argv) {
	//原稀疏矩阵
	int aArray[4][5]= {{0,5,0,1,0},{0,0,3,0,0},{0,7,0,0,0},{0,0,9,0,0}};
	//实例化压缩矩阵
	Matrix matrix(4,5);
	//压缩矩阵
	for(int row=0; row<4; row++) {
		for(int col=0; col<5; col++) {
			if (aArray[row][col]!=0) {
				matrix.setData(row,col,aArray[row][col]);
			}
		}
	}
	cout<<"显示 A 稀疏矩阵压缩后的结果："<<endl;
	matrix.showInfo();
	cout<<"在A的三元组表的基础上转置后的结果："<<endl;
	Matrix bMatrix= matrix.transMatrix();
	bMatrix.showInfo();
	return 0;
}