[数据结构] 稀疏矩阵的存储

【问题描述】

稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。

【基本要求】

以三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。

【Talk is cheap, show you the code】

#include<iostream>
// By Titan 2020-03-30
using namespace std;
typedef struct TupNode TUP;
typedef struct Matrix *TSM;

struct TupNode {
	int col;
	int row;
	int data;
};
struct Matrix {
	int cols;
	int rows;
	int nums;
	TUP data[100];
};

TSM inputData(int rows,int cols) {
	int a[rows][cols];
	for(int i=0; i<rows; i++) {
		for(int j=0; j<cols; j++) {
			cin>>a[i][j];
		}
	}
	TSM T=new Matrix;
	T->rows=rows;
	T->cols=cols;
	T->nums=0;
	for(int i=0; i<rows; i++) {
		for(int j=0; j<cols; j++) {
			if(a[i][j]!=0) {
				T->data[T->nums].data=a[i][j];
				T->data[T->nums].row=i;
				T->data[T->nums].col=j;
				T->nums++;
			}
		}
	}
	return T;
}

void printTSM(TSM T) {
	if(!T) {
		cout<<"Invalid TSMatrix!"<<endl;
		return;
	} else if(T->nums<=0) {
		cout<<"Invalid TSMatrix!"<<endl;
		return;
	}
	cout<< "Total Rows:" << T->rows << endl<<"Total Columns: " << T->cols << endl;
	cout<< "Non-Zero Elements Count: "<<T->nums<<endl;
	cout<<"--------------------------------------------------------"<<endl;
	cout<<"Row\tColumn\tData"<<endl;
	for(int i=0; i<T->nums; i++) {
		cout<<T->data[i].row
		    <<"\t"<<T->data[i].col
		    <<"\t"<<T->data[i].data
		    <<endl;
	}
}
void printAsArray(TSM T){
	if(!T){
		cout<<"Invalid TSMatrix!"<<endl;
		return;
	}
	int a,b,col,row,data;
	a=T->cols;
	b=T->rows;
	int arr[a][b];
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			arr[i][j]=0;
		}
	}
	for(int i=0;i<T->nums;i++){
		col=T->data[i].col;
		row=T->data[i].row;
		data=T->data[i].data;
		arr[row][col]=data;
	}
	for(int i=0;i<b;i++){
		for(int j=0;j<a;j++){
			cout<<arr[i][j]<<"\t";
		}
		cout<<endl;
	}
}
void insertTSM(TSM T,int data,int row,int col){
	if(!T){
		return;
	}
	bool flag=true;
	for(int i=0;i<T->nums;i++){
		if(T->data[i].col==col && T->data[i].row == row){
			T->data[i].data+=data;
			if(T->data[i].data==0){
				for(int j=T->nums-1;j>i;j--){
					T->data[j-1]=T->data[j];
				}
				T->nums--;
			}
			flag=false;
			break;
		}
	}
	if(flag){
		T->data[T->nums].col=col;
		T->data[T->nums].row=row;
		T->data[T->nums].data=data;
		T->nums++;
	}

}
TSM addTSM(TSM T1,TSM T2){
	if(T1->cols!=T2->cols || T1->rows!=T2->rows){
		return NULL;
	}
	TSM NT=new Matrix();
	NT->cols=T1->cols;
	NT->rows=T1->rows;
	NT->nums=0;
	for(int i=0;i<T1->nums;i++){
		insertTSM(NT,T1->data[i].data,T1->data[i].row,T1->data[i].col);
	}
	for(int i=0;i<T2->nums;i++){
		insertTSM(NT,T2->data[i].data,T2->data[i].row,T2->data[i].col);
	}
	return NT;
}

TSM subTSM(TSM T1,TSM T2){
	for(int i=0;i<T2->nums;i++){
		T2->data[i].data=-T2->data[i].data;
	}
	return addTSM(T1,T2);
}

int main() {
	int a,b,choice=-1;
	cout<<"Please input the total rows and columns:"<<endl;
	cin>>a>>b;
	TSM T1=inputData(a,b);
	printTSM(T1);
	cout<<"Please input the total rows and columns:"<<endl;
	cin>>a>>b;
	TSM T2=inputData(a,b);
	printTSM(T2);
	TSM NewT;
	cout<<"Please select the action(0=Addition,1=Subtraction:)"<<endl;
	while(choice !=0 && choice!=1){
		cin>>choice;
		if(choice==0){
			NewT=addTSM(T1,T2);
		}else if(choice==1){
			NewT=subTSM(T1,T2);
		}else{
			cout<<"Invilid Choice!"<<endl;
		}
	}
	cout<<"The New TSMatrix is:"<<endl; 
	printTSM(NewT);
	cout<<"------------------------------------"<<endl;
	cout<<"The New Matrix is:"<<endl; 
	printAsArray(NewT);
}