线性表

n个具有相同特性的数据元素的有限序列,线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部)

特征:1．集合中必存在唯一的一个“第一元素”。

2．集合中必存在唯一的一个 “最后元素” 。

3．除最后一个元素之外，均有唯一的后继(后件)。

4．除第一个元素之外，均有唯一的前驱(前件)。

存储结构:线性表主要由顺序表示或链式表示。在实际应用中，常以栈、队列、字符串等特殊形式使用。

顺序表

定义:采用顺序存储结构的线性表通常称为顺序表，如:数组。

顺序存储结构：一组地址连续的存储单元依次存储线性表中的各个元素使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中

广义表

定义:广义表是n(n≥0)个元素a1，a2，…，ai，…，an的有限序列。

长度：n ——– 最大括号中的元素（子广义表看作一个整体）

深度：嵌套的字表最多的嵌套次数 ——– 最里层括号到最外层括号的层数

注意点：

（1）表头：当广义表LS非空时，称第一个元素为LS的表头；

（2）表尾：称广义表LS中除去表头后其余元素组成的广义表为LS的表尾。

对任意一个非空的广义表，其表头可能是单元素，也可能是广义表。但是表尾一定是广义表！

eg:(a,(b,c),d) 这个广义表的长度为3,深度为2,表头是a, 表尾是(d) .

eg:((x，(a，b))，((x，(a，b))，y)) 这个广义表的长度为2, 深度为4

eg：LS“（）”与LS“（（））”不一样，前者为空表，后者为长度为 1 的表，可分解得到表头和表尾都是长度为 1 的空表。

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

or

typedef int Atomtype;
typedef enum { Atom, list }Elenment;
typedef struct Glnode {
	Elenment tag;//公共部分用于区分原子节点与表结点
	union {
		Atomtype atom;
		struct {
			struct Glnode *hp;//表结点指针域，tp表尾指针域
			struct Glnode *tp;
		}ptr;
	};
};

补充：多重链表

多重链表：链表中的节点可能同时隶属于多个链。(但包含两个指针域的链表不一定是多重链表，比如双向链表不是多重链表)

eg:

十字链表来储存稀疏矩阵

只储存矩阵非0元素项
结点的数据域：行坐标Row、列坐标Col、数值Value

每个节点通过两个指针域，把同行、同列串起来
行指针（或称为右指针）Right
列指针（或称为向下指针）Down

参考文章

https://blog.csdn.net/laizhuoyu/article/details/87905506

数据结构–线性表、广义表

广义表的表头和表尾是什么？