稀疏矩阵的压缩存储表示及实现（1）三元组顺序表按照压缩存储的概念，只需存储稀疏矩阵的非零元。因此除了存储非零元的值之外，还
必须同时记住它所在的行和列的位置（i，j）。即：一个三元组（i，j，aij）唯一确定了矩阵的一个非零元。
因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。例如：01290000
00-300150000000
12000180M=-30000140T=90
0240000240000000
00–70180000000000
01500–70000014000
000000数据结
构第5章T的三元组描述(1,3,-3)(1,6,15)(2,1,12)(2,
5,18)(3,1,9)(3,4,24)(4,6,-7)(6,3,
14)加上(7,6)M的三元组描述(1,2,12)(1,3,9)(3,1,
-3)(3,6,14)(4,3,24)(5,2,18)(6,1,15)
(6,4,-7)加上(6,7)#defineMAXSIZE12500typedefstruc
t{inti,j;//该非零元的行下标和列下标ElemTypee;//该
非零元的值}Triple;//三元组类型三元组顺序表存储表示typedefstruct{
Tripledata[MAXSIZE+1];//data[0]未用intmu,nu,tu;
}TSMatrix;//稀疏矩阵类型如何求转置矩阵？稀疏矩阵基本操作的实现利用三元组
顺序表法存储稀疏矩阵实现矩阵转置运算矩阵转置：将一个mn的矩阵M转置成一个nm的矩阵T，且T(i,j)=M(j,i),
1≤i≤n,1≤j≤m用常规的二维数组表示时的算法其时间复杂度为:O(mu×nu)for(col=1;
col<=nu;++col)for(row=1;row<=mu;++row)T[c
ol][row]=M[row][col];？用“三元组”表示时如何实现？121415-522
-731363428ijvM.data1336211422-74
32851-5ijvT.data观察M->T需三步：211451-52
2-713364328ijv1.将矩阵的行列值互换2.将每个三元组中的i和j对调
3.按行序重排三元组第三步的实现有两种处理方法：第一种方法：按照T.data中三元组的次序在M.data
中找到相应的三元组进行转置。即：按原矩阵的列从小到大重新排序。121415-5
22-731363428ijvM.data1336211422
-7432851-5ijvT.data具体做法：（1）为了找到M的一列中所有的非
零元素，需要对其三元组表M.data从第一行起整个扫描一遍。121415-5
22-731363428ijvM.data（2）要找到所有列非零元素，需重复做第一步
M.nu次for(p=1;p<=M.tu;++p)1P13362114
432851-5ijvT.dataT.data[q].i=M.data[p].j;T.d
ata[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++q;if(M.data[
p].j==){}PPPqqP
P2for(col=1;col<=M.nu;++col)q=1COLq22-7PP
q完整程序如下：StatusTransposeSMatrix(TSMatrixM,TSMatrix&T)
{T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){q=1;
for(col=1;col<=M.nu;++col)for(p=1;p<=M.t
u;++p)if(M.data[p].j==col)
{T.data[q].i=M.data[p].jT.data[q].j=M.da
ta[p].i;T.data[q].e=M.data[p].e;++q;}
}returnOK;}时间复杂度：O（nutu)第三步的实现有两种处理方法：第二种方法：按照M.
data中三元组的次序进行转置，并将转置后的三元组置入T中恰当位置。12
1415-522-731363428ijvM.data1336
211422-7432851-5ijvT.data①②④⑤若能预先确
定矩阵M中每一列（即T中每一行）的第一个非零元素在T.data中应有的位置，那么在对M.data中的三元组依次作转置时，便可直接放
到T.data中的恰当位置。关键的问题：求M的每一列第一个非零元在T.data中的位置。首先应求得Ｍ的每一列中非零元的个
数，进而求得每一列的第一个非零元在Ｔ三元组中的位置。需设两个向量num和cpot，辅助求得。cpot[1]=1;
cpot[col]=cpot[col-1]+num[col-1]2≤col≤m.nucpot[1]=
1;for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-
1]+num[col-1];121415-522-731363428i
jvM.datacol12345num[
col]12011Cpot[col]124
45StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){
T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for
(col=1;col<=M.nu;++col)num[col]=0;for(t=1;t<=M.tu;+
+t)++num[M.data[t].j];cpot[1]=1;for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=M.tu;++p){}}//ifreturnOK;}//FastTransposeSMatrix转置矩阵元素 |
|
