广义表的递归实现-创新互联
广义表是一种数据结构，是线性表的推广。也有人称之为列表（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;
}另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
网站名称：广义表的递归实现-创新互联
文章位置：http://shouzuofang.com/article/phedj.html