既然要用链表节点来模拟矩阵中的非零元素,肯定需要如下5个元素(row,col,val,down,right),其中:
row:矩阵中的行。
col:矩阵中的列。
val:矩阵中的值。
right:指向右侧的一个非零元素。
down:指向下侧的一个非零元素。
现在我们知道单个节点该如何表示了,那么矩阵中同行的非零元素的表示不就是一个单链表吗?比如如下:
那么进一步来说一个多行的非零元素的表示不就是多个单链表吗,是的,这里我把单链表做成循环链表,我们来看看如何用十字链表
来表示稀疏矩阵。
从上面的十字链表中要注意两个问题:
第一:这里有一个填充色的节点,是十字链表中的总结点,它是记录该矩阵中的(row,col,value)和一个指向下一个头节点的next指针。
第二:每个链表都有一个头指针,总结点用next指针将它们贯穿起来。