广义表与多重链表_广义表和多重链表

 广义表

 广义表是线性表的推广

 对于线性表，n个元素都是基本的单元素。广义表中，这些元素不仅可以是单元素也可以是另一个广义表。

广义表的构造

一个域有可能是不能分解的单元，有可能是一个指针。这里采用联合union的手段。

union可以把不同类型的数据组合在一起。

为了区分不同的类型，再设一个标记

typedef struct GNode* GList;
struct GNode{
	int Tag;//标志域：0代表结点是单元素，1代表结点是广义表 
	union{//共用存储空间 
		ElementType Data;
		GList SubList;
	}URegion;
	GList Next;//指向后继结点 
}; 

 {这里复习一下union。

存储，所有成员共享一个空间

同一时间，只有一个成员是有效的

union的大小是其最大的成员

 实际上广义表就是一个多重链表

多重链表:链表中的结点可能同时隶属于多个链

多重链表中结点的指针域会有多个（但包含两个指针域的链表不一定是多重链表，如双向链表。

下面引入例子

矩阵可以用二维数组表示，但二维数组有两个缺陷：

1.数组的大小需要事先确定

2.对于“稀疏矩阵”，将造成大量的存储浪费 

我们采用一种典型的多重链表——十字链表，来存储稀疏矩阵

只存储非0元素项

（结点的数据域：行坐标Row，列坐标Col，数值Value

每个结点通过两个指针域，把同行同列串起来

（行指针Right，列指针Down

以上就是基本思路