在实际应用中，我们经常碰到这样一类矩阵，它们的非零元素很少，而且分布没有规律，我们称之为稀疏矩阵。很显然，若用二维数组存储稀疏矩阵，将浪费大量的时间和空间。因此我们对稀疏矩阵一般采取压缩存储的方法，即只存储其非零元素。常用的数据结构有三元组顺序表 和十字链表。
我们先来看三元组顺序表。
//------稀疏矩阵的三元组顺序表存储表示-------------------
#define MAXSIZE 1000 //假设非零元素的个数最多为1000个
typedef struct
{
int x, y; //该非零元素的行下标和列下标
ElemType e; //该非零元素的值
} Triple;
typedef struct
{
Triple data[MAXSIZE+1];//非零元素三元组顺序表data[0]未用
int mu, nu, tu; //矩阵的行数，列数和非零元素的个数
} TSMatrix;
在此，data域中表示非零元素的三元组是以行序为主序顺序排列的，这为我们的某些计算将
带来方便。
创建一个三元组
TSMatrix CreateTriple(int m, int n) //构造一个三元组顺序表存储矩阵
{
TSMatrix T;
int i=0;
puts("请按行序为主序依次输入矩阵的非零元素的行号，列号和元素值，每行输入一个元素的信息：");
printf("注意行号不能超过%d,列号不能超过%d\n", m, n);
do
{
i++;
scanf("%d%d%d", &T.data[i].x, &T.data[i].y, &T.data[i].e);
fflush(stdin);
} while(T.data[i].x > 0 && T.data[i].x <= m && T.data[i].y > 0 && T.data[i].y <= n) ;
T.mu = m;
T.nu = n;
T.tu = i;
return T;
}
二维数组存储稀疏矩阵和三元组顺序表的相互转换
TSMatrix ArrayToTriple(const int A[][N], int m, int n)//二维数组转换为三元组顺序表
{
TSMatrix T;
int i, j, k;
k = 1;
for(i=0; i
{
T.data[k].x = i+1;
T.data[k].y = j+1;
T.data[k].e = A[i][j];
k++;
}
T.mu = m;
T.nu = n;
T.tu = k-1;
return T;
}
void TripleToArray(TSMatrix T, int A[][N], int *m, int *n)//三元组顺序表转换为二维数组
{
int i, j, k;
*m = T.mu;
*n = T.nu;
for(i=0; i<*m; i++) //先设所有元素均为0
for(j=0; j<*n; j++)
A[i][j] = 0;
for(i=1; i<=T.tu; i++)//把三元组顺序表中的元素写入二维数组
A[T.data[i].x-1][T.data[i].y-1] = T.data[i].e;
} //注意二维数组的下标从0开始，而三元组顺序表的行，列下标从1开始
1。转置矩阵
显然，一个稀疏矩阵的转置矩阵仍然是稀疏矩阵。假设a和b是TSMatrix型的变量，分别表示矩阵M和T。那么，如何由a得到b呢？
从分析a和b之间的差异可见只要做到：1。将矩阵的行列值互换；2。将每个三元组中的i和j互换；3。重排三元组之间的次序便可以实现矩阵的转置。前两条是容易做到的，关键是如何实现第三条，即如何使b.data中的三元组是以T的行序（M的列序）为主序依次排列的。可以有两种处理方法：
1，按照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置。即按照M的列序来进行转置。其函数如下；
bool TransposeSMatrix(TSMatrix M, TSMatrix *T)//三元组顺序表 转置矩阵
{
int k, i, col;
(*T).mu = M.nu;
(*T).nu = M.mu;
(*T).tu = M.tu;
if((*T).tu == 0)
return 0;
else
{
k=1;
for(col=1; col<=M.nu; col++) //按照T的行序（M的列序）为主序依次排列
for(i=1; i<=M.tu; i++)//扫描M的所有元素
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;
k++;
}//if
} //else
return 1;
}
算法的时间复杂度为O（mu.tu），而使用二维数组存储进行转置矩阵运算时时间复杂度为O（mu.nu）。所以此算法仅适用于tu《mu.nu的情况。
2。按照a.data中三元组的次序进行转置，并将转置后的三元组置入b中恰当的位置。即预先确定M中每一列（即T中的每一行）的第一个非零元素在b.data中应有的位置。在此，需要附设num和cpot两个数组，num[col]表示矩阵M中第col列中非零元素的个数，cpot[col]指示M中第col列中第一个非零元素在b.data中的位置，显然有：
cpot[1] = 1；
cpot[col] = cpot[col-1] + num[col-1] 2<=col<=a.nu
此算法的时间复杂度为O（mu+tu），在M的非零元素的个数tu和mu*nu等数量级时，其时间复杂度为O（mu.nu），和使用二维数组存储进行转置矩阵运算时时间复杂度相同，故称为快速转置。
其函数如下；
bool FastTransposeSMatrix(TSMatrix M, TSMatrix *T) //三元组顺序表 快速转置矩阵
{
int k, i, col;
int num[N] = {0};
int cpot[N] = {0};
(*T).mu = M.nu;
(*T).nu = M.mu;
(*T).tu = M.tu;
if((*T).tu == 0)
return 0;
else
{
for(i=1; i<=M.tu; i++)//扫描M的所有元素
num[M.data[i].y]++; //确定矩阵M每一列中非零元素的个数
cpot[1] = 1;
for(col=2; col<=M.nu; col++)
cpot[col] = cpot[col-1]+num[col-1];// 确定矩阵M第col列中第一个非零元素在b.data中的位置
for(i=1; i<=M.tu; i++)//扫描M的所有元素
{
col = M.data[i].y; //标出该元素所在的列
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中的位置向前移动一位
}//for
}//if
return 1;
}
2。矩阵相加
基本算法，依次扫描A和B的行列值，并且以行序为主序。当行列相同时，将两个元素值相加产生的结果放入结果数组中；不相同时，将A或B的元素直接放入结果数组中。
这种算法的时间复杂度为O（A.tu+B.tu），速度非常快。其函数如下；
TSMatrix AddSMatrix(TSMatrix A, TSMatrix B) //三元组顺序表 矩阵相加
{
TSMatrix C;
int i=1, j=1, k=1; //i,j,k分别是A，B，C的下标，这些下标都是从1开始的
while(i<=A.tu && j<=B.tu)//循环直到A，B 中有一个结束
{
if(A.data[i].x == B.data[j].x) //行相等
{
if(A.data[i].y == B.data[j].y)//且列相等
{
C.data[k].x = A.data[i].x;
C.data[k].y = A.data[i].y;
C.data[k].e = A.data[i].e + B.data[j].e;
i++;
j++;
if(C.data[k].e != 0) //结果值不为0时放入C中
k++;
}
else if(A.data[i].y < B.data[j].y)//A的列小于B的列，将A的元素直接放入C中
{
C.data[k].x = A.data[i].x;
C.data[k].y = A.data[i].y;
C.data[k].e = A.data[i].e;
i++;
k++;
}
else //B的列小于A的列，将B的元素直接放入C中
{
C.data[k].x = B.data[j].x;
C.data[k].y = B.data[j].y;
C.data[k].e = B.data[j].e;
j++;
k++;
}
} //if
else if(A.data[i].x < B.data[j].x) //A的行小于B的行，将A的元素直接放入C中
{
C.data[k].x = A.data[i].x;
C.data[k].y = A.data[i].y;
C.data[k].e = A.data[i].e;
i++;
k++;
}
else //否则将B的元素直接放入C中
{
C.data[k].x = B.data[j].x;
C.data[k].y = B.data[j].y;
C.data[k].e = B.data[j].e;
j++;
k++;
}
} //while
if(i>A.tu) //A结束，若B还有元素，则将B的元素直接放入C中
{
while(j<=B.tu)
{
C.data[k].x = B.data[j].x;
C.data[k].y = B.data[j].y;
C.data[k].e = B.data[j].e;
j++;
k++;
}
} //if
else //B结束，若A还有元素，则将A的元素直接放入C中
{
while(i<=A.tu)
{
C.data[k].x = A.data[i].x;
C.data[k].y = A.data[i].y;
C.data[k].e = A.data[i].e;
i++;
k++;
}
}//else
C.mu = A.mu;
C.nu = A.nu;
C.tu = k-1;
return C;
}
3。矩阵相乘
压缩存储的矩阵与用二维数组存储的矩阵在进行乘法运算时最大的不同是，在经典（二维数组存储）算法中，不论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) //计算出C的行号i和列号j处元素的值
{
int k=1;
while(k<=M.tu && M.data[k].x<=i) //因为是按行序排列，故不必扫描行号比i大的元素
{
if(M.data[k].x==i && M.data[k].y==j)
return M.data[k].e;
k++;
}
return 0;
}
bool MultSMatrix(TSMatrix A, TSMatrix B, TSMatrix *C)
{
int i, j, k, l, p, s;
if(A.nu != B.mu)
return 0;
if(A.tu * B.tu != 0)
{
p=1;
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;
p++;
}
} //for(j=1; j<=B.nu; j++)
(*C).mu = A.mu;
(*C).nu = B.nu;
(*C).tu = p-1;
}//if(A.tu * B.tu != 0)
return 1;
}
这种算法的存储空间虽然很少，但时间复杂度为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[])//确定矩阵的每一行的第一个非零元素在三元组顺序表中的位置
{
int num[N] = {0};
int i, row;
for(i=1; i<=M.tu; i++)//扫描M的所有元素
num[M.data[i].x]++; //确定矩阵M每一行中非零元素的个数
rpos[1] = 1;
for(row=2; row<=M.mu; row++)
rpos[row] = rpos[row-1]+num[row-1];// 确定矩阵M第row行中第一个非零元素在M.data中的位置
}// RPos
bool FastMultSMatrix(TSMatrix A, TSMatrix B, TSMatrix *C)
{
int Arpos[N] = {0}, Brpos[N] = {0};//分别存储矩阵A，B的每一行的第一个非零元素在三元组中的位置
int ctemp[N] = {0};//存储正在处理的该行中每一列的乘积值，是一个累积的和值
int arow, brow, ccol;
int i, p, q;
int ta, tb;
if(A.nu != B.mu)
return 0;
(*C).mu = A.mu; //C初始化
(*C).nu = B.nu;
(*C).tu = 0;
if(A.tu * B.tu != 0)//若C是非零矩阵
{
RPos(A, Arpos); //确定矩阵A的每一行的第一个非零元素在三元组顺序表中的位置
RPos(B, Brpos); //确定矩阵B的每一行的第一个非零元素在三元组顺序表中的位置
for(arow=1; arow<=A.mu; arow++)//对A进行逐行处理 ，即对C进行逐行处理
{
for(i=0; i<=B.nu; i++)//当前各元素累加器清零
ctemp[i] = 0;
if(arow < A.mu) //处理A中第arow的每一个非零元素ta指示下一行第一个非零元素的位置
ta = Arpos[arow+1];
else //最后一行的 下一行第一个非零元素的位置 当然是 A.tu + 1
ta = A.tu + 1;
for(p=Arpos[arow]; p
brow = A.data[p].y; //标出该元素的列号，在B中找到与它对应的行号
if(brow < B.mu)//处理B中第brow的每一个非零元素tb指示下一行第一个非零元素的位置
tb = Brpos[brow+1];
else
tb = B.tu + 1;
for(q=Brpos[brow]; q
ccol = B.data[q].y; //直到该行所有的元素都处理完毕，再把ctemp[ccol]的值放入C中
ctemp[ccol] += A.data[p].e * B.data[q].e;
}//for q
}//for p
for(ccol=1; ccol<=(*C).nu; ccol++)//得到C的第arow中每一列（个）元素的值
if(ctemp[ccol] != 0)//压缩存储该行非零元
{
if(++(*C).tu > MAXSIZE)
return 0;
(*C).data[(*C).tu].x = arow; //C的行数等于A的行数
(*C).data[(*C).tu].y =ccol; //C的列数等于B的列数
(*C).data[(*C).tu].e = ctemp[ccol]; //C的元素值等于A的行数ctemp[ccol]的累积值
} // if(ctemp[ccol] != 0)
}//for arow
} //if(A.tu * B.tu != 0)
return 1;
} // MultSMatrix
分析上述算法的时间复杂度有如下结果：确定矩阵的每一行的第一个非零元素在三元组顺序表中的位置的时间复杂度为O（A.tu+A.mu+B.tu+B.mu+），累加器ctemp初始化的时间复杂度为O（A.mu*B.nu），C的所有非零元素的时间复杂度为O（A.tu*B.tu/B.mu），进行压缩存储的时间复杂度为O（A.mu*B.tu），因此总的时间复杂度为O（A.mu*B.nu + A.tu*B.tu/B.mu）。当矩阵为稀疏矩阵时，这种算法的时间复杂度接近O（A.mu*B.nu）比经典算法要快。
/*创建方形矩阵的行列式（人工输入数据），输出该矩阵的逆矩阵*/
/*2006-1-10 梁见斌*/
#include
#include
#define N 10
#define MAXSIZE 1000 //假设非零元素的个数最多为1000个
typedef struct
{
int x, y; //该非零元素的行下标和列下标
int e; //该非零元素的值
} Triple;
typedef struct
{
Triple data[MAXSIZE+1];//非零元素三元组顺序表data[0]未用
int mu, nu, tu; //矩阵的行数，列数和非零元素的个数
} TSMatrix;
typedef struct node
{
int data; //存储元素的值
int x; //存储元素的横坐标
int y; //存储元素的纵坐标
} array;
int sum; //全局变量，存储行列式的值
void CreateArray(int H[][N], int m, int n); //构造一个二维数组存储矩阵
void PrintArray(const int H[][N], int m, int n) ; //输出二维数组存储矩阵
void SolveHT(const TSMatrix A, array S[], int rpos[], int row, int top, int NiXu);//采用递归方式求行列式的值
bool Judge(const array S[], int line, int len); //判断行列式的元素的纵坐标是否重复
void trsmat(const int A[][N], int B[][N], int m, int n) ; //二维数组存储转置矩阵
TSMatrix ArrayToTriple(const int A[][N], int m, int n);//二维数组转换为三元组顺序表
void TripleToArray(TSMatrix T, int A[][N], int *m, int *n);//三元组顺序表转换为二维数组
void PrintTriple(TSMatrix M);//输出三元组顺序表存储矩阵
void RPos(TSMatrix M, int rpos[]);//确定矩阵的每一行的第一个非零元素在三元组顺序表中的位置
TSMatrix CreateYH(TSMatrix T, int x, int y); //求代数余子式矩阵
int main(void)
{
array SL[N]; //栈，存储行列式的每一个乘积项的元素（因子）
int H[N][N], YH[N][N]; //存储原矩阵的行列式和代数余子式
int Y[N][N], YZ[N][N];//存储代数余子式的值，其转置矩阵即原矩阵的伴随矩阵
TSMatrix Triple1, Triple2; //三元组顺序表
int Trpos[N] = {0};//存储矩阵T的每一行的第一个非零元素在三元组中的位置
int D; // 存储原矩阵的行列式的值
int x, y;
int m, ym; //分别存储原矩阵的行列式和代数余子式的阶次
m = 3;
CreateArray(H, m, m); //构造一个矩阵行列式
PrintArray(H, m, m); //输出矩阵行列式
Triple1 = ArrayToTriple(H, m, m); //二维数组转换为三元组顺序表
// PrintTriple(Triple1);
RPos(Triple1, Trpos);//确定矩阵的每一行的第一个非零元素在三元组顺序表中的位置
sum = 0; //设原矩阵的行列式的初值为0
SolveHT(Triple1, SL, Trpos, 1, 0, 0); //采用递归方式求矩阵行列式的值
D = sum;
// printf("D = %d\n", D); //输出原矩阵的行列式的值
for(x=1; x<=m; x++) //构造各元素的代数余子式
for(y=1; y<=m; y++)
{
Triple2 = CreateYH(Triple1, x, y); //求代数余子式矩阵
// PrintTriple(Triple2); //输出代数余子式
// TripleToArray(Triple2, YH, &ym, &ym);//三元组顺序表转换为二维数组
// PrintArray(YH, ym, ym); //输出行列式
RPos(Triple2, Trpos);//确定矩阵的每一行的第一个非零元素在三元组顺序表中的位置
sum = 0; //设代数余子式的初值为0
SolveHT(Triple2, SL, Trpos, 1, 0, 0);//采用递归方式求代数余子式的值
if((x+y)%2==0)
Y[x-1][y-1] = sum;
else
Y[x-1][y-1] = sum*(-1);
}
trsmat(Y, YZ, m, m);//求转置矩阵
//PrintArray(YZ, m, m); //输出伴随矩阵
puts("逆矩阵:");
printf("(1/%d)*\n", D);
PrintArray(YZ, m, m); //输出伴随矩阵
system("pause");
return 0;
}
TSMatrix CreateYH(TSMatrix T, int x, int y) //求代数余子式矩阵
{
int i, k = 1;
TSMatrix TY;
for(i=1; i<=T.tu; i++) //构造代数余子式
{
if(x != T.data[i].x && y != T.data[i].y)
{
if(x > T.data[i].x) //若该非零元素的行号比x小，其代数余子式对应的元素行号不变
TY.data[k].x = T.data[i].x;
else //若该非零元素的行号比x大，其代数余子式对应的元素行号减1
TY.data[k].x = T.data[i].x-1;
if(y > T.data[i].y) //列号的处理方法与行号相同
TY.data[k].y = T.data[i].y;
else
TY.data[k].y = T.data[i].y-1;
TY.data[k].e = T.data[i].e;
k++;
}
} //for(i=1; i<=T.tu; i++)
TY.mu = T.mu-1;
TY.nu = T.nu-1;
TY.tu = k-1;
return TY;
}
void RPos(TSMatrix M, int rpos[])//确定矩阵的每一行的第一个非零元素在三元组顺序表中的位置
{
int num[N] = {0};
int i, row;
for(i=1; i<=M.tu; i++)//扫描M的所有元素
num[M.data[i].x]++; //确定矩阵M每一行中非零元素的个数
rpos[1] = 1;
for(row=2; row<=M.mu; row++)
rpos[row] = rpos[row-1]+num[row-1];// 确定矩阵M第row行中第一个非零元素在M.data中的位置
}// RPos
void CreateArray(int H[][N], int m, int n) //构造一个二维数组存储矩阵
{
int i, j;
for(i=0; i
for(j=0; j
fflush(stdin);
}
}
void PrintArray(const int H[][N], int m, int n) //输出二维数组存储矩阵
{
int i, j;
for(i=0; i
for(j=0; j
printf("\n");
}
}
void trsmat(const int A[][N], int B[][N], int m, int n) //二维数组存储转置矩阵
{
int i, j;
for(i=0; i
}
void SolveHT(const TSMatrix A, array S[], int rpos[], int row, int top, int NiXu)//采用递归方式求行列式的值
{
array CS[N]; //栈，存储S[]的拷贝
int ta, p, i, j, k, ctop;
int mul; //存储每一个乘积项的值
int CNiXu; //累积每一个乘积项的逆序数
if(row < A.mu) //处理A中第arow的每一个非零元素ta指示下一行第一个非零元素的位置
ta = rpos[row+1];
else //最后一行的 下一行第一个非零元素的位置 当然是 A.tu + 1
ta = A.tu + 1;
for(p=rpos[row]; p
ctop = top;
if(Judge(S, A.data[p].y, ctop))//如果当前元素的纵坐标不与栈中存储的元素重复，将其入栈
{
S[ctop].x = A.data[p].x;
S[ctop].y = A.data[p].y;
S[ctop++].data = A.data[p].e;
CNiXu = NiXu; //把逆序数复制到CNiXu
for(k=0; k
if(S[ctop-1].y < S[k].y) //累积逆序数
CNiXu++;
}
for(k=0; k
if(row < A.mu) //如果未分析到该乘积项的最后一个元素，递归继续分析
SolveHT(A, CS, rpos, row+1, ctop, CNiXu);
else //否则计算该乘积项的值，并存储到栈中
{
if(ctop == row)
{
for(mul=1, k=0; k
if(CNiXu%2==0) //如果逆序数为偶数，该乘积项为正
sum += mul;
else //否则为负
sum -= mul;
}
}
}
}
}
bool Judge(const array S[], int line, int len)
{
int i;
for(i=0; i
return 0;
return 1;
}
TSMatrix ArrayToTriple(const int A[][N], int m, int n)//二维数组转换为三元组顺序表
{
TSMatrix T;
int i, j, k;
k = 1;
for(i=0; i
{
T.data[k].x = i+1;
T.data[k].y = j+1;
T.data[k].e = A[i][j];
k++;
}
T.mu = m;
T.nu = n;
T.tu = k-1;
return T;
}
void TripleToArray(TSMatrix T, int A[][N], int *m, int *n)//三元组顺序表转换为二维数组
{
int i, j, k;
*m = T.mu;
*n = T.nu;
for(i=0; i<*m; i++) //先设所有元素均为0
for(j=0; j<*n; j++)
A[i][j] = 0;
for(i=1; i<=T.tu; i++)//把三元组顺序表中的元素写入二维数组
A[T.data[i].x-1][T.data[i].y-1] = T.data[i].e;
} //注意二维数组的下标从0开始，而三元组顺序表的行，列下标从1开始
void PrintTriple(TSMatrix M) //输出三元组顺序表存储矩阵
{
int i;
printf("\n");
for(i=1; i<=M.tu; i++)//扫描M的所有元素
printf("M%d(%d,%d,%d)\t", i, M.data[i].x, M.data[i].y, M.data[i].e);
printf("\n");
}
评论