# 一、广义表
- 是线性表的推广
- 对于线性表而言，n 个元素都是基本的单元素
- 广义表中，这些元素不仅可以使单元素也可以是另一个广义表
> typedef struct GNode *GList; struct GNode { | |
> int Tag; // 标志域：0 表示结点是单元素，1 表示结点是广义表 | |
> union { // 子表指针域 SubList 域单元素数据域 Data 复用，共用存储空间 | |
> ElementType Data; | |
> GList SubList; | |
> } URegion; | |
> GList Next; // 指向后继结点 }; |
# 二、多重链表
- 链表中的结点可能隶属于多个链
多重链表中结点的指针域 会有多个，如前面例子包含 Next 和 SubList;
但包含两个指针域的链表并不一定是多重链表，比如在双向链表不是多重链表
- 多重链表具有广泛的用途:
基本上如树、图这样相对复杂的数据结构都可以采用多重链表的方式实现存储
# eg: 存储矩阵
用二维数组有两个缺陷
- 一是数组的大小需要事先确定
- 二是对于稀疏矩阵会造成大量的存储空间浪费
分析：用一种典型多重链表 ——— 十字链表来存储稀疏矩阵
只存储非 0 元素
- 节点的指针域
行坐标 Row、列坐标 Col、数值 Value - 每个结点通过两个值针域，把同行、同列串起来；
行指针 (或称为向右指针) Right
列指针 (或称为向下指针) Down - 用一个标识域 Tag 来区分头结点和非 0 元素结点
头结点的标识值为 "Head", 矩阵非 0 元素节点的标识值为 "Term"
