GeneralList-廣義表

GeneralList-廣義表：

廣義表是非線(xiàn)性的結(jié)構(gòu)，是線(xiàn)性表的一種擴(kuò)展，是有n個(gè)元素組成有限序列。

廣義表的定義是遞歸的，因?yàn)樵诒淼拿枋鲋杏值玫搅吮?，允許表中有表。

廣義表結(jié)構(gòu)

protected:
	GeneralizedNode* _head;

節(jié)點(diǎn)結(jié)構(gòu)

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//聯(lián)合（共用體）
	{
		GeneralizedNode* _sublink;
		char _value;
	};
};

利用聯(lián)合來(lái)實(shí)現(xiàn)不同節(jié)點(diǎn)的成員不同

enum Type
{
	HEAD,
	VALUE,
	SUB,
};

構(gòu)造函數(shù)：構(gòu)造函數(shù)調(diào)用_CreateList函數(shù)

GeneralizedNode* _CreateList(const char*& str)//加引用避免子表遞歸返回時(shí)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;//遇見(jiàn)其他字符直接跳過(guò)
			}
		}
		assert(false);
		return head;
	}

析構(gòu)函數(shù)：調(diào)用_Destroy

void _Destory(GeneralizedNode* head)
	{
		GeneralizedNode* cur=head;
		while(cur)
		{
			GeneralizedNode* del=cur;//記錄要?jiǎng)h除的節(jié)點(diǎn)
			if(cur->_type==SUB)
			{
				_Destory(cur->_sublink);//遞歸的條件：遇到SUB類(lèi)型的節(jié)點(diǎn)
			}
			cur=cur->_next;
			delete del;
		}
	}

打印函數(shù)：調(diào)用_Print

void _Print(GeneralizedNode* head)
	{
		GeneralizedNode* cur=head;
		while(cur)
		{
			if(cur->_type==HEAD)//遇到頭結(jié)點(diǎn)，打印前括號(hào)
			{
				cout<<"(";
			}
			else if(cur->_type==VALUE)
			{
				cout<<cur->_value;
				if(cur->_next)//當(dāng)前value節(jié)點(diǎn)后面不為空，打印逗號(hào)
				{
					cout<<",";
				}

			}
			else 
			{
				_Print(cur->_sublink);//遞歸的條件：遇到SUB類(lèi)型的節(jié)點(diǎn)
				if(cur->_next)//子表遞歸返回時(shí)的next不為空
				{
					cout<<",";
				}
			}
			cur=cur->_next;
		}
		cout<<")";//表遍歷完成之后，打印表的后括號(hào)
	}

求廣義表的size：調(diào)用_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類(lèi)型的節(jié)點(diǎn)
			}
			cur=cur->_next;
		}
		return size;
	}

求廣義表的深度：調(diào)用_Depth

size_t _Depth(GeneralizedNode* head)
	{
		size_t index=1;//廣義表為空時(shí)，深度為1
		GeneralizedNode* cur=head;
		while(cur)
		{
			if(cur->_type==SUB)
			{
				size_t subDepth=_Depth(cur->_sublink);//遞歸的條件：遇到SUB類(lèi)型的節(jié)點(diǎn)
				if(subDepth+1>index)//更新深度
				{
					index=subDepth+1;
				}
			}
			cur=cur->_next;
		}
		return index;
	}

拷貝構(gòu)造函數(shù)：調(diào)用_Copy

GeneralizedNode* _Copy(GeneralizedNode* head)
	{
		assert(head->_type==HEAD);//傳入的是頭結(jié)點(diǎn)才正確
		GeneralizedNode* newhead=new GeneralizedNode(HEAD);//構(gòu)造新廣義表的頭結(jié)點(diǎn)
		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);//遞歸進(jìn)入子表
				                                      //遞歸的條件：遇到SUB類(lèi)型的節(jié)點(diǎn)
			}
			cur=cur->_next;
		}
		return newhead;
	}

賦值操作符的重載（采用現(xiàn)代寫(xiě)法）

Generalized& operator=(Generalized g)//現(xiàn)代寫(xiě)法
	{
		swap(_head,g._head);
		return *this;
	}