广义表的实现

1.概念

广义表是线性表的推广。广义表GL = (a1,a2,a3…,an)，如果ai是单个数据元素，则称ai是广义表的原子；如果ai也是一个广义表，则称ai是广义表的子表。在广义表中要求各原子具有相同的类型，但允许各子表具有不同的结构。

举一个广义表的例子：D=((a,b), ( c), d, ((e,f),g))，这个广义表D有4个元素，其中4表示广义表的长度。D中所包含括号的最大层数称为广义表的`深度``，D的深度 = 3。广义表的第一个元素称为广义表的表头（head(D) = (a,b)），除表头外，其余部分称之为表尾（tail(D)=(( c), d, ((e,f),g)）。原子和空表没有表头和表尾。

广义表通常使用链式存储结构（带头节点），链表中的每一个结点对应广义表中的一个元素。其中节点有不同的类型：

2.图解

前面广义表D的存储结构如下图所示：

3.广义表的实现

1. 广义表的结点类型

typedef char DataType;

//广义表结点类型的定义
typedef struct GLNode
{
	int tag;//结点类型表示
	union
	{
		DataType data;
		struct GLNode *sublist;
	}val;
	struct GLNode *link;   //指向下一个元素
};

2. 创建广义表

假定广义表中的元素类型DataType为char类型，每个原子的值被限定为英文字母。并假定广义表是一个表达式，其格式为：元素之间用一个逗号分割，表元素的起止符号分别为左，右括号，空表在其圆括号内不包含任何字符。

建立广义表存储结构的算法同样是一个递归算法。该算法使用一个具有广义表格式的字符串参数s，返回由他生成的广义表存储结构的头结点指针h。在算法的执行过程中，需要从头到尾扫描s的每一个字符。当碰到左括号时，表明它是一个表元素的开始，则应该建立一个由h指向的表结点，并由它的sublist作为子表的表头指针进行递归调用，来建立子表的存储结构；当碰到一个英文字母，表明它是一个原子，则应该建立一个由h指向的原子结点；当碰到一个右括号，表明它是一个空表，应该h置为空。当建立一个由h指向的结点后，接着碰到逗号字符时，表明存在后继结点，需要建立当前结点的后继表；否则表明当前所处理的表已经结束，应该置当前结点的link为空。

GLNode *CreatGL(char *&s)
{
	GLNode *h;
	char ch; 
	ch = *s;          //取一个扫描字符
	s++;              //串指针向后移动一位
	if ('\0' != ch)   //串未结束标识
	{
		h = (GLNode*)malloc(sizeof(GLNode));     //创建一个新结点
		if ('(' == ch)                //当前字符为左括号
		{
			h->tag = 1;         //新结点为表头结点
			h->val.sublist = CreatGL(s);            //递归构造子表并链接到表头节点上
		}
		else if (')' == ch)         //当前字符为右括号
		{
			h = NULL;
		}
		else
		{
			h->tag = 0;   //新结点为原子结点
			h->val.data = ch;
		}
	}
	else   //串结束，子表为空
		h = NULL;
	ch = *s;
	s++;
	if (h != NULL)   
	{
		if (',' == ch)
		{
			h->link = CreatGL(s);
		}
		else
		{
			h->link = NULL;
		}
	}
	return h;
}

3. 输出广义表运算算法

以h作为带节点附加节点的广义表的表头指针，打印输出该广义表时，需要对子表进行递归调用。当h结点为表元素结点时，应该首先输出一个左括号作为表的起始符号，然后再输出h->sublist为表头指针的表；当h结点为单元素结点时，则应该输出该元素的值。当以h->sublist为表头指针的表输出完毕时，应在其最后输出一个右括号作为结束标志。当h结点输出完毕后，若存在后继结点，则应该输出一个逗号作为分隔符，然后在递归输出由h->link指针所指向的后继表。

void DispGL(GLNode* g)
{
	if (NULL != g)//表不为空
	{
		if (1 == g->tag)  //为表结点
		{
			cout << "(";
			if (NULL == g->val.sublist)
				cout << "";//输出空子表
			else
				DispGL(g->val.sublist);//递归输出子表
		}
		else
		{
			cout << g->val.data;
		}

		if (1 == g->tag)
			cout << ")";
		if (g->link != NULL)
		{
			cout << ",";
			DispGL(g->link);
		}
	}
}

4. 求广义表长度运算算法

在广义表中，同一层次的每个及诶但是通过link链接在一起的，所以可以把它看作是由link连接起来的单链表。这样，求广义表的长度就是求单链表的长度。

int GLLenght(GLNode *g)
{
	int n = 0;
	g = g->val.sublist;
	while(NULL != g)
	{
		n++;
		g = g->link;
	}
	return n;
}

5. 求广义表深度运算算法

int GLDepth(GLNode *g)
{
	int max = 0, dep;
	if (0 == g->tag)
	{
		return 0;
	}
	g = g->val.sublist;
	if (NULL == g)
	{
		return 1;
	}
	while (g != NULL)
	{
		if (1 == g->tag)
		{
			dep = GLDepth(g);
			if (dep > max)
				max = dep;
		}
		g = g->link;
	}
	return (max + 1);
}

6. 复制广义表运算算法

复制一个广义表的过程如下：对于广义表的头结点*p，若为空，则返回空指针；若为表结点，则递归复制子表；否则，复制原子结点，然后再递归复制后续表。返回复制后的广义表链表的指针。

GLNode *GLCopy(GLNode *p)
{
	GLNode *q;
	if (NULL == p)
		return NULL;
	
	q = (GLNode*)malloc(sizeof(GLNode));
	q->tag = p->tag;
	if (1 == p->tag)
		q->val.sublist = GLCopy(p->val.sublist);
	else
		q->val.data = p->val.data;
	q->link = GLCopy(p->link);
	return q;
}

7. 求表头运算算法

空表和原子不能求表头；若表头结点为原子，则复制该节点并记为q；若表头结点是子表，则由于其link不一定为NULL，所以复制该表头结点产生t，并置t->link =NULL ，t称为虚拟表头结点。

GLNode *head(GLNode *g)
{
	GLNode *p = g->val.sublist;
	GLNode *q, *t;
	if (NULL == p)
	{
		cout << "空表不能求表头\n" << endl;
		return NULL;
	}
	else if (0 == g->tag)
	{
		cout << "原子不能求表头\n" << endl;
		return NULL;
	}
	if (0 == p->tag)   //原子结点
	{
		q = (GLNode*)malloc(sizeof(GLNode));
		q->tag = 0;
		q->val.data = p->val.data;
		q->link = NULL;
	}
	else     //为子表
	{
		t = (GLNode*)malloc(sizeof(GLNode));
		t->tag = 1;
		t->val.sublist = p->val.sublist;
		t->link = NULL;
		q = GLCopy(t);
		free(t);
	}
	return q;
}

8. 求表尾运算算法

空表和原子不能求表尾；否则创建一个虚拟表头结点t，并置t->val.sublist = h->val.sublist->link。

GLNode *tail(GLNode *g)
{
	GLNode *p = g->val.sublist;
	GLNode *q, *t;

	if (NULL == g)
	{
		cout << "空表不能求表尾" << endl;
		return NULL;
	}
	else if (0 == g->tag)
	{
		cout << "空表不能求表尾" << endl;
		return NULL;
	}
	p = p->link;
	t = (GLNode*)malloc(sizeof(GLNode));
	t->tag = 1;
	t->link = NULL;
	t->val.sublist = p;
	q = GLCopy(t);
	free(t);
	return q;
}

9. 测试与结果展示

void Test()
{
	char s[] = "((a,b),(c),d,((e,f),g))";
	char *ps =(char*)&s;
	char *&pps = ps;

	GLNode *gl = CreatGL(ps);
	cout << "广义表为：";
	DispGL(gl);
	cout << endl;
	cout << "广义表的长度:" << GLLenght(gl) << endl;
	cout << "广义表的深度:" << GLDepth(gl) << endl;

	GLNode *copy = GLCopy(gl);
	cout << "复制后广义表为：";
	DispGL(copy);
	cout << endl;

	GLNode *head1 = head(gl);
	cout << "表头为：";
	DispGL(head1);
	cout <<endl;

	GLNode *tail1 = tail(gl);
	cout << "表尾为：" ;
	DispGL(tail1);
	cout << endl;

}

int main()
{
	Test();
	system("pause");
	return 0;
}