廣義表的實(shí)現(xiàn)-創(chuàng)新互聯(lián)

廣義表：非線性結(jié)構(gòu)，是線性表的一種擴(kuò)展，是有n個(gè)元素組成有限序列，是遞歸的，因?yàn)樵诒淼拿枋鲋杏值玫搅吮?，允許表中有表。

創(chuàng)新互聯(lián)專注于企業(yè)網(wǎng)絡(luò)營(yíng)銷推廣、網(wǎng)站重做改版、閻良網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、H5建站、商城網(wǎng)站制作、集團(tuán)公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站建設(shè)、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁(yè)設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性價(jià)比高，為閻良等各大城市提供網(wǎng)站開(kāi)發(fā)制作服務(wù)。

廣義表的實(shí)現(xiàn)

#include<cassert>      
#include<iostream>
using namespace std;

enum Type    //枚舉節(jié)點(diǎn)的類型
{
	HEAD,  //頭結(jié)點(diǎn)
	VALUE, //有數(shù)據(jù)成員的節(jié)點(diǎn)
	SUB,   //有子鏈的節(jié)點(diǎn)
};

template<class T>
struct GeneralizedNode   //定義節(jié)點(diǎn)
{
	Type _type;
	GeneralizedNode* _next;
	union            //運(yùn)用聯(lián)合體使得該數(shù)據(jù)成員只含有一種節(jié)點(diǎn)
	{
		T _value;
		GeneralizedNode* _sublink;
	};
	GeneralizedNode(Type type = HEAD, T value = 0)  //構(gòu)造節(jié)點(diǎn)
		:_type(type)
		,_next(NULL)
	{
		if (_type == VALUE)
		{
			_value = value;
		}
		if (_type == SUB)
		{
			_sublink = NULL;
		}
	}
};

template<class T>
class Generalized
{
public:
	Generalized()
		:_head(NULL)
	{}
	Generalized(const char* str)    //構(gòu)造函數(shù)
		:_head(NULL)
	{
		_head = _Creatlize(str);
	}


	Generalized(const Generalized& g)   //拷貝構(gòu)造
	{
		_head = _Copy(g._head);

	}


	Generalized& operator=(const Generalized& g) //傳統(tǒng)寫法
	{
		if (this != &g)
		{
		 GeneralizedNode *temp=_Copy(g._head);
		 _Destroy(_head);
		 _head = temp;
		}
		return *this;
	}

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

	size_t Size()   //求表中的結(jié)點(diǎn)個(gè)數(shù)
	{
		return _size(_head);
	}

	size_t Depth()    //求深度
	{
		return _Depth(_head);
	}

	void print()    //打印節(jié)點(diǎn)
	{
		_print(_head);
	}

protected:
	bool ISValue(char m)
	{
		if (m >= 'a'&&m <= 'z' || m >= 'A'&&m <= 'Z' || m >= '0'&&m <= '9')
		{
			return true;
		}
		else
		{
			return false;
		}

	}
	void _print(GeneralizedNode<T>* head)  //打印節(jié)點(diǎn) 運(yùn)用遞歸方式進(jìn)行
	{
		assert(head);
		GeneralizedNode<T> *cur = head;
		while (cur)
		{
			if (cur->_type == HEAD)
			{
				cout << "(" << "";
				//cur = cur->_next;
			}
			else if (cur->_type == VALUE) //如果是VALUE，則打印該節(jié)點(diǎn)
			{
				cout << cur->_value;
				if (cur->_next == NULL)
				{
					cout << ")";
				}
				else
				{
					cout << ",";
				}
			}
			else if (cur->_type == SUB) //如果是SUB類型，則遞歸調(diào)用下一層
			{
				_print(cur->_sublink);
				if (cur->_next == NULL)
				{
					cout << ")";
				}
				else
				{
					cout << ",";
				}
				
			}
			else
			{
				
				cout << ")";
			}
			cur = cur->_next;
		}
		
	}

	size_t _size(GeneralizedNode<T>* p)
	{
		GeneralizedNode<T> *cur = p;
		int count = 0;
		while (cur)
		{
			if (cur->_type == VALUE) //如果是VALUE，則count++
			{
				++count;
			}
			else if (cur->_type == SUB) //如果是SUB，則調(diào)用下一層
			{
				count += _size(cur->_sublink);
			}
			cur = cur->_next;
		}
		return count;
	}

	int _Depth(GeneralizedNode<T>* head)
	{
		GeneralizedNode<T>* cur = head;
		int depth = 1;
		while (cur)
		{
			if (cur->_type == SUB)
			{
				int subdepth = _Depth(cur->_sublink);
				if (subdepth + 1 > depth)
				{
					depth = subdepth + 1;
				}
			}
			cur = cur->_next;
		}
		return depth;
	}

	GeneralizedNode<T>* _Creatlize(const char*& str)   //構(gòu)造廣義表
	{
		assert(*str == '(');
		while (*str)
		{
			if (*str == '(')
			{
				GeneralizedNode<T>* _head = new GeneralizedNode<T>(HEAD);
				GeneralizedNode<T>* cur = _head;
				++str;
				while (*str)
				{
					if (ISValue(*str))
					{
						GeneralizedNode<T> *temp = new GeneralizedNode<T>(VALUE);
						
						temp->_value = *str;
						cur->_next = temp;
						cur = cur->_next;
						++str;
					}
					else if (*str == '(')
					{
						GeneralizedNode<T>* sub = new GeneralizedNode<T>(SUB);
						sub->_sublink = _Creatlize(str);
						cur->_next = sub;
						cur = cur->_next;
					}
					else if (*str == ')')
					{
						++str;
						return _head;
					}
					else
					{
						++str;
					}
				}
				return _head;
			}
		}
		return _head;
	}
	GeneralizedNode<T>* _Copy(GeneralizedNode<T>* head)  //拷貝
	{
		GeneralizedNode<T>* newhead = new GeneralizedNode<T>(HEAD);
		GeneralizedNode<T>* cur = head->_next;
		GeneralizedNode<T>* newcur = newhead;
		while (cur)
		{
			if (cur->_type == VALUE)
			{
				newcur->_next = new GeneralizedNode<T>(VALUE, cur->_value);
				newcur = newcur->_next;
			}
			else if (cur->_type == SUB)
			{
				newcur->_next = new GeneralizedNode<T>(SUB);
				newcur = newcur->_next;
				newcur->_sublink = _Copy(cur->_sublink);
			}
			cur = cur->_next;
		}
		return newhead;
	}

protected:
	GeneralizedNode<T>* _head;

};

測(cè)試代碼如下：

void test4()
{
	Generalized<char> a("(a,b)");
	Generalized<char> b("(a,(c,(f),d),b)");

	Generalized<char> c(a);
	Generalized<char> d(b);
	c.print();
	cout<< endl;
	d.print();
	cout << endl;
	cout << d.Depth()<<endl;
	cout << d.Size()<<endl;
}
int main()
{

	test4();
	system("pause");
	return 0;
}

運(yùn)行結(jié)果如下：

廣義表的實(shí)現(xiàn)

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

網(wǎng)站欄目：廣義表的實(shí)現(xiàn)-創(chuàng)新互聯(lián)
新聞來(lái)源：http://muchs.cn/article26/dodicg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站排名、網(wǎng)頁(yè)設(shè)計(jì)公司、建站公司、品牌網(wǎng)站制作、微信公眾號(hào)、App開(kāi)發(fā)

廣告

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

搜索引擎優(yōu)化