当前位置:   article > 正文

【数据结构】广义表的存储结构及基本运算(C语言)_广义表的运算

广义表的运算

1. 广义表基本概念

广义表是n个数据元素(d1,d2,d3,…,dn)的有限序列,di 既可以是单个元素,也可以是一个广义表。通常记作GL =(d1,d2,d3,…,dn),n是广义表长度。若其中 di 是一个广义表,则称 di 是广义表GL的子表。在广义表GL中,d1是广义表表头,其余部分组成的表称为广义表表尾。
例如:
D=():空表,长度为0。
A=(a,(b,c)):表长度为2的广义表,第一个元素是单个数据a,第二个元素是一个子表(b,c)。
B=(A,A,D):长度为3的广义表,前两个元素为表A,第三个元素为空表D。
C=(a,C):长度为2递归定义的广义表,C相当于无穷表C=(a,(a,(a,(…))))。

① 广义表的元素可以是子表,而子表还可以是子表,因此广义表是一个多层的结构。
② 广义表可以被其它广义表共享。如广义表B共享表A,在表B中不必列出表A的内容,只要通过子表的名称就可以引用该表。
③ 广义表具有递归性,如广义表C。

2. 广义表的存储结构

2.1 头尾链表存储结构

广义表中的每一个元素用一个结点来表示,表中有两类结点:一类是单个元素结点,即原子结点;另一类是子表结点,即表结点。任何一个非空的广义表都可以将其分解成表头和表尾两部分,反之,一对确定的表头和表尾可以唯一地确定一个广义表。因此,一个表结点可由三个域构成:标志域、指向表头的指针域和指向表尾的指针域,而元素结点只需要两个域:标志域和值域。
结点结构头尾链表存储结构
代码

/*广义表的头尾链表存储结构*/
typedef enum { ATOM, LIST }ElemTag;		//ATOM=0,表示原子;LIST=1,表示子表
typedef struct GLNode {
	ElemTag tag;						//标志位tag用来区分原子结点和表结点
	union {
		int atom;						//原子结点的值域
		struct {
			struct GLNode* hp, * tp		//表结点的指针域htp,包括表头指针域hp和表尾指针域tp
		}htp;
	}atom_htp;							//atom_htp是原子结点的值域atom和表结点的指针域htp的联合体域
}GLNode, * GList;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

2.2 同层结点链存储结构

原子结点和表结点均由三个域构成。
结点结构同层结点链存储结构
代码

/*广义表的同层结点链存储结构*/
typedef enum { ATOM, LIST }ElemTag;		//ATOM=0,表示原子;LIST=1,表示子表
typedef struct GLNode {
	ElemTag tag;						//标志位tag用来区分原子结点和表结点
	union {
		int atom;						//原子结点的值域
		struct GLNode* hp;				//表头指针域
	}atom_hp;							//atom_hp是原子结点的值域atom和表结点的表头指针域hp的联合体域
	struct GLNode* tp;					//同层下一个结点的指针域
}GLNode, * GList;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

3. 广义表的基本运算

3.1 求表头、表尾

/*求广义表L的表头,并返回表头指针*/
GList Head(GList L) {
	if (L == NULL)					//空表无表头
		return NULL;
	if (L->tag == ATOM)				//原子不是表
		exit(0);
	else
		return L->atom_htp.htp.hp;	//返回表头指针
}

/*求广义表L的表尾,并返回表尾指针*/
GList Tail(GList L) {
	if (L == NULL)					//空表无表尾
		return NULL;
	if (L->tag == ATOM)				//原子不是表
		exit(0);
	else
		return L->atom_htp.htp.tp;	//返回表尾指针
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

3.2 求长度、深度

/*求广义表长度*/
int Length(GList L) {
	int k = 0;
	GLNode* s;
	if (L == NULL)
		return 0;					//空表长度为0
	if (L->tag == ATOM)				//原子不是表
		exit(0);
	s = L;
	while (s != NULL) {				//统计最上层表的长度
		k++;
		s = s->atom_htp.htp.tp;
	}
	return k;
}

/*求广义表的深度*/
int Depth(GList L) {
	int d, max;
	GLNode* s;
	if (L == NULL)
		return 1;					//空表深度为1
	if (L->tag == ATOM)
		return 0;					//原子深度为0
	s = L;
	while (s != NULL) {				//求每个子表的深度的最大值
		d = Depth(s->atom_htp.htp.hp);
		if (d > max)
			max = d;
		s = s->atom_htp.htp.tp;
	}
	return (max + 1);				//表的深度等于最深子表的深度+1
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33

3.3 统计原子数目

/*统计广义表中原子结点数目*/
int CountAtom(GList L) {
	int n1, n2;
	if (L == NULL)
		return 0;							//空表中没有原子
	if (L->tag == ATOM)
		return 1;							//L指向单个原子
	n1 = CountAtom(L->atom_htp.htp.hp);		//统计表头中的原子数目
	n2 = CountAtom(L->atom_htp.htp.tp);		//统计表尾中的原子数目
	return (n1 + n2);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

3.4 广义表的复制

/*复制广义表*/
int CopyGList(GList S, GList* T) {
	if (S == NULL) {				//复制空表
		*T = NULL;
		return OK;
	}
	*T = (GLNode*)malloc(sizeof(GLNode));
	if (*T == NULL)
		return ERROR;
	(*T)->tag = S->tag;
	if (S->tag == ATOM)
		(*T)->atom_htp.atom = S->atom_htp.atom;		//复制单个原子
	else {
		/*复制表头*/
		CopyGList(S->atom_htp.htp.hp, &((*T)->atom_htp.htp.hp));
		/*复制表尾*/
		CopyGList(S->atom_htp.htp.tp, &((*T)->atom_htp.htp.tp));
	}
	return OK;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

参考:耿国华《数据结构——用C语言描述(第二版)》

更多数据结构内容关注我的《数据结构》专栏https://blog.csdn.net/weixin_51450101/category_11514538.html?spm=1001.2014.3001.5482

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/675169
推荐阅读
相关标签
  

闽ICP备14008679号