广义表的递归实现

   广义表是一种数据结构，是线性表的推广。也有人称之为列表（lists）。广泛的用于人工智能等领域的表处理结构。

 对于广义表，我们需要了解它的结构，通过学习广义表，也加深了对递归的了解。整个广义表都是了利用递归的特性实现的。

  （一）首先我们要确定表中每个节点的结构，因为在广义表中有三种不同结构的节点，我们可以使用枚举enum列出我们所用到的结构节点类型。

enum Type
{
	HEAD,
	SUB,
	VALUE
};

  （二）有了type类型，只要定义一个type类型的一个对象就可以轻松定义不同类型的节点。

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;
		}
	}
};

  我们可以看到一个广义表节点的结构就定义出来了。对于HEAD类型的节点不需要_value和_SubLink这两个数据成员，但是VALUE类型的节点需要_value，而SUB类型需要_SubLink。所以可以使用联合union来把_value和_SubLink放在同一块内存，以节省空间。

  （三）有了节点的结构，下面就开始定义广义表的框架。

  对于广义表，我们在意的是广义表的结构，也就是说我们实现构造，拷贝构造，赋值重载，打印表，析构等函数即可。

class GeneralizedList
{
public:
	GeneralizedList(const char* str);
	GeneralizedList();
	~GeneralizedList();
	GeneralizedList(const GeneralizedList& g);
	GeneralizedList operator=(GeneralizedList g);
	size_t Size();//表中数据的个数
	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;
};

  其实广义表的结构并不难，也就是一个主表上链了一些子表。在这里我们可以把子表看作是一个主表，利用递归的特性，达到分治的效果。这样实现起来会非常的好理解。

  要使用递归就不能使用公有成员函数，因为我们需要一个变量来控制递归的开始和结束。显然一个私有成员变量_head是不能实现的，所以我们要定义一些内部私有函数来实现公有函数的功能，

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);//现代写法
	return *this;
}
void GeneralizedList::Print()
{
	_Print(_head);
}
size_t GeneralizedList::Size()
{
	return _Size(_head);
}
size_t GeneralizedList::Deepth()
{
	return _Deepth(_head);
}

  可以看到我们通过间接调用私有方法，不仅利用了类的封装的特性，还控制了递归的层数。

（四）下面是私有方法的实现。

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);
			//如果是'('说明后面是一个子表，我们递归的创建子表，
			然后返回子表的头指针，将头指针链到主表上
		}
		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);
			//如果是子表节点，
		//就递归拷贝子表，将子表的头节点返回链接到SUB节点上，
		//通过SubLink可以找到子表
		}
		cur = cur->_next;
	}
	newCur = NULL;
	return newHead;
}