• 【数据结构】数组和字符串（九）：稀疏矩阵的链接存储：十字链表的插入、查找、删除操作

    文章目录

    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三元组表的转置、加法、乘法、操作

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

    4.2.4十字链表

      在稀疏矩阵的十字链表中，每个非零元素都由一个节点表示。节点包含了几个字段：

    1. LEFT：指向该节点在同一行中的左邻非零元素的地址信息。
    2. UP：指向该节点在同一列中的上邻非零元素的地址信息。
    3. ROW：存储该节点在矩阵中的行号。
    4. COL：存储该节点在矩阵中的列号。
    5. VAL：存储该节点的元素值。

      每一行都有一个表头节点，它引导着该行的循环链表，循环链表中的每个节点按照列号的顺序排列。同样，每一列也有一个表头节点，它引导着该列的循环链表，循环链表中的每个节点按照行号的顺序排列。
      关于循环链表： 【数据结构】线性表（三）循环链表的各种操作（创建、插入、查找、删除、修改、遍历打印、释放内存空间）

    在这里插入图片描述

    • 在稀疏矩阵的十字链表中，每一行和每一列都有一个表头节点。

      • 对于行表头节点 BASEROW[i]，其中 i 表示行号，范围从 1 到 m（矩阵的行数）。如果该行为空（即没有非零元素），则 COL(Loc(BASEROW[i])) 的值为 -1。否则，COL(Loc(BASEROW[i])) 的值为该行中最右边的非零元素的列号。

      • 对于列表头节点 BASECOL[j]，其中 j 表示列号，范围从 1 到 n（矩阵的列数）。如果该列为空（即没有非零元素），则 ROW(Loc(BASECOL[j])) 的值为 -1。否则，ROW(Loc(BASECOL[j])) 的值为该列中最下边的非零元素的行号。

    • 由于行和列都是循环链表，行表头节点 BASEROW[i] 中的 LEFT 指针循环地链接到该行最右边的非零元素，列表头节点 BASECOL[j] 中的 UP 指针循环地链接到该列最下边的非零元素。
       
       通过这种方式，可以用较少的空间表示稀疏矩阵，并且可以快速地进行行和列的遍历操作。每个节点的 LEFT 和 UP 指针可以用来定位其左邻和上邻非零元素，从而实现矩阵的访问和操作。

    0. 十字链表的创建、遍历打印、销毁

    【数据结构】数组和字符串（八）：稀疏矩阵的链接存储：十字链表的创建、遍历打印（按行、按列、打印矩阵）、销毁

    1. 插入

    void insertElement(SparseMatrix* matrix, int row, int col, int value) {
    if (row <= 0 || row > matrix->rows || col <= 0 || col > matrix->cols) {
        printf("Invalid position!\n");
        return;
    }

    // 创建新节点
    MatrixNode* newNode = (MatrixNode*)malloc(sizeof(MatrixNode));
    newNode->row = row;
    newNode->col = col;
    newNode->value = value;
    newNode->right = NULL;
    newNode->down = NULL;

    // 插入到行链表
    if (matrix->rowHeaders[row] == NULL || matrix->rowHeaders[row]->col > col) {
        // 插入到行链表的头部
        newNode->right = matrix->rowHeaders[row];
        matrix->rowHeaders[row] = newNode;
    } else {
        MatrixNode* current = matrix->rowHeaders[row];
        while (current->right != NULL && current->right->col < col) {
            current = current->right;
        }
        newNode->right = current->right;
        current->right = newNode;
    }

    // 插入到列链表
    if (matrix->colHeaders[col] == NULL || matrix->colHeaders[col]->row > row) {
        // 插入到列链表的头部
        newNode->down = matrix->colHeaders[col];
        matrix->colHeaders[col] = newNode;
    } else {
        MatrixNode* current = matrix->colHeaders[col];
        while (current->down != NULL && current->down->row < row) {
            current = current->down;
        }
        newNode->down = current->down;
        current->down = newNode;
    }
}


    • 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
    • 检查行数和列数是否在有效范围内，如果不是，则打印错误消息并返回。
    • 创建一个新的节点，并将行、列和值存储在节点的相应字段中。
    • 在行链表中插入节点：
      • 如果当前行的行链表为空，或者当前行的行链表头节点的列大于要插入的列：
        • 将要插入的节点的右指针指向当前行的行链表头节点。
        • 将当前行的行链表头节点更新为要插入的节点。
      • 否则，遍历当前行的行链表，直到找到插入位置：
        • 将要插入的节点的右指针指向当前节点的右指针。
        • 将当前节点的右指针指向要插入的节点。
    • 在列链表中插入节点：
      • 如果当前列的列链表为空，或者当前列的列链表头节点的行大于要插入的行：
        • 将要插入的节点的下指针指向当前列的列链表头节点。
        • 将当前列的列链表头节点更新为要插入的节点。
      • 否则，遍历当前列的列链表，直到找到插入位置：
        • 将要插入的节点的下指针指向当前节点的下指针。
        • 将当前节点的下指针指向要插入的节点。

    2. 查找

    MatrixNode* findElement(SparseMatrix* matrix, int row, int col) {
    if (row <= 0 || row > matrix->rows || col <= 0 || col > matrix->cols) {
        printf("Invalid position!\n");
        return NULL;
    }

    MatrixNode* current = matrix->rowHeaders[row];
    while (current != NULL && current->col != col) {
        current = current->right;
    }

    return current;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 检查行数和列数是否在有效范围内，如果不是，则打印错误消息并返回NULL。
    • 从第一行开始遍历稀疏矩阵的每一行：
      • 通过行表头节点数组获取当前行的行链表头节点。
      • 遍历当前行的行链表，直到找到要查找的节点或遍历完整个链表。
    • 如果找到要查找的节点，则返回节点的指针；否则，返回NULL。

    3. 删除

    void deleteElement(SparseMatrix* matrix, int row, int col) {
    if (row <= 0 || row > matrix->rows || col <= 0 || col > matrix->cols) {
        printf("Invalid position!\n");
        return;
    }

    // 在行链表中删除节点
    MatrixNode* current = matrix->rowHeaders[row];
    MatrixNode* prev = NULL;
    while (current != NULL && current->col != col) {
        prev = current;
        current = current->right;
    }
    if (current == NULL) {
        printf("Element not found!\n");
        return;
    }
    if (prev == NULL) {
        matrix->rowHeaders[row] = current->right;
    } else {
        prev->right = current->right;
    }

    // 在列链表中删除节点
    current = matrix->colHeaders[col];
    prev = NULL;
    while (current != NULL && current->row != row) {
        prev = current;
        current = current->down;
    }
    if (prev == NULL) {
        matrix->colHeaders[col] = current->down;
    } else {
        prev->down = current->down;
    }

    // 释放节点内存
    free(current);
}


    • 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
    • 检查行数和列数是否在有效范围内，如果不是，则打印错误消息并返回。
    • 在行链表中查找要删除的节点：
      • 从当前行的行链表头节点开始遍历行链表，直到找到要删除的节点或遍历完整个链表。
    • 如果找到要删除的节点：
      • 如果要删除的节点是行链表的头节点：
        • 将当前行的行链表头节点更新为要删除的节点的右指针。
      • 否则，遍历行链表，直到找到要删除的节点的前一个节点：
        • 将前一个节点的右指针指向要删除的节点的右指针。
    • 在列链表中查找要删除的节点：
      • 从当前列的列链表头节点开始遍历列链表，直到找到要删除的节点或遍历完整个链表。
    • 如果找到要删除的节点：
      • 如果要删除的节点是列链表的头节点：
        • 将当前列的列链表头节点更新为要删除的节点的下指针。
      • 否则，遍历列链表，直到找到要删除的节点的前一个节点：
        • 将前一个节点的下指针指向要删除的节点的下指针。
    • 释放要删除的节点的内存。

    4. 主函数

    int main() {
    // 创建一个3x3的稀疏矩阵
    SparseMatrix* matrix = createSparseMatrix(6, 6);

    // 插入元素
    insertElement(matrix, 1, 3, 5);
    insertElement(matrix, 1, 4, 2);
    insertElement(matrix, 5, 2, 1);
    insertElement(matrix, 5, 1, 8);
    insertElement(matrix, 5, 5, 7);

    // 打印稀疏矩阵
    printf("Sparse Matrix:\n");
    printSparseMatrix(matrix);


    // 查找节点
    MatrixNode* node = findElement(matrix, 1, 4);
    if (node != NULL) {
        printf("\nFound node: (%d, %d, %d)\n", node->row, node->col, node->value);
    } else {
        printf("\nNode not found!\n");
    }
    // 删除节点
    deleteElement(matrix,5,5);
    printf("Sparse Matrix after deletion:\n");
    printSparseMatrix(matrix);

    // 销毁稀疏矩阵
    destroySparseMatrix(matrix);

    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

    在这里插入图片描述

    5. 代码整合

    #include 
#include 

// 定义矩阵节点结构
typedef struct MatrixNode {
    int row;
    int col;
    int value;
    struct MatrixNode* right;
    struct MatrixNode* down;
} MatrixNode;

// 定义稀疏矩阵结构
typedef struct SparseMatrix {
    int rows;
    int cols;
    MatrixNode** rowHeaders;
    MatrixNode** colHeaders;
} SparseMatrix;

// 创建稀疏矩阵
SparseMatrix* createSparseMatrix(int rows, int cols) {
    SparseMatrix* matrix = (SparseMatrix*)malloc(sizeof(SparseMatrix));
    matrix->rows = rows;
    matrix->cols = cols;

    // 创建行表头节点数组
    matrix->rowHeaders = (MatrixNode**)malloc((rows + 1) * sizeof(MatrixNode*));
    for (int i = 0; i <= rows; i++) {
        matrix->rowHeaders[i] = NULL;
    }

    // 创建列表头节点数组
    matrix->colHeaders = (MatrixNode**)malloc((cols + 1) * sizeof(MatrixNode*));
    for (int j = 0; j <= cols; j++) {
        matrix->colHeaders[j] = NULL;
    }

    return matrix;
}

// 销毁稀疏矩阵
void destroySparseMatrix(SparseMatrix* matrix) {
    if (matrix == NULL) {
        return;
    }

    // 释放所有节点内存
    for (int i = 1; i <= matrix->rows; i++) {
        MatrixNode* current = matrix->rowHeaders[i];
        while (current != NULL) {
            MatrixNode* temp = current;
            current = current->right;
            free(temp);
        }
    }

    // 释放行表头节点数组
    free(matrix->rowHeaders);

    // 释放列表头节点数组
    free(matrix->colHeaders);

    // 释放稀疏矩阵结构
    free(matrix);
}

// 插入元素
void insertElement(SparseMatrix* matrix, int row, int col, int value) {
    if (row <= 0 || row > matrix->rows || col <= 0 || col > matrix->cols) {
        printf("Invalid position!\n");
        return;
    }

    // 创建新节点
    MatrixNode* newNode = (MatrixNode*)malloc(sizeof(MatrixNode));
    newNode->row = row;
    newNode->col = col;
    newNode->value = value;
    newNode->right = NULL;
    newNode->down = NULL;

    // 插入到行链表
    if (matrix->rowHeaders[row] == NULL || matrix->rowHeaders[row]->col > col) {
        // 插入到行链表的头部
        newNode->right = matrix->rowHeaders[row];
        matrix->rowHeaders[row] = newNode;
    } else {
        MatrixNode* current = matrix->rowHeaders[row];
        while (current->right != NULL && current->right->col < col) {
            current = current->right;
        }
        newNode->right = current->right;
        current->right = newNode;
    }

    // 插入到列链表
    if (matrix->colHeaders[col] == NULL || matrix->colHeaders[col]->row > row) {
        // 插入到列链表的头部
        newNode->down = matrix->colHeaders[col];
        matrix->colHeaders[col] = newNode;
    } else {
        MatrixNode* current = matrix->colHeaders[col];
        while (current->down != NULL && current->down->row < row) {
            current = current->down;
        }
        newNode->down = current->down;
        current->down = newNode;
    }
}

// 删除元素
void deleteElement(SparseMatrix* matrix, int row, int col) {
    if (row <= 0 || row > matrix->rows || col <= 0 || col > matrix->cols) {
        printf("Invalid position!\n");
        return;
    }

    // 在行链表中删除节点
    MatrixNode* current = matrix->rowHeaders[row];
    MatrixNode* prev = NULL;
    while (current != NULL && current->col != col) {
        prev = current;
        current = current->right;
    }
    if (current == NULL) {
        printf("Element not found!\n");
        return;
    }
    if (prev == NULL) {
        matrix->rowHeaders[row] = current->right;
    } else {
        prev->right = current->right;
    }

    // 在列链表中删除节点
    current = matrix->colHeaders[col];
    prev = NULL;
    while (current != NULL && current->row != row) {
        prev = current;
        current = current->down;
    }
    if (prev == NULL) {
        matrix->colHeaders[col] = current->down;
    } else {
        prev->down = current->down;
    }

    // 释放节点内存
    free(current);
}

// 查找节点
MatrixNode* findElement(SparseMatrix* matrix, int row, int col) {
    if (row <= 0 || row > matrix->rows || col <= 0 || col > matrix->cols) {
        printf("Invalid position!\n");
        return NULL;
    }

    MatrixNode* current = matrix->rowHeaders[row];
    while (current != NULL && current->col != col) {
        current = current->right;
    }

    return current;
}

// 打印稀疏矩阵
void printSparseMatrix(SparseMatrix* matrix) {
    for (int i = 1; i <= matrix->rows; i++) {
        MatrixNode* current = matrix->rowHeaders[i];
        for (int j = 1; j <= matrix->cols; j++) {
            if (current != NULL && current->col == j) {
                printf("%d ", current->value);
                current = current->right;
            } else {
                printf("0 ");
            }
        }
        printf("\n");
    }
}


int main() {
    // 创建一个3x3的稀疏矩阵
    SparseMatrix* matrix = createSparseMatrix(6, 6);

    // 插入元素
    insertElement(matrix, 1, 3, 5);
    insertElement(matrix, 1, 4, 2);
    insertElement(matrix, 5, 2, 1);
    insertElement(matrix, 5, 1, 8);
    insertElement(matrix, 5, 5, 7);

    // 打印稀疏矩阵
    printf("Sparse Matrix:\n");
    printSparseMatrix(matrix);


    // 查找节点
    MatrixNode* node = findElement(matrix, 1, 4);
    if (node != NULL) {
        printf("\nFound node: (%d, %d, %d)\n", node->row, node->col, node->value);
    } else {
        printf("\nNode not found!\n");
    }
    // 删除节点
    deleteElement(matrix,5,5);
    printf("Sparse Matrix after deletion:\n");
    printSparseMatrix(matrix);

    // 销毁稀疏矩阵
    destroySparseMatrix(matrix);

    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
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
  • 相关阅读:
    服务器开发系列（三）——Linux与Windows操作系统基础功能对比
    ScanImage介绍
    国内大模型五虎
    AI大模型的制作：RAG和向量数据库，分别是什么？
    openGauss内核：SQL解析过程分析
    有哪些常见的网络安全威胁？
    MyBatis
    进程间通讯-共享内存
    测试环境搭建教程（APP+WEB）
    探究js数据类型和底层原理
  • 原文地址：https://blog.csdn.net/m0_63834988/article/details/134090707