稀疏矩阵的行逻辑链接顺序表存储表示

121 阅读 0 评论 80 点赞

我是靠谱客的博主虚心大炮，最近开发中收集的这篇文章主要介绍稀疏矩阵的行逻辑链接顺序表存储表示，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

// Header.h

#ifndef HEADER_H
#define HEADER_H 1

// 预定义常量和类型
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;

#endif // HEADER_H

// RLSMatrix.h

#ifndef RLSMATRIX_H
#define RLSMATRIX_H 1

#include <iostream>
#include "Header.h"
using namespace std;

#define MAXSIZE 1024
#define MAXRC    1024

typedef int ElemType;

typedef struct {
    int i, j; // 该非零元的行下标和列下标
    ElemType e;
} Triple;

typedef struct {
    Triple data[MAXSIZE + 1]; // 非零元三元组表, data[0]未用
    int rpos[MAXRC + 1]; // 各行第一个非零元的位置表
    int mu, nu, tu; // 矩阵的行数，列数和非零元个数
} RLSMatrix;

Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix& Q);
ostream& operator<<(ostream& os, const RLSMatrix& m);

#endif // RLSMATRIX_H

// RLSMatrix.cpp

#include "RLSMatrix.h"

#define LEN 1024

// 求矩阵乘积Q = M x N，采用行逻辑链接存储表示
Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix& Q)
{
    int arow, brow, p, q, t, ctemp[LEN], l, ccol, tp;

    if (M.nu != N.mu)
        return ERROR;

    Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; // Q初始化

    if (M.tu * N.tu != 0) { // Q是非零矩阵
        for (arow = 1; arow <= M.mu; ++arow) { // 处理M的每一行
            for (l = 1; l <= M.nu; ++l)
                ctemp[l] = 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]; p < tp; ++p) {
                // 对当前行中每一个非零元找到对应元在N中的行号
                brow = M.data[p].j;

                if (brow < N.mu)
                    t = N.rpos[brow + 1];
                else
                    t = N.tu + 1;

                for (q = N.rpos[brow]; q < t; ++q) {
                    ccol = N.data[q].j; // 乘积元素在Q中列号
                    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;
} // MultSMatrix

ostream& operator<<(ostream& os, const RLSMatrix& m)
{
    for (int n = 1; n <= m.tu; ++n)
        os << m.data[n].i << " " << m.data[n].j << " " << m.data[n].e << endl;
    return os;
}

// main.cpp

#include <iostream>
#include "RLSMatrix.h"

using namespace std;

int main()
{
    RLSMatrix M, N, Q;
    M.mu = 3; M.nu = 4; M.tu = 4;
    M.rpos[1] = 1; M.rpos[2] = 3; M.rpos[3] = 4;
    M.data[1].i = 1; M.data[1].j = 1; M.data[1].e = 3;
    M.data[2].i = 1; M.data[2].j = 4; M.data[2].e = 5;
    M.data[3].i = 2; M.data[3].j = 2; M.data[3].e = -1;
    M.data[4].i = 3; M.data[4].j = 1; M.data[4].e = 2;

    N.mu = 4; N.nu = 2; N.tu = 4;
    N.rpos[1] = 1; N.rpos[2] = 2; N.rpos[3] = 3; N.rpos[4] = 5;
    N.data[1].i = 1; N.data[1].j = 2; N.data[1].e = 2;
    N.data[2].i = 2; N.data[2].j = 1; N.data[2].e = 1;
    N.data[3].i = 3; N.data[3].j = 1; N.data[3].e = -2;
    N.data[4].i = 3; N.data[4].j = 2; N.data[4].e = 4;

    MultSMatrix(M, N, Q);

    cout << M << string(16, '*') << endl << N << string(16, '*') << endl << Q;

    return 0;
}