【代码】C++实现广义表及其测试用例

    广义表是我第一次用递归接触链式的数据结构，其结构如下：

    HEAD->VAL->VAL->LINK(->HEAD.....)->VAL->......

    在这里，我们的头结点与link节点是不存储数据的，由此我们便可以定义出节点的数据结构：

typedef int DataType; enum NodeType//枚举类型定义节点类型 {	HEAD,	VALUE,	SUB, }; struct GeneralizedNode { public:	GeneralizedNode()	:_next(NULL)	, _link(NULL)	{}	NodeType _type;	GeneralizedNode* _next;	union//因为link与value是不可能同时存在的，故用共同体节省空间	{	GeneralizedNode* _link;	DataType _value;	}; };

    因为广义表是链式的嵌套结构，所以我们必须用递归来进行遍历，这里面递归的方式有很多种，可以循环套递归，也可以递归套递归，也可以递归套循环，根据我们不同的需求，可以吧这三种方法都运用在合适的地方，这里，我简单的实现了，返回对象的层数，数据个数，以及一些常用的成员函数，其代码如下：

class Generalized { public:	Generalized()	:_head(NULL)	{}	Generalized(const char *str)//构造函数是用字符串来体现广义表如（1,2，（2,3））	{                           //这样可以更好的体现出广义表的结构	_head = _CreatList(str);	}	~Generalized()	{	_Destory(_head);	}	void Print()//控制台打印广义表，也是打印出字符串类型	{	_Print(_head);	}	Generalized(const Generalized &g)	{	_head = _Copy(g._head);	}	Generalized&operator = (Generalized g)	{	swap(_head, g._head);	return *this;	}	size_t Depth()	{	return _Depth(_head);	}	size_t Size()	{	size_t size = 0;	_Size(_head, size);	return size;	} protected:	size_t _Depth(GeneralizedNode* head)	{	size_t depth = 1;	GeneralizedNode* cur = head;	while (cur)	{	if (cur->_type == SUB)	{	size_t newdepth = _Depth(cur->_link) + 1;	depth = depth < newdepth ? newdepth : depth;	}	cur = cur->_next;	}	return depth;	}	void _Size(GeneralizedNode* head, size_t &size)	{	GeneralizedNode* cur = head;	while (cur)	{	if (cur->_type == VALUE)	++size;	else if (cur->_type == SUB)	_Size(cur->_link, size);	cur = cur->_next;	}	}	GeneralizedNode* _Copy(GeneralizedNode *head)	{	GeneralizedNode* cur = head;	GeneralizedNode* newHead = new GeneralizedNode;	GeneralizedNode*tail = newHead;	tail->_type = HEAD;	while (cur)	{	if (cur->_type == SUB)	{	tail->_next = new GeneralizedNode;	tail = tail->_next;	tail->_type = SUB;	tail->_link = _Copy(cur->_link);	}	else if (cur->_type == VALUE)	{	tail->_next = new GeneralizedNode;	tail = tail->_next;	tail->_type = VALUE;	tail->_value = cur->_value;	}	cur = cur->_next;	}	return newHead;	}	void _Print(GeneralizedNode* head)	{	GeneralizedNode* cur = head;	while (cur)	{	if (cur->_type == HEAD)	{	cout << "(";	}	else if (cur->_type == VALUE)	{	cout << cur->_value;	if (cur->_next!=NULL&&	cur->_next->_type == VALUE)	cout << ",";	}	else	_Print(cur->_link);	cur = cur->_next;	}	cout << ")";	}	GeneralizedNode* _CreatList(const char* &str)	{	assert('(' == *str);	GeneralizedNode* head = new GeneralizedNode;	GeneralizedNode* cur = head;	head->_type = HEAD;	while (*++str)	{	if (IsValue(str))	{	cur->_next = new GeneralizedNode;	cur = cur->_next;	cur->_type = VALUE;	cur->_value = *str;	str++;	}	else if (')' == *str)	{	return head;	}	else if ('(')	{	cur->_next = new GeneralizedNode;	cur = cur->_next;	cur->_type = SUB;	cur->_link = _CreatList(str);	}	cur->_next = NULL;	*str++;	}	return head;	}	bool IsValue(const char *str)//判断表内存储数据是否为所需数据类型	{	if (*str <= '9'&&	*str >= '0')	return true;	return false;	}	void _Destory(GeneralizedNode*head)	{	GeneralizedNode*cur = head;	if (cur->_value == SUB)	_Destory(cur->_link);	else if (cur->_next != NULL)	_Destory(cur->_next);	delete cur;	} protected:	GeneralizedNode* _head; };

    如有什么不足或疑问希望提出。