5.3 矩阵的压缩存储
?矩阵, 二维数组
?特殊矩阵, 大量重复元素或大量 0元素
?稀疏矩阵, 大量 0元素
?压缩存储, 重复元素只分配一个存储空
间,0元素不分配存储空间
5.3.1 特殊矩阵
? 对称矩阵, aij = aji (1<=i,j<=n)
? 下三角矩阵, 当 i<j时,aij = 0,(1<=i,j<=n)
? 三对角矩阵, 当 |i-j| > 1时,aij = 0,(1<=i,j<=n)
a11 a12 a13,.,a1n
a21 a22 a23,.,a2n
a31 a32 a33,.,a3n
......
an1 an2 an3,.,ann
Anxn =
对称矩阵, aij = aji (1<=i,j<=n)
存储元素数, 1+2+...+n = n(n+1)/2
? 一维数组 SA[1..n(n+1)/2]作为数组 A下三角元素的
? 存储结构,
? SA[k] = [a11,a21,a22,a31,...,an1,...,ann]
? k = 1 2 3 4 n(n-1)/2+1 n(n+1)/2
? SA[k]和 A[i,j]的一一对应关系,
? i(i-1)/2 + j 当 i >= j
? k = {
? j(j-1)/2 + i 当 i < j
例 5.3 对称矩阵
?n = 5,1+2+3+4+5 = 5*(5+1)/2 = 15
? 一维数组 SA[1..15]作为数组 A的存储结构,
?SA=(4 5 2 3 1 3 2 5 2 8 1 6 7 9 5)
? 如, a[5,3] = a[3,5] = 7
? k = 5(5-1)/2 + 3 = 13
? 故,sa[13] = 7
4 5 3 2 1
5 2 1 5 6
3 1 3 2 7
2 5 2 8 9
1 6 7 9 5
A =
4
5 2 0
3 1 3
2 5 2 8
1 6 7 9 5
A =
下三角矩阵,
当 i<j时,aij = 0,(1<=i,j<=n)
? 同样用一维数组 SA[1..n(n+1)/2]作为数组 A非
零元素的存储结构,
?sa[k]和 a[i,j]的一一对应关系,
? sa[k],k = i(i-1)/2 + j
?a[i,j] = { (当 i >= j)
? 0 (当 i < j)
例 5.4 下三角矩阵
? 4 0 0 0 0
? 5 2 0 0 0
? A = 3 1 3 0 0
? 2 5 2 8 0
? 1 6 7 9 5
? 如, a[5,3] = 7
? k = 5(5-1)/2 + 3 = 13
? 故,sa[13] = 7 但 a[3,5] = 0
三对角矩阵,
当 |i-j| > 1时,aij = 0,(1<=i,j<=n)
? a11 a12 0 0,.,0
? a21 a22 a23 0,.,0
?Anxn = 0 a32 a33 a34,.,0
?,.....
? 0 0 0,.,ann-1 ann
? 一维数组 SA[1..3*n-2]作为数组 A下三角元素的
存储结构,
? SA[k]=[a11,a12,a21,a22,a23,a32,a33,a34,...,ann-1,ann]
? k = 1 2 3 4 5 6 7 8 3n-3 3n-2
? sa[k]和 a[i,,j]的一一对应关系,
? sa[k],k = 3*(i-1) + j-i+1,
? a[i,j] = { 当 |i - j|<=1
? 0 当 |i - j|>1
例 5.5 三对角矩阵
? 4 3 0 0 0
? 5 2 2 0 0
? A = 0 1 0 4 0
? 0 0 2 8 7
? 0 0 0 9 5
? 一维数组 SA[1..3*5-2]作为数组 A的存储结构,
SA=(4 3 5 2 2 1 0 4 2 8 7 9 5)
? 如, a[5,4] = 9
? k = 3*(5-1) + 4-5+1 = 12
? 故,sa[12] = 9
5.3.2 稀 疏 矩 阵
通常 稀疏因子 <0.05时称为稀疏矩阵,
? 例 5.6
? 0 12 9 0 0 0 0 0 0 -3 0 0 15
? 0 0 0 0 0 0 0 12 0 0 0 18 0
? M= -3 0 0 0 0 14 0 9 0 0 24 0 0
? 0 0 24 0 0 0 0 T= 0 0 0 0 0 -7
? 0 18 0 0 0 0 0 0 0 0 0 0 0
? 15 0 0 -7 0 0 0 0 0 14 0 0 0
? 0 0 0 0 0 0
? M,mu x nu (6x7)
? T,nu x mu (7x6)
? M是 T的转置
稀疏矩阵的存储结构
一, 三元组顺序表
? M,i j e T,i j e
? 1 2 12 1 3 -3
? 1 3 9 1 6 15
? 3 1 -3 2 1 12
? 3 6 14 2 5 18
? 4 3 24 3 1 9
? 5 2 18 3 4 24
? 6 1 15 4 6 -7
? 6 4 -7 6 3 14
三元组顺序表结构定义
?#define MAXSIZE 12500
?typedef struct {
? int i,j;
? Elemtype e;
?}Triple;
?typedef union {
? Triple data[MAXSIZE+1];
? int mu,nu,tu;
?}TSMatrix;
?TSMatrix M,T;
M.data[p],i,j,e
0
1
2
..
..
..
..
maxsize
mu nu tu
1 2 12
..,.,.
6 4 -7
求 稀 疏 矩 阵 M 的 转 置 矩 阵 T
TSMatrix M,T;
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
0
1
2
3
4
5
6
7
8
7 6 8
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
0
1
2
3
4
5
6
7
8
M.data[p],i,j,e T.data[q],i,j,e
求稀疏矩阵 M的转置矩阵 T
? Status TransposeSMatrix(TSMatrix M,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.tu; ++p)
? if(M.data[p].j == col ){
? T.data[q].i = M.data[p].j;
? T.data[q].j = M.data[p].i;
? T.data[q].e = M.data[p].e; ++q;
? }
? }
? retrun OK;
? } // TransposeSMatrix
求稀疏矩阵转置的 算法复杂度
? 其算法复杂度是 O(nu*tu)
? 而一般矩阵的转置算法的复杂度是 O(mu*nu):
? for ( col =1; col<= nu; ++col)
? for ( row =1; row<= mu; ++row)
? T[col][row] = M[row][col];
? 所以,当 tu = mu*nu 时,
? 算法复杂度是 O(nu*nu*mu)
? 当 tu << mu*nu 时,才适用
求 稀 疏 矩 阵 M 的 转 置 矩 阵 T 的
快速方法
? 为了减少算法复杂度,增加两个向量 num 和 cpot:
? num[col],M中第 col 列中非零元素的个数 ;
?cpot[col]:M中第 col列中的第一个非零元素在
T.data中的位置 ;
? 有, cpot[1] = 1;
? cpot[col] = cpot[col-1]+num[col-1]
? 2<= col<=m.nu
? 例 5.6
? 0 12 9 0 0 0 0 0 0 -3 0 0 15
? 0 0 0 0 0 0 0 12 0 0 0 18 0
? M= -3 0 0 0 0 14 0 9 0 0 24 0 0
? 0 0 24 0 0 0 0 T= 0 0 0 0 0 -7
? 0 18 0 0 0 0 0 0 0 0 0 0 0
? 15 0 0 -7 0 0 0 0 0 14 0 0 0
? 0 0 0 0 0 0
? 例 5.6的向量 num 和 cpot:
? col 1 2 3 4 5 6 7
? num 2 2 2 1 0 1 0
? cpot 1 3 5 7 8 8 9
? Status FastTransposeSMatrix(TSMatrix M,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){
? col = M.data[p].j; q = cpot[col];
? T.data[q].i = M.data[p].j;
? T.data[q].j = M.data[p].i;
? T.data[q].e = M.data[p].e; ++cpot[col];
? }
? }
? retrun OK;
? } // FastTransposeSMatrix
col 1 2 3 4 5 6 7
num 2 2 2 1 0 1 0
cpot 1 3 5 7 8 8 9
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
0
1
2
3
4
5
6
7
8
M.data[p],i,j,e
7 6 8
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
0
1
2
3
4
5
6
7
8
T.data[q],i,j,e
求稀疏矩阵转置的快速算法的
算法复杂度
? 其算法复杂度是 O(nu+tu)
? 当 tu = mu*nu 时,算法复杂度是 O(nu*mu)
? 当 tu << mu*nu 时,时间复杂度将小得多
?#define MAXRC 100
?typedef struct {
? int i,j;
? Elemtype e;
?}Triple;
?typedef struct {
? Triple data[MAXSIZE+1];
? int rpos[MAXRC+ 1];
? int mu,nu,tu;
?}RLSMatrix;
二, 行逻辑链接的顺序表
指出每一行的第一个非零元素在三元组中的位置
1 2 12
..,.,.
6 4 -7
M.data[p],i,j,e
0
1
2
..
..
..
..
maxsize
1 3 3 5 6 7
M.rpos[row]
例 5.7 矩阵的乘法 Q = M x N
M,m1 x n1 N,m2 x n2 当 n1 = m2时
3 0 0 5 0 2 0 6
M = 0 -1 0 0 N= 1 0 Q = -1 0
2 0 0 0 -2 4 0 4
0 0
M.data N.data Q.data
i j e i j e i j e
1 1 3 1 2 2 1 2 6
1 4 5 2 1 1 2 1 -1
2 2 -1 3 1 -2 3 2 4
3 1 2 3 2 4
row 1 2 3
M.rpos 1 3 4
row 1 2 3
Q.rpos 1 2 3
row 1 2 3 4
N.rpos 1 2 3 5
求两个稀疏矩阵的乘积的算法
?Q初始化 ;
?if (M和 N均 是非零矩阵 ){
? for(arow = 1; arow<=M.mu;++arow){
? ctemp[] = 0;
? 计算 Q中第 arow行的积并存入 ctemp[]中 ;
? 将 ctemp[]中非零元压缩存储到 Q.data;
? }
?}
Status MultiSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix &Q)
{
if(M.nu != N.mu) return ERROR;
Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; // Q初始化 ;
if (M.tu * N.tu != 0){ // Q可能是非零矩阵
for(arow = 1; arow<=M.mu;++arow){
ctemp[] = 0;Q.rpos[arow] = Q.tu +1；
for(p = M.rpos[arow]; p<M.rpos[arow+1];++p){
brow = M.data[p].j;
if(brow < N.nu /*N.mu?*/ ) t = N.rpos[brow+1];
else { t =N.tu + 1};
for( q = N.rpos[brow]; q < t; ++q){
ccol = N.data[q].j;ctemp[ccol] += M.data[p].e * N.data[q].e;
}} // for p
for(ccol =1; ccol<Q.nu; ++ccol) // 将非零元压缩存储
if(ctemp[ccol]){
if(++Q.tu > MAXSIZE) return ERROR;
Q.data[Q.tu] = {arow,ccol,ctemp[ccol]};}
} // for arow
}//if
return OK;}
时间复杂度,
ctemp[] 的时间复杂度是 O(M.mu X N.nu);
? 求 Q所有非零元的时间复杂度是
? O(M.tu X N.tu/N.mu);
? 压缩存储的时间复杂度是 O(M.tu X N.tu/N.mu);
? 时间复杂度是,
? O(M.mu X N.nu + M.tu X N.tu/N.mu);
?for( i = 1; i<=m1; ++i)
? for( j = 1; j<=n2; ++j){
? Q[i][j] = 0;
? for( k = 1; k<=n1; ++k)
? Q[i][j] += M[i][k] * N[k][j];
? }// 算法复杂度是 O(m1*n1*n2)
实验与习题
?理论习题 5.6,5.7,5.8,5.9
?实验题,
? ① 写一个主程序来 上机验证 求稀疏矩阵 M的转置矩
阵 T的快速方法 的存储结构；并计算 A的转置
? 15 0 0 22
? A = 0 -6 0 0
? 91 0 0 0
? ② 5.21
?矩阵, 二维数组
?特殊矩阵, 大量重复元素或大量 0元素
?稀疏矩阵, 大量 0元素
?压缩存储, 重复元素只分配一个存储空
间,0元素不分配存储空间
5.3.1 特殊矩阵
? 对称矩阵, aij = aji (1<=i,j<=n)
? 下三角矩阵, 当 i<j时,aij = 0,(1<=i,j<=n)
? 三对角矩阵, 当 |i-j| > 1时,aij = 0,(1<=i,j<=n)
a11 a12 a13,.,a1n
a21 a22 a23,.,a2n
a31 a32 a33,.,a3n
......
an1 an2 an3,.,ann
Anxn =
对称矩阵, aij = aji (1<=i,j<=n)
存储元素数, 1+2+...+n = n(n+1)/2
? 一维数组 SA[1..n(n+1)/2]作为数组 A下三角元素的
? 存储结构,
? SA[k] = [a11,a21,a22,a31,...,an1,...,ann]
? k = 1 2 3 4 n(n-1)/2+1 n(n+1)/2
? SA[k]和 A[i,j]的一一对应关系,
? i(i-1)/2 + j 当 i >= j
? k = {
? j(j-1)/2 + i 当 i < j
例 5.3 对称矩阵
?n = 5,1+2+3+4+5 = 5*(5+1)/2 = 15
? 一维数组 SA[1..15]作为数组 A的存储结构,
?SA=(4 5 2 3 1 3 2 5 2 8 1 6 7 9 5)
? 如, a[5,3] = a[3,5] = 7
? k = 5(5-1)/2 + 3 = 13
? 故,sa[13] = 7
4 5 3 2 1
5 2 1 5 6
3 1 3 2 7
2 5 2 8 9
1 6 7 9 5
A =
4
5 2 0
3 1 3
2 5 2 8
1 6 7 9 5
A =
下三角矩阵,
当 i<j时,aij = 0,(1<=i,j<=n)
? 同样用一维数组 SA[1..n(n+1)/2]作为数组 A非
零元素的存储结构,
?sa[k]和 a[i,j]的一一对应关系,
? sa[k],k = i(i-1)/2 + j
?a[i,j] = { (当 i >= j)
? 0 (当 i < j)
例 5.4 下三角矩阵
? 4 0 0 0 0
? 5 2 0 0 0
? A = 3 1 3 0 0
? 2 5 2 8 0
? 1 6 7 9 5
? 如, a[5,3] = 7
? k = 5(5-1)/2 + 3 = 13
? 故,sa[13] = 7 但 a[3,5] = 0
三对角矩阵,
当 |i-j| > 1时,aij = 0,(1<=i,j<=n)
? a11 a12 0 0,.,0
? a21 a22 a23 0,.,0
?Anxn = 0 a32 a33 a34,.,0
?,.....
? 0 0 0,.,ann-1 ann
? 一维数组 SA[1..3*n-2]作为数组 A下三角元素的
存储结构,
? SA[k]=[a11,a12,a21,a22,a23,a32,a33,a34,...,ann-1,ann]
? k = 1 2 3 4 5 6 7 8 3n-3 3n-2
? sa[k]和 a[i,,j]的一一对应关系,
? sa[k],k = 3*(i-1) + j-i+1,
? a[i,j] = { 当 |i - j|<=1
? 0 当 |i - j|>1
例 5.5 三对角矩阵
? 4 3 0 0 0
? 5 2 2 0 0
? A = 0 1 0 4 0
? 0 0 2 8 7
? 0 0 0 9 5
? 一维数组 SA[1..3*5-2]作为数组 A的存储结构,
SA=(4 3 5 2 2 1 0 4 2 8 7 9 5)
? 如, a[5,4] = 9
? k = 3*(5-1) + 4-5+1 = 12
? 故,sa[12] = 9
5.3.2 稀 疏 矩 阵
通常 稀疏因子 <0.05时称为稀疏矩阵,
? 例 5.6
? 0 12 9 0 0 0 0 0 0 -3 0 0 15
? 0 0 0 0 0 0 0 12 0 0 0 18 0
? M= -3 0 0 0 0 14 0 9 0 0 24 0 0
? 0 0 24 0 0 0 0 T= 0 0 0 0 0 -7
? 0 18 0 0 0 0 0 0 0 0 0 0 0
? 15 0 0 -7 0 0 0 0 0 14 0 0 0
? 0 0 0 0 0 0
? M,mu x nu (6x7)
? T,nu x mu (7x6)
? M是 T的转置
稀疏矩阵的存储结构
一, 三元组顺序表
? M,i j e T,i j e
? 1 2 12 1 3 -3
? 1 3 9 1 6 15
? 3 1 -3 2 1 12
? 3 6 14 2 5 18
? 4 3 24 3 1 9
? 5 2 18 3 4 24
? 6 1 15 4 6 -7
? 6 4 -7 6 3 14
三元组顺序表结构定义
?#define MAXSIZE 12500
?typedef struct {
? int i,j;
? Elemtype e;
?}Triple;
?typedef union {
? Triple data[MAXSIZE+1];
? int mu,nu,tu;
?}TSMatrix;
?TSMatrix M,T;
M.data[p],i,j,e
0
1
2
..
..
..
..
maxsize
mu nu tu
1 2 12
..,.,.
6 4 -7
求 稀 疏 矩 阵 M 的 转 置 矩 阵 T
TSMatrix M,T;
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
0
1
2
3
4
5
6
7
8
7 6 8
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
0
1
2
3
4
5
6
7
8
M.data[p],i,j,e T.data[q],i,j,e
求稀疏矩阵 M的转置矩阵 T
? Status TransposeSMatrix(TSMatrix M,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.tu; ++p)
? if(M.data[p].j == col ){
? T.data[q].i = M.data[p].j;
? T.data[q].j = M.data[p].i;
? T.data[q].e = M.data[p].e; ++q;
? }
? }
? retrun OK;
? } // TransposeSMatrix
求稀疏矩阵转置的 算法复杂度
? 其算法复杂度是 O(nu*tu)
? 而一般矩阵的转置算法的复杂度是 O(mu*nu):
? for ( col =1; col<= nu; ++col)
? for ( row =1; row<= mu; ++row)
? T[col][row] = M[row][col];
? 所以,当 tu = mu*nu 时,
? 算法复杂度是 O(nu*nu*mu)
? 当 tu << mu*nu 时,才适用
求 稀 疏 矩 阵 M 的 转 置 矩 阵 T 的
快速方法
? 为了减少算法复杂度,增加两个向量 num 和 cpot:
? num[col],M中第 col 列中非零元素的个数 ;
?cpot[col]:M中第 col列中的第一个非零元素在
T.data中的位置 ;
? 有, cpot[1] = 1;
? cpot[col] = cpot[col-1]+num[col-1]
? 2<= col<=m.nu
? 例 5.6
? 0 12 9 0 0 0 0 0 0 -3 0 0 15
? 0 0 0 0 0 0 0 12 0 0 0 18 0
? M= -3 0 0 0 0 14 0 9 0 0 24 0 0
? 0 0 24 0 0 0 0 T= 0 0 0 0 0 -7
? 0 18 0 0 0 0 0 0 0 0 0 0 0
? 15 0 0 -7 0 0 0 0 0 14 0 0 0
? 0 0 0 0 0 0
? 例 5.6的向量 num 和 cpot:
? col 1 2 3 4 5 6 7
? num 2 2 2 1 0 1 0
? cpot 1 3 5 7 8 8 9
? Status FastTransposeSMatrix(TSMatrix M,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){
? col = M.data[p].j; q = cpot[col];
? T.data[q].i = M.data[p].j;
? T.data[q].j = M.data[p].i;
? T.data[q].e = M.data[p].e; ++cpot[col];
? }
? }
? retrun OK;
? } // FastTransposeSMatrix
col 1 2 3 4 5 6 7
num 2 2 2 1 0 1 0
cpot 1 3 5 7 8 8 9
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
0
1
2
3
4
5
6
7
8
M.data[p],i,j,e
7 6 8
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
0
1
2
3
4
5
6
7
8
T.data[q],i,j,e
求稀疏矩阵转置的快速算法的
算法复杂度
? 其算法复杂度是 O(nu+tu)
? 当 tu = mu*nu 时,算法复杂度是 O(nu*mu)
? 当 tu << mu*nu 时,时间复杂度将小得多
?#define MAXRC 100
?typedef struct {
? int i,j;
? Elemtype e;
?}Triple;
?typedef struct {
? Triple data[MAXSIZE+1];
? int rpos[MAXRC+ 1];
? int mu,nu,tu;
?}RLSMatrix;
二, 行逻辑链接的顺序表
指出每一行的第一个非零元素在三元组中的位置
1 2 12
..,.,.
6 4 -7
M.data[p],i,j,e
0
1
2
..
..
..
..
maxsize
1 3 3 5 6 7
M.rpos[row]
例 5.7 矩阵的乘法 Q = M x N
M,m1 x n1 N,m2 x n2 当 n1 = m2时
3 0 0 5 0 2 0 6
M = 0 -1 0 0 N= 1 0 Q = -1 0
2 0 0 0 -2 4 0 4
0 0
M.data N.data Q.data
i j e i j e i j e
1 1 3 1 2 2 1 2 6
1 4 5 2 1 1 2 1 -1
2 2 -1 3 1 -2 3 2 4
3 1 2 3 2 4
row 1 2 3
M.rpos 1 3 4
row 1 2 3
Q.rpos 1 2 3
row 1 2 3 4
N.rpos 1 2 3 5
求两个稀疏矩阵的乘积的算法
?Q初始化 ;
?if (M和 N均 是非零矩阵 ){
? for(arow = 1; arow<=M.mu;++arow){
? ctemp[] = 0;
? 计算 Q中第 arow行的积并存入 ctemp[]中 ;
? 将 ctemp[]中非零元压缩存储到 Q.data;
? }
?}
Status MultiSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix &Q)
{
if(M.nu != N.mu) return ERROR;
Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; // Q初始化 ;
if (M.tu * N.tu != 0){ // Q可能是非零矩阵
for(arow = 1; arow<=M.mu;++arow){
ctemp[] = 0;Q.rpos[arow] = Q.tu +1；
for(p = M.rpos[arow]; p<M.rpos[arow+1];++p){
brow = M.data[p].j;
if(brow < N.nu /*N.mu?*/ ) t = N.rpos[brow+1];
else { t =N.tu + 1};
for( q = N.rpos[brow]; q < t; ++q){
ccol = N.data[q].j;ctemp[ccol] += M.data[p].e * N.data[q].e;
}} // for p
for(ccol =1; ccol<Q.nu; ++ccol) // 将非零元压缩存储
if(ctemp[ccol]){
if(++Q.tu > MAXSIZE) return ERROR;
Q.data[Q.tu] = {arow,ccol,ctemp[ccol]};}
} // for arow
}//if
return OK;}
时间复杂度,
ctemp[] 的时间复杂度是 O(M.mu X N.nu);
? 求 Q所有非零元的时间复杂度是
? O(M.tu X N.tu/N.mu);
? 压缩存储的时间复杂度是 O(M.tu X N.tu/N.mu);
? 时间复杂度是,
? O(M.mu X N.nu + M.tu X N.tu/N.mu);
?for( i = 1; i<=m1; ++i)
? for( j = 1; j<=n2; ++j){
? Q[i][j] = 0;
? for( k = 1; k<=n1; ++k)
? Q[i][j] += M[i][k] * N[k][j];
? }// 算法复杂度是 O(m1*n1*n2)
实验与习题
?理论习题 5.6,5.7,5.8,5.9
?实验题,
? ① 写一个主程序来 上机验证 求稀疏矩阵 M的转置矩
阵 T的快速方法 的存储结构；并计算 A的转置
? 15 0 0 22
? A = 0 -6 0 0
? 91 0 0 0
? ② 5.21
