请问广义表（（a,b）,c,d）表头和表尾分别是什么？谢谢

广义表((a,b,c,d))的表头是(a,b,c,d)，表尾是()。

根据广义表对表头和表尾的定义可知：

（1）对任意一个非空的广义表，其表头可能是单元素，也可能是广义表。

（2）而其表尾一定是广义表。

（3）注意表尾的深度（即括号的嵌套层数）。

（4）表尾是由除了表头以外的其余元素组成的广义表，所以，需要在表尾的直接元素外面再加一层括号。

扩展资料

广义表的存储结构

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

由于广义表中有两种数据元素，原子或广义表，因此，需要两种结构的结点：一种是表结点，用以表示列表；一种是原子结点，用以表示原子。

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

/* bo5-6.c 广义表的扩展线性链表存储(存储结构由c5-6.h定义)的基本 *** 作(13个) */

#include"c4-2.h" /* 定义HString类型 */

#include"bo4-2.c" /* HString类型的基本 *** 作 */

/* 广义表的书写形式串为HString类型 */

Status InitGList(GList *L)

{ /* 创建空的广义表L */

*L=NULL

return OK

}

Status sever(HString *str,HString *hstr) /* 同bo5-52.c */

{ /* 将非空串str分割成两部分:hstr为第一个','之前的子串,str为之后的子串 */

int n,i=1,k=0/* k记尚未配对的左括号个数 */

HString ch,c1,c2,c3

InitString(&ch)/* 初始化HString类型的变量 */

InitString(&c1)

InitString(&c2)

InitString(&c3)

StrAssign(&c1,",")

StrAssign(&c2,"(")

StrAssign(&c3,")")

n=StrLength(*str)

do

{

SubString(&ch,*str,i,1)

if(!StrCompare(ch,c2))

++k

else if(!StrCompare(ch,c3))

--k

++i

}while(i<=n&&StrCompare(ch,c1)||k!=0)

if(i<=n)

{

StrCopy(&ch,*str)

SubString(hstr,ch,1,i-2)

SubString(str,ch,i,n-i+1)

}

else

{

StrCopy(hstr,*str)

ClearString(str)

}

return OK

}

Status CreateGList(GList *L,HString S)

{ /* 初始条件: S是广义表的书写形式串。 *** 作结果: 由S创建广义表L */

HString emp,sub,hsub

GList p

InitString(&emp)

InitString(&sub)

InitString(&hsub)

StrAssign(&emp,"()")/* 设emp="()" */

*L=(GList)malloc(sizeof(GLNode))

if(!*L) /* 建表结点不成功 */

exit(OVERFLOW)

if(!StrCompare(S,emp)) /* 创建空表 */

{

(*L)->tag=LIST

(*L)->a.hp=NULL

(*L)->tp=NULL

}

else if(StrLength(S)==1) /* 创建单原子广义表 */

{

(*L)->tag=ATOM

(*L)->a.atom=S.ch[0]

(*L)->tp=NULL

}

else /* 创建一般表 */

{

(*L)->tag=LIST

(*L)->tp=NULL

SubString(&sub,S,2,StrLength(S)-2)/* 脱外层括号 */

sever(&sub,&hsub)/* 从sub中分离出表头串hsub */

CreateGList(&(*L)->a.hp,hsub)

p=(*L)->a.hp

while(!StrEmpty(sub)) /* 表尾不空,则重复建n个子表 */

{

sever(&sub,&hsub)/* 从sub中分离出表头串hsub */

CreateGList(&p->tp,hsub)

p=p->tp

}

}

return OK

}

void DestroyGList(GList *L)

{ /* 初始条件: 广义表L存在。 *** 作结果: 销毁广义表L */

GList ph,pt

if(*L) /* L不为空表 */

{ /* 由ph和pt接替L的两个指针 */

if((*L)->tag) /* 是子表 */

ph=(*L)->a.hp

else /* 是原子 */

ph=NULL

pt=(*L)->tp

free(*L)/* 释放L所指结点 */

*L=NULL/* 令L为空 */

DestroyGList(&ph)/* 递归销毁表ph */

DestroyGList(&pt)/* 递归销毁表pt */

}

}

Status CopyGList(GList *T,GList L)

{ /* 初始条件: 广义表L存在。 *** 作结果: 由广义表L复制得到广义表T */

if(!L) /* L空 */

{

*T=NULL

return OK

}

*T=(GList)malloc(sizeof(GLNode))

if(!*T)

exit(OVERFLOW)

(*T)->tag=L->tag/* 复制枚举变量 */

if(L->tag==ATOM) /* 复制共用体部分 */

(*T)->a.atom=L->a.atom/* 复制单原子 */

else

CopyGList(&(*T)->a.hp,L->a.hp)/* 复制子表 */

if(L->tp==NULL) /* 到表尾 */

(*T)->tp=L->tp

else

CopyGList(&(*T)->tp,L->tp)/* 复制子表 */

return OK

}

int GListLength(GList L)

{ /* 初始条件: 广义表L存在。 *** 作结果: 求广义表L的长度,即元素个数 */

int len=0

GList p

if(L->tag==LIST&&!L->a.hp) /* 空表 */

return 0/* 空表返回0 */

else if(L->tag==ATOM) /* 单原子表 */

return 1

else /* 一般表 */

{

p=L->a.hp

do

{

len++

p=p->tp

}while(p)

return len

}

}

int GListDepth(GList L)

{ /* 初始条件: 广义表L存在。 *** 作结果: 求广义表L的深度 */

int max,dep

GList pp

if(L==NULL||L->tag==LIST&&!L->a.hp)

return 1/* 空表深度为1 */

else if(L->tag==ATOM)

return 0/* 单原子表深度为0 */

else /* 求一般表的深度 */

for(max=0,pp=L->a.hppppp=pp->tp)

{

dep=GListDepth(pp)/* 求以pp为头指针的子表深度 */

if(dep>max)

max=dep

}

return max+1/* 非空表的深度是各元素的深度的最大值加1 */

}

Status GListEmpty(GList L)

{ /* 初始条件: 广义表L存在。 *** 作结果: 判定广义表L是否为空 */

if(!L||L->tag==LIST&&!L->a.hp)

return OK

else

return ERROR

}

GList GetHead(GList L)

{ /* 初始条件: 广义表L存在。 *** 作结果: 取广义表L的头 */

GList h

InitGList(&h)

if(!L||L->tag==LIST&&!L->a.hp)

{

printf("\n空表无表头!")

exit(0)

}

h=(GList)malloc(sizeof(GLNode))

if(!h)

exit(OVERFLOW)

h->tag=L->a.hp->tag

h->tp=NULL

if(h->tag==ATOM)

h->a.atom=L->a.hp->a.atom

else

CopyGList(&h->a.hp,L->a.hp->a.hp)

return h

}

GList GetTail(GList L)

{ /* 初始条件: 广义表L存在。 *** 作结果: 取广义表L的尾 */

GList T

if(!L)

{

printf("\n空表无表尾!")

exit(0)

}

T=(GList)malloc(sizeof(GLNode))

if(!T)

exit(OVERFLOW)

T->tag=LIST

T->tp=NULL

CopyGList(&T->a.hp,L->a.hp->tp)

return T

}

Status InsertFirst_GL(GList *L,GList e)

{ /* 初始条件: 广义表存在 */

/* *** 作结果: 插入元素e作为广义表L的第一元素(表头,也可能是子表) */

GList p=(*L)->a.hp

(*L)->a.hp=e

e->tp=p

return OK

}

Status DeleteFirst_GL(GList *L,GList *e)

{ /* 初始条件:广义表L存在。 *** 作结果:删除广义表L的第一元素,并用e返回其值 */

if(*L)

{

*e=(*L)->a.hp

(*L)->a.hp=(*e)->tp

(*e)->tp=NULL

}

else

*e=*L

return OK

}

void Traverse_GL(GList L,void(*v)(AtomType))

{ /* 利用递归算法遍历广义表L */

GList hp

if(L) /* L不空 */

{

if(L->tag==ATOM) /* L为单原子 */

{

v(L->a.atom)

hp=NULL

}

else /* L为子表 */

hp=L->a.hp

Traverse_GL(hp,v)

Traverse_GL(L->tp,v)

}

}

广义表（Lists，又称列表） 是线性表的推广。线性表定义为n>=0个元素a1,a2,a3,…,an的有限序列。线性表的元素仅限于原子项，原子是作为结构上不可分割的成分，它可以是一个数或一个结构，若放松对表元素的这种限制，容许它们具有其自身结构，这样就产生了广义表的概念。

广义表是n (n>=0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。通常记作LS=（a1,a2,a3,…,an)。LS是广义表的名字，n为它的长度。若ai是广义表，则称它为LS的子表。

抽象数据类型广义表的定义如下：

ADT Glist

{

数据对象：D={ei | i=1,2,..,nn>=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处理每个元素。

｝

通常用圆括号将广义表括起来，用逗号分隔其中的元素。为了区别原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。若广义表LS（n>=1)非空，则a1是LS的表头，其余元素组成的表(a2,…an)称为LS的表尾。

显然广义表是递归定义的，这是因为在定义广义表时又用到了广义表的概念。广义表的例子如下：

（1）A=（）——A是一个空表，其长度为零。

（2）B=（e）——表B只有一个原子e，B的长度为1。

（3）C=（a,(b,c,d))——表C的长度为2，两个元素分别

为原子a和子表(b,c,d)。

（4）D=（A，B，C）——表D的长度为3，三个元素

都是广义表。显然，将子表的值代入后，

则有D=(( ),(e),(a,(b,c,d)))。

（5）E=（E）——这是一个递归的表，它的长度为2，E相当于一个无限的广义表E=(a,(a,(a,(a,…)))).

从上述定义和例子可推出广义表的三个重要结论：

（1）广义表的元素可以是子表，而子表的元素还可以是子表，。由此，广义表是一个多层次的结构，可以用图形象地表示。P108

（2）广义表可为其它表所共享。例如在上述例（4）中，广义表A，B，C为D的子表，则在D中可以不必列出子表的值，而是通过子表的名称来引用。

（3）广义表的递归性。

综上所述，广义表不仅是线性表的推广，也是树的推广。

由表头、表尾的定义可知：任何一个非空广义表其表头可能是原子，也可能是列表，而其表尾必定是列表。

gethead(B)=egettail(B)=()

gethead(D)=Agettail(D)=(B,C)

由于（B，C）为非空广义表，则可继续分解得到：

gethead(B,C)=Bgettail(B,C)=(C)

注意广义表（）和( ( ) )不同。前者是长度为0的空表，

对其不能做求表头的和表尾的运算；而后者是长度为1的非空表（只不过该表中唯一的一个元素是空表）。对其可进行分解，得到表头和表尾均为空表（）。

广义表的存储结构

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

由于广义表中有两种数据元素，原子或广义表，因此，需要两种结构的结点：一种是表结点，用以表示列表；一种是原子结点，用以表示原子。

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

1、仅有表结点由三个域组成：

标志域、指示表头的指针域和指示表尾的指针域；而原子域只需两个域：标志域和值域。

头尾链表存储表示

[cpp] view plain copy

typedefenum{ATOM,LIST } ElemTag//ATOM==0:表示原子,LIST==1:表示子表

typedefstructGLNode {

ElemTag  tag//公共部分，用以区分原子部分和表结点

union{//原子部分和表结点的联合部分

AtomType  atom//atom是原子结点的值域,AtomType由用户定义

struct{structGLNode *hp, *tp} ptr

// ptr是表结点的指针域,ptr.hp 和ptr.tp分别指向表头和表尾

}

} *Glist//广义表类型

示例如图：

这种存储结构的三个特点：

1。除空表的表头指针为空外，对任何非空列表，其表头指针均指向一个表结点，且该结点中的hp域指示列表表头，tp域指向列表表尾（除非表尾为空，则指针为空，否则必为表结点）；

2。容易分清列表中原子和子表所在层次。如在列表D中，原子e和a在同一层次上，而b、c和d在同一层次且比e和a低一层，B和C是同一层的子表；

3。最高层的表结点个数即为列表的长度。

2、表结点和原子结点均由三个域组成： 标志域、指示表头的指针域和指示表尾的指针域；原子结点的三个域为：标志域、值域和指示表尾的指针域。

其类型定义如下：

扩展线性链表存储表示

[cpp] view plain copy

Typedefenum{ATOM,LIST} ElemTag

//ATOM==0:表示原子,LIST==1:表示子表

TypedefstructGLNode {

ElemTag    tag//公共部分，用以区分原子部分和表结点

union{//原子部分和表结点的联合部分

AtomType    atom//原子结点的值域

structGLNode  *hp//表结点的表头指针

}

structGLNode    *tp

//相当于线性链表的next，指向下一个元素结点

} *Glist//广义表类型Glist 是一种扩展的线性链表

示例如图：

---