最近学习了广义表，我们知道广义表也是一种线性表，而顾名思义广义表就是不止一个表，下面来举个栗子：
成都创新互联公司是一家集网站建设,确山企业网站建设,确山品牌网站建设,网站定制,确山网站建设报价,网络营销,网络优化,
确山网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。
A=( )
B=（1 , 2，3）
C=(1 ,2 ,3, ( a , b ,c) )
D=(1, 2, 3, (a,( b,c),d),4)
以上A,B,C,D都是广义表，只不过深度不一样，也就是括号的对数不一样，A是个特殊的广义表，即空表。B里面有三个元素，C里面有6个元素，包括一个子表（a，b，c），C也同理，只不过多了一层子表。由此可总结为一句话：表里有表
这样看可能不太直观，下面以广义表C为例来看一下它的结构图：
（图画得有点丑，不要吐槽我）
每当遇到一个前括号，就要创建一个子表，直到遇见收括号。
那么如何创建一个广义表呢，在创建节点结构体的时候，我们要考虑每个节点的类型，有可能是头结
点，也有可能是子表节点，也有可能是普通的值节点，所以在构造节点的时候就要定义一个三元体，由
于是表里有表，我们可以用递归的方法来解决广义表的问题，每个子表都可以递归为一个子问题，就可
以很轻松的解决掉这个问题了。
下面是具体实现的代码：
先构造一个三元结构体：
enum Type
{
HEAD,
VALUE,
SUB,
};
template
struct GeneralizedNode
{
Type _type;
GeneralizedNode* _next;
union
{
char _value;
GeneralizedNode* _sublink; //子表的头结点
};
public:
GeneralizedNode(Type type = HEAD,char value = '\0')
:_type(type)
,_next(NULL)
{
if (type == VALUE)
{
_value = value;
}
else if (type == SUB)
{
_sublink = NULL;
}
}
};下面来构造一个广义表类
template
class GeneralizedList
{
public:
GeneralizedList()
:_head(new GeneralizedNode(HEAD))
{}
GeneralizedList(const char* str)
{
_head=_CreateList(str);
}
GeneralizedList(const GeneralizedList& g) //拷贝构造
{
_head = Copy(g._head;)
}
size_t Size()
{
return size(_head);
}
size_t depth()
{
return Depth(_head);
}
void print()
{
Print(_head);
}
protected:
GeneralizedNode* _CreateList(const char*& str)
{
assert(str && *str == '(');
++str;
GeneralizedNode* Head = new GeneralizedNode(HEAD,NULL);
GeneralizedNode* cur = Head;
while (*str)
{
if (_IsValue(*str))
{
cur->_next = new GeneralizedNode(VALUE,*str);
cur = cur->_next;
str++;
}
else if (*str == '(')
{
GeneralizedNode* newNode= new GeneralizedNode(SUB); //将一个子表结点加入到链表中
cur->_next = newNode;
cur = cur->_next;
cur->_sublink = _CreateList(str);
str++;//递归创建一个子表结点
}
else if (*str == ')') //表示一个表已经结束
{
str++;
return Head;
}
else
{
str++; //不需要处理的情况
}
}
assert(false);
return Head;
}
size_t Depth(GeneralizedNode* head)
{
GeneralizedNode* cur = head;
size_t depth = 1;
while (cur)
{
if (cur->_type == SUB)
{
size_t subdepth = Depth(cur->_sublink);
if (subdepth+1 > depth)
{
depth=subdepth;//保存较大的深度
}
}
cur = cur->_next;
}
return depth;
}
size_t size(GeneralizedNode* head)
{
GeneralizedNode* cur = head;
size_t count = 0;
while (cur)
{
if (cur->_type != SUB)
{
count++;
}
else
{
count += size(cur->_sublink);
}
cur = cur->_next;
}
return count;
}
void 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 if (cur->_type == SUB)
{
Print(cur->_sublink);
if (cur->_next != NULL)
{
cout << ',';
}
}
cur = cur->_next;
}
cout << ')';
}
bool _IsValue(char ch) //检查是否为合法值
{
if ((ch >= '0'&&ch<='9') || (ch>='a'&&ch<='z') || (ch>='A'&&ch <= 'Z'))
{
return true;
}
return false;
}
protected:
GeneralizedNode* _head;
};
下面给出测试代码：
#include"Generalized.h"
void Test()
{
char* ch = "(a,b,c,(1,2),c)";
GeneralizedList gl1(ch);
gl1.print();
cout << endl;
cout << "广义表深度为：" << gl1.depth() << endl;
cout << "广义表大小为：" << gl1.Size() << endl;
}
int main()
{
Test();
getchar();
return 0;
}运行结果：
以上就是C++实现广义表的方法啦，里面也许还存在着一些问题，希望大家能够指正出来，共同促进学习。
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
网站栏目：c++数据结构之广义表-创新互联
浏览地址：
http://bjjierui.cn/article/dcjecg.html
