GeneralList-广义表

GeneralList-广义表：

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

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

广义表结构

protected:
	GeneralizedNode* _head;

节点结构

struct GeneralizedNode
{
	GeneralizedNode(Type type=HEAD,char value=0)
		:_type(type)
		,_next(NULL)
	{
		if(_type==VALUE)
		{
			_value=value;
		}
		else if(_type==SUB)
		{
			_sublink=NULL;
		}
	}
	Type _type;
	GeneralizedNode* _next;

	union//联合（共用体）
	{
		GeneralizedNode* _sublink;
		char _value;
	};
};

利用联合来实现不同节点的成员不同

enum Type
{
	HEAD,
	VALUE,
	SUB,
};

构造函数：构造函数调用_CreateList函数

GeneralizedNode* _CreateList(const char*& str)//加引用避免子表递归返回时str跳到递归之前的位置
	{
		assert(str&&*str=='(');
		GeneralizedNode* head=new GeneralizedNode(HEAD);
		GeneralizedNode* cur = head;
		++str;
		while(*str)
		{
			if(IsValue(*str))
			{
				cur->_next=new GeneralizedNode(VALUE,*str);
				cur=cur->_next;
				++str;
			}
			else if(*str=='(')
			{
				cur->_next=new GeneralizedNode(SUB);
				cur=cur->_next;
				cur->_sublink=_CreateList(str);
			}
			else if(*str==')')
			{
				++str;
				return head;
			}
			else
			{
				++str;//遇见其他字符直接跳过
			}
		}
		assert(false);
		return head;
	}

析构函数：调用_Destroy

void _Destory(GeneralizedNode* head)
	{
		GeneralizedNode* cur=head;
		while(cur)
		{
			GeneralizedNode* del=cur;//记录要删除的节点
			if(cur->_type==SUB)
			{
				_Destory(cur->_sublink);//递归的条件：遇到SUB类型的节点
			}
			cur=cur->_next;
			delete del;
		}
	}

打印函数：调用_Print

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)//当前value节点后面不为空，打印逗号
				{
					cout<<",";
				}

			}
			else 
			{
				_Print(cur->_sublink);//递归的条件：遇到SUB类型的节点
				if(cur->_next)//子表递归返回时的next不为空
				{
					cout<<",";
				}
			}
			cur=cur->_next;
		}
		cout<<")";//表遍历完成之后，打印表的后括号
	}

求广义表的size：调用_Size

size_t _Size(GeneralizedNode* head)
	{
		GeneralizedNode* cur=head;
		size_t size=0;
		while(cur)
		{
			if(cur->_type==VALUE)//遇到value，size++
			{ 
				++size;
			}
			else if(cur->_type==SUB)
			{
				size+=_Size(cur->_sublink);//递归的条件：遇到SUB类型的节点
			}
			cur=cur->_next;
		}
		return size;
	}

求广义表的深度：调用_Depth

size_t _Depth(GeneralizedNode* head)
	{
		size_t index=1;//广义表为空时，深度为1
		GeneralizedNode* cur=head;
		while(cur)
		{
			if(cur->_type==SUB)
			{
				size_t subDepth=_Depth(cur->_sublink);//递归的条件：遇到SUB类型的节点
				if(subDepth+1>index)//更新深度
				{
					index=subDepth+1;
				}
			}
			cur=cur->_next;
		}
		return index;
	}

拷贝构造函数：调用_Copy

GeneralizedNode* _Copy(GeneralizedNode* head)
	{
		assert(head->_type==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);//递归进入子表
				                                      //递归的条件：遇到SUB类型的节点
			}
			cur=cur->_next;
		}
		return newhead;
	}

赋值操作符的重载（采用现代写法）

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