廣義表是非線性的結(jié)構(gòu)，是線性表的一種擴展，是有n個元素組成有限序列。由于在表的描述中可以嵌套表，允許表中有表，所以可以通過遞歸實現(xiàn)廣義表。

創(chuàng)新互聯(lián)是一家專注于成都網(wǎng)站設(shè)計、成都做網(wǎng)站和達州主機托管的網(wǎng)絡(luò)公司，有著豐富的建站經(jīng)驗和案例。

具體實現(xiàn)如下：

頭文件

#pragma once
//實現(xiàn)廣義表的結(jié)構(gòu)
enum Type//枚舉類型
{
	HEAD,
	VALUE,
	SUB,
};

struct GeneralizedNode//廣義表的結(jié)點
{
	Type _type;//類型
	GeneralizedNode* _next;//值相同層的下一個節(jié)點
	union//共用體/聯(lián)合
	{
		int _value;//值節(jié)點
		GeneralizedNode* _SubLink;//指向字表的指針
	};
	GeneralizedNode();
	GeneralizedNode(Type type, int value); //全缺省構(gòu)造函數(shù)
};

class Generalized
{
public:
	Generalized();
	Generalized(const char* str);//構(gòu)造
	Generalized(const Generalized& g);//拷貝構(gòu)造
	Generalized& operator=(const Generalized& g);
	~Generalized();
	void Print();
	size_t Size();
	size_t Depth();
protected:
	GeneralizedNode* _CreatList(const char*& str);
	GeneralizedNode* _Copy(GeneralizedNode* head);
	bool _isValue(char ch);//判斷是否為字母或數(shù)字
	void _Distory(GeneralizedNode* head);
	void _Print(GeneralizedNode* head);
	size_t _Size(GeneralizedNode* head);
	size_t _Depth(GeneralizedNode* head);
protected:
	GeneralizedNode* _head;
};

各函數(shù)的具體實現(xiàn)

#include
#include
#include
using namespace std;
#include"Generalized.h"

GeneralizedNode::GeneralizedNode()
:_next(NULL)
{}
GeneralizedNode::GeneralizedNode(Type type, int value)
: _type(type)
, _next(NULL)
{
	if (_type == VALUE)
	{
		_value = value;
	}
	if (_type == SUB)
	{
		_SubLink = NULL;
	}
}
Generalized::Generalized()
:_head(NULL)
{}
Generalized::Generalized(const char* str)//構(gòu)造函數(shù)
: _head(NULL)
{
	_head = _CreatList(str);
}
GeneralizedNode* Generalized::_CreatList(const char*& str)
{//廣義表：(a, (b, c))
	assert('(' == *str); 
	str++;
	GeneralizedNode* head = new GeneralizedNode(HEAD, 0);//建立表的頭結(jié)點
	GeneralizedNode* cur = head;
	while (str)
	{
		if (_isValue(*str))//*str為字母或數(shù)字
		{
			cur->_next = new GeneralizedNode(VALUE, *str);//建立value結(jié)點
			cur = cur->_next;
			str++;
		}
		else if (*str == '(')//如果為（，則出現(xiàn)字表，進行遞歸調(diào)用
		{
			GeneralizedNode* subNode = new GeneralizedNode(SUB, 0);//建立子表結(jié)點
			cur->_next = subNode;
			cur = cur->_next;
			subNode->_SubLink = _CreatList(str);//_SubLink指向子表構(gòu)造子表
		}
		else if (*str == ')')//表示表的結(jié)束（包括子表）,返回表的頭結(jié)點
		{
			str++;
			return head;
		}
		else
		{
			str++;
		}
	}
	assert(false);
	return head;
}
bool Generalized::_isValue(char ch)//判斷是否為字母或數(shù)字
{
	if (ch >= '0' && ch <= '9' || ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z')
	{
		return true;
	}
	return false;
}
Generalized::Generalized(const Generalized& g)//拷貝構(gòu)造函數(shù)
{
	_head = _Copy(g._head);
}
GeneralizedNode* Generalized::_Copy(GeneralizedNode* head)
{
	GeneralizedNode* newhead = new GeneralizedNode(HEAD, 0);
	GeneralizedNode* cur = head;
	GeneralizedNode* newcur = newhead;
	while (cur)
	{
		if (cur->_type == VALUE)//cur._type為VALUE或SUB時建立結(jié)點，newcur才存在指向下一個結(jié)點
		{
			newcur->_next = new GeneralizedNode(VALUE, cur->_value);
			newcur = newcur->_next;
		}
		if (cur->_type == SUB)
		{
		    newcur->_next= new GeneralizedNode(SUB, 0);
			newcur = newcur->_next;
			newcur->_SubLink = _Copy(cur->_SubLink);//遞歸調(diào)用_Copy進行復(fù)制
		}
		cur = cur->_next;
	}
	return newhead;
}
Generalized& Generalized::operator=(const Generalized& g)//傳統(tǒng)寫法
{
	if (this != &g)
	{
		GeneralizedNode* tmp = _Copy(g._head);
		_Distory(_head);
		_head = tmp;
	}
	return *this;
}
Generalized::~Generalized()
{
	_Distory(_head);
}
void Generalized::_Distory(GeneralizedNode* head)
{
	GeneralizedNode* cur = head;
	while (cur)
	{
		GeneralizedNode* del = cur;
		if (cur->_type == SUB)
		{
			_Distory(cur->_SubLink);//釋放cur結(jié)點的字表
		}
		cur = cur->_next;
		delete del;
	}
}
void Generalized::Print()
{
	_Print(_head);
	cout << endl;
}
void Generalized::_Print(GeneralizedNode* head)
{
	GeneralizedNode* cur = head;
	while (cur)
	{
		if (cur->_type == HEAD)
		{
			cout << "(";
		}
		if (cur->_type == VALUE)
		{
			cout << (char)cur->_value;//強轉(zhuǎn)為char類型
			if (cur->_next)//如果cur->_next不為空打印“,”
				cout << ",";
		}
		if (cur->_type == SUB)
		{
			_Print(cur->_SubLink);
			if (cur->_next)
				cout << ",";
		}
		cur = cur->_next;
	}
	cout << ")";
}
size_t Generalized::Size()
{
	return _Size(_head);
}
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 += _Size(cur->_SubLink);
		}
		cur = cur->_next;
	}
	return count;
}
size_t Generalized::Depth()
{
	return _Depth(_head);
}
size_t Generalized::_Depth(GeneralizedNode* head)
{
	GeneralizedNode* cur = head;
	size_t depth = 1;
	while (cur)
	{
		if (cur->_type == SUB)
		{
			size_t cdepth = _Depth(cur->_SubLink);
			if (cdepth + 1 > depth)//比較子表深度，保存較大的
			{
				depth = cdepth + 1;
			}
		}
		cur = cur->_next;
	}
	return depth;
}

測試用例如下：

void Test()
{
	//Generalized g1("(a)");
	//Generalized g2("(a,b)");
	Generalized g3("(a,(a,b))");
	Generalized g4("(a,(a,(b),c),d)");
	Generalized g5 = g4;
	g5 = g3;
	//g1.Print();
	//g2.Print();
	g3.Print();
	g4.Print();
	g5.Print();
	cout << "g3.Size():" << g3.Size() << endl;
	cout << "g4.Size():" << g4.Size() << endl;
	cout << "g3.Depth():" << g3.Depth() << endl;
	cout << "g4.Depth():" << g4.Depth() << endl;
}

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

網(wǎng)站題目：遞歸實現(xiàn)廣義表-創(chuàng)新互聯(lián)
轉(zhuǎn)載來于：http://weahome.cn/article/gsjpp.html