顺序存储结构的定义:广义表的定义及存储结构

课主题: 广义表 
教学目: 广义表定义及存储结构
教学重点: 广义表操作及意义
教学难点: 广义表存储结构
授课内容:
、广义表定义
广义表是线性表推广其表中元素可以是另个广义表,或其自身.
广义表定义:
ADT GList{
数据对象:D={i=1,2,...,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(L);
条件:广义表L存在
操作结果:取广义表L尾
InsertFirst_GL(&L,e);
条件:广义表L存在
操作结果:插入元素e作为广义表L第元素
DeleteFirst_GL(&L,&e);
条件:广义表L存在
操作结果:删除广义表L第元素,并用e返回其值
Traverse_GL(L,Visit);
条件:广义表L存在
操作结果:遍历广义表L,用Visit处理每个元素
}ADT GList
广义表般记作:LS=(a1,a2,...,an)
其中LS是广义表名称,n是它长度,ai可以是单个元素也可是广义表,分别称为原子和子表,当广义表非空时,称第个元素a1为LS表头称其余元素组成广义表为表尾.
2、广义表存储结构
广义表头尾链表存储表示
typedef emnu{ATOM,LIST} ElemTag;
typedef struct GLNode{
ElemTag tag;
union{
AtomType atom;
struct{struct GLNode *hp,*tp;}ptr;
}
}
有A、B、C、D、E 5个广义表描述如下:
A= A是个空表,它长度为零
B=(e) 列表B只有个原子e,B长度为1.
C=(a,(b,c,d)) 列表C长度为2,两个元素分别为原子a和子表(b,c,d)
D=(A,B,C) 列表D长度为3, 3个元素都是列表,显然,将子表值代入后,则有D=(,(e),(a,(b,c,d)))
E=(a,E) 这是个递归表,它长度为2,E相当于个无限列表E=(a,(a,(a,...)))
上述 5个广义表用以上存储结构存储映像如下:

延伸阅读