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

   廣義表是一種數(shù)據(jù)結(jié)構(gòu)，是線性表的推廣。也有人稱之為列表（lists）。廣泛的用于人工智能等領(lǐng)域的表處理結(jié)構(gòu)。

 對于廣義表，我們需要了解它的結(jié)構(gòu)，通過學(xué)習(xí)廣義表，也加深了對遞歸的了解。整個廣義表都是了利用遞歸的特性實現(xiàn)的。

  （一）首先我們要確定表中每個節(jié)點的結(jié)構(gòu)，因為在廣義表中有三種不同結(jié)構(gòu)的節(jié)點，我們可以使用枚舉enum列出我們所用到的結(jié)構(gòu)節(jié)點類型。

enum Type
{
	HEAD,
	SUB,
	VALUE
};

  （二）有了type類型，只要定義一個type類型的一個對象就可以輕松定義不同類型的節(jié)點。

struct GeneralizedNode
{
	Type _type;
	union
	{
		int _value;
		GeneralizedNode* _SubLink;
	};
	GeneralizedNode* _next;

	GeneralizedNode(Type type)
	{
		if (type == HEAD)
		{
			_type = HEAD;
			_next = NULL;
		}
		else if (type == VALUE)
		{
			_type = VALUE;
			_value = 0;
			_next = NULL;
		}
		else
		{
			_type = SUB;
			_SubLink = NULL;
			_next = NULL;
		}
	}
};

  我們可以看到一個廣義表節(jié)點的結(jié)構(gòu)就定義出來了。對于HEAD類型的節(jié)點不需要_value和_SubLink這兩個數(shù)據(jù)成員，但是VALUE類型的節(jié)點需要_value，而SUB類型需要_SubLink。所以可以使用聯(lián)合union來把_value和_SubLink放在同一塊內(nèi)存，以節(jié)省空間。

  （三）有了節(jié)點的結(jié)構(gòu)，下面就開始定義廣義表的框架。

  對于廣義表，我們在意的是廣義表的結(jié)構(gòu)，也就是說我們實現(xiàn)構(gòu)造，拷貝構(gòu)造，賦值重載，打印表，析構(gòu)等函數(shù)即可。

class GeneralizedList
{
public:
	GeneralizedList(const char* str);
	GeneralizedList();
	~GeneralizedList();
	GeneralizedList(const GeneralizedList& g);
	GeneralizedList operator=(GeneralizedList g);
	size_t Size();//表中數(shù)據(jù)的個數(shù)
	size_t Deepth();//表的深度
	void Print();//打印表
private:
	size_t _Size(GeneralizedNode* head);
	size_t _Deepth(GeneralizedNode* head);
	bool _IsValue(const char& c);
	GeneralizedNode* _CreatList(const char*& str);
	void _Print(GeneralizedNode* head);
	GeneralizedNode* _Copy(GeneralizedNode* head);
	void _Release(GeneralizedNode* head);
private:
	GeneralizedNode* _head;
};

  其實廣義表的結(jié)構(gòu)并不難，也就是一個主表上鏈了一些子表。在這里我們可以把子表看作是一個主表，利用遞歸的特性，達(dá)到分治的效果。這樣實現(xiàn)起來會非常的好理解。

  要使用遞歸就不能使用公有成員函數(shù)，因為我們需要一個變量來控制遞歸的開始和結(jié)束。顯然一個私有成員變量_head是不能實現(xiàn)的，所以我們要定義一些內(nèi)部私有函數(shù)來實現(xiàn)公有函數(shù)的功能，

GeneralizedList::GeneralizedList(const char* str)
{
	_head = _CreatList(str);
}
GeneralizedList::GeneralizedList()
	:_head(NULL)
{
}
GeneralizedList::~GeneralizedList()
{
	_Release(_head);
}
GeneralizedList::GeneralizedList(const GeneralizedList& g)
{
	_head = _Copy(g._head);
}
GeneralizedList GeneralizedList::operator = (GeneralizedList g)//不能加const和&
{

	//if (this != &g)
	//{
	//	GeneralizedNode* tmp = _Copy(g._head);
	//	_Release(_head);
	//	_head = tmp;
	//}
	//return *this

	swap(_head, g._head);//現(xiàn)代寫法
	return *this;
}
void GeneralizedList::Print()
{
	_Print(_head);
}
size_t GeneralizedList::Size()
{
	return _Size(_head);
}
size_t GeneralizedList::Deepth()
{
	return _Deepth(_head);
}

  可以看到我們通過間接調(diào)用私有方法，不僅利用了類的封裝的特性，還控制了遞歸的層數(shù)。

（四）下面是私有方法的實現(xiàn)。

void GeneralizedList::_Release(GeneralizedNode* head)
{
	GeneralizedNode* cur = head;
	while (cur)
	{
		GeneralizedNode* del = cur;
		cur = cur->_next;
		if (del->_type == SUB)
		{
			_Release(del->_SubLink);
		}
		delete del;
	}
}
bool GeneralizedList::_IsValue(const char& c)
{
	if (c >= '1'&&c <= '9'
		|| c >= 'a'&&c <= 'z'
		|| c >= 'A'&& c <= 'Z')
	{
		return true;
	}
	return false;
}
GeneralizedNode* GeneralizedList::_CreatList(const char*& str)
{
	assert(*str == '(');
	++str;
	GeneralizedNode* newhead = new GeneralizedNode(HEAD);//biaozhi
	GeneralizedNode* cur = newhead;
	while (*str)
	{
		if (_IsValue(*str))
		{
			GeneralizedNode* tmp = new GeneralizedNode(VALUE);
			tmp->_value = *str;
			cur->_next = tmp;
			cur = cur->_next;
			str++;
		}
		else if (*str == '(')
		{
			GeneralizedNode * subNode = new GeneralizedNode(SUB);
			cur->_next = subNode;
			cur = cur->_next;
			subNode->_SubLink = _CreatList(str);
			//如果是'('說明后面是一個子表，我們遞歸的創(chuàng)建子表，
			然后返回子表的頭指針，將頭指針鏈到主表上
		}
		else if (*str == ')')
		{
			str++;
			return newhead;
		}
		else
		{
			++str;
		}

	}
	assert(false);
	return _head;
}
void GeneralizedList::_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
		{
			_Print(cur->_SubLink);
			if (cur->_next)//(1,2,(3,4))cur為空,不打印','
			{
				cout << ',';
			}
		}
		cur = cur->_next;
	}
	cout << ')';
}
size_t GeneralizedList::_Size(GeneralizedNode* head)
{
	GeneralizedNode* cur = head;
	size_t size = 0;
	while (cur)
	{
		if (cur->_type == VALUE)
		{
			size++;
		}
		else if (cur->_type==SUB)
		{
			size +=_Size(cur->_SubLink);
		}
		cur = cur->_next;
	}
	return size;
}

size_t GeneralizedList::_Deepth(GeneralizedNode* head)
{
	GeneralizedNode* cur = head;
	size_t maxDeep = 1;
	while (cur)
	{
		if (cur->_type == SUB)
		{
			size_t deep = _Deepth(cur->_SubLink);
			//最深的一層子表返回1，
		//	每返回一層deep就會+1；
			if (deep + 1 > maxDeep)
			{
				maxDeep = deep + 1;
			}
		}
		cur = cur->_next;
	}
	return maxDeep;
}
GeneralizedNode* GeneralizedList::_Copy(GeneralizedNode* head)
{
	GeneralizedNode* cur = head->_next;
	GeneralizedNode* newHead = new GeneralizedNode(HEAD);
	GeneralizedNode* newCur = newHead;
	while (cur)
	{
		if (cur->_type == VALUE)
		{
			newCur->_next = new GeneralizedNode(VALUE);
			newCur = newCur->_next;
			newCur->_value = cur->_value;
		}
		else if (cur->_type == SUB)
		{
			newCur->_next = new GeneralizedNode(SUB);
			newCur = newCur->_next;
			newCur->_SubLink = _Copy(cur->_SubLink);
			//如果是子表節(jié)點，
		//就遞歸拷貝子表，將子表的頭節(jié)點返回鏈接到SUB節(jié)點上，
		//通過SubLink可以找到子表
		}
		cur = cur->_next;
	}
	newCur = NULL;
	return newHead;
}