GeneralList-廣義表：

為正定等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計制作服務(wù)，及正定網(wǎng)站建設(shè)行業(yè)解決方案。主營業(yè)務(wù)為成都網(wǎng)站設(shè)計、成都網(wǎng)站制作、正定網(wǎng)站設(shè)計，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會得到認(rèn)可，從而選擇與我們長期合作。這樣，我們也可以走得更遠(yuǎn)！

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

廣義表的定義是遞歸的，因為在表的描述中又得到了表，允許表中有表。

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

protected:
	GeneralizedNode* _head;

節(jié)點結(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)合來實現(xiàn)不同節(jié)點的成員不同

enum Type
{
	HEAD,
	VALUE,
	SUB,
};

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

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

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

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

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

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

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

求廣義表的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類型的節(jié)點
			}
			cur=cur->_next;
		}
		return size;
	}

求廣義表的深度：調(diào)用_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類型的節(jié)點
				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é)點才正確
		GeneralizedNode* newhead=new GeneralizedNode(HEAD);//構(gòu)造新廣義表的頭結(jié)點
		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類型的節(jié)點
			}
			cur=cur->_next;
		}
		return newhead;
	}

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

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

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務(wù)器買多久送多久。

分享名稱：GeneralList-廣義表-創(chuàng)新互聯(lián)
當(dāng)前鏈接：http://weahome.cn/article/copogi.html