行逻辑三元组稀疏矩阵加减乘的编程实现

DSP

行逻辑三元组稀疏矩阵加减乘的编程实现

2019-07-13 17:53发布生成海报

站内文章 / DSP

17575 0

目的：
编程实现稀疏矩阵的四则运算。
实现：
1. 稀疏矩阵的存储结构采用行逻辑表示的三元组
2.

#define MAXSIZE  12500
#define MAXRC 12500
typedef struct {
    int i, j;
    int e;
}Triple;
typedef struct {
    Triple data[MAXSIZE + 1];
    int rpos[MAXRC + 1];
    int mu, nu, tu;
}RLSMatrix;

先通过创建mu nu tu的值再根据这些值采用循环输入得到data，之后再通过扫描确定rpos的值则可以完成创建。
通过三元组的形式将非零元对应的行列以及数值存储下来，再由稀疏矩阵结构存下矩阵的行数列数以及非零元个数，即可囊括稀疏矩阵的所有信息。这样就可以以三元组的形式把矩阵非零元素存储下来，节省了存储量的同时便于矩阵运算。

矩阵的加法
根据矩阵的相关知识，两个矩阵相加要求两个矩阵的行数，列数要相等。故需要设置判断是否满足矩阵相加的条件。若满足条件，则进行加法运算。根据矩阵加法法则，得到的新矩阵拥有与原来两矩阵相同的行数和列数，其元素数值则为两矩阵对应位置的元素值之和。
矩阵的减法
和加法相同地根据三种情况采用三个循环处理对应的数据，只不过两个都有的情况结果要变为两者之差，N有M没有的情况要改为N元素的相反数，其余相同。则可以得到减法的算法。
矩阵的乘法
根据矩阵乘法的理论，在满足M.nu==N.mu的情况下，新矩阵Q（i，j）的值即满足M（i，k）与N（k，j）的所有元素乘积之和。对于稀疏矩阵不需要对满足条件的每个元素都进行乘积，因为两者中若有一个为零则其乘积为零。所以只要在所有非零元中找到满足条件的配对进行相乘，在将乘积进行累加即可得到该位置的元素值。结合rpos可以高效地进行循环查找。
程序代码：
Matrix.h文件

#include
#define MAXSIZE  12500
#define MAXRC 12500
#define ERROR 0
#define OK 1
typedef struct {
    int i, j;
    int e;
}Triple;
typedef struct {
    Triple data[MAXSIZE + 1];
    int rpos[MAXRC + 1];
    int mu, nu, tu;
}RLSMatrix;
void CreateMatrix(RLSMatrix *M);
void Initrpos(RLSMatrix *M);
void Printrpos(RLSMatrix M);
int Add(RLSMatrix M, RLSMatrix N, RLSMatrix  *sum);
int Minus(RLSMatrix M, RLSMatrix N, RLSMatrix *minus);
int Multi(RLSMatrix M, RLSMatrix N, RLSMatrix *multi);
void PrintMatrix(RLSMatrix M);

Matrix.c文件

#include
#include"Matrix.h"
void CreateMatrix(RLSMatrix *M) {
    printf("请输入矩阵的行数，列数，和非零元个数
");
    scanf("%d%d%d", &M->mu, &M->nu, &M->tu);
    if (M->tu > (M->mu)*(M->nu)) { printf("该矩阵不存在！请重新输入！
"); CreateMatrix(&M); }
    int s;
    for (s = 1; s <= M->tu; s++) {
        printf("请输入第%d非零元所在的行，列，及其数值
", s);
        scanf("%d%d%d", &M->data[s].i, &M->data[s].j, &M->data[s].e);
        if (M->data[s].i < 0) { printf("行数须为正数！n"); s -= 1; continue; }
        if(M->data[s].j < 0) { printf("列数须为正数！n"); s -= 1; continue; }
        if(M->data[s].e==0){ printf("非零元不能为零！n"); s -= 1; continue; }
    }
}
void Initrpos(RLSMatrix *M) {
    int i, j, tag, s;
    for (i = M->mu; i >= 1; i--) {
        tag = 0;
        for (j = 1; j <= M->nu; j++) {
            for (s = 1; s <= M->tu; s++) {
                if (M->data[s].i == i&&M->data[s].j == j) {
                    M->rpos[i] = s; tag = 1; break;
                }
            }
            if (tag == 1)break;
        }
        if (i == M->mu&&tag == 0)M->rpos[i] = M->tu + 1;
        if (i != M->mu&&tag == 0)M->rpos[i] = M->rpos[i + 1];
    }
}
void Printrpos(RLSMatrix M) {
    int i;
    printf("rpos
");
    for (i = 1; i <= M.mu; i++) {
        printf("第%d行：%d
", i, M.rpos[i]);
    }
}

int Add(RLSMatrix M, RLSMatrix N, RLSMatrix *sum) {
    int m, n, c = 1;
    if (M.mu != N.mu || M.nu != N.nu) { printf("无法相加！
"); return ERROR; }
    sum->mu = M.mu;
    sum->nu = M.nu;
    for (m = 1; m <= M.tu; m++) {
        for (n = 1; n <= N.tu; n++) {
            if (N.data[n].i == M.data[m].i&&N.data[n].j == M.data[m].j) {
                sum->data[c].i = N.data[n].i;
                sum->data[c].j = N.data[n].j;
                sum->data[c].e = M.data[m].e + N.data[n].e;
                c++;
            }

        }       
    }
    for (m = 1; m <= M.tu; m++) {
        for (n = 1; n <= N.tu; n++) {
            if (N.data[n].i == M.data[m].i && N.data[n].j == M.data[m].j) {
                 break;
            }           
        }
        if (n-1 == N.tu) {
            sum->data[c].i = M.data[m].i;
            sum->data[c].j = M.data[m].j;
            sum->data[c].e = M.data[m].e;
            c++;
        }
    }

    for (n = 1; n <= N.tu; n++) {
        for (m = 1; m <= M.tu; m++) {
            if (N.data[n].i == M.data[m].i && N.data[n].j == M.data[m].j) {
                break;
            }
        }
        if (m-1 == M.tu) {
            sum->data[c].i = N.data[n].i;
            sum->data[c].j = N.data[n].j;
            sum->data[c].e = N.data[n].e;
            c++;
        }
    }
    sum->tu = c - 1;
    return OK;
}

int Minus(RLSMatrix M, RLSMatrix N, RLSMatrix *minus) {
    int m, n, c = 1;
    if (M.mu != N.mu || M.nu != N.nu) { printf("无法相减！
"); return ERROR; }
    minus->mu = M.mu;
    minus->nu = M.nu;
    for (m = 1; m <= M.tu; m++) {
        for (n = 1; n <= N.tu; n++) {
            if (N.data[n].i == M.data[m].i&&N.data[n].j == M.data[m].j) {
                minus->data[c].i = N.data[n].i;
                minus->data[c].j = N.data[n].j;
                minus->data[c].e = M.data[m].e - N.data[n].e;
                c++;
            }

        }
    }
    for (m = 1; m <= M.tu; m++) {
        for (n = 1; n <= N.tu; n++) {
            if (N.data[n].i == M.data[m].i && N.data[n].j == M.data[m].j) {
                 break;
            }           
        }
        if (n-1 == N.tu) {
            minus->data[c].i = M.data[m].i;
            minus->data[c].j = M.data[m].j;
            minus->data[c].e = M.data[m].e;
            c++;
        }
    }
    for (n = 1; n <= N.tu; n++) {
        for (m = 1; m <= M.tu; m++) {
            if (M.data[m].i == N.data[n].i && M.data[m].j == N.data[n].j) {
               break;
            }           
        }
        if (m-1 == M.tu) {
            minus->data[c].i = N.data[n].i;
            minus->data[c].j = N.data[n].j;
            minus->data[c].e = -N.data[n].e;
            c++;
        }
    }
    minus->tu = c - 1;
    return OK;
}
int Multi(RLSMatrix M, RLSMatrix N, RLSMatrix *Q) {
    if (M.nu != N.mu)return ERROR;
    Q->mu = M.mu; Q->nu=N.nu; Q->tu = 0;
    int tp; int i;
    int p, brow;
    int q, ccol;
    if (M.tu*N.tu != 0) {
        int arow;
        int ctemp[12500];
        for (arow = 1; arow <= M.mu; ++arow) {
            for (i = 1; i <= M.nu; i++) ctemp[i] = 0;
            Q->rpos[arow] = Q->tu + 1;
            if (arow < M.mu)tp = M.rpos[arow + 1];
            else { tp = M.tu + 1; }
            for (p = M.rpos[arow]; pM.data[p].j;
                int t;
                if (brow < M.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 (ccol = 1; ccol <= Q->nu; ++ccol) {
                if (ctemp[ccol]) {
                    if (++Q->tu > MAXSIZE)return ERROR;
                    Q->data[Q->tu].i = arow;
                    Q->data[Q->tu].j = ccol;
                    Q->data[Q->tu].e = ctemp[ccol];
                }
            }
        }
    }
    return OK;
}

void PrintMatrix(RLSMatrix M) {
    int m, n, s;
    int tag;
    for (m = 1; m <= M.mu; m++) {
        for (n = 1; n <= M.nu; n++) {
            tag = 0;
            for (s = 1; s <= M.tu; s++) {
                if (M.data[s].j == n && M.data[s].i == m) { 
                    if(M.data[s].e>=0)printf(" %d ", M.data[s].e);
                    else if(M.data[s].e<0){ printf("%d ", M.data[s].e); }
                    tag = 1;
                }
            }
            if(tag==0)printf(" 0 ");
        }printf("
");
    }
}
}

Main.c文件

#include
#include
#include"Matrix.h"
int main() {
RLSMatrix M, N, temp;
int tag;
CreateMatrix(&M); Initrpos(&M); printf("所得矩阵为：
"); PrintMatrix(M); Printrpos(M);
CreateMatrix(&N); Initrpos(&N); printf("所得矩阵为：
"); PrintMatrix(N); Printrpos(N);
tag=Add(M, N, &temp); Initrpos(&temp); 
 if(tag == OK) {
     printf("两矩阵相加所得为：
"); PrintMatrix(temp);
  }
tag=Minus(M, N, &temp); Initrpos(&temp); 
if (tag == OK) {
      printf("两矩阵相减所得为：
"); PrintMatrix(temp);
  }
tag=Multi(M, N, &temp); Initrpos(&temp); 
  if(tag == OK){ 
      printf("两矩阵相乘所得为：
"); 
      PrintMatrix(temp);
  }
system("pause");
}

演示示例如下：

注：
1. 为了使输出的矩阵更加形状好看规则，设计了元素的正负判定（因为负数输出时会多一个负号），使得正数和负数的数字部分可以对齐。
2. 为了减少非法输入的可能，在创建矩阵的函数中加入了非零元素不能多于矩阵行列数乘积的判定。以及列数行数必须为正整数，输入非零元不能为零的判定。
3. 在矩阵不满足加法减法（或是乘法）条件的时候，需要报错。为此将运算函数设置为int类型，根据返回值来判断该打印运算结果还是直接打印报错。
4. 在主函数的设计过程中，在创建函数和rpos初始化结束后立即打印输出矩阵和对应的rpos值便于立即检验函数创建的矩阵是否正确，也便于用户查看对比。

行逻辑三元组稀疏矩阵加减乘的编程实现

Ta的文章更多 >>

热门文章

行逻辑三元组稀疏矩阵加减乘的编程实现

Ta的文章 更多 >>

热门文章

举报内容

检举类型

检举原因

检举说明(必填)

打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮

Ta的文章更多 >>