#include<iostream>//cout,cin
using namespace std;


struct MNode											//三元组结点
{
	int i, j;											//行号，列号
	int e;												//非零元
};


struct TSMatrix
{
	int mu, nu, tu;										// 行数、列数、非零元个数
	MNode* data;										// 三元组表
};

TSMatrix MCreate(int d[][3], int m, int n, int k)			//由三元组的二维数组生成行向量稀疏存储矩阵
{
	TSMatrix M = { m,n,k,NULL };
	if (k != 0)
		M.data = new MNode[k];
	for (int i = 0; i < k; i++)
	{
		M.data[i].i = d[i][0];
		M.data[i].j = d[i][1];
		M.data[i].e = d[i][2];
	}
	return M;
}//


void MDisp(TSMatrix a)									//矩阵显示
{
	MNode p;
	int i, j, k = 0, c = 0;
	p = a.data[k];
	for (i = 0; i < a.mu; i++)
	{
		for (j = 0; j < a.nu; j++)
		{
			if (k < a.tu && p.i == i && p.j == j)
			{
				cout << '\t' << p.e;
				k++;
				if (k < a.tu) p = a.data[k];
			}
			else
			{
				cout << '\t' << c;
			}
		}//for
		cout << endl;
		cout << endl;
	}//for
}//MatrixDisp

//算法4.1											转置算法一
void MatrixTrans_1(TSMatrix A, TSMatrix& B)
{//
	int col, p, q;
	B.mu = A.nu; B.nu = A.mu; B.tu = A.tu;					//B的行数、列数、非零元个数分别等于A的列数、行数和非零元个数
	if (B.tu)										// 矩阵B有非零元
	{
		q = 0;
		for (col = 0; col < A.nu; ++col)					// 按列扫描A矩阵
			for (p = 0; p < A.tu; ++p)
				if (A.data[p].j == col)				// col列有非零元
				{
					B.data[q].i = A.data[p].j;		// 交换行、列号，生成转置元素
					B.data[q].j = A.data[p].i;
					B.data[q].e = A.data[p].e;
					++q;
				}
	}
}



//算法4.2											快速转置
void MatrixTrans_2(TSMatrix A, TSMatrix& B)
{
	int col, i, k, q;
	int* num, * cpot;
	B.mu = A.nu; B.nu = A.mu; B.tu = A.tu;					//B的行数、列数、非零元个数分别等于A的列数、行数和非零元个数
	num = new int[B.nu];
	cpot = new int[B.nu];
	if (B.tu)										// 非零元个数不为零，实施转置
	{
		for (col = 0; col < A.nu; col++)					//A中每一列非零元个数初始化为0
			num[col] = 0;
		for (i = 0; i < A.tu; i++)							//求矩阵A中每一列非零元个数
			num[A.data[i].j]++;
		cpot[0] = 0;									//A中第0列首个非零元在B中的下标
		for (col = 1; col <= A.nu; ++col)					// 求A中每一列首个非零元在B中的下标
			cpot[col] = cpot[col - 1] + num[col - 1];
		for (k = 0; k < A.tu; ++k)							//扫描A的三元组表
		{
			col = A.data[k].j;						//当前三元组列号
			q = cpot[col];							//当前三元组在B中的下标
			B.data[q].i = A.data[k].j;
			B.data[q].j = A.data[k].i;
			B.data[q].e = A.data[k].e;
			cpot[col]++;							// 预置同一列下一个三元组在B中的下标
		}//for
	}//if
}//



void main()
{
	TSMatrix ma, mb1, mb2;
	int m1 = 4, n1 = 6, k1 = 6;								//被乘矩阵行数，列数，非零元个数
	int da[6][3] = { {0,2,11},{0,4,12},{1,3,22},
	{2,1,31},	{2,3,32},{3,0,41} };					//ma阵的非零元
	ma = MCreate(da, m1, n1, k1);                        //生成三元组顺序存储的ma阵
	cout << "ma=" << endl;
	MDisp(ma);                                      //显示ma阵
	mb1.data = new MNode[ma.tu];
	mb2.data = new MNode[ma.tu];
	cout << "方法一：直接取，顺序存" << endl;           //用方法一转置矩阵
	MatrixTrans_1(ma, mb1);
	cout << "mb=" << endl;                              //显示转置矩阵
	MDisp(mb1);
	cout << "方法二：顺序取，直接存" << endl;           //用方法二转置矩阵
	MatrixTrans_2(ma, mb2);
	cout << "mb=" << endl;                              //显示转置矩阵
	MDisp(mb2);
}//