【数据结构】稀疏矩阵

1.存储

---

三元组顺序表。

三元组（i，j，Aij）

 

2.转置运算

---

算法1：遍历查找

设原矩阵为M，转置后为T

1）行列互置

2）遍历所有的列号（c=1，2，3...M.col）

      遍历M的所有元素

           如果存在列数等于c的，存在T表的位置q（q初始值为0，每次递增）

算法2：带辅助向量的遍历

1）附设的辅助向量：num[col]：表示M中第col列中非零元的个数

                cpot[col]：表示M中第col列的第一个非零元在T中的位置

                |cpot[1]=1;

                |cpot[col]=cpot[col-1]+num[col-1]             【1】

2）遍历M所有列，得到num[col]的所有值，由公式【1】得到cpot[col]的所有值

3）遍历M的所有元素，通过每个元素的列号得到对应的cpot[col]，然后在T[cpot[col]]的位置放置上转置的元素（行列赋值给列行，元素赋值）

 

3.乘积运算

---

设M:m1*n1,N:n1*n2

乘积结果矩阵为Q:m1*n2

Q(i,j)=sum(M(i,k)*N(k,j))     k=1,2...n1

1）遍历M的每一行i

        对于每一行的每个元素将其列号映射为N中的行号，然后在N中搜索该行的非零值，与p相乘，遍历

        过一行后，对乘积结果进行累加

3）将得到的结果压缩到Q的存储空间中去