最近學(xué)習(xí)了廣義表，我們知道廣義表也是一種線性表，而顧名思義廣義表就是不止一個(gè)表，下面來(lái)舉個(gè)栗子：

成都創(chuàng)新互聯(lián)公司是一家集網(wǎng)站建設(shè),確山企業(yè)網(wǎng)站建設(shè),確山品牌網(wǎng)站建設(shè),網(wǎng)站定制,確山網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷,網(wǎng)絡(luò)優(yōu)化,確山網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

A=( )

B=（1 , 2，3）

C=(1 ,2 ,3, ( a , b ,c) )

D=(1, 2, 3, (a,( b,c),d),4)

以上A,B,C,D都是廣義表，只不過(guò)深度不一樣，也就是括號(hào)的對(duì)數(shù)不一樣，A是個(gè)特殊的廣義表，即空表。B里面有三個(gè)元素，C里面有6個(gè)元素，包括一個(gè)子表（a，b，c），C也同理，只不過(guò)多了一層子表。由此可總結(jié)為一句話：表里有表

這樣看可能不太直觀，下面以廣義表C為例來(lái)看一下它的結(jié)構(gòu)圖：

（圖畫得有點(diǎn)丑，不要吐槽我）

每當(dāng)遇到一個(gè)前括號(hào)，就要?jiǎng)?chuàng)建一個(gè)子表，直到遇見收括號(hào)。

那么如何創(chuàng)建一個(gè)廣義表呢，在創(chuàng)建節(jié)點(diǎn)結(jié)構(gòu)體的時(shí)候，我們要考慮每個(gè)節(jié)點(diǎn)的類型，有可能是頭結(jié)

點(diǎn)，也有可能是子表節(jié)點(diǎn)，也有可能是普通的值節(jié)點(diǎn)，所以在構(gòu)造節(jié)點(diǎn)的時(shí)候就要定義一個(gè)三元體，由

于是表里有表，我們可以用遞歸的方法來(lái)解決廣義表的問(wèn)題，每個(gè)子表都可以遞歸為一個(gè)子問(wèn)題，就可

以很輕松的解決掉這個(gè)問(wèn)題了。

下面是具體實(shí)現(xiàn)的代碼：

先構(gòu)造一個(gè)三元結(jié)構(gòu)體：

enum Type
{
	HEAD,
	VALUE,
	SUB,
};
template
struct GeneralizedNode
{
	Type _type;
	GeneralizedNode* _next;

	union
	{
		char _value;
		GeneralizedNode* _sublink;   //子表的頭結(jié)點(diǎn)
	};
public:
	GeneralizedNode(Type type = HEAD,char value = '\0')
		:_type(type)
		,_next(NULL)
	{
			if (type == VALUE)
			{
				_value = value;
			}
			else if (type == SUB)
			{
				_sublink = NULL;
			}
		}
};

下面來(lái)構(gòu)造一個(gè)廣義表類

template
class GeneralizedList
{
public:
	GeneralizedList()
		:_head(new GeneralizedNode(HEAD))
	{}
	GeneralizedList(const char* str)
	{
		_head=_CreateList(str);
	}
	GeneralizedList(const GeneralizedList& g)    //拷貝構(gòu)造
	{
		_head = Copy(g._head;)
	}
	size_t Size()
	{
		return size(_head);
	}
	size_t depth()
	{
		return Depth(_head);
	}
	
	void print()
	{
		Print(_head);
	}
protected:
	GeneralizedNode* _CreateList(const char*& str)
	{
		assert(str && *str == '(');
			++str;

		GeneralizedNode* Head = new GeneralizedNode(HEAD,NULL);
		GeneralizedNode* cur = Head;

		while (*str)
		{
			if (_IsValue(*str))
			{
				cur->_next = new GeneralizedNode(VALUE,*str);

				cur = cur->_next;
				str++;
			}
			else if (*str == '(')
			{
				GeneralizedNode* newNode= new GeneralizedNode(SUB);        //將一個(gè)子表結(jié)點(diǎn)加入到鏈表中
				cur->_next = newNode;
				cur = cur->_next;
				cur->_sublink = _CreateList(str);

				str++;//遞歸創(chuàng)建一個(gè)子表結(jié)點(diǎn)
			}
			else if (*str == ')')               //表示一個(gè)表已經(jīng)結(jié)束
			{
				str++;
				return Head;
			}
			else
			{
				str++;     //不需要處理的情況
			}
			
		}
		assert(false);
		return Head;
	}


	size_t Depth(GeneralizedNode* head)
	{
		GeneralizedNode* cur = head;
		size_t depth = 1;

		while (cur)
		{
			if (cur->_type == SUB)
			{
				size_t subdepth = Depth(cur->_sublink);
			
			if (subdepth+1 > depth)
			{
				depth=subdepth;//保存較大的深度
			}
			}
			cur = cur->_next;
		}
		
		return depth;
	}


	size_t size(GeneralizedNode* head)
	{
		GeneralizedNode* cur = head;

		size_t count = 0;
		while (cur)
		{
			if (cur->_type != SUB)
			{
				count++;
			}
			else
			{
				count += size(cur->_sublink);
			}
			cur = cur->_next;
		}
		return count;
	}

	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 != NULL)
				{
					cout << ',' ;
				}
			}
			
			else if (cur->_type == SUB)
			{
				Print(cur->_sublink);
				if (cur->_next != NULL)
				{
					cout << ',';
				}
			}
			cur = cur->_next;
		}
		cout << ')';
		
	}
	
	
	bool _IsValue(char ch)   //檢查是否為合法值
	{
		if ((ch >= '0'&&ch<='9') || (ch>='a'&&ch<='z') || (ch>='A'&&ch <= 'Z'))
		{
			return true;
		}
		return false;
	}
protected:
	GeneralizedNode* _head;
};

下面給出測(cè)試代碼：

#include"Generalized.h"
void Test()
{
	char* ch = "(a,b,c,(1,2),c)";
	GeneralizedList gl1(ch);
	gl1.print();
	cout << endl;
	cout << "廣義表深度為：" << gl1.depth() << endl;
	cout << "廣義表大小為：" << gl1.Size() << endl;
}

int main()
{
	Test();
	getchar();
	return 0;
}

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

以上就是C++實(shí)現(xiàn)廣義表的方法啦，里面也許還存在著一些問(wèn)題，希望大家能夠指正出來(lái)，共同促進(jìn)學(xué)習(xí)。

創(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)已開啟，新人活動(dòng)云服務(wù)器買多久送多久。

當(dāng)前文章：c++數(shù)據(jù)結(jié)構(gòu)之廣義表-創(chuàng)新互聯(lián)
鏈接URL：http://weahome.cn/article/dcjecg.html