北京市建设教育协会网站北京住房城乡建设部网站八大员

  三元组稀疏矩阵是一种高效存储稀疏矩阵的方法。它通过记录矩阵中非零元素的行、列和值来表示一个稀疏矩阵。我们在三元组里存储的是每个元素的行、列以及值。

题目：

  任意输入一个稀疏矩阵M，用三元组顺序表压缩存储该稀疏矩阵M，然后求其转置矩阵T，并输出转置矩阵T。

思路： 

1、这里运用了快速转置，降低时间复杂度

2、快速转置的核心是确定转置后矩阵，每行的第一个非零元在三元表中的序号

3、详细在代码注释中

代码：

#include<iostream>
using namespace std;
typedef struct node
{int i, j, e;
}Triple;
typedef struct node1
{node data[1000];int mu, nu, tu=0;//矩阵行数、列数、非零元个数
}TSMatrix;
void Transpose(TSMatrix m, TSMatrix& t)
{int num[100]={0}, head[100];t.mu = m.nu, t.nu = m.mu, t.tu = m.tu;if (t.tu)//非零元不为0个，则做下列操作{for (int i = 1; i <= t.mu; i++)//逆置矩阵的列变行，初始每行中的非零元个数为0num[i] = 0;for (int i = 1; i <= t.tu; i++)//遍历非零元num[m.data[i].j]++;//列变行，m中每列的非零元个数就是t中每列非零元的个数head[1] = 1;for (int i = 2; i <= t.mu; i++)//遍历t的行数head[i] = head[i - 1] + num[i-1];//每行的第一个非零元在三元表中的序号for (int i = 1; i <= t.tu; i++)//遍历非零元{int col = m.data[i].j;//取非零元的列数int l = head[col];//该列要存储的位置t.data[l].i = m.data[i].j, t.data[l].j = m.data[i].i;//行转列，列转行t.data[l].e = m.data[i].e;head[col]++;//该列元素下次存储往下一位}}
}
int main()
{TSMatrix m,t;int ju[51][51];cout << "输入行数，列数：" << endl;cin >>m.mu >> m.nu;for (int i = 1; i <= m.mu; i++)//输入初始矩阵,建立三元组for (int j = 1; j <= m.nu; j++){cin >> ju[i][j];if (ju[i][j] != 0){m.tu++;m.data[m.tu].e = ju[i][j];m.data[m.tu].i = i, m.data[m.tu].j = j;}}Transpose(m, t);//for (int i = 1; i <= m.tu; i++)//cout << m.data[i].e << " " << m.data[i].i << " " << m.data[i].j << endl;//cout << endl;//for (int i = 1; i <= t.tu; i++)//cout << t.data[i].e << " " << t.data[i].i << " " << t.data[i].j << endl;cout << "逆置后矩阵：" << endl;int k = 1;for (int i = 1; i <= t.mu; i++){for (int j = 1; j <= t.nu; j++){if (t.data[k].i == i && t.data[k].j == j)cout << t.data[k++].e << " ";elsecout << "0 ";}cout << endl;}}