5-4 稀疏矩阵的链式存储结构
（考点）稀疏矩阵的链式存储结构：十字链表
优点：它能够灵活地插入因运算而产生的新的非零元素，删除因运算而产生的新的零元素，实现矩阵的运算。
在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除了（row，col，value）外，还有两个域：
right： 用于链接同一行中的下一个非零元素；
down：用以链接同一列中的下一个非零元素。
十字链表中结点的结构示意图：
（必考）广义表
1. 广义表（又称列表 Lists）是n≥0个元素 a1, a2, …, an的有限序列，其中每一个ai 或者是原子，或者是一个子表。
2.广义表通常记作： LS = (a1，a2，…，an) 其中： LS 为表名， n 为表的长度， 每一个 ai 为表的元素。 习惯上，一般用大写字母表示广义表，小写字母表示原子。
表头：若 LS 非空 (n≥1 )，则其第一个元素 a1 就是表头。 记作head(LS) = a1。注：表头可是原子，也可是子表。
表尾：除表头之外的其它元素组成的表。 记作 tail(LS) = (a2, ..., an)。
注：表尾不是最后一个元素，而是一个子表。
广义表的性质
- 广义表中的数据元素有相对次序；
（2）广义表的长度定义为最外层所包含元素的个数；如： C=(a, (b, c)) 是长度为 2 的广义表。
(3)广义表的深度定义为该广义表展开后所含括号的重数；
A = (b, c) 的深度为 1，B = (A, d) 的深度为 2，
C = (f, B, h) 的深度为 3。
注意：“原子”的深度为 0 ; “空表”的深度为 1 。
(4) 广义表可以为其他广义表共享；如：广义表 B 就共享表 A。在 B 中不必列出 A 的值，而是通过名称来引用。
(5) 广义表可以是递归的表。如：F=(a, F)=(a, (a, (a, …)))注意：递归表的深度是无穷值，长度是有限值。
广义表是多层次结构，广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，可以用图形象地表示。
广义表可看成是线性表的推广，线性表是广义表的特例
广义表的结构相当灵活，在某种前提下，它可以兼容线性表、数组、树和有向图等各种常用的数据结构。
广义表基本运算
若广义表 LS=(a1, a2, …, an)，
则 GetHead(LS) = a1 GetTail(LS) = (a2, …, an)。
注意：取表头得到的结果可以是原子，也可以是一个子表。取表尾得到的结果一定是一个子表。
例: D = ( E, F ) = ((a, (b, c))，F )
GetHead( D ) = E GetTail( D ) = ( F )
GetHead( E ) = a GetTail( E ) = ((b, c))
GetHead(((b, c))) = (b, c) GetTail(((b, c))) = ( )
GetHead((b, c)) = b GetTail((b, c)) = (c)
GetHead((c)) = c GetTail((c)) = ( )
广义表的存储结构及相关算法
1. 由于广义表是递归定义的，所以不能用顺序存储结构；但（原子或列表）可具有不同的结构，采用链式存储结构（广义链表）。
2. 结点的结构形式 1、首尾链表