十字链表法，十字链表压缩存储稀疏矩阵详解
对于压缩存储稀疏矩阵，无论是使用三元组顺序表，还是使用行逻辑链接的顺序表，归根结底是使用数组存储稀疏矩阵。介于数组 "不利于插入和删除数据" 的特点，以上两种压缩存储方式都不适合解决类似 "向矩阵中添加或删除非 0 元素" 的问题。
例如，A 和 B 分别为两个矩阵，在实现 "将矩阵 B 加到矩阵 A 上" 的操作时，矩阵 A 中的元素会发生很大的变化，之前的非 0 元素可能变为 0，而 0 元素也可能变为非 0 元素。对于此操作的实现，之前所学的压缩存储方法就显得力不从心。
本节将学习用十字链表存储稀疏矩阵，该存储方式采用的是 "链表+数组" 结构，如图 1 所示。
图 1 十字链表示意图
可以看到，使用十字链表压缩存储稀疏矩阵时，矩阵中的各行各列都各用一各链表存储，与此同时，所有行链表的表头存储到一个数组（rhead），所有列链表的表头存储到另一个数组（chead）中。
因此，各个链表中节点的结构应如图 2 所示:
图 2 十字链表的节点结构
两个指针域分别用于链接所在行的下一个元素以及所在列的下一个元素。
链表中节点的 C 语言代码表示应为：
typedef struct OLNode{ int i,j;//元素的行标和列标 int data;//元素的值 struct OLNode * right,*down;//两个指针域 }OLNode; 同时，表示十字链表结构的 C 语言代码应为： #include<stdio.h> #include<stdlib.h> typedef struct OLNode { int i, j, e; //矩阵三元组i代表行 j代表列 e代表当前位置的数据 struct OLNode *right, *down; //指针域 右指针 下指针 }OLNode, *OLink; typedef struct { OLink *rhead, *chead; //行和列链表头指针 int mu, nu, tu; //矩阵的行数,列数和非零元的个数 }CrossList; CrossList CreateMatrix_OL(CrossList M); void display(CrossList M); int main() { CrossList M; M.rhead = NULL; M.chead = NULL; M = CreateMatrix_OL(M); printf("输出矩阵M:\n"); display(M); return 0; } CrossList CreateMatrix_OL(CrossList M) { int m, n, t; int i, j, e; OLNode *p, *q; printf("输入矩阵的行数、列数和非0元素个数："); scanf("%d%d%d", &m, &n, &t); M.mu = m; M.nu = n; M.tu = t; if (!(M.rhead = (OLink*)malloc((m + 1) * sizeof(OLink))) || !(M.chead = (OLink*)malloc((n + 1) * sizeof(OLink)))) { printf("初始化矩阵失败"); exit(0); } for (i = 1; i <= m; i++) { M.rhead[i] = NULL; } for (j = 1; j <= n; j++) { M.chead[j] = NULL; } for (scanf("%d%d%d", &i, &j, &e); 0 != i; scanf("%d%d%d", &i, &j, &e)) { if (!(p = (OLNode*)malloc(sizeof(OLNode)))) { printf("初始化三元组失败"); exit(0); } p->i = i; p->j = j; p->e = e; //链接到行的指定位置 if (NULL == M.rhead[i] || M.rhead[i]->j > j) { p->right = M.rhead[i]; M.rhead[i] = p; } else { for (q = M.rhead[i]; (q->right) && q->right->j < j; q = q->right); p->right = q->right; q->right = p; } //链接到列的指定位置 if (NULL == M.chead[j] || M.chead[j]->i > i) { p->down = M.chead[j]; M.chead[j] = p; } else { for (q = M.chead[j]; (q->down) && q->down->i < i; q = q->down); p->down = q->down; q->down = p; } } return M; } void display(CrossList M) { for (int i = 1; i <= M.nu; i++) { if (NULL != M.chead[i]) { OLink p = M.chead[i]; while (NULL != p) { printf("%d\t%d\t%d\n", p->i, p->j, p->e); p = p->down; } } } }
运行结果：
输入矩阵的行数、列数和非0元素个数：3 3 3 2 2 3 2 3 4 3 2 5 0 0 0 输出矩阵M: 2 2 3 3 2 5 2 3 4
矩阵（稀疏矩阵）的转置算法（C语言）详解
矩阵（包括稀疏矩阵）的转置，即互换矩阵中所有元素的行标和列标，如图 1 所示：
图 1 矩阵转置示意图
但如果想通过程序实现矩阵的转置，互换行标和列标只是第一步。因为实现矩阵转置的前提是将矩阵存储起来，数据结构中提供了 3 种存储矩阵的结构，分别是
如果采用前两种结构，矩阵的转置过程会涉及三元组表也跟着改变的问题，如图 2 所示：
图 2 三元组表的变化
图 2a) 表示的是图 1 中转置之前矩阵的三元组表，2b) 表示的是图 1 中矩阵转置后对应的三元组表。
不仅如此，如果矩阵的行数和列数不等，也需要将它们互换。
因此通过以上分析，矩阵转置的实现过程需完成以下 3 步：
- 将矩阵的行数和列数互换；
- 将三元组表（存储矩阵）中的 i 列和 j 列互换，实现矩阵的转置；
- 以 j 列为序，重新排列三元组表中存储各三元组的先后顺序；
此 3 步中，前两步比较简单，关键在于最后一步的实现。本节先介绍较容易的一种。
矩阵转置的实现思路是：不断遍历存储矩阵的三元组表，每次都取出表中 j 列最小的那一个三元组，互换行标和列标的值，并按次序存储到一个新三元组表中，。
例如，将图 2a) 三元组表存储的矩阵进行转置的过程为：
- 新建一个三元组表（用于存储转置矩阵），并将原矩阵的行数和列数互换赋值给新三元组；
- 遍历三元组表，找到表中 j 列最小值 1 所在的三元组 (3,1,6)，然后将其行标和列标互换后添加到一个新的三元组表中，如图 3 所示：
图 3 矩阵转置的第一个过程 - 继续遍历三元组表，找到表中 j 列次小值为 2 的三元组，分别为 (1,2,1)、(2,2,3) 和 (3,2,5)，根据找到它们的先后次序将各自的行标和列标互换后添加到新三元组表中，如图 4 所示：
图 4 矩阵转置的第二个过程
对比图 4 和图 2b) 可以看到，矩阵被成功地转置。
因此，矩阵转置的 C 语言实现代码为：
#include<stdio.h> #define number 10 typedef struct { int i, j; int data; }triple; typedef struct { triple data[10]; int n, m, num; }TSMatrix; TSMatrix transposeMatrix(TSMatrix M, TSMatrix T) { T.m = M.n; T.n = M.m; T.num = M.num; if (T.num) { int q = 0; for (int col = 1; col <= M.m; col++) { for (int p = 0; p < M.num; p++) { if (M.data[p].j == col) { T.data[q].i = M.data[p].j; T.data[q].j = M.data[p].i; T.data[q].data = M.data[p].data; q++; } } } } return T; } int main() { TSMatrix M; M.m = 2; M.n = 3; M.num = 4; M.data[0].i = 1; M.data[0].j = 2; M.data[0].data = 1; M.data[1].i = 2; M.data[1].j = 2; M.data[1].data = 3; M.data[2].i = 3; M.data[2].j = 1; M.data[2].data = 6; M.data[3].i = 3; M.data[3].j = 2; M.data[3].data = 5; TSMatrix T; for (int k = 0; k < number; k++) { T.data[k].i = 0; T.data[k].j = 0; T.data[k].data = 0; } T = transposeMatrix(M, T); for (int i = 0; i < T.num; i++) { printf("(%d,%d,%d)\n", T.data[i].i, T.data[i].j, T.data[i].data); } return 0; }
程序运行结果为：
(1,3,6)
(2,1,1)
(2,2,3)
(2,3,5)
由于此算法中嵌套使用了两个 for 循环，时间复杂度为 O(n2)。
