实现广义表的递归

广义表是什么？如何实现广义表的递归？这篇文章运用了实例代码展示，代码非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下。

广义表的定义

广义表是非线性的结构，是线性表的一种扩展，是有n个元素组成有限序列。

广义表的定义是递归的，因为在表的描述中又得到了表，允许表中有表。

例如

    <1> A = ()

    <2> B = (a,b)

    <3> C = (a,b,(c,d))

    <4> D = (a,b,(c,d),(e,(f),h)) 

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

广义表的节点结构定义：

enum Type
{
	HEAD,//头结点
	VALUE,//数据
	SUB,//子表
};

//广义表结构
struct GeneralizedNode
{
public:
	//无参构造函数
	GeneralizedNode()
		:_type(HEAD)
		,_next(NULL)
	{}

	//有参的构造函数
	GeneralizedNode(Type type, char ch);
	
public:
	Type _type;
	GeneralizedNode* _next;

	//因为节点类型不可能既是数据节点又是子表结点，所以采用联合结构，
	//节省空间，便于管理。
	union
	{
		char _value;//数据结点
		GeneralizedNode* _subLink;//子表结点
	};
};

//有参的构造函数
GeneralizedNode::GeneralizedNode(Type type, char ch = 0)
	:_type(type)
	, _next(NULL)
{
	//数据节点则为数据初始化
	if (_type == VALUE)
	{
		_value = ch;
	}
	//子表结点的初始化
	else if (_type == SUB)
	{
		_subLink = NULL;
	}
}

广义表的定义：

注意：由于广义表的采用的是用递归实现。但构造函数，等成员函数不能够采用递归，而且在函数内部需要不断的传子表的head，对于成员函数直接使用成员变量_head,则无法递归下去。

//广义表类
class Generalized
{
public:
	//无参构造函数
	Generalized()
		:_head(new GeneralizedNode(HEAD))
	{}
	//有参构造函数
	Generalized(const char* str)
		:_head(NULL)
	{
		_head = CreateList(str);
	}

	//拷贝构造函数
	Generalized(const Generalized& g)
	{
		_head=_CopyList(g._head);
	}
	GeneralizedNode* _CopyList(GeneralizedNode* head);
	//赋值运算符的重载
	Generalized& operator=(Generalized g)
	{
		swap(_head, g._head);
		return *this;
	}

	//析构函数
	~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:
	//判断数据是否有效
	bool IsVaild(const char ch);
	//创建广义表
	GeneralizedNode* CreateList(const char* &str);
	void _Print(GeneralizedNode* head);
	size_t _Size(GeneralizedNode* head);
	size_t _Depth(GeneralizedNode* head);
private:
	GeneralizedNode* _head;
};

函数的实现

GeneralizedNode* Generalized::_CopyList(GeneralizedNode* head)
{
	GeneralizedNode* cur = head;//需要拷贝的广义表的当前节点
	GeneralizedNode* _head = new GeneralizedNode();//拷贝广义表的头结点
	GeneralizedNode* index = _head;//拷贝广义表的当前节点
	while (cur)
	{
		//数据结点
		if (cur->_type == VALUE)
		{
			index->_next = new GeneralizedNode(VALUE, cur->_value);
			index = index->_next;
		}
		//子表结点，递归复制
		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;
	}
}

//判断广义表的数据是否合法
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 == '(');//断言防止传的广义表格式不对，或者为空
	str++;//跳过第一个(

	GeneralizedNode* head = new GeneralizedNode();//创建头结点
	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 == ')')//广义表结束
		{
			str++;//返回之前需要给str++指向下一个
			return head;
		}
		else//空格或者逗号
		{
			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不是最后一个值
			if (cur->_next)
			{
				cout << ",";
			}
		}
		else if (cur->_type == SUB)
		{
			_Print(cur->_subLink);
			if (cur->_next)
			{
				cout << ",";
			}
		}
		cur = cur->_next;
	}
	//输出每个表最后一个(
	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大于当前广义表的最大深度，则更新广义表的深度
			if (newDepth +1 > depth)
			{
				depth = newDepth + 1;
			}
		}
		cur = cur->_next;
	}
	return depth;
}

测试代码

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

测试结果

以上就是实现广义表的递归的具体操作，代码应该是足够清楚的，而且我也相信有相当的一些例子可能是我们日常工作可能会见得到的。通过这篇文章，希望你能收获更多。