广义表
广义表不仅跟线性表一样可以表示简单是线性顺序关系，而且可以表达更复杂的非线性多元关系。
G
L
i
s
t
=
(
a
1
,
a
2
,
.
.
.
,
a
i
−
1
,
a
i
,
a
i
+
1
,
.
.
.
,
a
n
)
GList = (a_1, a_2,...,a_{i-1},a_i,a_{i+1},...,a_n)
GList=(a1,a2,...,ai−1,ai,ai+1,...,an)
其中，
a
i
a_i
ai可以是单元素，也可以是广义表。
由于广义表的元素可以是不同的结构，因此不适于顺序存储，通常用链式存储结构，也就是用由结点组成的链表来表示广义表。结点对应每个元素。如果该元素还是一个广义表，则通过该节点引出另一个链表。
广义表的结点可能由两种情况。
- 单元素：需要一个域来存储该单元素的值
- 广义表：需要一个域来指向另一个链表。
数据结构
typedef int ElementType;
typedef struct GNode* GList;
typedef struct GNode* PtrToGNode;
struct GNode {
int Tag; // 标志域： 0表示该节点为单元素； 1表示该节点为广义表
union MyUnion
{
//子表指针域Sublist和单元素数据域Data复用，即共享存储空间
ElementType Data;
GList Sublist;
};
PtrToGNode Next;//指向后继结点
};
举例： 广义表LS:（a, (b,…),(c,d),(e,f)）
多重链表
存在结点属于多个链的链表叫做多重链表。
一般来说，多重链表的每个结点的指针域会有很多个，如前面列子包含Next和Sublist的两个指针域。但是包含两个指针域的链表不一定是多重链表，如双向链表，其每个结点还是属于同一个链表。
稀疏矩阵的存储
对于矩阵A
A
=
[
18
0
0
2
0
0
27
0
0
0
0
0
0
−
4
0
23
−
1
0
0
12
]
A = \begin{bmatrix} 18& 0 &0 &2 &0 \\ 0& 27 &0 &0 &0 \\ 0& 0 & 0 & -4 & 0 \\ 23& -1 & 0 &0 &12 \end{bmatrix}
A=
1800230270−1000020−4000012
可以采用一种经典的多重链表——十字链表来存储稀疏矩阵。
特点
（1）、只存储矩阵中非0的元素项；
（2）、结点的数据域：行坐标Row、列坐标Col、数值Value
（3）、每个结点通过两个指针域，把同行、同列串起来
行指针（或者称为向右指针）Right
列指针（或者称为向下指针）：Down
（4）、用一个Tag来区分头结点和非0元素结点
（5）、头节点的标识值为“Head”,矩阵非0元素结点的标识值为“Term”
结点分类：
- 每行每列的头结点 （右图）
- 矩阵的非0元素节点 （左图)
A矩阵的十字链表表示
