广义表与多重链表

1.广义表1.性质2.结构体的定义3.例：用广义表存储二元多项式 2.多重链表1.性质2.例：使用十字链表存储稀疏矩阵

1.广义表

1.性质

①广义表是线性表的推广 ②线性表，n个元素都是基本的单元素 ③广义表这些元素不仅可以使单元素也可以是另一个广义表

2.结构体的定义

typedef struct GNode *GList; struct GNode { int Tag; //标志域 0表示单元素，1表示结点是广义表 union //子表指针域Sublist与单元素数据域Data复用，共享存储空间 { ElementType Data; GList SubList; }URegion; GList Next; //指向后继结点 };

补： 共用体：共用体有时也被称为联合或者联合体。 ①结构体和共用体的区别在于： A.结构体的各个成员会占用不同的内存，互相之间没有影响；而共用体的所有成员占用同一段内存，修改一个成员会影响其余所有成员。 B.结构体占用的内存大于等于所有成员占用的内存的总和（成员之间可能会存在缝隙），共用体占用的内存等于最长的成员占用的内存。共用体使用了内存覆盖技术，同一时刻只能保存一个成员的值，如果对新的成员赋值，就会把原来成员的值覆盖掉。

union 共用体名{ 成员列表 };

eg：

union data{ int n; char ch; double f; }; union data a, b, c;

3.例：用广义表存储二元多项式

将二元多项式看成关于x的一元多项式

2.多重链表

1.性质

①链表中的结点可能同时隶属于多个链 ②多重链表中结点的指针域会有多个，但包含两个指针域的链表并不一定是多重链表（例如双向链表） ③用途：树、图等相对复杂的数据结构可用多重链表方式存储。

2.例：使用十字链表存储稀疏矩阵