GeneralList-廣義表：

成都創(chuàng)新互聯(lián)公司專注于成都網站制作、成都網站設計、網頁設計、網站制作、網站開發(fā)。公司秉持“客戶至上,用心服務”的宗旨,從客戶的利益和觀點出發(fā),讓客戶在網絡營銷中找到自己的駐足之地。尊重和關懷每一位客戶，用嚴謹?shù)膽B(tài)度對待客戶，用專業(yè)的服務創(chuàng)造價值，成為客戶值得信賴的朋友，為客戶解除后顧之憂。

廣義表是非線性的結構，是線性表的一種擴展，是有n個元素組成有限序列。

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

廣義表結構

protected:
	GeneralizedNode* _head;

節(jié)點結構

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

構造函數(shù)：構造函數(shù)調用_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;
	}

析構函數(shù)：調用_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ù)：調用_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節(jié)點后面不為空，打印逗號
				{
					cout<<",";
				}

			}
			else 
			{
				_Print(cur->_sublink);//遞歸的條件：遇到SUB類型的節(jié)點
				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類型的節(jié)點
			}
			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類型的節(jié)點
				if(subDepth+1>index)//更新深度
				{
					index=subDepth+1;
				}
			}
			cur=cur->_next;
		}
		return index;
	}

拷貝構造函數(shù)：調用_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類型的節(jié)點
			}
			cur=cur->_next;
		}
		return newhead;
	}

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

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

文章名稱：GeneralList-廣義表
分享URL：http://jinyejixie.com/article46/gpsjeg.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供定制網站、建站公司、手機網站建設、網頁設計公司、軟件開發(fā)、用戶體驗

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)