十字链表比稀疏矩阵更耗费空间，它存在的意义和具体的应用场景是什么?

cdsfiui

什么领域里面必须要使用十字链表，不用还不行呢?

action08

一些理论探索的领域，不需要过度关心

windoze

十字链表不是稀疏矩阵的一种存储方式么？怎么还有优劣之分？
lz你这不等于是在问丰田和汽车哪个好么？

action08

回复 3# windoze


    斑竹大大过来给大家讲解一下吧

windoze

回复 4# action08

稀疏矩阵指的是一个矩阵里面大多数元素都为0，这只是一个数学上的概念，并不涉及到具体的存储方式。

用传统的二维数组存储稀疏矩阵显然很低效，因为大部分元素都是0，实际只需要存储所有的非零值就足以描述整个矩阵，所以人们针对它的特点有设计出一些高效的存储方式，比如用三元组列表，列表中每一项包含一个纵横轴坐标和一个数值，整个矩阵用一个线性的数据结构比如数组或链表存储，这样做的好处是遍历矩阵的所有元素很方便，你只需要遍历一个线性表就可以了，但缺点就是定位困难，理论上说复杂度是O(m*n)，m和n是矩阵的长度和宽度，这么做另外一个问题就是如果你只想遍历一行或者一列也需要多次的扫描整个列表。
针对这个问题，人们又设计了一种结构叫十字链表，链表中的每个元素在纵轴和横轴上都有一个前驱和一个后继，也就是说每个元素都同时属于行和列两个单/双向链表，这样的结构对于扫描某一行或者某一列的场景特别合适，因为每一行每一列都是一个链表，定位、插入、删除元素也比较方便，但缺点是如果你需要遍历整个矩阵就会比较麻烦。
上面这两种是经典的教科书存储方式，当然在实际应用中还有很多其它的方式，比如行/列/块压缩、针对特殊形状的矩阵进行变换等，都是针对特定的应用场景设计出来的，都有各自的优缺点和适用范围。

action08

当然在实际应用中还有很多其它的方式，比如行/列/块压缩、针对特殊形状的矩阵进行变换等，都是针对特定的应用场景设计出来的，都有各自的优缺点和适用范围。


这个可以详细一点的，

windoze

回复 6# action08

你真懒……

随便举个例子，有一类特殊矩阵叫对角矩阵，只在对角线上有非0元素，其余的元素都是0，这类矩阵你可以用一个一维数组存储，这就是我说的针对特殊形状矩阵的变换。