稀疏矩阵的三元组顺序表存储及矩阵相乘算法小结
巧若拙（欢迎转载，但请注明出处：http://blog.csdn.net/qiaoruozhuo）
一：稀疏矩阵的三元组顺序表数据结构
typedef int ElemType;
typedef struct
{
intx, y; //该非零元素的行下标和列下标
ElemTypee; //该非零元素的值
} Triple;
typedef struct
{
Tripledata[MAXSIZE]; //非零元素三元组顺序表
intmu, nu, tu; //矩阵的行数，列数和非零元素的个数
} TSMatrix;
二：三元组顺序表实现矩阵转置
显然，一个稀疏矩阵的转置矩阵仍然是稀疏矩阵。假设a和b是TSMatrix型的变量，分别表示矩阵M和T。那么，如何由a得到b呢？
从分析a和b之间的差异可见只要做到：1。将矩阵的行列值互换；2。将每个三元组中的i和j互换；3。重排三元组之间的次序便可以实现矩阵的转置。
前两条是容易做到的，关键是如何实现第三条，即如何使b.data中的三元组是以T的行序（M的列序）为主序依次排列的。
可以有两种处理方法：
1， 按照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置。即按照M的列序来进行转置。代码如下：
TSMatrix TransposeSMatrix(TSMatrix M)//三元组顺序表 转置矩阵
{
intk, i, col;
TSMatrixT;
T.mu= M.nu;
T.nu= M.mu;
T.tu= M.tu;
if(T.tu > 0)
{
k= 0;
for(col=1; col<=M.nu; col++) //按照T的行序（M的列序）为主序依次排列
for(i=0; i
if(M.data[i].y == col)
{
T.data[k].x= M.data[i].y;
T.data[k].y= M.data[i].x;
T.data[k++].e= M.data[i].e;
}
}
returnT;
}
2，按照a.data中三元组的次序进行转置，并将转置后的三元组置入b中恰当的位置。
即预先确定M中每一列（即T中的每一行）的第一个非零元素在b.data中应有的位置。在此，需要附设num和cpot两个数组，num[col-1]表示矩阵M中第col列中非零元素的个数，cpot[col-1]指示M中第col列中第一个非零元素在b.data中的位置，显然有：
cpot[0] = 0；
cpot[col] = cpot[col-1] + num[col-1] 0
此算法的时间复杂度为O（mu+tu），在M的非零元素的个数tu和mu*nu等数量级时，其时间复杂度为O（mu.nu），和使用二维数组存储进行转置矩阵运算时时间复杂度相同，故称为快速转置。代码如下：
TSMatrix FastTransposeSMatrix(TSMatrixM) //三元组顺序表快速转置矩阵
{
TSMatrixT;
intk, i, col;
intnum[N] = {0};
intcpot[N] = {0};
T.mu= M.nu;
T.nu= M.mu;
T.tu= M.tu;
if(T.tu > 0)
{
for(i=0; i
num[M.data[i].y-1]++;//确定矩阵M每一列中非零元素的个数
cpot[0]= 0;
for(col=1; col
cpot[col]= cpot[col-1] + num[col-1];// 确定矩阵M第col列中第一个非零元素在b.data中的位置
for(i=0; i
{
col= M.data[i].y - 1; //标出该元素所在的列
k= cpot[col]; //k即矩阵M第col列（即T中的第col行）中第一个非零元素在b.data中的位置
T.data[k].x= M.data[i].y;
T.data[k].y= M.data[i].x;
T.data[k].e= M.data[i].e;
cpot[col]++;//矩阵M第col列中第一个非零元素在b.data中的位置向前移动一位
}
}
returnT;
}
三：三元组顺序表实现矩阵相乘
压缩存储的矩阵与用二维数组存储的矩阵在进行乘法运算时最大的不同是，在经典（二维数组存储）算法中，不论M（i,k）和N（k,j）的值是否为零，都要进行一次乘法计算，这样造成很大的浪费。而压缩存储则只需在M.data和N.data中找到相应的元素相乘即可。
这里介绍三种算法。
第一种，通过给定的行号i和列号j找出原矩阵的对应的元素，设计一个函数Value()，当在三元组顺序表中找到该元素时，返回其元素值，否则说明该位置元素值为0，返回0。然后利用该函数计算出C的行号i和列号j处元素的值，若该值不为0，则存入C，否则不存入。代码如下：
int Value(TSMatrix M, int i, int j) //计算出矩阵M的i行j列处元素的值
{
intk = 0;
while(k < M.tu && M.data[k].x <= i) //因为是按行序排列，故不必扫描行号比i大的元素
{
if(M.data[k].x == i && M.data[k].y == j)
returnM.data[k].e;
k++;
}
return0;
}
TSMatrix MultSMatrix(TSMatrix A, TSMatrixB) //三元组顺序表低效矩阵乘法
{
TSMatrixC;
inti, j, k, l, p, s;
C.mu= A.mu;
C.nu= B.nu;
C.tu= 0;
if(A.tu * B.tu != 0)
{
p= 0;
for(i=1; i<=A.mu; i++)
{
for(j=1; j<=B.nu; j++)
{
s= 0;
for(k=1; k<=A.nu; k++)
s+= Value(A, i, k) * Value(B, k, j);
if(s != 0)
{
C.data[p].x= i;
C.data[p].y= j;
C.data[p++].e= s;
}
}
}
C.tu= p;
}
returnC;
}
这种算法的存储空间虽然很少，但时间复杂度为O（A.mu*A.nu*B.nu*（A.tu+B.tu）），比经典的算法时间复杂度还高，因此是一种用时间换空间的方法。
如果我们预先确定矩阵的每一行的第一个非零元素在三元组顺序表中的位置，则可以得到改进的算法。
基本操作是对于A中每个元素A.data[p]，找到N中所有满足条件A.data[p].y==B.data[q].x的元素B.data[q]，求得A.data[p].e和B.data[q].e的乘积，当然这个乘积的值只是乘积矩阵C[i][j]中的一部分。
为了便于操作，我们可以对每个元素设置一个累计乘积值的变量，使其初值为0，然后扫描A，求得相应元素的乘积值并累积到相应的累计乘积值的变量中。
由于C中元素的行号和A中元素的行号一致，又都是以行序为主序排列的，因此可以对C进行逐行处理。代码如下：
void RPos(TSMatrix M, int rpos[])//确定矩阵的每一行的第一个非零元素在三元组顺序表中的位置
{
intnum[N] = {0};
inti, row;
for(i=0; i
num[M.data[i].x-1]++;//确定矩阵M每一行中非零元素的个数
rpos[0]= 0;
for(row=1; row
rpos[row]= rpos[row-1] + num[row-1];// 确定矩阵M第row行中第