温州网站建设首选龙诚互联,wordpress建站博客园,网络推广外包哪家好,泰州专门做网站三元组稀疏矩阵是一种高效存储稀疏矩阵的方法。它通过记录矩阵中非零元素的行、列和值来表示一个稀疏矩阵。我们在三元组里存储的是每个元素的行、列以及值。
题目#xff1a; 任意输入一个稀疏矩阵M#xff0c;用三元组顺序表压缩存储该稀疏矩阵M#xff0c;然后求其转置矩… 三元组稀疏矩阵是一种高效存储稀疏矩阵的方法。它通过记录矩阵中非零元素的行、列和值来表示一个稀疏矩阵。我们在三元组里存储的是每个元素的行、列以及值。
题目 任意输入一个稀疏矩阵M用三元组顺序表压缩存储该稀疏矩阵M然后求其转置矩阵T并输出转置矩阵T。
思路
1、这里运用了快速转置降低时间复杂度
2、快速转置的核心是确定转置后矩阵每行的第一个非零元在三元表中的序号
3、详细在代码注释中
代码
#includeiostream
using namespace std;
typedef struct node
{int i, j, e;
}Triple;
typedef struct node1
{node data[1000];int mu, nu, tu0;//矩阵行数、列数、非零元个数
}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;}}
