#include <iostream>
using namespace std;
int main(int argc, char** argv) {
	//對(duì)稱(chēng)矩陣
	int nums[4][4]= { {3,5,6,8},{5,4,7,9},{6,7,12,10},{8,9,10,13} };
	//一維數(shù)組，根據(jù)上述公式，一維數(shù)組長(zhǎng)度為 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}};
//轉(zhuǎn)置后矩陣
int bArray[5][4];
//轉(zhuǎn)置算法 
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
//三元組結(jié)構(gòu)
struct Node {
	//行號(hào)
	int row=-1;
	//列號(hào)
	int col=-1;
	//非零元素的值
	DataType val=0;
} ;

//維護(hù)三元組表的類(lèi)
class Matrix {
	private:
		//位置編號(hào)
		int idx=0;
		//壓縮前稀疏矩陣的行數(shù)
		int rows;
		//壓縮前稀疏矩陣的列數(shù)
		int cols;
		//原稀疏矩陣中非零數(shù)據(jù)的個(gè)數(shù)
		int terms;
		//壓縮存儲(chǔ)的一維數(shù)組，初始化
		Node node;
		Node data[maxSize]= {node};
	public:
		//構(gòu)造函數(shù)
		Matrix(int row,int col) {
			this->rows=row;
			this->cols=col;
             this->terms=0;
		}
		//存儲(chǔ)三元結(jié)點(diǎn)
		void setData(int row ,int col,int val) {
			Node n;
			n.row=row;
			n.col=col;
			n.val=val;
			this->data[idx++]=n;
             //記錄非零數(shù)據(jù)的數(shù)量
             this->terms++;
		}
        //重載上面函數(shù)
    	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++;
		}
		//顯示三無(wú)組表中的數(shù)據(jù)
		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;
			}
		}
		//基于三元組表的轉(zhuǎn)置算法
		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}};
	//實(shí)例化
	Matrix matrix(4,5);
	//壓縮矩陣
	for(int row=0; row<4; row++) {
		for(int col=0; col<5; col++) {
			if (aArray[row][col]!=0) {
                 //轉(zhuǎn)存至三元組表中
				matrix.setData(row,col,aArray[row][col]);
			}
		}
	}
	matrix.showInfo();
	return 0;
}

Matrix Matrix::transMatrix(){
	//轉(zhuǎn)置后的三元組表對(duì)象
	Matrix bMatrix(this->cols,this->rows);
	//對(duì)原稀疏矩陣以列優(yōu)先搜索
	for(int c=0;c<this->cols;c++){
		//在對(duì)應(yīng)的三元組表上查找此列上是否有非零數(shù)據(jù)
	 	for(int j=0;j<this->terms;j++ ){
	 		if(this->data[j].col==c){
	 			//如果此列上有數(shù)據(jù)，則轉(zhuǎn)置并保存
				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}};
//實(shí)例化壓縮矩陣
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 稀疏矩陣壓縮后的結(jié)果："<<endl; 
matrix.showInfo();
cout<<"在A的三元組表的基礎(chǔ)上轉(zhuǎn)置后的結(jié)果："<<endl;
Matrix bMatrix= matrix.transMatrix();
bMatrix.showInfo(); 	 
return 0;
}

Matrix Matrix::transMatrix() {
	//保存轉(zhuǎn)置后數(shù)據(jù)的壓縮矩陣
	Matrix bMatrix(this->cols,this->rows);
	//初始化數(shù)組，用來(lái)保存A稀疏矩陣中第一列中非零數(shù)據(jù)的個(gè)數(shù)
	int counts[this->cols]= {0};
	//計(jì)算每一列中非零數(shù)據(jù)個(gè)數(shù)
	for(int i=0; i<this->terms; i++)
		counts[this->data[i].col]++;
	//初始化數(shù)組，用來(lái)保存A稀疏矩陣每列中非零數(shù)據(jù)在B三元組表中的起始位置
	int position[this->cols]= {0};	
	for(int i=1;i<this->cols;i++ ){
        //上一列的起始位置加上上一列非零數(shù)據(jù)的個(gè)數(shù)
		position[i]=position[i-1]+counts[i-1];
	}
    //轉(zhuǎn)置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三元組中的起始存儲(chǔ)位置
		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}};
	//實(shí)例化壓縮矩陣
	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 稀疏矩陣壓縮后的結(jié)果："<<endl;
	matrix.showInfo();
	cout<<"在A的三元組表的基礎(chǔ)上轉(zhuǎn)置后的結(jié)果："<<endl;
	Matrix bMatrix= matrix.transMatrix();
	bMatrix.showInfo();
	return 0;
}