广义表

2017-11-28

广义表的定义

广义表(Lists，又称列表)是一种非线性的数据结构，是线性表的一种推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构，每一个元素也可以是一个表，得到一个表中有表的结构，这就是广义表。
广义表（Generalized List）一般记作
L=（a1,a2….,an）

其中，ai可以是不可再分的元素，也可以是广义表，分别称为广义表L的原子和子表。
ADT Glist
{
数据对象： D={ei | i=1,2,..,n;n>=0 ; eiÎAtomSet 或ei ÎGlist,
AtomSet为某个数据对象}
数据关系：R1={< ei-1, ei > | ei-1 , ei ÎD,2<=i<=n}
基本操作：
InitGList( &L);
操作结果：创建空的广义表L。
CreateGList(&L,S);
初始条件：S是广义表的书写形式串。
操作结果：由S创建广义表L。
DestroyGList(&L);
初始条件：广义表L存在。
操作结果：销毁广义表L。
CopyGList( &T,L);
初始条件：广义表L存在。
操作结果：由广义表L复制得到广义表T。
GListLength(L);
初始条件：广义表L存在。
操作结果：求广义表L的长度，即元素个数。
GListDepth(L);
初始条件：广义表L存在。
操作结果：求广义表L的深度。
GListEmpty (L);
初始条件：广义表L存在。
操作结果：判定广义表L是否为空。
GetHead(L);
初始条件：广义表L存在。
操作结果：取广义表L的头。
GetTail( &T,L);
初始条件：广义表L存在。
操作结果：取广义表L的尾。
InsertFirst_GL(&L,e);
初始条件：广义表L存在。
操作结果：插入元素e作为广义表L的第一元素。
DeleteFirst_GL(&L,&e);
初始条件：广义表L存在。
操作结果：删除广义表L的第一元素，并用e返回其值。
Traverse_GL (L,visit());
初始条件：广义表L存在。
操作结果：遍历广义表L，用函数visit处理每个元素。
｝

广义表的存储结构

由于广义表(a1,a2,a3,…an)中的数据元素可以具有不同的结构，（或是原子，或是广义表），因此，难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可用一个结点表示。
由于广义表中有两种数据元素，原子或广义表，因此，需要两种结构的结点：一种是表结点，用以表示列表；一种是原子结点，用以表示原子。

　　若列表不空，则可分解成表头和表尾；反之，一对确定的表头和表尾可唯一确定列表。由此，一个表结点可由三个域组成：标志域、指示表头的指针域和指示表尾的指针域；而原子结点只需两个域：标志域和值域。

例如

|阅读量(45)