|
||
漩涡的中心有一块空地,空空的 |
||
|
上一篇我们看了矩阵的顺序存储这篇我们再看看一种链式存储方法“十字链表”,当然目的都是一样压缩空间。
right:指向右侧的一个非零元素
down:指向下侧的一个非零元素。
现在我们知道单个节点该如何表示了那么矩阵中同行的非零元素的表示不就是一个单链表吗?比如如下:
那么进一步来说一个多行嘚非零元素的表示不就是多个单链表吗是的,这里我把单链表做成循环链表我们来看看如何用十字链表
从上面的十字链表中要注意两個问题:
第一:这里有一个填充色的节点,是十字链表中的总结点它是记录该矩阵中的(row,col,value)和一个指向下一个头节点的next指针。
第二:每個链表都有一个头指针总结点用next指针将它们贯穿起来。
刚才也说了十字链表的总结点有一个next指针,而其他非零节点没有所以为了方便,我们用一个Unit类包装起来
这一步,我们初始化总结点并且用next指针将每个单链表的头節点链接成单链表(也就是上图中十字链表的第一行)
1 #region 十字链表中的“行数,列数非零元素个数” 3 /// 十字链表中的“行数,列数非零元素个数” 12 //从下标1开始算起 15 //十字链表的总头节点 32 //初始化多条链表的头结点 45 //给上一个节点的next域赋值 48 //将当前节点作为下一次循环的上一个节点
根據插入节点的row和col将节点插入到十字链表中指定的位置即可。