上一篇我们看了矩阵的顺序存储,这篇我们再看看一种链式存储方法“十字链表”,当然目的都是一样,压缩空间。
一:概念
既然要用链表节点来模拟矩阵中的非零元素,肯定需要如下5个元素(row,col,val,down,right),其中:
row:矩阵中的行。
col:矩阵中的列。
val:矩阵中的值。
right:指向右侧的一个非零元素。
down:指向下侧的一个非零元素。
现在我们知道单个节点该如何表示了,那么矩阵中同行的非零元素的表示不就是一个单链表吗?比如如下:
那么进一步来说一个多行的非零元素的表示不就是多个单链表吗,是的,这里我把单链表做成循环链表,我们来看看如何用十字链表
来表示稀疏矩阵。
从上面的十字链表中要注意两个问题:
第一:这里有一个填充色的节点,是十字链表中的总结点,它是记录该矩阵中的(row,col,value)和一个指向下一个头节点的next指针。
第二:每个链表都有一个头指针,总结点用next指针将它们贯穿起来。
二:操作
1:数据结构
刚才也说了,十字链表的总结点有一个next指针,而其他非零节点没有,所以为了方便,我们用一个Unit类包装起来。
2:初始化
这一步,我们初始化总结点,并且用next指针将每个单链表的头节点链接成单链表(也就是上图中十字链表的第一行)
3:插入节点
根据插入节点的row和col将节点插入到十字链表中指定的位置即可。
4:打印链表
我们只要遍历每行链表的right指针即可。
总的代码:
View Code