[数组](2)矩阵运算

三元组顺序表

假设以顺序存储结构来表示三元组表,则可得稀疏矩阵的一种压缩存储方式——我们称之为:三元组顺序表:

#define MAXSIZE 12500//假设非零元个数的最大值为12500
typedef struct
{
    int i, j;//该非零元的行下标和列下标
    ElemType e;
}Triple;
typedef struct
{
    Triple data[MAXSIZE + 1];//非零元三元组表,data[0]未用
    int mu, nu, tu;//矩阵的行数,列数和非零元
}TSMatrix;

在此,data域中表示非零元的三元组是以行序为主序顺序排列的,从下面的讨论中读者容易看出这样做将有利于进行某些矩阵运算,下面讨论在这种压缩存储结构下如何实现矩阵的转置运算

转置矩阵

转置运算是一种最简单的矩阵运算,对于一个m×n的矩阵M,它的转置矩阵T是一个n×m的矩阵,且T(i,j)=M(j,i),1<=i<=n,1<=j<=m。

例如上图中的M和T互为转置矩阵。

显然,一个稀疏矩阵的转置矩阵仍然是稀疏矩阵,假设a和b是TSMatrix型的变量,分别表示矩阵M和T,那么如何由a得到b呢?

从分析a和b之间的差异可见只要做到:

  1. 将矩阵的行列值相互交换;
  2. 将每个三元组中的i和j相互调换;
  3. 重排三元组之间的次序便可实现矩阵的转置;

前两条是容易做到的,关键是如何实现第三条,即如何使b.data中的三元组是以T的行(M的列)为主序依次排列的。

可以有两种处理方法:

img

(1)按照b.data中的三元组的次序依次在a.data中找到相应的三元组进行转置,换句话说,按照矩阵M的列序来进行转置,为了找到M每一列中所有的非零元素,需要对其三元组表a.data从第一行起整个扫描一遍,由于a.data是以M的行序为主序来存放每个非零元的,由此得到的恰是b.data应有的顺序,其具体算法描述如下算法所示

Status TransposeSMatrix(TSMatrix M, TSMatrix* T)
//采用三元组表存储表示,求稀疏矩阵M的转置矩阵T
{
    T->mu = M.mu;
    T->nu = M.mu;
    T->tu = M.tu;
    if (T->tu)
    {
        int q = 1;
        for (col = 1; col <= M.nu; ++col)
        {
            for (p = 1; p <= M.tu; ++p)
            {
                if (M.data[p].j == col)
                {
                    T->data[q].i = M.data[p].j;
                    T->data[q].j = M.data[p].i;
                    T->data[q].e = M.data[p].e;
                    q++;
                }
            }
        }
    }
    return OK;
}
//枚举算法,第一次循环控制转置后的三元组,第二个循环不断去遍历M表,从1到M.nu(此时M.nu(列)为T.mu(行))去找寻与该其相等的在M中的列数,然后载入进T表

分析这个算法,主要的工作是在p和col两重循环中完成的,故算法的时间复杂度为O(nu×tu),即和M的列数及非零元的个数的乘积成正比,我们知道,一般矩阵的转置算法为:

Status Transpose(char** M,char** T)
{
    for (col = 1; col <= nu; col++)
    {
        for (row = 1; row <= mu; row++)
        {
            T[col][row] = M[row][col];
        }
    }
}
  1. 其实际复杂度为O(mu×nu),当非零元的个数tu和mu×nu同数量级时,上述算法的时间复杂度就为O(mu×nu²)(例如,假设在100×500的矩阵中有tu=10000个非零元),虽然节省了存储空间,但是时间复杂度提高了。
  2. 按照a.data中三元组的次序进行转置,并将转置后的三元组置入b中恰当的位置,如果能预先确定矩阵M中每一列(即T中每一行)的第一个非零元在b.data中应有的位置,那么在对a.data中的三元组依次作转置时,便可直接放到b.data中恰当的位置上去,为了确定这些位置,在转置前,应先求得M的每一列中非零元的个数,进而求得每一列的第一个非零元在b.data中应有的位置。

在此,需要附设num和cpot两个向量,num[col]表示矩阵M中第col列中非零元素个数cpot[col]指示M中第col列的第一个非零元在b.data中的恰当位置,显然有状态如下

  • copt[1]=1;
  • copt[col]=copt[col-1]+num[col-1] 2<=col<=a.nu

这种转置方法称为快速转置,其算法如下:

Status FastTransposeSMatrix(TSMatrix M, TSMatrix* T)
//采用三元组顺序表存储表示,求稀疏矩阵M的转置矩阵T
{
    T->mu = M.mu;
    T->nu = M.mu;
    T->tu = M.tu;

    if (T->tu)
    {
        for (col = 1; col <= M.nu; col++)//num数组清零
        {
            num[col] = 0;
        }
        for (t = 1; t <= M.tu; t++)
        {
            num[M.data[t].j]++;//求M中每一列含非零元的个数
        }
        cpot[1] = 1;
        //求第col列中第一个非零元在b.data中的序号
        for (col = 2; col <= M.mu; col++)
        {
            cpot[col] = cpot[col - 1] + num[col - 1];
        }
        for (p = 1; p <= M.mu; p++)
        {
            col = M.data[p].j;
            q = cpot[col];
            T->data[q].i = M.data[p].j;
            T->data[q].j = M.data[p].i;

            T->data[q].e = M.data[p].e;
            cpot[col]++;
        }
    }
    return OK;
}

这个算法仅比前一个算法多用了两个辅助向量,从时间上看,算法中有四个并列的单循环,循环次数分别为nu和tu,因而总时间复杂度为O(nu+tu),在M的非零元个数tu和mu×nu等数量级时,其时间复杂度为O(mu×nu),和经典算法的时间复杂度相同。

三元组顺序表又称有序的双下标法,它的特点是,非零元在表中行行序有序存储,由此便于进行依行顺序处理的矩阵运算,然而,若需按行号存取某一行的非零元,则需从头开始进行查找。

行逻辑链接的顺序表

为了便于随机存取任一一行的非零元,则需知道每一行的第一个非零元在三元组表中的位置,为此,可将上节快速转置矩阵的算法中创建的,指示“行”信息的辅助数组cpot固定在稀疏矩阵的存储结构中。

称这种“带行链接信息”的三元组表为行逻辑链接的顺序表,其类型描述如下:

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

在两矩阵相乘的例子中,可以看出上述方法的优越性。

若设:

Q=M×N

其中,M是m[1]×n[1],N是m[2]×n[2],当n[1]=m[2]时有:

    for (int i = 1; i < m1; i++)
    {
        for (int j = 1; j <= n2; j++)
        {
            Q[i][j] = 0;
            for (int k = 1; k <= n1; k++)
            {
                Q[i][j] += M[i][k] * N[k][j];
            }
        }
    }

此算法的时间复杂度是O(m1×n1×n2)

当M和N是稀疏矩阵并用三元组表作存储结构时,就不能套用上述算法,假设M和N分别为:

img

则Q=M×N为:

img

它们的三元组M.data、N.data和Q.data分别为:

img

两矩阵需要相乘的定义为:

  • A矩阵×B矩阵需要满足:
  • A矩阵的行数等于B矩阵的列数
  • 乘积矩阵Q的行数为A矩阵的行数,列数为B矩阵的列数
  • 乘积矩阵的每一行的每一个元素等于A矩阵当行×B矩阵当列每个元素之和

由上方M、N、Q矩阵图和代码可推导而出

在经典算法中,不论M(i,k)和N(k,j)的值是否为零,都要进行一次乘法运算,而实际上,这两者有一个值为零时,其乘积也为零,因此,在对稀疏矩阵进行运算时,应免去这种无效操作

换句话说,只需在M.data和N.data中找到相应的各对元素(即M.data中的 j 值和N.data中的 i 值相等的各对元素)相乘即可

例如,M.data[1]表示矩阵元(1,1,3)只要个N.data[1]表示的矩阵元(1,2,2)相乘,而M.data[2]表示的矩阵元(1,4,5)则不需和N中任何元素相乘,因为N.data中没有i为4的元素

由此可见,为了得到非零的乘积,只要对M.data[1..M.tu]中的每个元素(i,k,M(i,k)) ——<(1<=i<=m[1],1<=k<=n[1])>找到N.data中所有相应的元素(k,j,N(k,j))——(<1<=k<=m[2],1<=j<=n[2]>)相乘即可,为此需在N.data中寻找矩阵N中第k行的所有非零元,在稀疏矩阵的行逻辑链接的顺序表中,N.data为我们提供了有关信息,例如:的矩阵N的rpos值如下表所示

img

并且,由于rpos[row]指示矩阵N的第row行中第一个非零元在N.data中的序号,则rpos[row+1]-1指示矩阵N的第row行中最后一个非零元在N.data中的序号,而最后一行中最后一个非零元在N.data中的位置显然就是N.tu了

注意:两个稀疏矩阵相乘的乘积不一定是稀疏矩阵,反之,即每个分量值M(i,k)×N(k,j)不为零,其累加值Q[i] [j]也可能为零,因此乘积矩阵Q中的元素是否为非零元,只有在求得累加和后才能得知,由于Q中元素的行号和M中元素的行号一致,又M中元素排列是以M的行序为主序的,由此可对Q进行逐行处理,先求得累加求和的中间结果(Q的一行),然后再压缩存储到Q.data中去

由此,两个稀疏矩阵相乘(Q=M×N)的过程可大致描述如下:

Q初始化;
if (Q是非零矩阵)
{//逐行求积
    for (arow = 1; arow <= M.mu; arow++)
    {//处理M的每一行
        ctemp[] = 0;//累加器清零
        计算Q中第arow行的积并存入ctemp[]中;
        将ctemp[]中非零元压缩存储到Q.data;
    }//for arow
}//if

下列算法是根据上述过程求精过程的结果:

Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix* Q)
{//求矩阵乘积Q=M×N,采用行逻辑链接存储表示
    if (M.mu != 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的每一行
        {
            ctemp[] = 0;//当前行各元素累加器清零
            Q.rpos[arow] = Q.tu + 1;
            if (arow < M.mu)
            {
                rp = M.rpos[arow + 1];
            }
            else
            {
                tp = M.tu + 1;
            }
            for (p = M.rpos[arow]; p < tp; p++)//对当前行中每一个非零元
            {
                brow = M.data[p].j;//找到对应元在N中的行号
                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;
                }

            }
        }//求得Q中crow(=arow)行的非零元
        for (ccol = 1; ccol <= Q.nu; ccol++)
        {
            if (ctemp[ccol])
            {
                if (Q.tu++ > MAXSIZE)
                {
                    return ERROR;
                }
                Q.data[Q.tu] = (arow, ccol, ctemp[ccol]);
            }
        }
    }
    return OK;
}

对照书本的学习以及[懒猫老师的视频]我们明白了转置矩阵,快速转置,矩阵加法及乘法的知识点:

对照懒猫老师的教程有以下的矩阵三元组测试代码。

三元组的构造以及根据三元组相加、相乘等测试代码如下所示(以下采用经典算法):

#define _CRT_SECURE_NO_WARNINGS
typedef int Status;
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAXSIZE 12500//假设非零原个数的最大值为:12500

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

typedef struct
{
    Triple data[MAXSIZE];//非零元三元组表,data[0]未用
    int mu, nu, tu;//矩阵的行数,列数和非零元个数
}TSMatrix;



//功能函数
void PrintTriple(TSMatrix* TS, int** Array);//构造并且打印二维数组
void SetTriple(TSMatrix* TS);//打印三元组
int FoundTriple(TSMatrix* TS, int mu, int nu, int tu);//构造一个三元组
void AddMatrix(TSMatrix M, TSMatrix N, TSMatrix* Q);//矩阵相加
void MultMatrix(TSMatrix M, TSMatrix N, TSMatrix* Q);//矩阵相乘 


int main()
{
    int mu, nu, tu;
    TSMatrix A, B, Q;
    printf("请输入A矩阵的:行、列、非零元个数");
    scanf("%d,%d,%d", &mu, &nu, &tu);


    FoundTriple(&A, mu, nu, tu);


    printf("请输入B矩阵的:行、列、非零元个数");
    scanf("%d,%d,%d", &mu, &nu, &tu);


    FoundTriple(&B, mu, nu, tu);


    //AddMatrix(A, B, &Q);

    MultMatrix(A, B, &Q);

    system("pause");
    return 0;
}

int FoundTriple(TSMatrix* TS, int mu, int nu, int tu)
{
    TS->mu = mu;
    TS->nu = nu;
    TS->tu = 0;
    
    int row, col, item;
    //判断非法输入值
    if (mu == 0 || nu == 0 || tu > mu * nu)
    {
        return 0;
    }

    //依次输入元素值所在位置
    for (int i = 0; i < tu; i++)
    {
        printf("请依次输入行、列和非零元:");
        scanf("%d,%d,%d", &row, &col, &item);
        if (row > mu || col > nu||item==0)
        {
            printf("非法输入值\n");
            return 0;
        }
        else
        {
            if (TS->tu == 0)
            {
                TS->data[TS->tu].i = row;
                TS->data[TS->tu].j = col;
                TS->data[TS->tu].item = item;
                TS->tu++;
            }
            else
            {
                int i;
                for (i = 0; i < TS->tu; i++)
                {
                    if (TS->data[i].i >= row)
                    {
                        break;
                    }
                }
                while (TS->data[i].i == row && TS->data[i].j < col)
                {
                    i++;
                }
                if (TS->data[i].i == row && TS->data[i].j == col)
                {
                    TS->data[i].i = row;
                    TS->data[i].j = col;
                    TS->data[i].item = item;
                }
                else
                {

                    for (int j = TS->tu - 1; j >= i; j--)//移动三元组元素
                    {
                        TS->data[j + 1] = TS->data[j];
                    }
                    TS->data[i].i = row;
                    TS->data[i].j = col;
                    TS->data[i].item = item;
                    TS->tu++;
                }
            }
        }
    }

    //打印出三元组表:

    int** Array;

    SetTriple(TS);
    
    printf("\n\n");

    PrintTriple(TS, &Array);

    return 1;
}


void SetTriple(TSMatrix* TS)
{
    
    printf("三元组表如下:\n");
    for (int i = 0; i < TS->tu; i++)
    {
        printf("%d  %d  %d\n", TS->data[i].i, TS->data[i].j, TS->data[i].item);
    }
    printf("\n总行:%d,总列:%d,总元素个数:%d\n", TS->mu, TS->nu, TS->tu);

}

void PrintTriple(TSMatrix* TS, int** Array)
{
    //映射到二维数组中的状态
    //初始化二维数组
    Array = (int**)malloc(sizeof(int*) * TS->mu + 1);
    for (int k = 0; k < TS->mu; k++)
    {
        Array[k] = (int*)malloc(sizeof(int) * TS->nu + 1);
        for (int k1 = 0; k1 < TS->nu; k1++)
        {
            Array[k][k1] = 0;
        }
    }

    //添加元素
    for (int i = 0; i < TS->tu; i++)
    {
        Array[TS->data[i].i][TS->data[i].j] = TS->data[i].item;
    }



    printf("二维数组如下:\n");
    for (int k = 0; k < TS->mu; k++)
    {
        for (int k1 = 0; k1 < TS->nu; k1++)
        {
            printf("%d ", Array[k][k1]);
        }
        printf("\n");
    }
}
void AddMatrix(TSMatrix M, TSMatrix N, TSMatrix* Q)
{
    if (M.mu != N.mu || M.nu != N.nu || M.tu + N.tu > MAXSIZE)
    {
        printf("两矩阵不能相加");
    }
    else
    {
        int i = 0, j = 0, k = 0;
        Q->tu = 0;
        Q->mu = M.mu;
        Q->nu = M.nu;
        while (i < M.tu && j < N.tu)
        {
            if (M.data[i].i == N.data[j].i && M.data[i].j == N.data[i].j)
            {
                Q->data[k].i = M.data[i].i;
                Q->data[k].j = M.data[i].j;
                Q->data[k].item = M.data[i].item + N.data[j].item;
                i++; j++;
                k++;
                Q->tu++;
            }
            else
            {
                if (M.data[i].i < N.data[j].i)
                {
                    Q->data[k].i = M.data[i].i;
                    Q->data[k].j = M.data[i].j;
                    Q->data[k].item = M.data[i].item;
                    i++, k++, Q->tu++;

                }
                else if (M.data[i].i == N.data[j].i && M.data[i].j < N.data[j].j)
                {
                    Q->data[k].i = M.data[i].i;
                    Q->data[k].j = M.data[i].j;
                    Q->data[k].item = M.data[i].item;
                    i++, k++, Q->tu++;
                }
                else
                {
                    Q->data[k].i = N.data[j].i;
                    Q->data[k].j = N.data[j].j;
                    Q->data[k].item = N.data[j].item;
                    j++, k++, Q->tu++;
                }

            }

        }

        if (i < M.tu)
        {
            for (i; i < M.mu; i++)
            {
                Q->data[k].i = M.data[i].i;
                Q->data[k].j = M.data[i].j;
                Q->data[k].item = M.data[i].item;
                i++, k++, Q->tu++;
            }
        }
        else
        {
            Q->data[k].i = N.data[j].i;
            Q->data[k].j = N.data[j].j;
            Q->data[k].item = N.data[j].item;
            j++, k++, Q->tu++;

        }

        int** Array;

        printf("\n\n构造Q映射到矩阵内为:\n");

        PrintTriple(Q, &Array);

        SetTriple(Q);
    }
}
void MultMatrix(TSMatrix M, TSMatrix N, TSMatrix* Q)//矩阵相乘 
{
    if (M.nu != N.mu)
    {
        printf("不满足相乘条件");
    }
    else
    {
        Q->tu = 0;
        Q->mu = M.mu;
        Q->nu = N.nu;
        int k = 0;
        for (int i = 0; i < M.tu; i++)
        {
            for (int j = 0; j < N.tu; j++)
            {
                if (M.data[i].j == N.data[j].i)
                {
                    Q->data[k].i = M.data[i].i;
                    Q->data[k].j = N.data[j].j;
                    Q->data[k].item = M.data[i].item * N.data[j].item;
                    k++;
                    Q->tu++;
                }
            }
        }
        int** Array;

        printf("\n\n构造Q映射到矩阵内为:\n");

        PrintTriple(Q, &Array);

        SetTriple(Q);
    }

}

本文链接:

https://nullcode.fun/33.html
1 + 1 =
快来做第一个评论的人吧~