c++实现广义表

广义表是非线性的结构，是线性表的一种扩展，是有n个元素组成有限序列。

广义表的定义是递归的，因为在表的描述中又得到了表，允许表中有表。

<1> A = ()

<2> B = (a,b)

<3> C = (a,b,(c,d))

<4> D = (a,b,(c,d),(e,(f),h)) 

<5> E = (((),()))

如下图所示：

广义表主要使用递归实现，表与表之间使用链式结构来存储。下面就来看看代码怎样实现的：

#pragma once #include <iostream> #include <assert.h> using namespace std; //节点类型 enum Type {	HEAD,//头节点	VALUE,//数据项	SUB,//子表的头节点 }; //广义表结构 struct GeneralizedNode { public:	GeneralizedNode()//无参构造函数	:_type(HEAD)	, _next(NULL)	{}	GeneralizedNode(Type type, char ch = 0)	:_type(type)	,_next(NULL)	{	if (_type == VALUE)	{	_value = ch;//数据节点	}	if (_type == SUB)	{	_sublink = NULL;//子表节点	}	} public:	Type _type;//节点类型	GeneralizedNode * _next;	union	{	char _value;//数据	GeneralizedNode * _sublink;//子表的头指针	}; }; //广义表类 class Generalized { public:	Generalized()//无参构造函数	:_head(new GeneralizedNode(HEAD))	{}	Generalized(const char* str)//构造函数	:_head(NULL)	{	_head = _CreateList(str);	}	Generalized(const Generalized & g)//拷贝构造	{	_head = _CopyList(g._head);	}	Generalized& operator=(Generalized g)//赋值运算符的重载	{	swap(_head, g._head);//现代写法	return *this;	}	~Generalized()//析构函数	{	_Delete(_head);//递归析构	} public:	void print()//打印	{	_Print(_head);	}	size_t size()//元素个数	{	size_t ret=_Size(_head);	return ret;	}	size_t depth()//广义表的深度	{	size_t ret=_Depth(_head);	return ret;	} public:	GeneralizedNode * _CreateList(const char* &str)//创建广义表	{	assert(str&&*str == '(');	//判断传入的广义表是否正确	str++;//跳过'('	GeneralizedNode* head = new GeneralizedNode();//创建头节点	GeneralizedNode* cur = head;	while (*str)	{	if (_IsVaild(*str))	{	cur->_next = new GeneralizedNode(VALUE, *str);//创建数据节点	cur = cur->_next;//节点后移	str++;//指针后移	}	else if (*str == '(')//子表	{	GeneralizedNode* SubNode = new GeneralizedNode(SUB);//创建字表的头节点	SubNode->_sublink = _CreateList(str);//递归调用_CreateList函数	cur->_next = SubNode;	cur = cur->_next;	}	else if (*str == ')')//表的结束	{	str++;//跳过')'	return head;//返回头节点	}	else//其他字符（' '或者','）	{	str++;	}	}	assert(false);//强制判断程序是否出错	return head;	}	bool _IsVaild(const char ch)//判断输入是否合理	{	if ((ch >= '0'&&ch <= '9')	|| (ch >= 'a'&&ch <= 'z')	|| (ch >= 'A'&&ch <= 'Z'))	{	return true;	}	else	{	return false;	}	}	GeneralizedNode* _CopyList(GeneralizedNode* head)//复制	{	GeneralizedNode* cur = head;	//创建新的头节点	GeneralizedNode* newHead = new GeneralizedNode();	GeneralizedNode* tmp = newHead;	while (cur)	{	if (cur->_type == VALUE)//数据节点	{	tmp->_next = new GeneralizedNode(VALUE, cur->_value);	tmp = tmp->_next;	}	else if (cur->_type == SUB)//子表节点	{	GeneralizedNode* SubNode = new GeneralizedNode(SUB);	tmp->_next = SubNode;	SubNode->_sublink = _CopyList(cur->_sublink);//递归调用	tmp = tmp->_next;	}	cur = cur->_next;	}	return newHead;	}	void _Delete(GeneralizedNode * head)	{	GeneralizedNode* cur = head;	while (cur)	{	GeneralizedNode* del = cur;	if (cur->_type == SUB)//子表节点时递归析构	{	_Delete(cur->_sublink);	}	cur = cur->_next;	delete del;	}	}	void _Print(GeneralizedNode* head)//打印	{	GeneralizedNode* cur = head;	if (cur == NULL)	{	return;	}	while (cur)	{	if (cur->_type == HEAD)	{	cout << "(";	}	else if (cur->_type == VALUE&&cur->_next)	{	cout << cur->_value<<",";	}	else if (cur->_type == VALUE&&cur->_next == NULL)	{	cout << cur->_value;	}	else if (cur->_type == SUB)	{	_Print(cur->_sublink);	if (cur->_next)	{	cout << ",";	}	}	cur = cur->_next;	}	if (cur == NULL)	{	cout << ")";	return;	}	}	size_t _Size(GeneralizedNode* head)//元素的个数	{	GeneralizedNode* cur = head;	size_t count = 0;	while (cur)	{	if (cur->_type == VALUE)	{	count++;	}	else if (cur->_type == SUB)	{	count += _Size(cur->_sublink);	}	cur = cur->_next;	}	return count;	}	size_t _Depth(GeneralizedNode* head)//广义表的深度	{	GeneralizedNode* cur = head;	size_t depth = 1;	while (cur)	{	if (cur->_type == VALUE)	{	depth++;	}	else if (cur->_type == SUB)	{	size_t newdepth = _Depth(cur->_sublink);	if (newdepth++ > depth)//当后面子表的深度比现在的深时，更新深度	{	depth = newdepth++;	}	}	cur = cur->_next;	}	return depth;	} private:	GeneralizedNode * _head; };

测试代码和结果如下：

void Test() {	Generalized g1("(a,b(c,d),(e,(f),h))");	Generalized g2;	g1.print();	cout << endl;	cout << "g1.size()="<< g1.size() << endl << endl;	cout << "g1.depth()=" << g1.depth() << endl << endl;	g2 = g1;	g2.print();	cout << endl;	cout << "g2.size()=" << g1.size() << endl << endl;	cout << "g2.depth()=" << g1.depth() << endl << endl; }