• 【数据结构】数组和字符串（七）：特殊矩阵的压缩存储：三元组表的转置、加法、乘法操作

    文章目录

    4.2.1 矩阵的数组表示

    【数据结构】数组和字符串（一）：矩阵的数组表示

    4.2.2 特殊矩阵的压缩存储

      矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵，如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等, 如果用这种方式存储，会出现大量存储空间存放重复信息或零元素的情况，这样会造成很大的空间浪费。为节约存储空间和算法（程序）运行时间，通常会采用压缩存储的方法。

    • 对角矩阵：指除了主对角线以外的元素都为零的矩阵，即对 任意 i ≠ j (1≤ i , j ≤n)，都有M(i, j)=0。由于只有主对角线上有非零元素，只需存储主对角线上的元素即可。
    • 三角矩阵：指上三角或下三角的元素都为零的矩阵。同样地，只需存储其中一部分非零元素，可以节省存储空间。
    • 对称矩阵：指矩阵中的元素关于主对角线对称的矩阵。由于对称矩阵的非零元素有一定的规律，可以只存储其中一部分元素，从而减少存储空间。
    • 稀疏矩阵：指大部分元素为零的矩阵。传统的按行优先次序存储方法会浪费大量空间来存储零元素，因此采用压缩存储的方法更为合适。常见的压缩存储方法有：压缩稠密行（CSR）、压缩稠密列（CSC）、坐标列表（COO）等。

    a. 对角矩阵的压缩存储

    【数据结构】数组和字符串（二）：特殊矩阵的压缩存储：对角矩阵——一维数组

    b~c. 三角、对称矩阵的压缩存储

    【数据结构】数组和字符串（三）：特殊矩阵的压缩存储：三角矩阵、对称矩阵——一维数组

    d. 稀疏矩阵的压缩存储——三元组表

      对于稀疏矩阵的压缩存储，由于非零元素的个数远小于零元素的个数，并且非零元素的分布没有规律，无法简单地利用一维数组和映射公式来实现压缩存储。针对稀疏矩阵，通常采用特定的数据结构来进行压缩存储，以减少存储空间的占用。

      一种常见的稀疏矩阵压缩存储方法是使用"三元组"表示法，也称为COO（Coordinate）格式，只存储非零元素的值以及它们的行列坐标。通过使用三元组（Triplet）来表示非零元素的位置和值，每个三元组包含三个信息：非零元素的行索引、非零元素的列索引以及非零元素的值。

    【数据结构】数组和字符串（四）：特殊矩阵的压缩存储：稀疏矩阵——三元组表

    4.2.3三元组表的转置、加法、乘法、操作

    转置

      假设稀疏矩阵存储在一个三元组表a中，且A的非零元素个数为count，算法Transpose求A的转置矩阵并将其保存在三元组表b中。

    • 算法的主要思想是针对每个列号k（k=0, 2,… , n-1）对a进行扫描，考察a中是否有列号为k的结点（注意：列号为k的结点可能不止一个），若有，记为a[u]（假定a[u]在a中的行号为i ），将a[u]依次保存在b的b[w] 中，则row(b[w])=k，col(b[w])=i，value(b[w]) =value(a[u]).
      在这里插入图片描述
    TripletTable matrixTranspose(TripletTable* table) {
    TripletTable result;
    initTable(&result, table->cols, table->rows);  // 转置后的矩阵行列互换
    int j = 0;
    for (int k = 0; k < table->cols; k++) {
        for (int i = 0; i < table->length; i++) {
            Triple* element = &(table->data[i]);
            if (element->col == k) {
                insertElement(&result, k, element->row, element->value);
//                result.data[j].row = k;  // 该元素在result中的行号应为k
//                result.data[j].col = element->row;  // 该元素在result中的列号应为其在table中的行号
//                result.data[j].value = element->value;
                j++;  // 考察result中的下一个结点
                result.length = j;  // 更新result的长度
            }
        }
//        printf("\n");
//        displayMatrix(&result);
    }
    return result;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

       matrixTranspose函数实现稀疏矩阵的转置操作：

    • 首先，创建一个新的TripletTable变量result，用于存储输入矩阵的转置。
    • 使用initTable函数初始化result，将其行数设置为输入矩阵的列数，列数设置为输入矩阵的行数。
    • 使用一个循环遍历输入矩阵的所有元素：
      • 对于每个元素，将其行号作为转置后矩阵中的列号，列号作为转置后矩阵中的行号，并将值保持不变。
      • 将转置后的元素插入到result中。
    • 返回result作为输入矩阵的转置。

    加法

    TripletTable matrixAddition(TripletTable* table1, TripletTable* table2) {
    TripletTable result;
    initTable(&result, table1->rows, table1->cols);

    int i = 0, j = 0;
    while (i < table1->length && j < table2->length) {
        Triple* element1 = &(table1->data[i]);
        Triple* element2 = &(table2->data[j]);

        if (element1->row < element2->row || (element1->row == element2->row && element1->col < element2->col)) {
            insertElement(&result, element1->row, element1->col, element1->value);
            i++;
        } else if (element1->row > element2->row || (element1->row == element2->row && element1->col > element2->col)) {
            insertElement(&result, element2->row, element2->col, element2->value);
            j++;
        } else {
            int sum = element1->value + element2->value;
            if (sum != 0) {
                insertElement(&result, element1->row, element1->col, sum);
            }
            i++;
            j++;
        }
    }

    while (i < table1->length) {
        Triple* element1 = &(table1->data[i]);
        insertElement(&result, element1->row, element1->col, element1->value);
        i++;
    }

    while (j < table2->length) {
        Triple* element2 = &(table2->data[j]);
        insertElement(&result, element2->row, element2->col, element2->value);
        j++;
    }

    return result;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

       matrixAddition函数实现稀疏矩阵的加法操作：

    • 创建一个新的TripletTable变量result，用于存储两个输入矩阵的和。
    • 使用initTable函数初始化result，将其行数和列数设置为与输入矩阵相同。
    • 使用两个指针i和j分别指向两个输入矩阵的元素。
    • 通过比较当前元素的行号和列号，以及使用循环遍历的方式，将两个输入矩阵的元素逐个比较并进行相应的操作：
      • 如果第一个矩阵的元素在行号和列号上小于第二个矩阵的元素，将第一个矩阵的元素插入到result中，并增加指向第一个矩阵元素的指针i。
      • 如果第一个矩阵的元素在行号和列号上大于第二个矩阵的元素，将第二个矩阵的元素插入到result中，并增加指向第二个矩阵元素的指针j。
      • 如果两个矩阵的元素在行号和列号上相等，将它们的值相加，并将结果插入到result中。然后，增加指向两个矩阵元素的指针i和j。
    • 处理完所有元素后，将剩余的未处理元素插入到result中。
    • 返回result作为两个输入矩阵的和。

    乘法

    TripletTable matrixMultiplication(TripletTable* table1, TripletTable* table2) {
    TripletTable result;
    initTable(&result, table1->rows, table2->cols);

    int matrix[table1->rows][table2->cols];
    for (int i = 0; i < table1->rows; i++) {
        for (int j = 0; j < table2->cols; j++) {
            matrix[i][j] = 0;
        }
    }

    for (int i = 0; i < table1->length; i++) {
        Triple* element1 = &(table1->data[i]);

        for (int j = 0; j < table2->length; j++) {
            Triple* element2 = &(table2->data[j]);

            if (element1->col == element2->row) {
                matrix[element1->row][element2->col] += element1->value * element2->value;
            }
        }
    }

    for (int i = 0; i < table1->rows; i++) {
        for (int j = 0; j < table2->cols; j++) {
            if (matrix[i][j] != 0) {
                insertElement(&result, i, j, matrix[i][j]);
            }
        }
    }

    return result;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

       matrixMultiplication函数实现稀疏矩阵的乘法操作：

    • 创建一个新的TripletTable变量result，用于存储两个输入矩阵的乘积。
    • 使用initTable函数初始化result，将其行数设置为第一个输入矩阵的行数，列数设置为第二个输入矩阵的列数。
    • 创建一个临时的二维数组matrix，用于存储两个输入矩阵相乘的结果。
    • 将matrix中的所有元素初始化为0。
    • 使用两个嵌套的循环遍历第一个输入矩阵的所有元素：
      • 对于每个元素，使用另一个嵌套的循环遍历第二个输入矩阵的所有元素。
      • 如果第一个矩阵的元素的列号等于第二个矩阵的元素的行号，将它们的值相乘，并将结果累加到matrix中对应位置的元素上。
    • 遍历matrix中的所有元素，将非零元素插入到result中。
    • 返回result作为两个输入矩阵的乘积。

    算法测试

    int main() {
    TripletTable matrixA, matrixB;
    initTable(&matrixA, 3, 3);
    initTable(&matrixB, 3, 3);

    // Insert elements into matrix A
    insertElement(&matrixA, 0, 0, 1);
    insertElement(&matrixA, 0, 2, 2);
    insertElement(&matrixA, 1, 1, 3);
    insertElement(&matrixA, 2, 0, 4);
    insertElement(&matrixA, 2, 2, 5);

    // Insert elements into matrix B
    insertElement(&matrixB, 0, 1, 6);
    insertElement(&matrixB, 1, 0, 7);
    insertElement(&matrixB, 1, 2, 8);
    insertElement(&matrixB, 2, 1, 9);

    printf("Matrix A:\n");
    displayMatrix(&matrixA);

    printf("\nMatrix B:\n");
    displayMatrix(&matrixB);

    TripletTable matrixC = matrixAddition(&matrixA, &matrixB);
    printf("\nMatrix A + B:\n");
    displayMatrix(&matrixC);

    TripletTable matrixD = matrixTranspose(&matrixA);
    printf("\nTranspose of Matrix A:\n");
    displayMatrix(&matrixD);

    TripletTable matrixE = matrixMultiplication(&matrixA, &matrixB);
    printf("\nMatrix A * B:\n");
    displayMatrix(&matrixE);
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    实验结果

    在这里插入图片描述

    代码整合

    #include 
#include 
#include 
#define MAX_SIZE 10

typedef struct {
    int row;
    int col;
    int value;
} Triple;

typedef struct {
    Triple data[MAX_SIZE];
    int rows;
    int cols;
    int length;
} TripletTable;

void initTable(TripletTable* table, int rows, int cols) {
    table->rows = rows;
    table->cols = cols;
    table->length = 0;
    memset(table->data, 0, sizeof(Triple) * MAX_SIZE);  // 新添加
}

void insertElement(TripletTable* table, int row, int col, int value) {
    if (table->length >= MAX_SIZE) {
        printf("Table is full. Cannot insert more elements.\n");
        return;
    }

    Triple* element = &(table->data[table->length]);
    element->row = row;
    element->col = col;
    element->value = value;

    table->length++;
}

void displayMatrix(TripletTable* table) {
    int matrix[table->rows][table->cols];
    for (int i = 0; i < table->rows; i++) {
        for (int j = 0; j < table->cols; j++) {
            matrix[i][j] = 0;
        }
    }
//    printf("Row\tColumn\tValue\n");
    for (int i = 0; i < table->length; i++) {
        Triple* element = &(table->data[i]);
//        printf("%d\t%d\t%d\n", element->row, element->col, element->value);
        matrix[element->row][element->col] = element->value;
    }

//    printf("Matrix:\n");
    for (int i = 0; i < table->rows; i++) {
        for (int j = 0; j < table->cols; j++) {
            printf("%d\t", matrix[i][j]);
        }
        printf("\n");
    }
}
TripletTable matrixAddition(TripletTable* table1, TripletTable* table2) {
    TripletTable result;
    initTable(&result, table1->rows, table1->cols);

    int i = 0, j = 0;
    while (i < table1->length && j < table2->length) {
        Triple* element1 = &(table1->data[i]);
        Triple* element2 = &(table2->data[j]);

        if (element1->row < element2->row || (element1->row == element2->row && element1->col < element2->col)) {
            insertElement(&result, element1->row, element1->col, element1->value);
            i++;
        } else if (element1->row > element2->row || (element1->row == element2->row && element1->col > element2->col)) {
            insertElement(&result, element2->row, element2->col, element2->value);
            j++;
        } else {
            int sum = element1->value + element2->value;
            if (sum != 0) {
                insertElement(&result, element1->row, element1->col, sum);
            }
            i++;
            j++;
        }
    }

    while (i < table1->length) {
        Triple* element1 = &(table1->data[i]);
        insertElement(&result, element1->row, element1->col, element1->value);
        i++;
    }

    while (j < table2->length) {
        Triple* element2 = &(table2->data[j]);
        insertElement(&result, element2->row, element2->col, element2->value);
        j++;
    }

    return result;
}



TripletTable matrixMultiplication(TripletTable* table1, TripletTable* table2) {
    TripletTable result;
    initTable(&result, table1->rows, table2->cols);

    int matrix[table1->rows][table2->cols];
    for (int i = 0; i < table1->rows; i++) {
        for (int j = 0; j < table2->cols; j++) {
            matrix[i][j] = 0;
        }
    }

    for (int i = 0; i < table1->length; i++) {
        Triple* element1 = &(table1->data[i]);

        for (int j = 0; j < table2->length; j++) {
            Triple* element2 = &(table2->data[j]);

            if (element1->col == element2->row) {
                matrix[element1->row][element2->col] += element1->value * element2->value;
            }
        }
    }

    for (int i = 0; i < table1->rows; i++) {
        for (int j = 0; j < table2->cols; j++) {
            if (matrix[i][j] != 0) {
                insertElement(&result, i, j, matrix[i][j]);
            }
        }
    }

    return result;
}

TripletTable matrixTranspose(TripletTable* table) {
    TripletTable result;
    initTable(&result, table->cols, table->rows);  // 转置后的矩阵行列互换
    int j = 0;
    for (int k = 0; k < table->cols; k++) {
        for (int i = 0; i < table->length; i++) {
            Triple* element = &(table->data[i]);
            if (element->col == k) {
                insertElement(&result, k, element->row, element->value);
//                result.data[j].row = k;  // 该元素在result中的行号应为k
//                result.data[j].col = element->row;  // 该元素在result中的列号应为其在table中的行号
//                result.data[j].value = element->value;
                j++;  // 考察result中的下一个结点
                result.length = j;  // 更新result的长度
            }
        }
//        printf("\n");
//        displayMatrix(&result);

    }
    return result;
}


int main() {
    TripletTable matrixA, matrixB;
    initTable(&matrixA, 3, 3);
    initTable(&matrixB, 3, 3);

    // Insert elements into matrix A
    insertElement(&matrixA, 0, 0, 1);
    insertElement(&matrixA, 0, 2, 2);
    insertElement(&matrixA, 1, 1, 3);
    insertElement(&matrixA, 2, 0, 4);
    insertElement(&matrixA, 2, 2, 5);

    // Insert elements into matrix B
    insertElement(&matrixB, 0, 1, 6);
    insertElement(&matrixB, 1, 0, 7);
    insertElement(&matrixB, 1, 2, 8);
    insertElement(&matrixB, 2, 1, 9);

    printf("Matrix A:\n");
    displayMatrix(&matrixA);

    printf("\nMatrix B:\n");
    displayMatrix(&matrixB);

    TripletTable matrixC = matrixAddition(&matrixA, &matrixB);
    printf("\nMatrix A + B:\n");
    displayMatrix(&matrixC);

    TripletTable matrixD = matrixTranspose(&matrixA);
    printf("\nTranspose of Matrix A:\n");
    displayMatrix(&matrixD);

    TripletTable matrixE = matrixMultiplication(&matrixA, &matrixB);
    printf("\nMatrix A * B:\n");
    displayMatrix(&matrixE);
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
  • 相关阅读:
    最新！基于Open3D的点云处理入门与实战教程
    超详细BootLoader原理分析
    uniapp开发微信小程序：为什么用户授权信息弹窗没有了？
    软件设计模式系列之五——建造者模式
    Kubernetes：详解如何将CPU Manager做到游刃有余
    操作系统绪论习题
    flutter系列之:把box布局用出花来
    图嵌入概述：节点、边和图嵌入方法及Python实现
    保持checkbox选中状态
    springboot和vue：四、web入门(静态资源访问+文件上传+拦截器)
  • 原文地址：https://blog.csdn.net/m0_63834988/article/details/134081298