学步园

第五章-数组和广义表

5.4 广义表
广义表是线性表的推广，也有人称其为列表(lists，用复数形式以示与统称的表list的区别)。
由于广义表中的数据元素可以具有不同的结构(或是原子，或是列表)，因此难以用顺序存储结构表示，通常采用链式存储结构，每个元素可用一个结点表示。

(1)列表是一个多层次的结构。除空表的表头指针为空外，对任何非空列表，其表头指针均指向一个表结点，且该结点中的hp域指示列表表头，tp域指向列表表尾。
(2)任何一个非空列表其表头可能是原子，也可能是列表。而其表尾必定为列表。
(3)最高层的表结点个数即为列表的长度。

广义表运用在哪里：
(1)程序所需要的存储量事先不好预知，只能选用动态结构。
(2)使用中会出现频繁的插入与删除操作，链表的作用可以充分发挥。

typedef char AtomType; /* 定义原子类型为字符型 */
typedef enum {ATOM, LIST}ElemTag;/*ATOM==0:原子,LIST==1:子表*/
typedef struct GLNode{
	ElemTag tag;/* 公共部分,用于区分原子结点和表结点 */
	union{ /* 原子结点和表结点的联合部分 */
		AtomType atom; /* atom是原子结点的值域,AtomType由用户定义 */
		struct{
			struct GLNode *hp,*tp;
		}ptr;/* ptr是表结点的指针域,prt.hp和ptr.tp分别指向表头和表尾 */
	}a;
}*GList,GLNode; /* 广义表类型 */

Status InitGList(GList *L)
{ /* 创建空的广义表L */
	*L = NULL;
	return OK;
}

void DestroyGList(GList *L) /* 广义表的头尾链表存储的销毁操作 */
{ /* 销毁广义表L */
	GList q1,q2;
	if (*L){
		if ( (*L)->tag == ATOM ){
			free(*L);/* 删除原子结点 */
			*L = NULL;
		}
		else{ /* 删除表结点 */
			q1=(*L)->a.ptr.hp;
			q2=(*L)->a.ptr.tp;
			free(*L);
			*L = NULL;
			DestroyGList(&q1);
			DestroyGList(&q2);
		}
	}
}
Status CopyGList(GList *T,GList L)
{ /* 采用头尾链表存储结构,由广义表L复制得到广义表T。算法5.6 */
	if (!L){
		*T = NULL;
	}
	else{
		*T = (GList)malloc(sizeof(GLNode));/*建立表结点*/
		if(*T){
			exit(OVERFLOW);
		}
		(*T)->tag = L->tag;
		if(L->tag == ATOM){
			(*T)->a.atom = L->a.atom;/* 复制单原子 */
		}
		else{
			/* 复制广义表L->ptr.hp的一个副本T->ptr.hp */
			CopyGList(&(*T)->a.ptr.hp, L->a.ptr.hp);
			/* 复制广义表L->ptr.tp的一个副本T->ptr.tp */
			CopyGList(&(*T)->a.ptr.tp, L->a.ptr.tp);
		}
	}
	return OK;
}
int GListLength(GList L)
{ /* 返回广义表的长度,即元素个数 */
	int len = 0;
	if (!L){
		return 0;
	}
	if (L->tag == ATOM){
		return 1;
	}
	
	while(L){
		L = L->a.ptr.tp;
		len++;
	}
	return len;
}

int GListDepth(GList L)
{ /* 采用头尾链表存储结构,求广义表L的深度。算法5.5 */
	int max,dep;
	GList pp;
	if(!L){
		return 1; /* 空表深度为1 */
	}
	if(L->tag == ATOM){
		return 0; /* 原子深度为0 */
	}
	for(max = 0,pp = L; pp != NULL; pp = pp->a.ptr.tp){
		dep = GListDepth(pp->a.ptr.hp); /* 求以pp->a.ptr.hp为头指针的子表深度 */
		if(dep > max){
			max = dep;
		}
	}
	return max + 1; /* 非空表的深度是各元素的深度的最大值加1 */
}
Status GListEmpty(GList L)
{ /* 判定广义表是否为空 */
	if (L){
		return TRUE;
	}
	else{
		return FALSE;
	}
}
GList GetHead(GList L)
{ /* 取广义表L的头 */
	GList h,p;
	if(!L){
		printf("空表无表头!\n");
		exit(0);
	}
	p = L->a.ptr.tp;
	L->a.ptr.tp = NULL;
	CopyGList(&h, L);
	L->a.ptr.tp = p;
	return h;
}
GList GetTail(GList L)
{ /* 取广义表L的尾 */
	GList t;
	if(!L){
		printf("空表无表头!\n");
		exit(0);
	}
	CopyGList(&t, L->a.ptr.tp);
	return t;
}
Status InsertFirst_GL(GList *L,GList e)
{ /* 初始条件: 广义表存在 */
   /* 操作结果: 插入元素e作为广义表L的第一元素(表头,也可能是子表) */
	GList p = (GList)malloc(sizeof(GLNode));
	if(!p){
		exit(OVERFLOW);
	}
	p->tag = LIST;
	p->a.ptr.hp = e;
	p->a.ptr.tp = *L;
	*L = p;
	return OK;
}
Status DeleteFirst_GL(GList *L,GList *e)
{ /* 初始条件: 广义表L存在 */
	/* 操作结果: 删除广义表L的第一元素,并用e返回其值 */
	GList p;
	*e = (*L)->a.ptr.hp;
	p = *L;
	*L = (*L)->a.ptr.tp;
	free(p);
	return OK;
}
void Traverse_GL(GList L, void(*v)(AtomType))
{ /* 利用递归算法遍历广义表L */
	if(L){ /* L不空 */
		if(L->tag == ATOM){ /* L为单原子 */
			v(L->a.atom);
		}
		else{/* L为广义表 */
			Traverse_GL(L->a.ptr.hp, v);
			Traverse_GL(L->a.ptr.tp, v);
		}
	}
}
 void visit(AtomType e)
 {
   printf("%c ", e);
 }

int _tmain(int argc, _TCHAR* argv[])
{
	return 0;
}