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

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）来表示非零元素的位置和值，每个三元组包含三个信息：非零元素的行索引、非零元素的列索引以及非零元素的值。

结构体

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

typedef struct {
    Triple data[MAX_SIZE];
    int rows;
    int cols;
    int length;
} TripletTable;
1
2
3
4
5
6
7
8
9
10
11
12

  定义了两个结构体：Triple 和 TripletTable。

• Triple 结构体表示稀疏矩阵的非零元素，包含三个字段：row 表示行号，col 表示列号，value 表示元素的值。
• TripletTable 结构体用于存储稀疏矩阵的数据，包含一个 data 数组用于存储非零元素的 Triple 结构体，以及 rows、cols 和 length 字段分别表示矩阵的行数、列数和非零元素的数量。

初始化

void initTable(TripletTable* table, int rows, int cols) {
    table->rows = rows;
    table->cols = cols;
    table->length = 0;
}
1
2
3
4
5

   initTable 函数用于初始化 TripletTable 结构体，指定矩阵的行数和列数，并将 length 字段置为 0。

元素设置

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++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

  insertElement 函数用于向稀疏矩阵中插入一个元素，传入参数为行号、列号和元素的值。

• 函数首先检查当前非零元素的数量是否已达到上限 MAX_SIZE
  • 如果达到上限则输出错误信息并返回。
  • 否则，将新元素插入到 data 数组的末尾，并更新 length 字段。

打印矩阵

void displayTable(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");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

  displayTable 函数用于显示稀疏矩阵的内容：

• 创建一个与稀疏矩阵相同大小的二维数组 matrix，并将其所有元素初始化为 0；
• 遍历 data 数组中的非零元素，输出每个元素的行号、列号和值，并将相应位置的 matrix 数组元素更新为对应的值；
• 输出整个矩阵的内容。

主函数

int main() {
    TripletTable table;
    initTable(&table, 3, 3);

    insertElement(&table, 0, 0, 1);
    insertElement(&table, 0, 1, 2);
    insertElement(&table, 1, 1, 3);
    insertElement(&table, 2, 2, 4);

    displayTable(&table);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

• 创建一个 TripletTable 结构体 table，并使用 initTable 函数初始化它，指定矩阵的行数和列数为3。
• 调用 insertElement 函数向 table 中插入四个非零元素，分别位于 (0, 0)、(0, 1)、(1, 1) 和 (2, 2) 位置。
• 通过调用 displayTable 函数，打印出稀疏矩阵的内容和对应的完整矩阵表示。

输出结果

代码整合

#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;
}

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 displayTable(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");
    }
}

int main() {
    TripletTable table;
    initTable(&table, 3, 3);

    insertElement(&table, 0, 0, 1);
    insertElement(&table, 0, 1, 2);
    insertElement(&table, 1, 1, 3);
    insertElement(&table, 2, 2, 4);

    displayTable(&table);

    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