稀疏矩阵的压缩-三元组表（转置）

若矩阵中的非零元素远远小于矩阵元素的个数，且分布没有规律，则称这个矩阵为稀疏矩阵。 压缩存储是指对多个值相同的元素只分配一个存储空间，对零元素不分配空间。

稀疏矩阵的压缩存储有两种方法：三元组的顺序存储（三元组表）和链式存储（十字链表）。

现在主要讲三元组表，由于两个阶数不同的矩阵可能具有相同的非零元素，为了区别，在存储三元组时，同时还应存储该矩阵的行数、列数。通常为了运算的方便，也存放非零元素的个数。这种以顺序存储

结构来表示三元组的线性表，称之为三元组表。稀疏矩阵的存储的三元组表的存储结构可定义如下：

#define MAXSIZE 1000            //用户自定义三元组最大个数
typedef int ElemType;
typedef struct {                //三元组
    int row,col;                //非零元素的行数和列数
    ElemType e;                 //非零元素的值
}Triple;
typedef struct {
    Triple data[MAXSIZE];       //三元组表
    int m,n, len;               //矩阵的行数、列数和非零个数
}TSMatrix;

三元组表的矩阵转置运算-“直接取，顺序存”

//转置
TSMatrix TransTSMatrixSlow(TSMatrix a,TSMatrix b) {
    int q;
    b.m = a.n;
    b.n = a.m;
    b.len = a.len;
    if (b.len) {
        q = 0;                          //B中的非零个数
        for (int j = 0; j < a.n;j++) {          //按列转置
            for (int h = 0; h < a.len; h++) {
                if (j==a.data[h].col) {         //本列中一个非零元素
                    b.data[q].row = a.data[h].col;
                    b.data[q].col = a.data[h].row;
                    b.data[q].e = a.data[h].e;
                    q++;
                }
            }
        }
    }
    else {
        cout << "矩阵为空，无需转置！" << endl;
    }
    return b;
}

但是每处理一列就要查遍三元组表，工作量比较大

三元组表的矩阵快速转置运算-“顺序取，直接存”

//快速转置
TSMatrix TransTSMatrixFast(TSMatrix a, TSMatrix b) {
    int number[MAXSIZE],position[MAXSIZE];
    b.m = a.n;
    b.n = a.m;
    b.len = a.len;
    for (int j = 0; j < a.n;j++) {
        number[j] = 0;      //将矩阵a每一列非零元素的个数初始化为零
    }
    for (int t = 0; t < a.len; t++) {
        number[a.data[t].col]++;        //求每一列非零元素的个数
    }
    position[0] = 0;
    for (int j = 1; j < a.n; j++) { //a.data[]的第j列第一个非零元素在b.data中的序号
        position[j] = position[j - 1] + number[j - 1];
    }
    int j,q;
    for (int p = 0; p < a.len; p++) {   //求转置矩阵b的三元组表
        j = a.data[p].col;
        q = position[j];
        b.data[q].row = a.data[p].col;
        b.data[q].col = a.data[p].row;
        b.data[q].e = a.data[p].e;
        position[j]++;
    }
    return b;
}

核心：若用number数组记录矩阵A中每列的非零元素个数，用position数组记录A中每列第一个非零元素在三元组表中的位置，则若第j-1列的第一个非零元素在position[j-1]的位置上，第j列的第一个非零元素必在第position[j-1]+number[j-1]位置上。

完整代码

#include<iostream>
using namespace std;
#define MAXSIZE 1000            //用户自定义三元组最大个数
typedef int ElemType;
typedef struct {                //三元组
    int row,col;                //非零元素的行数和列数
    ElemType e;                 //非零元素的值
}Triple;
typedef struct {
    Triple data[MAXSIZE];       //三元组表
    int m,n, len;               //矩阵的行数、列数和非零个数
}TSMatrix;
//输出矩阵
void print(TSMatrix a){
    int k;
    for (int i = 0; i < a.m;i++) {
        for (int j = 0; j < a.n;j++) {
            k = 0;
            for(int h=0;h<a.len;h++){
                if (i == a.data[h].row && j==a.data[h].col) {
                    cout <<"     "<< a.data[h].e;
                    k = 1;
                }
            }
            if (k == 0) {
                cout << "     " << k;
            }
        }
        cout << endl;
    }
}
//转置
TSMatrix TransTSMatrixSlow(TSMatrix a,TSMatrix b) {
    int q;
    b.m = a.n;
    b.n = a.m;
    b.len = a.len;
    if (b.len) {
        q = 0;                          //B中的非零个数
        for (int j = 0; j < a.n;j++) {          //按列转置
            for (int h = 0; h < a.len; h++) {
                if (j==a.data[h].col) {         //本列中一个非零元素
                    b.data[q].row = a.data[h].col;
                    b.data[q].col = a.data[h].row;
                    b.data[q].e = a.data[h].e;
                    q++;
                }
            }
        }
    }
    else {
        cout << "矩阵为空，无需转置！" << endl;
    }
    return b;
}
//快速转置
TSMatrix TransTSMatrixFast(TSMatrix a, TSMatrix b) {
    int number[MAXSIZE],position[MAXSIZE];
    b.m = a.n;
    b.n = a.m;
    b.len = a.len;
    for (int j = 0; j < a.n;j++) {
        number[j] = 0;      //将矩阵a每一列非零元素的个数初始化为零
    }
    for (int t = 0; t < a.len; t++) {
        number[a.data[t].col]++;        //求每一列非零元素的个数
    }
    position[0] = 0;
    for (int j = 1; j < a.n; j++) { //a.data[]的第j列第一个非零元素在b.data中的序号
        position[j] = position[j - 1] + number[j - 1];
    }
    int j,q;
    for (int p = 0; p < a.len; p++) {   //求转置矩阵b的三元组表
        j = a.data[p].col;
        q = position[j];
        b.data[q].row = a.data[p].col;
        b.data[q].col = a.data[p].row;
        b.data[q].e = a.data[p].e;
        position[j]++;
    }
    return b;
}
void main() {
    TSMatrix A, B;
    A.m = 5;
    A.n = 6;
    A.len = 7;
    A.data[0].row = 0; A.data[0].col = 1; A.data[0].e = 6;
    A.data[1].row = 0; A.data[1].col = 5; A.data[1].e = -2;
    A.data[2].row = 2; A.data[2].col = 3; A.data[2].e = -8;
    A.data[3].row = 3; A.data[3].col = 1; A.data[3].e = 3;
    A.data[4].row = 3; A.data[4].col = 5; A.data[4].e = 7;
    A.data[5].row = 4; A.data[5].col = 0; A.data[5].e = -12;
    A.data[6].row = 4; A.data[6].col = 2; A.data[6].e = 9;
    cout << "矩阵A为：" << endl;
    print(A);
    cout << "求系数矩阵A的转置矩阵B？" << endl;
    B = TransTSMatrixSlow(A,B);
    cout << "转置矩阵B为:" << endl;
    print(B);
    cout << endl;
    B = TransTSMatrixFast(A,B);
    print(B);
    system("pause");
}

---

本文总阅读量次 本站访客数人次