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;
	}