数组还能玩出花来.

一. 稀疏矩阵的存储

稀疏矩阵顾名思义就是元素很少的矩阵, 如果采取一般的存储方式会导致空间的浪费, 因为要存储很多没有意义的元素.
稀疏矩阵存储一个非零元素就要存储这个元素的行列坐标和值(通过结构体实现), 非零元素这么存储, 而整个稀疏矩阵就要存储数组的行数, 列数, 非零元素的个数, 以及非零元素数组.

#define MAXSIZE 12500

typedef int ElemType;

typedef struct 
{
    int i, j;    //非零元素的坐标
    ElemType e;    //非零元素元素的值
}Triple;

typedef struct 
{
    Triple data[MAXSIZE+1];    //非零元素数组, 0 号元素未使用
    int mu, nu, tu;    //行数, 列数, 非零元个数
}TSMatrix;

二. 稀疏矩阵的转置

稀疏矩阵的初始化就不谈了.
一般的二维数组的转置: a[i][j] = b[j][i] 即可.
如果是稀疏矩阵, 非零元素数组里面的数据可能是这样的: (1,2,12), (1,3,9), (3,1,-3), (3,6,14). 假设把每个元素的坐标交换, 就变成了: (2,1,12), (3,1,9), (1,3,-3), (6,3,14).
转置的确是这么干的, 第 i 行 j 列的值转置后就变成了第 j 行 i 列. 问题是这么做了之后, 我原来是一行一行来存储的, 现在存了一个第二行的, 存了一个第三行的, 又存了一个第一行的, 显然乱了.

转置算法一

构造新矩阵的时候, 先构造第一行, 然后第二行, 以此类推.
每构造一行, 我都遍历原来的矩阵, 遇到列数等于我行数的就存起来. 相当于我要构造第一行, 我就找到原数组的第一列, 把这一列的元素以此保存起来. 这样子是为了保证新矩阵的顺序是对的.

存的时候, 非零元素行变成列, 列变成行, 值相等. 使得 a[i][j] = b[j][i];

int TransposeSMatrix(TSMatrix M, TSMatrix *T)
{
    int i, j, n;
    T->tu = M.tu; T->mu = M.nu; T->nu = M.mu;    //新矩阵的行数(列数)=原矩阵的列数(行数), 并且个数相同
    if(T->tu)    //确保原矩阵不为空
    {
        n = 1;    //n 是新矩阵非零元素的序号, 从 1 开始(也可以从 0 开始, 并不重要)
        for(i=1; i<=T->mu; i++)    //遍历新矩阵的每一行, 从第一行开始
        {
            for(j=1; j<=M.tu; j++)    //遍历原数组的每一个元素
            {
                if(M.data[j].j == i)    //遇到原数组 i 列的元素, 就保存起来
                {
                    T->data[n].i = M.data[j].j;    //行=列
                    T->data[n].j = M.data[j].i;    //列=行
                    T->data[n].e = M.data[j].e;    //值相等
                    n++;    //下面准备给新数组的下一个非零元素赋值
                }
            }
        }
    }
    return 1;
}

复杂度分析

普通的二维数组转置的时间复杂度是 mu*nu .(也就是行数乘以列数, 因为只要遍历矩阵一遍. 第 i 行 j 列的元素用新矩阵第 j 行 i 列的元素存储即可.)
而上面这个算法, 首先遍历原矩阵每一列(也就是新矩阵的每一列) nu, 然后遍历原矩阵 tu. 如果 tu 接近于 mu*nu, 那么时间复杂度就是: O(mu*nu^2), 时间复杂度比一般情况要高, 所以, 这个算法只适用于 tu 远远小于 mu*nu 的情况.

转置算法二

先求出原来每一列有多少个元素
再求出每一列的第一个元素在新矩阵中出现的位置, 很显然, 第一列的第一个元素出现在新矩阵的一号位置. 然后第二列的第一个元素出现在位置是 1 加上第一列元素的个数. 比如第一行有 4 个元素, 1+4=5 , 所以第二列第一个元素的位置就是 5. 此后, 每一列的第一个元素在新矩阵中的位置都等于: 前一列第一个元素的位置加上前一列元素的个数.

然后从头开始取原矩阵的元素, 看它是第几列的, 我们已经知道某一列的第一个元素应该出现在新矩阵中的什么位置, 所以进行赋值即可, 记得交换行号列号. 同时记录一下, 再次遇到这一列的元素时候, 就放到下一个位置.

int FastTransposeSMatrix(TSMatrix M, TSMatrix *T)
{
    int i, n, col;
    T->tu = M.tu; T->nu = M.mu; T->mu = M.nu;
    int * num = malloc(sizeof(int)*(M.nu+1));    //动态生成数组, 存储原矩阵每列的元素个数(0 号不使用)
    for(i=1; i<=M.nu; i++)    num[i] = 0;     //每列元素个数初始化为 0
    for(i=1; i<=M.tu; i++)    num[M.data[i].j]++;    //计算出每列有多少个元素
    int * cpot = malloc(sizeof(int)*(M.nu+1));    //用来存储每列第一个元素在新矩阵中出现的位置的数组
    cpot[1] = 1;    //第一列第一个元素肯定是新矩阵的一号元素
    for(i=2; i<=M.nu; i++)
    {
        cpot[i] = cpot[i-1] + num[i-1];    //每列第一个元素的位置都是前一列的位置加上前一列的个数
    }
    for(i=1; i<=M.tu; i++)
    {
        col = M.data[i].j;    //遇到某一列的元素
        n = cpot[col];        //看看这一列的元素应该存放到哪一个位置
        T->data[n].i = M.data[i].j;
        T->data[n].j = M.data[i].i;
        T->data[n].e = M.data[i].e;
        cpot[col]++;          //加一是为了: 下次遇到这一列的元素时, 放到下一个位置
    }
    return 1;
}

复杂度分析

时间复杂度为 O(nu+tu), 当 tu 和 mu*nu 等数量级的时候, 复杂度为 O(mu*nu), 和经典算法的时间复杂度相同.

三. 完整代码

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 12500

typedef int ElemType;

typedef struct 
{
    int i, j;    //元素的坐标
    ElemType e;    //元素的值
}Triple;

typedef struct 
{
    Triple data[MAXSIZE];    //非零元素数组, 0 号元素未使用
    int mu, nu, tu;    //行数, 列数, 非零元个数
}TSMatrix;

void Init(TSMatrix * TSM)
{
    int i;
    printf("输入非零元素的个数, 行数, 列数: \n");
    scanf("%d %d %d", &TSM->tu, &TSM->mu, &TSM->nu);    //输入非零元素的个数
    for(i=1; i<=TSM->tu; i++)
    {
        printf("输入坐标(从 1 开始), 值: \n");
        scanf("%d %d %d", &TSM->data[i].i, &TSM->data[i].j, &TSM->data[i].e);
    }
}

void Show(TSMatrix * TSM)
{
    int i;
    for(i=1; i<=TSM->tu; i++)
    {
        printf("%-2d %-2d %-2d\n", TSM->data[i].i, TSM->data[i].j, TSM->data[i].e);
    }
    printf("\n");
}

int TransposeSMatrix(TSMatrix M, TSMatrix *T)
{
    int i, j, n;
    T->tu = M.tu; T->mu = M.nu; T->nu = M.mu;    //新矩阵的行数(列数)=原矩阵的列数(行数), 并且个数相同
    if(T->tu)    //确保原矩阵不为空
    {
        n = 1;    //n 是新矩阵非零元素的序号, 从 1 开始(也可以从 0 开始, 并不重要)
        for(i=1; i<=T->mu; i++)    //遍历新矩阵的每一行, 从第一行开始
        {
            for(j=1; j<=M.tu; j++)    //遍历原数组的每一个元素
            {
                if(M.data[j].j == i)    //遇到原数组 i 列的元素, 就保存起来
                {
                    T->data[n].i = M.data[j].j;    //行=列
                    T->data[n].j = M.data[j].i;    //列=行
                    T->data[n].e = M.data[j].e;    //值相等
                    n++;    //下面准备给新数组的下一个非零元素赋值
                }
            }
        }
    }
    return 1;
}

int FastTransposeSMatrix(TSMatrix M, TSMatrix *T)
{
    int i, n, col;
    T->tu = M.tu; T->nu = M.mu; T->mu = M.nu;
    int * num = malloc(sizeof(int)*(M.nu+1));    //动态生成数组, 存储原矩阵每列的元素个数(0 号不使用)
    for(i=1; i<=M.nu; i++)    num[i] = 0;     //每列元素个数初始化为 0
    for(i=1; i<=M.tu; i++)    num[M.data[i].j]++;    //计算出每列有多少个元素
    int * cpot = malloc(sizeof(int)*(M.nu+1));    //用来存储每列第一个元素在新矩阵中出现的位置的数组
    cpot[1] = 1;    //第一列第一个元素肯定是新矩阵的一号元素
    for(i=2; i<=M.nu; i++)
    {
        cpot[i] = cpot[i-1] + num[i-1];    //每列第一个元素的位置都是前一列的位置加上前一列的个数
    }
    for(i=1; i<=M.tu; i++)
    {
        col = M.data[i].j;    //遇到某一列的元素
        n = cpot[col];        //看看这一列的元素应该存放到哪一个位置
        T->data[n].i = M.data[i].j;
        T->data[n].j = M.data[i].i;
        T->data[n].e = M.data[i].e;
        cpot[col]++;          //加一是为了: 下次遇到这一列的元素时, 放到下一个位置
    }
    return 1;
}

int main(int argc, char const *argv[])
{
    TSMatrix a, b;

    Init(&a);
    Show(&a);

    FastTransposeSMatrix(a, &b);
    Show(&b);


    
    return 0;
}

严蔚敏的书是好书, 但是有一点不好: 没有考虑到我的智商.