C++ 稀疏矩阵的转置
问题描述
问题陈述：稀疏矩阵的转置操作
设计思路概述
设计思路：稀疏矩阵中包含大量非零元素，若直接进行转置操作将导致较高的时间消耗。因此，选择采用三元组形式进行表示。依据压缩存储的理念，仅需保留稀疏矩阵中的非零元素，并且除了记录这些元素的数值外，还需同时标明其对应的行与列的位置信息。三元组表示法是通过一个包含三个数据域的一维数组来描述稀疏矩阵，其中每一行均包括三个字段，分别对应该元素的行号、列号以及数值。假设A和B分别为某一稀疏矩阵在转置前后的三元组表，i代表行号，j代表列号，v为元素的值。变量m表示稀疏矩阵的行数，n表示列数，tu则用于记录非零元素的数量。该算法的核心目标是将A中的行号与列号交换后存入B中，并确保B中的行号仍按照递增顺序排列。
数据结构：
i：行号
j：列号
v：数值
tu：非零元素数量
A：转置前的矩阵
B：转置后的矩阵
Ai：转置前的三元组表项
Bi：转置后的三元组表项
t[0]：工作数组
算法描述与实现
TRANSMAT ( A , B)
- 若 tu 不等于零，则执行以下操作
- { q<-1 //q 表示转置后 B 的行号//
- 对于列从 1 到 n 的每一个值
- 对于 p 从 1 到 tu 的每一个值 //p 表示转置前 A 的行号//
- 如果 A[p].j 等于当前列，则执行以下步骤
- { 将 B[q].i 设为 a[p].j；将 B[q].j 设为 A[p].i；
将 B[q].v 设为 A[p].v；q 增加 1 } - 结束 p 循环
- 结束列循环 }
- 返回结果
测试用例及结果说明
测试用例：稀疏矩阵元素为
A[0][0]=3;
A[0][4]=7;
A[1][2]=-1;
A[2][0]=-1;
A[2][1]=-2;
A[4][3]=2;
测试结果：
转置前矩阵A：
3 0 0 0 7
0 0 -1 0 0
-1 -2 0 0 0
0 0 0 0 0
0 0 0 2 0
工作三元组Ai：
1 1 3
1 5 7
2 3 -1
3 1 -1
3 2 -2
5 4 2
工作三元组Bi：
1 1 3
1 3 -1
2 3 -2
3 2 -1
4 5 2
5 1 7
转置后矩阵：
3 -1
7
设计与测试流程概述
第一步：明确待解决的疑问；
第二步：将原始疑问进行形式上的转化；
第三步：设计相应的计算方法；
第四步：以类代码形式进行逻辑描述；
第五步：编写实际运行的程序代码；
第六步：对所编写代码进行功能验证；
第七步：根据测试结果对代码进行调整与优化；
参考书籍：
《计算机软件技术基础》由清华大学出版社出版，为第三版。
#include<iostream>
using namespace std;
#define N 5
struct node
{
int i;
int j;
int v;
}Ai[N*N],Bi[N*N],t[1];
int main()
{
int A[N][N],B[N][N],a,b,tu=0,i,j=0;
node *q;
for(a=0;a<N;a++)
for(b=0;b<N;b++)
{
A[a][b]=0;
B[a][b]=0;
}
A[0][0]=3;
A[0][4]=7;
A[1][2]=-1;
A[2][0]=-1;
A[2][1]=-2;
A[4][3]=2;
cout<<"转置前矩阵为"<<endl;
for(a=0;a<N;a++)
{
for(b=0;b<N;b++)
cout<<A[a][b]<<'\t';
cout<<endl;
}
for(a=0;a<N;a++)
for(b=0;b<N;b++)
if(A[a][b]!=0)
{
Ai[tu].i=a+1;
Ai[tu].j=b+1;
Ai[tu].v=A[a][b];
tu++;
}
cout<<"转置前矩阵等效三元组为"<<endl;
for(i=0;i<tu;i++)
cout<<Ai[i].i<<'\t'<<Ai[i].j<<'\t'<<Ai[i].v<<endl;
for(i=0;i<tu-1;i++)
{
int min=i;
for(j=i+1;j<tu;j++)
if(Ai[j].j<Ai[min].j)
min=j;
t[0].i=Ai[i].i;
t[0].j=Ai[i].j;
t[0].v=Ai[i].v;
Ai[i].i=Ai[min].i;
Ai[i].j=Ai[min].j;
Ai[i].v=Ai[min].v;
Ai[min].i=t[0].i;
Ai[min].j=t[0].j;
Ai[min].v=t[0].v;
}
for(i=0;i<tu;i++)
{
Bi[i].i=Ai[i].j;
Bi[i].j=Ai[i].i;
Bi[i].v=Ai[i].v;
}
cout<<"转置后矩阵等效三元组为"<<endl;
for(i=0;i<tu;i++)
cout<<Bi[i].i<<'\t'<<Bi[i].j<<'\t'<<Bi[i].v<<endl;
for(i=0;i<tu;i++)
{
a=Bi[i].i-1;
b=Bi[i].j-1;
B[a][b]=Bi[i].v;
}
cout<<"转置后矩阵为"<<endl;
for(a=0;a<N;a++)
{
for(b=0;b<N;b++)
cout<<B[a][b]<<'\t';
cout<<endl;
}
system("pause");
return 0;
}