数据结构-广义表

广义表是非线性的结构，是线性表的一种扩展，是有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{	Type _type;	GeneralizedNode* _next;	union	{		char _value;		GeneralizedNode* _sublink;	};	GeneralizedNode(Type type, char value=' ')		: _type(type)		, _next(NULL)	{		if (_type == VALUE)		{			_value = value;		}		else if (_type == SUB)		{			_sublink = NULL;		}	}};class Generalized{public:	typedef GeneralizedNode Node;public:	Generalized(const char* s="()")	{		_head = _Creat(s);	}	Generalized(const Generalized& g)	{		_head = _Copy(g._head);	}	Generalized& Operator=(Generalized g)	{		swap(_head,g._head);		return *this;	}	~Generalized()	{		Destroy(_head);		_head = NULL;	}	void Print()	{		_Print(_head);		cout << endl;	}	size_t Size()	{		return _Size(_head);	}	size_t Depth()	{		return _Depth(_head);	}protected:	Node* _Creat(const char*& s)	{		assert(*s == '(');		Node* head = new Node(HEAD);		Node* tail = head;		++s;		while (*s != '/0')		{			if (IsValue(*s))			{				tail->_next = new Node(VALUE, *s);				tail = tail->_next;				++s;			}			else if (*s == '(')			{				tail->_next = new Node(SUB);				tail = tail->_next;				tail->_sublink = _Creat(s);			}			else if (*s == ')')			{				++s;				return head;			}			else			{				++s;			}		}	}	Node* _Copy(Node* head)	{		Node* cur = head->_next;		Node* newhead = new Node(HEAD);		Node* tail = newhead;		while (cur)		{			if (cur->_type == VALUE)			{				tail->_next = new Node(VALUE, cur->_value);				tail = tail->_next;			}			else if (cur->_type == SUB)			{				tail->_next = new Node(SUB);				tail = tail->_next;				tail->_sublink = _Copy(cur->_sublink);			}			else			{				assert(false);			}			cur = cur->_next;		}		return newhead;	}	void Destroy(Node* head)	{		if (NULL == head)		{			return;		}		Node* cur = head->_next;		Node* del = head;		while (cur)		{			if (cur->_type == SUB)			{				Destroy(cur->_sublink);			}			delete del;			del = cur;			cur = cur->_next;		}		delete del;	}	void _Print(Node* head)	{		assert(head);				Node* cur = head->_next;		cout << "(";		while (cur)		{			if (cur->_type == VALUE)			{				cout << cur->_value;				if (cur->_next)					cout << ",";					}			else if (cur->_type == SUB)			{				_Print(cur->_sublink);				if (cur->_next)					cout << ",";			}			else			{				assert(false);			}			cur = cur->_next;		}		cout << ")";			}	size_t _Size(Node* head)	{		assert(_head);		Node* cur = head->_next;		size_t count = 0;		while (cur)		{			if (cur->_type == VALUE)			{				count += 1;			}			else if (cur->_type == SUB)			{				count += _Size(cur->_sublink);			}			else			{				assert(false);			}			cur = cur->_next;		}		return count;	}	size_t _Depth(Node* head)	{		assert(head);		size_t size = 0;		size_t maxsize = 1;		Node* cur = head->_next;		while (cur)		{			if (cur->_type == SUB)			{				size = _Depth(cur->_sublink) + 1;				if (size > maxsize)				{					maxsize = size;				}			}			cur = cur->_next;		}		return maxsize;	}protected:	Node* _head;private:	bool IsValue(const char c)  //判断给定字符串当前位置的字符是否是有效的字符(规定数字和字母为有效的字符)	{		if ((c >= '0' && c <= '9')			|| (c >= 'a' && c <= 'z')			|| (c >= 'A' && c <= 'Z'))			return true;		return false;	}};