[数据结构] 稀疏矩阵的加法与乘法

2023-02-19 18:01:41 来源：博客园

(相关资料图)

稀疏矩阵的加法

传统矩阵的加法

矩阵相加的前提是两个矩阵的行数和列数相等，将矩阵的每个元素对应相加即可。

void NormalAddMatrix(int A[][N], int B[][N], int C[][N]){    for(int i = 0; i < m; i ++ )        for(int j = 0; j < n; j ++ )            C[i][j] = A[i][j] + B[i][j];}

稀疏矩阵的加法

稀疏矩阵是由三元组表表示的，在进行矩阵相加的操作时，需要对当前两个非零元行列的情况进行分类：1.当前两个非零元行相同（1）当前 A遍历到的非零元的列小于当前 B遍历到的非零元的列：将 A此时的非零元加入到 C的三元组表中（2）当前 A遍历到的非零元的列大于当前 B遍历到的非零元的列：将 B此时的非零元加入到 C的三元组表中（3）当前 A遍历到的非零元的列等于当前 B遍历到的非零元的列：将 A此时的非零元和 B此时非零元相加后加入到 C的三元组表中

2.当前两个非零元行不相同（1）A中的非零元已经遍历完了或者 A此时的非零元的行大于B的非零元的行：将 B此时的非零元加入到 C的三元组表中（2）B中的非零元已经遍历完了或者 A此时的非零元的行小于B的非零元的行：将 A此时的非零元加入到 C的三元组表中

//稀疏矩阵三元组加法void AddSMatrix(TSMatrix a, TSMatrix b, TSMatrix &c){    int i = 0, j = 0, k = 0;    ElemType v;                            //用于计算和    if(a.mu != b.mu || a.nu != b.nu){       //两矩阵无法相加        printf("两矩阵无法相加。\n");        return;      }    c.mu = a.mu;    c.nu = a.nu;    while(i < a.tu || j < b.tu){      //若行相等，看列      if(a.data[i + 1].i == b.data[j + 1].i){        //行相同时的第一种情况        if(a.data[i + 1].j < b.data[j + 1].j){            c.data[k + 1].i = a.data[i + 1].i;            c.data[k + 1].j = a.data[i + 1].j;            c.data[k + 1].e = a.data[i + 1].e;            k++;               i++;        //前往下一个a中的非0元        }        //行相同时的第二种情况        else if(a.data[i + 1].j > b.data[j + 1].j){            c.data[k + 1].i = b.data[j + 1].i;            c.data[k + 1].j = b.data[j + 1].j;            c.data[k + 1].e = b.data[j + 1].e;            k++;            j++;        //前往下一个b中的非0元        }        //行相同的第三种情况        else{            v = a.data[i + 1].e + b.data[j + 1].e;            if(v != 0){                c.data[k + 1].i = a.data[i + 1].i;                c.data[k + 1].j = a.data[i + 1].j;                c.data[k + 1].e = v;                k++;            }            i++;            j++;        }      }      //若行不相同 的两种情况      else if(i == a.tu || a.data[i + 1].i > b.data[j + 1].i && j != b.tu){          c.data[k + 1].i = b.data[j + 1].i;          c.data[k + 1].j = b.data[j + 1].j;          c.data[k + 1].e = b.data[j + 1].e;          k++;          j++;      //前往下一个b的非0元      }      else if(j == b.tu || a.data[i + 1].i < b.data[j + 1].i && i != a.tu){             c.data[k + 1].i = a.data[i + 1].i;          c.data[k + 1].j = a.data[i + 1].j;          c.data[k + 1].e = a.data[i + 1].e;          k++;          i++;      //前往下一个a的非0元      }    }    c.tu = k;}

稀疏矩阵的乘法

传统矩阵的乘法

矩阵相乘的前提是矩阵 A的列数等于矩阵 B的行数，假设矩阵 A是一个 m * l的矩阵， B是一个 l * n的矩阵，两者相乘后得到一个 m * n的新矩阵 *C。

void NormalMultMatrix(int A[][N], int B[][N], int C[][N]){    for(int i = 0; i < m; i ++ )        for(int j = 0; j < n; j ++ )            for(int k = 0; k < l; k ++ )                C[i][j] += A[i][k] * B[k][j];}

稀疏矩阵的乘法

乘法辅助函数

我们可以仿照传统矩阵乘法的样式来实现三元组表示矩阵的相乘，对于相乘后得到的矩阵 C，每个元素即 C[i][j]，其实只需要在 A和 B中找到对应下标相同的 A[i][k]和 B[k][j]即可。

//乘法辅助函数 找到对应下标相同的元素 A[i][k] 和 B[k][j]int Getval(TSMatrix a, int i, int j){    int k = 1;     //矩阵三元组下标    while(k <= a.tu && (a.data[k].i != i || a.data[k].j != j))        k++;    if(k <= a.tu)        return a.data[k].e;    else        return 0;}

稀疏矩阵的乘法代码

有了这个辅助函数，就可以轻松实现三元组表示的矩阵的乘法了。

//稀疏矩阵三元组乘法void MultSMatrix(TSMatrix a, TSMatrix b, TSMatrix &c){    int p = 0;    ElemType s;    if(a.nu != b.mu){       printf("两矩阵无法相乘\n");       return;    }    for(int i = 1; i <= a.mu; i++){        for(int j = 1; j <= b.nu; j++){            s = 0;            for(int k = 1; k <= a.nu; k++)               s += Getval(a, i, k) * Getval(b, k, j);            if(s != 0){               c.data[p + 1].i = i;               c.data[p + 1].j = j;               c.data[p + 1].e = s;               p++;            }        }    }    c.mu = a.mu;    c.nu = b.nu;    c.tu = p;}

程序测试

完整程序代码

点击查看代码

#include #include #define MAXSIZE 10000typedef int ElemType;typedef struct{    int i, j;    ElemType e;}Triple;typedef struct{    Triple data[MAXSIZE];    int mu, nu, tu;          //矩阵行数，列数和非0元个数}TSMatrix;//输入稀疏矩阵数据void InPutM(TSMatrix &M){    printf("输入稀疏矩阵的 行数, 列数, 非0元个数 :\n");    scanf("%d %d %d", &M.mu, &M.nu, &M.tu);    printf("输入矩阵非0元素的 所在行i, 所在列j, 值e:\n");    for(int k = 1; k <= M.tu; k++){        scanf("%d %d %d", &M.data[k].i, &M.data[k].j, &M.data[k].e);    }}//打印稀疏矩阵三元组数据void PrintM(TSMatrix T){    printf("  %d    %d    %d\n", T.mu, T.nu, T.tu);    printf("  ------------\n");    for(int k = 1; k <= T.tu; k++){        printf("  %d    %d    %d\n",T.data[k].i, T.data[k].j, T.data[k].e);    }}//稀疏矩阵三元组加法void AddSMatrix(TSMatrix a, TSMatrix b, TSMatrix &c){    int i = 0, j = 0, k = 0;    ElemType v;                            //用于计算和    if(a.mu != b.mu || a.nu != b.nu){       //两矩阵无法相加        printf("两矩阵无法相加。\n");        return;      }    c.mu = a.mu;    c.nu = a.nu;    while(i < a.tu || j < b.tu){      //若行相等，看列      if(a.data[i + 1].i == b.data[j + 1].i){        //行相同时的第一种情况        if(a.data[i + 1].j < b.data[j + 1].j){            c.data[k + 1].i = a.data[i + 1].i;            c.data[k + 1].j = a.data[i + 1].j;            c.data[k + 1].e = a.data[i + 1].e;            k++;               i++;        //前往下一个a中的非0元        }        //行相同时的第二种情况        else if(a.data[i + 1].j > b.data[j + 1].j){            c.data[k + 1].i = b.data[j + 1].i;            c.data[k + 1].j = b.data[j + 1].j;            c.data[k + 1].e = b.data[j + 1].e;            k++;            j++;        //前往下一个b中的非0元        }        //行相同的第三种情况        else{            v = a.data[i + 1].e + b.data[j + 1].e;            if(v != 0){                c.data[k + 1].i = a.data[i + 1].i;                c.data[k + 1].j = a.data[i + 1].j;                c.data[k + 1].e = v;                k++;            }            i++;            j++;        }      }      //若行不相同 的两种情况      else if(i == a.tu || a.data[i + 1].i > b.data[j + 1].i && j != b.tu){          c.data[k + 1].i = b.data[j + 1].i;          c.data[k + 1].j = b.data[j + 1].j;          c.data[k + 1].e = b.data[j + 1].e;          k++;          j++;      //前往下一个b的非0元      }      else if(j == b.tu || a.data[i + 1].i < b.data[j + 1].i && i != a.tu){             c.data[k + 1].i = a.data[i + 1].i;          c.data[k + 1].j = a.data[i + 1].j;          c.data[k + 1].e = a.data[i + 1].e;          k++;          i++;      //前往下一个a的非0元      }    }    c.tu = k;}//乘法辅助函数int Getval(TSMatrix a, int i, int j){    int k = 1;     //矩阵三元组下标    while(k <= a.tu && (a.data[k].i != i || a.data[k].j != j))        k++;    if(k <= a.tu)        return a.data[k].e;    else        return 0;}//稀疏矩阵三元组乘法void MultSMatrix(TSMatrix a, TSMatrix b, TSMatrix &c){    int p = 0;    ElemType s;    if(a.nu != b.mu){       printf("两矩阵无法相乘\n");       return;    }    for(int i = 1; i <= a.mu; i++){        for(int j = 1; j <= b.nu; j++){            s = 0;            for(int k = 1; k <= a.nu; k++)               s += Getval(a, i, k) * Getval(b, k, j);            if(s != 0){               c.data[p + 1].i = i;               c.data[p + 1].j = j;               c.data[p + 1].e = s;               p++;            }        }    }    c.mu = a.mu;    c.nu = b.nu;    c.tu = p;}int main(){   TSMatrix A, B, C, D;   printf("输入稀疏矩阵A的三元组:\n");   InPutM(A);   PrintM(A);   printf("\n输入稀疏矩阵B的三元组:\n");   InPutM(B);   PrintM(B);   printf("\n矩阵A与B相加得到矩阵C:\n");   AddSMatrix(A, B, C);   PrintM(C);   printf("\n矩阵A与B相乘得到矩阵D:\n");   MultSMatrix(A, B, D);   PrintM(D);}

测试运行结果

关键词：稀疏矩阵辅助函数