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

廣義表是什么？如何實(shí)現(xiàn)廣義表的遞歸？這篇文章運(yùn)用了實(shí)例代碼展示，代碼非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下。

創(chuàng)新互聯(lián)公司2013年成立，是專(zhuān)業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目網(wǎng)站建設(shè)、成都做網(wǎng)站網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元峽江做網(wǎng)站,已為上家服務(wù),為峽江各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話(huà):13518219792

廣義表的定義

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

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

例如

    <5> E = (((),())

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

廣義表的節(jié)點(diǎn)結(jié)構(gòu)定義：

enum Type
{
	HEAD,//頭結(jié)點(diǎn)
	VALUE,//數(shù)據(jù)
	SUB,//子表
};

//廣義表結(jié)構(gòu)
struct GeneralizedNode
{
public:
	//無(wú)參構(gòu)造函數(shù)
	GeneralizedNode()
		:_type(HEAD)
		,_next(NULL)
	{}

	//有參的構(gòu)造函數(shù)
	GeneralizedNode(Type type, char ch);
	
public:
	Type _type;
	GeneralizedNode* _next;

	//因?yàn)楣?jié)點(diǎn)類(lèi)型不可能既是數(shù)據(jù)節(jié)點(diǎn)又是子表結(jié)點(diǎn)，所以采用聯(lián)合結(jié)構(gòu)，
	//節(jié)省空間，便于管理。
	union
	{
		char _value;//數(shù)據(jù)結(jié)點(diǎn)
		GeneralizedNode* _subLink;//子表結(jié)點(diǎn)
	};
};

//有參的構(gòu)造函數(shù)
GeneralizedNode::GeneralizedNode(Type type, char ch = 0)
	:_type(type)
	, _next(NULL)
{
	//數(shù)據(jù)節(jié)點(diǎn)則為數(shù)據(jù)初始化
	if (_type == VALUE)
	{
		_value = ch;
	}
	//子表結(jié)點(diǎn)的初始化
	else if (_type == SUB)
	{
		_subLink = NULL;
	}
}

廣義表的定義：

注意：由于廣義表的采用的是用遞歸實(shí)現(xiàn)。但構(gòu)造函數(shù)，等成員函數(shù)不能夠采用遞歸，而且在函數(shù)內(nèi)部需要不斷的傳子表的head，對(duì)于成員函數(shù)直接使用成員變量_head,則無(wú)法遞歸下去。

//廣義表類(lèi)
class Generalized
{
public:
	//無(wú)參構(gòu)造函數(shù)
	Generalized()
		:_head(new GeneralizedNode(HEAD))
	{}
	//有參構(gòu)造函數(shù)
	Generalized(const char* str)
		:_head(NULL)
	{
		_head = CreateList(str);
	}

	//拷貝構(gòu)造函數(shù)
	Generalized(const Generalized& g)
	{
		_head=_CopyList(g._head);
	}
	GeneralizedNode* _CopyList(GeneralizedNode* head);
	//賦值運(yùn)算符的重載
	Generalized& operator=(Generalized g)
	{
		swap(_head, g._head);
		return *this;
	}

	//析構(gòu)函數(shù)
	~Generalized()
	{
		_Delete(_head);
	}
	void _Delete(GeneralizedNode* head);
public:
	//打印廣義表
	void Print()
	{
		_Print(_head);
	}

	//求廣義表的大小
	size_t Size()
	{
		return _Size(_head);
	}

	//求廣義表的深度
	size_t Depth()
	{
		return _Depth(_head);
	}

protected:
	//判斷數(shù)據(jù)是否有效
	bool IsVaild(const char ch);
	//創(chuàng)建廣義表
	GeneralizedNode* CreateList(const char* &str);
	void _Print(GeneralizedNode* head);
	size_t _Size(GeneralizedNode* head);
	size_t _Depth(GeneralizedNode* head);
private:
	GeneralizedNode* _head;
};

函數(shù)的實(shí)現(xiàn)

GeneralizedNode* Generalized::_CopyList(GeneralizedNode* head)
{
	GeneralizedNode* cur = head;//需要拷貝的廣義表的當(dāng)前節(jié)點(diǎn)
	GeneralizedNode* _head = new GeneralizedNode();//拷貝廣義表的頭結(jié)點(diǎn)
	GeneralizedNode* index = _head;//拷貝廣義表的當(dāng)前節(jié)點(diǎn)
	while (cur)
	{
		//數(shù)據(jù)結(jié)點(diǎn)
		if (cur->_type == VALUE)
		{
			index->_next = new GeneralizedNode(VALUE, cur->_value);
			index = index->_next;
		}
		//子表結(jié)點(diǎn)，遞歸復(fù)制
		else if (cur->_type == SUB)
			{
				GeneralizedNode*SubNode = new GeneralizedNode(SUB);
				index->_next = SubNode;
				SubNode->_subLink= _CopyList(cur->_subLink);
				index = index->_next;
			}
		cur = cur->_next;
	}
	return _head;
}

void Generalized::_Delete(GeneralizedNode* head)
{
	GeneralizedNode* cur = head;
	while (cur)
	{
		GeneralizedNode* del = cur;
		//遞歸刪除子表
		if (cur->_type == SUB)
		{
			_Delete(cur->_subLink);
		}
		cur = cur->_next;
		delete del;
	}
}

//判斷廣義表的數(shù)據(jù)是否合法
bool Generalized::IsVaild(const char ch)
{
	if ((ch >= '0'&&ch <= '9')
		|| (ch >= 'a'&&ch <= 'z')
		|| (ch >= 'A'&&ch <= 'Z'))
	{
		return true;//合法
	}
	return false;//非法
}

GeneralizedNode* Generalized::CreateList(const char* &str)
{
	assert(str &&*str == '(');//斷言防止傳的廣義表格式不對(duì)，或者為空
	str++;//跳過(guò)第一個(gè)(

	GeneralizedNode* head = new GeneralizedNode();//創(chuàng)建頭結(jié)點(diǎn)
	GeneralizedNode* cur = head;
	while (*str)
	{
		if (IsVaild(*str))
		{


			cur->_next = new GeneralizedNode(VALUE, *str);
			cur = cur->_next;
			str++;
		}
		else if (*str == '(')//新的子表
		{
			GeneralizedNode* SubNode = new GeneralizedNode(SUB);
			SubNode->_subLink = CreateList(str);
			cur->_next = SubNode;
			cur = cur->_next;
		}
		else if (*str == ')')//廣義表結(jié)束
		{
			str++;//返回之前需要給str++指向下一個(gè)
			return head;
		}
		else//空格或者逗號(hào)
		{
			str++;
		}
	}

	assert(false);
	return NULL;
}

void Generalized::_Print(GeneralizedNode* head)
{
	GeneralizedNode* cur = head;
	if (cur == NULL)
	{
		cout << "()" << endl;
		return;
	}

	while (cur)
	{
		if (cur->_type == HEAD)
		{
			cout << "(";
		}
		else if (cur->_type == VALUE)
		{
			cout << cur->_value;
			//_value不是最后一個(gè)值
			if (cur->_next)
			{
				cout << ",";
			}
		}
		else if (cur->_type == SUB)
		{
			_Print(cur->_subLink);
			if (cur->_next)
			{
				cout << ",";
			}
		}
		cur = cur->_next;
	}
	//輸出每個(gè)表最后一個(gè)(
	cout << ")";
}


size_t Generalized::_Size(GeneralizedNode* head)
{
	GeneralizedNode* cur = head;
	size_t count = 0;
	while (cur)
	{
		if (cur->_type == VALUE)
		{
			count++;
		}
		//遞歸求取子表的大小
		if (cur->_type == SUB)
		{
			count = count + _Size(cur->_subLink);
		}
		cur = cur->_next;
	}
	return count;
}


size_t Generalized::_Depth(GeneralizedNode* head)
{
	GeneralizedNode* cur = head;
	size_t depth = 1;//空表深度為1
	while (cur)
	{
		if (cur->_type == SUB)
		{
			size_t newDepth = _Depth(cur->_subLink);
			//如果子表的深度+1大于當(dāng)前廣義表的大深度，則更新廣義表的深度
			if (newDepth +1 > depth)
			{
				depth = newDepth + 1;
			}
		}
		cur = cur->_next;
	}
	return depth;
}

測(cè)試代碼

#include"Generalized.h"

void TestGeneralized()
{
	Generalized l("(a,b,(c,d),(e,(f),h))");
	Generalized l1;
	l1 = l;
	l.Print();
	cout << endl;
	cout << "size:" << l.Size() << endl;
	cout << "depth:" << l.Depth() << endl;

	l1.Print();
	cout << endl;
	cout << "size:" << l1.Size() << endl;
	cout << "depth:" << l1.Depth() << endl;
}
int main()
{
	TestGeneralized();
	getchar();
	return 0;
}

測(cè)試結(jié)果

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

以上就是實(shí)現(xiàn)廣義表的遞歸的具體操作，代碼應(yīng)該是足夠清楚的，而且我也相信有相當(dāng)?shù)囊恍├涌赡苁俏覀內(nèi)粘９ぷ骺赡軙?huì)見(jiàn)得到的。通過(guò)這篇文章，希望你能收獲更多。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線(xiàn)，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性?xún)r(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專(zhuān)為企業(yè)上云打造定制，能夠滿(mǎn)足用戶(hù)豐富、多元化的應(yīng)用場(chǎng)景需求。

新聞名稱(chēng)：實(shí)現(xiàn)廣義表的遞歸-創(chuàng)新互聯(lián)
文章路徑：http://bm7419.com/article4/hscoe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制開(kāi)發(fā)、品牌網(wǎng)站制作、外貿(mào)網(wǎng)站建設(shè)、Google、服務(wù)器托管、網(wǎng)站制作

廣告

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

成都網(wǎng)站建設(shè)公司