用十字链表构成稀疏矩阵时，为什么每行列链表为循环链表?
来源:千锋教育
发布人:xqq
2023-10-14
推荐
在线提问>>
一、用十字链表构成稀疏矩阵时，为什么每行\列链表为循环链表
因为每行\列链表为循环链表可以解决数组 “不利于插入和删除数据” 的特点，将所有行链表的表头存储到一个数组（rhead），将所有列链表的表头存储到另一个数组（chead）中。
两个指针域分别指向所在行的下一个元素和所在列的下一个元素。
可以用如下的结构体来表示链表中的节点：
typedef struct OLNode{ int i,j;//元素的行标和列标 int data;//元素的值
struct OLNode * right,*down;//两个指针域}OLNode, *OLink;
在此基础上，表示十字链表的结构体为：
typedef struct{ OLink *rhead, *chead; //行和列链表头指针 int mu, nu, tu; //矩阵的行数,列数和非零元的个数}CrossList;
以存储图 1 所示的矩阵为例，十字链表存储该矩阵的 C 语言实现代码为：
#include
#include 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; void CreateMatrix_OL(CrossList* M);void display(CrossList M); int main(){ CrossList M; M.rhead = NULL; M.chead = NULL; CreateMatrix_OL(&M); printf(“输出矩阵M:\n”); display(M); return 0;} void CreateMatrix_OL(CrossList* M){ int m, n, t; int num = 0; int i, j, e; OLNode* p = NULL, * q = NULL; 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 = 0; i <= m; i++) { (*M).rhead[i] = NULL; } for (j = 0; j <= n; j++) { (*M).chead[j] = NULL; } while (num < t) { scanf(“%d%d%d”, &i, &j, &e); num++; if (!(p = (OLNode*)malloc(sizeof(OLNode)))) { printf(“初始化三元组失败”); exit(0); } p->i = i; p->j = j; p->e = e; //链接到行的指定位置 //如果第 i 行没有非 0 元素，或者第 i 行为数不多的非 0 元素位于当前元素的右侧，直接将该元素放置到第 i 行的开头 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); //将新非 0 元素插入 q 之后 p->right = q->right; q->right = p; } //链接到列的指定位置 //如果第 j 列没有非 0 元素，或者第 j 列为数不多的非 0 元素位于当前元素的下方，直接将该元素放置到第 j 列的开头 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); //将当前元素插入到 q 指针下方 p->down = q->down; q->down = p; } }} void display(CrossList M) { int i,j; //一行一行的输出 for (i = 1; i <= M.mu; i++) { //如果当前行没有非 0 元素，直接输出 0 if (NULL == M.rhead[i]) { for (j = 1; j <= M.nu; j++) { printf(“0 “); } putchar(‘\n’); } else { int n = 1; OLink p = M.rhead[i]; //依次输出每一列的元素 while (n <= M.nu) { if (!p || (n < p->j) ) { printf(“0 “); } else { printf(“%d “, p->e); p = p->right; } n++; } putchar(‘\n’); } }}运行结果：
输入矩阵的行数、列数和非0元素个数：3 4 4
1 1 3
1 4 5
2 2 -1
3 1 2
输出矩阵M:
3 0 0 5
0 -1 0 0
2 0 0 0
延伸阅读：
二、稀疏矩阵的十字链表存储
当矩阵的非零元个数和位置在操作过程中变化较大时，就不宜采用顺序存储结构来表示三元组的线性表。对这种类型的矩阵，采用链式存储结构表示三元组的线性表更为恰当。
在链表中，每个非零元可用一个含 5 个域的结点表示，其中 i , j , e 这 3 个域分别表示该非零元所在的行、列和非零元的值，向右域 right 用以链接同一行中下一个非零元，向下域 down 用以链接同一列中下一个非零元。
同一行的非零元通过 right 域链接成一个线性链表，同一列的非零元通过 down 域链接成一个线性链表，每个非零元既是某个行链表中的一个结点，又是某个列链表中的一个结点，整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表。
可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示。
