广义表：非线性结构，是线性表的一种扩展，是有n个元素组成有限序列，是递归的，因为在表的描述中又得到了表，允许表中有表。

让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：域名与空间、雅安服务器托管、营销软件、网站建设、岑巩网站维护、网站推广。

#include      
#include
using namespace std;

enum Type    //枚举节点的类型
{
	HEAD,  //头结点
	VALUE, //有数据成员的节点
	SUB,   //有子链的节点
};

template
struct GeneralizedNode   //定义节点
{
	Type _type;
	GeneralizedNode* _next;
	union            //运用联合体使得该数据成员只含有一种节点
	{
		T _value;
		GeneralizedNode* _sublink;
	};
	GeneralizedNode(Type type = HEAD, T value = 0)  //构造节点
		:_type(type)
		,_next(NULL)
	{
		if (_type == VALUE)
		{
			_value = value;
		}
		if (_type == SUB)
		{
			_sublink = NULL;
		}
	}
};

template
class Generalized
{
public:
	Generalized()
		:_head(NULL)
	{}
	Generalized(const char* str)    //构造函数
		:_head(NULL)
	{
		_head = _Creatlize(str);
	}


	Generalized(const Generalized& g)   //拷贝构造
	{
		_head = _Copy(g._head);

	}


	Generalized& operator=(const Generalized& g) //传统写法
	{
		if (this != &g)
		{
		 GeneralizedNode *temp=_Copy(g._head);
		 _Destroy(_head);
		 _head = temp;
		}
		return *this;
	}

	Generalized& operator=(Generalized  g) //现代写法
	{
		swap(_head, g._head);
		return *this;
	}

	size_t Size()   //求表中的结点个数
	{
		return _size(_head);
	}

	size_t Depth()    //求深度
	{
		return _Depth(_head);
	}

	void print()    //打印节点
	{
		_print(_head);
	}

protected:
	bool ISValue(char m)
	{
		if (m >= 'a'&&m <= 'z' || m >= 'A'&&m <= 'Z' || m >= '0'&&m <= '9')
		{
			return true;
		}
		else
		{
			return false;
		}

	}
	void _print(GeneralizedNode* head)  //打印节点 运用递归方式进行
	{
		assert(head);
		GeneralizedNode *cur = head;
		while (cur)
		{
			if (cur->_type == HEAD)
			{
				cout << "(" << "";
				//cur = cur->_next;
			}
			else if (cur->_type == VALUE) //如果是VALUE，则打印该节点
			{
				cout << cur->_value;
				if (cur->_next == NULL)
				{
					cout << ")";
				}
				else
				{
					cout << ",";
				}
			}
			else if (cur->_type == SUB) //如果是SUB类型，则递归调用下一层
			{
				_print(cur->_sublink);
				if (cur->_next == NULL)
				{
					cout << ")";
				}
				else
				{
					cout << ",";
				}
				
			}
			else
			{
				
				cout << ")";
			}
			cur = cur->_next;
		}
		
	}

	size_t _size(GeneralizedNode* p)
	{
		GeneralizedNode *cur = p;
		int count = 0;
		while (cur)
		{
			if (cur->_type == VALUE) //如果是VALUE，则count++
			{
				++count;
			}
			else if (cur->_type == SUB) //如果是SUB，则调用下一层
			{
				count += _size(cur->_sublink);
			}
			cur = cur->_next;
		}
		return count;
	}

	int _Depth(GeneralizedNode* head)
	{
		GeneralizedNode* cur = head;
		int depth = 1;
		while (cur)
		{
			if (cur->_type == SUB)
			{
				int subdepth = _Depth(cur->_sublink);
				if (subdepth + 1 > depth)
				{
					depth = subdepth + 1;
				}
			}
			cur = cur->_next;
		}
		return depth;
	}

	GeneralizedNode* _Creatlize(const char*& str)   //构造广义表
	{
		assert(*str == '(');
		while (*str)
		{
			if (*str == '(')
			{
				GeneralizedNode* _head = new GeneralizedNode(HEAD);
				GeneralizedNode* cur = _head;
				++str;
				while (*str)
				{
					if (ISValue(*str))
					{
						GeneralizedNode *temp = new GeneralizedNode(VALUE);
						
						temp->_value = *str;
						cur->_next = temp;
						cur = cur->_next;
						++str;
					}
					else if (*str == '(')
					{
						GeneralizedNode* sub = new GeneralizedNode(SUB);
						sub->_sublink = _Creatlize(str);
						cur->_next = sub;
						cur = cur->_next;
					}
					else if (*str == ')')
					{
						++str;
						return _head;
					}
					else
					{
						++str;
					}
				}
				return _head;
			}
		}
		return _head;
	}
	GeneralizedNode* _Copy(GeneralizedNode* head)  //拷贝
	{
		GeneralizedNode* newhead = new GeneralizedNode(HEAD);
		GeneralizedNode* cur = head->_next;
		GeneralizedNode* newcur = newhead;
		while (cur)
		{
			if (cur->_type == VALUE)
			{
				newcur->_next = new GeneralizedNode(VALUE, cur->_value);
				newcur = newcur->_next;
			}
			else if (cur->_type == SUB)
			{
				newcur->_next = new GeneralizedNode(SUB);
				newcur = newcur->_next;
				newcur->_sublink = _Copy(cur->_sublink);
			}
			cur = cur->_next;
		}
		return newhead;
	}

protected:
	GeneralizedNode* _head;

};

测试代码如下：

void test4()
{
	Generalized a("(a,b)");
	Generalized b("(a,(c,(f),d),b)");

	Generalized c(a);
	Generalized d(b);
	c.print();
	cout<< endl;
	d.print();
	cout << endl;
	cout << d.Depth()<
运行结果如下：
            
            
                                                            

                                                分享文章：广义表的实现                                                

                                                文章地址：http://scpingwu.com/article/ijpjjp.html