一、广义表#
- 是线性表的推广
- 对于线性表而言，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"