十字链表

数据结构

稀疏矩阵的优雅表示：深入理解“十字链表”

1. 为什么需要十字链表？

考虑一个 1000×1000 的矩阵，如果它只有 100 个非零元素，却要占用 1000×1000×sizeof(int) 字节的内存（假设整型）。这无疑是巨大的浪费。为了解决这个问题，我们需要只存储非零元素。

传统的稀疏矩阵存储方式还有：

  • 三元组表（Triplet Form）： 存储非零元素的 (行，列，值) 三元组，但查找和修改某个元素不方便。
  • 行主序链表： 每行一个链表，存储该行的非零元素。
  • 列主序链表： 每列一个链表，存储该列的非零元素。

三元组表不利于矩阵的加法、乘法等操作；行主序链表在按列访问时效率低下，反之亦然。十字链表则巧妙地解决了这些问题，它允许我们既能按行遍历，也能按列遍历非零元素。

2. 十字链表的核心思想与节点结构

十字链表的核心思想是：每个非零元素都存储在一个节点中，并且这个节点同时连接着它所在行的下一个非零元素和它所在列的下一个非零元素。

它通过在矩阵的行和列方向上分别构建链表，将行链表和列链表“交叉”起来，从而形成一个十字形结构。

十字链表的基本组成部分：

  1. 行/列头节点（Row/Column Head Node）： 用于管理每一行或每一列的非零元素链表。它们通常构成一个头节点数组（或链表），其中每个头节点都包含指向该行/列第一个非零元素的指针。
    • 为了统一表示，我们通常也会把行/列头节点看作是特殊类型的节点。
  2. 元素节点（Element Node）： 存储非零元素的信息，并包含四个指针：
    • row: 非零元素所在的行索引。
    • col: 非零元素所在的列索引。
    • value: 非零元素的值。
    • right: 指向同一行中下一个非零元素的指针。
    • down: 指向同一列中下一个非零元素的指针。

节点结构体定义：

为了简化，我们可以将所有节点统一为一种类型，并使用一个标志位来区分是头节点还是元素节点，或者更常见地，使用两种不同的结构体，或者在一个统一的结构体中只在元素节点中存储 value。这里我们采用一种更灵活的定义，它可以表示普通元素节点，也可以表示行/列头节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>

// 定义稀疏矩阵的节点类型
typedef struct OLNode {
    int row;       // 行索引
    int col;       // 列索引
    int value;     // 存储的非零元素值（仅对元素节点有效）

    struct OLNode *right; // 指向同一行下一个非零元素的指针
    struct OLNode *down;  // 指向同一列下一个非零元素的指针
} OLNode;

// 定义稀疏矩阵的十字链表结构
typedef struct CrossList {
    OLNode** row_heads;   // 行头节点数组
    OLNode** col_heads;   // 列头节点数组
    int rows;             // 矩阵的行数
    int cols;             // 矩阵的列数
    int num_elements;     // 非零元素的数量
} CrossList;

3. 十字链表的基本操作

3.1 初始化十字链表

创建矩阵结构，并初始化行头节点数组和列头节点数组。

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
// 初始化一个空的十字链表
CrossList* initCrossList(int m_rows, int m_cols) {
    CrossList* matrix = (CrossList*)malloc(sizeof(CrossList));
    if (matrix == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    matrix->rows = m_rows;
    matrix->cols = m_cols;
    matrix->num_elements = 0;

    // 分配行头节点数组
    matrix->row_heads = (OLNode**)malloc(sizeof(OLNode*) * m_rows);
    if (matrix->row_heads == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    for (int i = 0; i < m_rows; i++) {
        matrix->row_heads[i] = NULL; // 初始化行链表为空
    }

    // 分配列头节点数组
    matrix->col_heads = (OLNode**)malloc(sizeof(OLNode*) * m_cols);
    if (matrix->col_heads == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    for (int i = 0; i < m_cols; i++) {
        matrix->col_heads[i] = NULL; // 初始化列链表为空
    }
    return matrix;
}

3.2 插入非零元素

插入是十字链表的核心操作。每插入一个元素，都需要将其正确地插入到其对应行的链表和列的链表中。

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
// 插入一个非零元素
void insertElement(CrossList* matrix, int row, int col, int value) {
    if (row < 0 || row >= matrix->rows || col < 0 || col >= matrix->cols) {
        printf("插入失败：索引越界。\n");
        return;
    }
    if (value == 0) { // 零元素不存储
        return;
    }

    OLNode* newNode = (OLNode*)malloc(sizeof(OLNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->row = row;
    newNode->col = col;
    newNode->value = value;
    newNode->right = NULL;
    newNode->down = NULL;

    // 1. 插入到行链表
    // 找到该行中，比新节点列索引小的最后一个节点，或找到该行链表头
    OLNode* p_row = matrix->row_heads[row];
    if (p_row == NULL || p_row->col > col) { // 当前行无节点或新节点应作为第一个
        newNode->right = p_row;
        matrix->row_heads[row] = newNode;
    } else {
        while (p_row->right != NULL && p_row->right->col < col) {
            p_row = p_row->right;
        }
        // 处理重复元素：如果已存在相同位置的元素，则更新值
        if (p_row->right != NULL && p_row->right->col == col) {
            p_row->right->value = value; // 更新值
            free(newNode); // 新节点不再需要
            return;
        }
        // 插入到正确位置
        newNode->right = p_row->right;
        p_row->right = newNode;
    }

    // 2. 插入到列链表 (与行链表类似)
    OLNode* p_col = matrix->col_heads[col];
    if (p_col == NULL || p_col->row > row) { // 当前列无节点或新节点应作为第一个
        newNode->down = p_col;
        matrix->col_heads[col] = newNode;
    } else {
        while (p_col->down != NULL && p_col->down->row < row) {
            p_col = p_col->down;
        }
        // 注意：这里不用处理重复元素了，因为行链表已经处理过了
        newNode->down = p_col->down;
        p_col->down = newNode;
    }

    matrix->num_elements++;
}

3.3 打印矩阵（遍历）

十字链表可以方便地按行或按列遍历非零元素，甚至可以还原出完整的矩阵。

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
// 打印矩阵（按行遍历非零元素）
void printMatrixByRow(CrossList* matrix) {
    printf("按行打印稀疏矩阵的非零元素 (row, col, value):\n");
    for (int i = 0; i < matrix->rows; i++) {
        OLNode* current = matrix->row_heads[i];
        while (current != NULL) {
            printf("(%d, %d, %d) ", current->row, current->col, current->value);
            current = current->right;
        }
        printf("\n");
    }
}

// 打印矩阵（还原完整矩阵）
void printFullMatrix(CrossList* matrix) {
    printf("完整矩阵：\n");
    for (int i = 0; i < matrix->rows; i++) {
        OLNode* current_row_node = matrix->row_heads[i];
        for (int j = 0; j < matrix->cols; j++) {
            if (current_row_node != NULL && current_row_node->col == j) {
                printf("%d ", current_row_node->value);
                current_row_node = current_row_node->right;
            } else {
                printf("0 "); // 没有非零元素，打印0
            }
        }
        printf("\n");
    }
}

3.4 查找元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 查找某个位置的元素值
int getElement(CrossList* matrix, int row, int col) {
    if (row < 0 || row >= matrix->rows || col < 0 || col >= matrix->cols) {
        printf("查找失败：索引越界。\n");
        return 0; // 假定超出范围是0
    }
    
    OLNode* current = matrix->row_heads[row]; // 从行头开始查找
    while (current != NULL && current->col < col) {
        current = current->right;
    }
    if (current != NULL && current->col == col) {
        return current->value;
    }
    return 0; // 未找到，返回0
}

3.5 删除元素

删除元素相对复杂，需要同时更新行链表和列链表。

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
// 删除一个非零元素
void deleteElement(CrossList* matrix, int row, int col) {
    if (row < 0 || row >= matrix->rows || col < 0 || col >= matrix->cols) {
        printf("删除失败：索引越界。\n");
        return;
    }

    OLNode* nodeToDelete = NULL;
    
    // 1. 从行链表中删除
    OLNode* prev_row = NULL;
    OLNode* current_row = matrix->row_heads[row];
    while (current_row != NULL && current_row->col < col) {
        prev_row = current_row;
        current_row = current_row->right;
    }
    if (current_row != NULL && current_row->col == col) {
        nodeToDelete = current_row; // 找到了要删除的节点
        if (prev_row == NULL) { // 删除的是行头
            matrix->row_heads[row] = current_row->right;
        } else {
            prev_row->right = current_row->right;
        }
    } else {
        printf("未找到 (%d, %d) 处的非零元素。\n", row, col);
        return; // 未找到，直接返回
    }

    // 2. 从列链表中删除
    OLNode* prev_col = NULL;
    OLNode* current_col = matrix->col_heads[col];
    while (current_col != NULL && current_col->row < row) {
        prev_col = current_col;
        current_col = current_col->down;
    }
    // 此时 current_col 应该就是 nodeToDelete (因为行和列都指向同一个节点)
    if (current_col != NULL && current_col->row == row && current_col->col == col) {
        if (prev_col == NULL) { // 删除的是列头
            matrix->col_heads[col] = current_col->down;
        } else {
            prev_col->down = current_col->down;
        }
    }

    free(nodeToDelete); // 释放节点内存
    matrix->num_elements--;
    printf("成功删除元素 (%d, %d)。\n", row, col);
}

3.6 释放内存

释放所有元素节点和头节点数组的内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 释放十字链表占用的所有内存
void freeCrossList(CrossList* matrix) {
    if (matrix == NULL) return;

    // 释放所有元素节点
    for (int i = 0; i < matrix->rows; i++) {
        OLNode* current = matrix->row_heads[i];
        while (current != NULL) {
            OLNode* temp = current;
            current = current->right; // 先移动到下一个，因为当前节点可能被其他行/列引用
            // 如果是双向链表，需要判断是否已经被释放过
            // 对于十字链表，一个节点只被释放一次。我们按行释放即可。
            free(temp);
        }
    }

    // 释放行头和列头数组本身
    free(matrix->row_heads);
    free(matrix->col_heads);
    free(matrix);
    printf("十字链表内存已释放。\n");
}

4. 完整示例代码

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
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
#include <stdio.h>
#include <stdlib.h>

// 定义稀疏矩阵的节点类型
typedef struct OLNode {
    int row;       // 行索引
    int col;       // 列索引
    int value;     // 存储的非零元素值

    struct OLNode *right; // 指向同一行下一个非零元素的指针
    struct OLNode *down;  // 指向同一列下一个非零元素的指针
} OLNode;

// 定义稀疏矩阵的十字链表结构
typedef struct CrossList {
    OLNode** row_heads;   // 行头节点数组
    OLNode** col_heads;   // 列头节点数组
    int rows;             // 矩阵的行数
    int cols;             // 矩阵的列数
    int num_elements;     // 非零元素的数量
} CrossList;

// 初始化一个空的十字链表
CrossList* initCrossList(int m_rows, int m_cols) {
    CrossList* matrix = (CrossList*)malloc(sizeof(CrossList));
    if (matrix == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    matrix->rows = m_rows;
    matrix->cols = m_cols;
    matrix->num_elements = 0;

    matrix->row_heads = (OLNode**)malloc(sizeof(OLNode*) * m_rows);
    if (matrix->row_heads == NULL) { /* handle error */ }
    for (int i = 0; i < m_rows; i++) {
        matrix->row_heads[i] = NULL;
    }

    matrix->col_heads = (OLNode**)malloc(sizeof(OLNode*) * m_cols);
    if (matrix->col_heads == NULL) { /* handle error */ }
    for (int i = 0; i < m_cols; i++) {
        matrix->col_heads[i] = NULL;
    }
    return matrix;
}

// 插入一个非零元素
void insertElement(CrossList* matrix, int row, int col, int value) {
    if (row < 0 || row >= matrix->rows || col < 0 || col >= matrix->cols) {
        printf("插入失败：索引越界 (%d, %d)。\n", row, col);
        return;
    }
    if (value == 0) {
        // 如果插入0，则尝试删除该位置的现有元素 (如果存在)
        // 简化起见，这里假设用户不会插入0，如果需要，可以调用 deleteElement
        return;
    }

    OLNode* newNode = (OLNode*)malloc(sizeof(OLNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->row = row;
    newNode->col = col;
    newNode->value = value;
    newNode->right = NULL;
    newNode->down = NULL;

    // 1. 插入到行链表 (保持按列索引升序)
    OLNode* p_row = matrix->row_heads[row];
    OLNode* prev_row = NULL;
    while (p_row != NULL && p_row->col < col) {
        prev_row = p_row;
        p_row = p_row->right;
    }
    
    // 如果该位置已存在元素，则更新其值并释放新节点
    if (p_row != NULL && p_row->col == col) {
        p_row->value = value; // 更新值
        free(newNode);
        return;
    }

    // 插入新节点到行链表
    if (prev_row == NULL) { // 插入到行头
        newNode->right = matrix->row_heads[row];
        matrix->row_heads[row] = newNode;
    } else {
        newNode->right = prev_row->right;
        prev_row->right = newNode;
    }

    // 2. 插入到列链表 (保持按行索引升序)
    OLNode* p_col = matrix->col_heads[col];
    OLNode* prev_col = NULL;
    while (p_col != NULL && p_col->row < row) {
        prev_col = p_col;
        p_col = p_col->down;
    }

    // 插入新节点到列链表
    if (prev_col == NULL) { // 插入到列头
        newNode->down = matrix->col_heads[col];
        matrix->col_heads[col] = newNode;
    } else {
        newNode->down = prev_col->down;
        prev_col->down = newNode;
    }

    matrix->num_elements++;
}

// 查找某个位置的元素值
int getElement(CrossList* matrix, int row, int col) {
    if (row < 0 || row >= matrix->rows || col < 0 || col >= matrix->cols) {
        printf("查找失败：索引越界。\n");
        return 0; // 假定超出范围是0
    }
    
    OLNode* current = matrix->row_heads[row]; // 从行头开始查找
    while (current != NULL && current->col < col) {
        current = current->right;
    }
    if (current != NULL && current->col == col) {
        return current->value;
    }
    return 0; // 未找到，返回0
}

// 删除一个非零元素
void deleteElement(CrossList* matrix, int row, int col) {
    if (row < 0 || row >= matrix->rows || col < 0 || col >= matrix->cols) {
        printf("删除失败：索引越界。\n");
        return;
    }

    OLNode* nodeToDelete = NULL; // 用于最终free的节点

    // 1. 从行链表中删除
    OLNode* prev_row = NULL;
    OLNode* current_row = matrix->row_heads[row];
    while (current_row != NULL && current_row->col < col) {
        prev_row = current_row;
        current_row = current_row->right;
    }
    
    if (current_row != NULL && current_row->col == col) {
        nodeToDelete = current_row; 
        if (prev_row == NULL) { // 删除的是行头
            matrix->row_heads[row] = current_row->right;
        } else {
            prev_row->right = current_row->right;
        }
    } else {
        printf("未找到 (%d, %d) 处的非零元素进行删除。\n", row, col);
        return; 
    }

    // 2. 从列链表中删除 (寻找并跳过该节点)
    OLNode* prev_col = NULL;
    OLNode* current_col = matrix->col_heads[col];
    while (current_col != NULL && current_col->row < row) {
        prev_col = current_col;
        current_col = current_col->down;
    }
    // 此时 current_col 应该就是 nodeToDelete (因为行和列都指向同一个节点)
    if (current_col != NULL && current_col->row == row && current_col->col == col) {
        if (prev_col == NULL) { // 删除的是列头
            matrix->col_heads[col] = current_col->down;
        } else {
            prev_col->down = current_col->down;
        }
    }
    
    free(nodeToDelete); // 释放节点内存
    matrix->num_elements--;
    printf("成功删除元素 (%d, %d)。\n", row, col);
}

// 打印矩阵（还原完整矩阵）
void printFullMatrix(CrossList* matrix) {
    printf("\n完整矩阵 (%d x %d):\n", matrix->rows, matrix->cols);
    for (int i = 0; i < matrix->rows; i++) {
        OLNode* current_row_node = matrix->row_heads[i];
        for (int j = 0; j < matrix->cols; j++) {
            if (current_row_node != NULL && current_row_node->col == j) {
                printf("%3d ", current_row_node->value); // 格式化输出
                current_row_node = current_row_node->right;
            } else {
                printf("%3d ", 0); // 没有非零元素，打印0
            }
        }
        printf("\n");
    }
}

// 释放十字链表占用的所有内存
void freeCrossList(CrossList* matrix) {
    if (matrix == NULL) return;

    // 释放所有元素节点
    // 只需要按行链表释放即可，因为每个节点只在某个行链表和某个列链表中出现一次
    for (int i = 0; i < matrix->rows; i++) {
        OLNode* current = matrix->row_heads[i];
        while (current != NULL) {
            OLNode* temp = current;
            current = current->right; 
            free(temp);
        }
    }

    // 释放行头和列头数组本身
    free(matrix->row_heads);
    free(matrix->col_heads);
    free(matrix);
    printf("十字链表内存已释放。\n");
}

int main() {
    int rows = 4, cols = 5;
    CrossList* sparseMatrix = initCrossList(rows, cols);

    printf("------ 插入元素 ------\n");
    insertElement(sparseMatrix, 0, 1, 5);
    insertElement(sparseMatrix, 0, 4, 8);
    insertElement(sparseMatrix, 1, 0, 12);
    insertElement(sparseMatrix, 1, 3, 7);
    insertElement(sparseMatrix, 2, 1, 9);
    insertElement(sparseMatrix, 3, 2, 6);
    insertElement(sparseMatrix, 3, 4, 10);
    
    printf("插入重复位置元素 (更新):\n");
    insertElement(sparseMatrix, 0, 1, 100); // 更新 (0,1) 的值

    printFullMatrix(sparseMatrix);

    printf("\n------ 查找元素 ------\n");
    printf("元素 (0, 1): %d\n", getElement(sparseMatrix, 0, 1)); // Expected: 100
    printf("元素 (1, 2): %d\n", getElement(sparseMatrix, 1, 2)); // Expected: 0
    printf("元素 (3, 4): %d\n", getElement(sparseMatrix, 3, 4)); // Expected: 10

    printf("\n------ 删除元素 ------\n");
    deleteElement(sparseMatrix, 0, 4); // 删除 (0,4)
    printFullMatrix(sparseMatrix);

    deleteElement(sparseMatrix, 1, 0); // 删除 (1,0)
    printFullMatrix(sparseMatrix);

    deleteElement(sparseMatrix, 2, 2); // 删除不存在的元素
    printFullMatrix(sparseMatrix);

    printf("\n------ 内存释放 ------\n");
    freeCrossList(sparseMatrix);

    return 0;
}

5. 十字链表的优势与应用

优势：

  • 空间效率高： 只存储非零元素，对于稀疏矩阵来说，大大节省了内存空间。
  • 灵活的双向访问： 既可以高效地按行遍历非零元素，也可以高效地按列遍历非零元素。
  • 插入和删除相对方便： 相较于三元组表等，插入和删除非零元素（在已知位置时）更为方便，只需调整少数指针。

应用场景：

  • 稀疏矩阵的存储和运算： 矩阵的加法、乘法等运算在十字链表上实现效率更高。
  • 图的邻接多重表表示： 图的一种特殊存储结构，每个边可以同时存在于两个顶点的邻接链表中，类似于十字链表的思想。
  • 数据挖掘和机器学习： 处理包含大量零值的矩阵数据，例如协同过滤中的用户-物品评分矩阵。

6. 总结

十字链表是一种为稀疏矩阵量身定制的数据结构。它通过巧妙地将非零元素组织成行链表和列链表的交织结构，实现了空间上的高效利用和访问上的高度灵活性。虽然它的实现比普通链表复杂，但在处理大规模稀疏数据时，其优势显而易见。

理解十字链表的原理和实现，将为你在处理稀疏数据和更复杂的数据结构（如图）时提供强大的工具。

Title:十字链表

Author:

Created:2025-05-30, 20:54:56

Updated:2025-05-30, 20:56:36

Full URL:http://example.com/2025/05/30/%E5%8D%81%E5%AD%97%E9%93%BE%E8%A1%A8/

License: "CC BY-NC-SA 4.0" Keep Link & Author if Distribute.

Contents
  1. 1. 稀疏矩阵的优雅表示：深入理解“十字链表”
    1. 1.1. 1. 为什么需要十字链表？
    2. 1.2. 2. 十字链表的核心思想与节点结构
    3. 1.3. 3. 十字链表的基本操作
      1. 1.3.1. 3.1 初始化十字链表
      2. 1.3.2. 3.2 插入非零元素
      3. 1.3.3. 3.3 打印矩阵（遍历）
      4. 1.3.4. 3.4 查找元素
      5. 1.3.5. 3.5 删除元素
      6. 1.3.6. 3.6 释放内存
    4. 1.4. 4. 完整示例代码
    5. 1.5. 5. 十字链表的优势与应用
    6. 1.6. 6. 总结
|