下面实现的特殊矩阵存储方法

三元组顺序存储方法&转置

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 12500
// 三元组顺序表示稀疏矩阵
// written at 2018-6-1 23:37:22

typedef int ElemType;
typedef struct{
    int i;  // row
    int j;  // column
    ElemType e;
}tripple;
typedef struct{
    tripple data[MAXSIZE+1];  // 0 not use
    int mu, nu, tu;  // 行，列，非零元总数
}tsMatrix;

tripple init_tribble(int i, int j, ElemType e){
    tripple temp;
    temp.i = i;
    temp.j = j;
    temp.e = e;
    return temp;
}

void print_sparse_matrix(tsMatrix temp){
    printf("**********START************\n");
    printf("i\tj\tv\t\n");
    for (int i=1; i<=temp.tu; i++){
        printf("%d\t%d\t%d\t\n",temp.data[i].i,temp.data[i].j,temp.data[i].e);
    }
    printf("***********END*************\n");
}

void transposeMatrix(tsMatrix m, tsMatrix *t){
    // 按列转置矩阵
    t->mu = m.nu;  // step 1
    t->nu = m.mu;  // step 1
    t->tu = m.tu;
    // step 2 & step 3
    if(t->tu){
        int q=1;
        for (int col=1;col<=m.nu;++col){
            for (int 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++;
                }
            }
        }
    }
}

void quickTranspose(tsMatrix m, tsMatrix *t){
    // 通过预先确认M中每一列的第一个非零元在b.data中的应有的位置，则可以省时间
    t->mu = m.nu;
    t->nu = m.mu;
    t->tu = m.tu;
    if (t->tu){
        int num[m.nu + 1];  // 0 not use
        for (int col=1; col<=m.nu; col++) num[col] = 0;  // 初始化num数组
        for (int temp=1; temp<=m.tu; temp++) ++num[m.data[temp].j];
        int cpot[m.nu + 1];  // 0 not use
        cpot[1] = 1; // 第一列中第一个元素肯定是在第一个位置
        // 求第col列中第一个非零元在b.data中的序号
        for (int col=2; col<=m.nu;++col){
            cpot[col]=cpot[col-1]+num[col-1];
        }
        for (int p=1;p<=m.tu;++p){
            int col = m.data[p].j;
            int 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];
        }
    }
}

void main(){
    // init the martix and let the matrix not empty
    tsMatrix temp;
    temp.data[1] = init_tribble(1, 2, 12);
    temp.data[2] = init_tribble(1, 3, 9);
    temp.data[3] = init_tribble(3, 1, -3);
    temp.data[4] = init_tribble(3, 6, 14);
    temp.data[5] = init_tribble(4, 3, 24);
    temp.data[6] = init_tribble(5, 2, 18);
    temp.data[7] = init_tribble(6, 1, 15);
    temp.data[8] = init_tribble(6, 4, -7);
    // 课本97页中的M矩阵
    temp.mu = 6;
    temp.nu = 7;
    temp.tu = 8;
    print_sparse_matrix(temp);
    tsMatrix t;
    tsMatrix t2;
    transposeMatrix(temp, &t2);
    quickTranspose(temp, &t);
    printf("\t按列转置\t\n");
    print_sparse_matrix(t2);
    printf("\t快速转置\t\n");
    print_sparse_matrix(t);
}

输出结果如下：

**********START************
i       j       v
1       2       12
1       3       9
3       1       -3
3       6       14
4       3       24
5       2       18
6       1       15
6       4       -7
***********END*************
        按列转置
**********START************
i       j       v
1       3       -3
1       6       15
2       1       12
2       5       18
3       1       9
3       4       24
4       6       -7
6       3       14
***********END*************
        快速转置
**********START************
i       j       v
1       3       -3
1       6       15
2       1       12
2       5       18
3       1       9
3       4       24
4       6       -7
6       3       14
***********END*************

行逻辑链接的顺序表

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 12500
/*
行逻辑连接的顺序表
为了便于随机存取任意一行的非零元引入的第二种表示方法
written at 2018-6-2 18:26:30
*/

typedef int ElemType;
typedef struct{
    int i;  // row
    int j;  // column
    ElemType e;
}tripple;
typedef struct RLSMatrix{
    tripple data[MAXSIZE+1];
    int mu, nu, tu;
    int rops[MAXRC + 1];  // 各行第一个非零元的位置表
}RLSMatrix;