广义表：非线性结构，是线性表的一种扩展，是有n个元素组成有限序列，是递归的，因为在表的描述中又得到了表，允许表中有表。
创新互联专注于企业
网络营销推广、网站重做改版、阎良网站定制设计、自适应品牌网站建设、
H5建站、
商城网站制作、集团公司官网建设、
成都外贸网站建设、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为阎良等各大城市提供网站开发制作服务。
#include
#include
using namespace std;
enum Type //枚举节点的类型
{
HEAD, //头结点
VALUE, //有数据成员的节点
SUB, //有子链的节点
};
template
struct GeneralizedNode //定义节点
{
Type _type;
GeneralizedNode* _next;
union //运用联合体使得该数据成员只含有一种节点
{
T _value;
GeneralizedNode* _sublink;
};
GeneralizedNode(Type type = HEAD, T value = 0) //构造节点
:_type(type)
,_next(NULL)
{
if (_type == VALUE)
{
_value = value;
}
if (_type == SUB)
{
_sublink = NULL;
}
}
};
template
class Generalized
{
public:
Generalized()
:_head(NULL)
{}
Generalized(const char* str) //构造函数
:_head(NULL)
{
_head = _Creatlize(str);
}
Generalized(const Generalized& g) //拷贝构造
{
_head = _Copy(g._head);
}
Generalized& operator=(const Generalized& g) //传统写法
{
if (this != &g)
{
GeneralizedNode *temp=_Copy(g._head);
_Destroy(_head);
_head = temp;
}
return *this;
}
Generalized& operator=(Generalized g) //现代写法
{
swap(_head, g._head);
return *this;
}
size_t Size() //求表中的结点个数
{
return _size(_head);
}
size_t Depth() //求深度
{
return _Depth(_head);
}
void print() //打印节点
{
_print(_head);
}
protected:
bool ISValue(char m)
{
if (m >= 'a'&&m <= 'z' || m >= 'A'&&m <= 'Z' || m >= '0'&&m <= '9')
{
return true;
}
else
{
return false;
}
}
void _print(GeneralizedNode* head) //打印节点 运用递归方式进行
{
assert(head);
GeneralizedNode *cur = head;
while (cur)
{
if (cur->_type == HEAD)
{
cout << "(" << "";
//cur = cur->_next;
}
else if (cur->_type == VALUE) //如果是VALUE，则打印该节点
{
cout << cur->_value;
if (cur->_next == NULL)
{
cout << ")";
}
else
{
cout << ",";
}
}
else if (cur->_type == SUB) //如果是SUB类型，则递归调用下一层
{
_print(cur->_sublink);
if (cur->_next == NULL)
{
cout << ")";
}
else
{
cout << ",";
}
}
else
{
cout << ")";
}
cur = cur->_next;
}
}
size_t _size(GeneralizedNode* p)
{
GeneralizedNode *cur = p;
int count = 0;
while (cur)
{
if (cur->_type == VALUE) //如果是VALUE，则count++
{
++count;
}
else if (cur->_type == SUB) //如果是SUB，则调用下一层
{
count += _size(cur->_sublink);
}
cur = cur->_next;
}
return count;
}
int _Depth(GeneralizedNode* head)
{
GeneralizedNode* cur = head;
int depth = 1;
while (cur)
{
if (cur->_type == SUB)
{
int subdepth = _Depth(cur->_sublink);
if (subdepth + 1 > depth)
{
depth = subdepth + 1;
}
}
cur = cur->_next;
}
return depth;
}
GeneralizedNode* _Creatlize(const char*& str) //构造广义表
{
assert(*str == '(');
while (*str)
{
if (*str == '(')
{
GeneralizedNode* _head = new GeneralizedNode(HEAD);
GeneralizedNode* cur = _head;
++str;
while (*str)
{
if (ISValue(*str))
{
GeneralizedNode *temp = new GeneralizedNode(VALUE);
temp->_value = *str;
cur->_next = temp;
cur = cur->_next;
++str;
}
else if (*str == '(')
{
GeneralizedNode* sub = new GeneralizedNode(SUB);
sub->_sublink = _Creatlize(str);
cur->_next = sub;
cur = cur->_next;
}
else if (*str == ')')
{
++str;
return _head;
}
else
{
++str;
}
}
return _head;
}
}
return _head;
}
GeneralizedNode* _Copy(GeneralizedNode* head) //拷贝
{
GeneralizedNode* newhead = new GeneralizedNode(HEAD);
GeneralizedNode* cur = head->_next;
GeneralizedNode* newcur = newhead;
while (cur)
{
if (cur->_type == VALUE)
{
newcur->_next = new GeneralizedNode(VALUE, cur->_value);
newcur = newcur->_next;
}
else if (cur->_type == SUB)
{
newcur->_next = new GeneralizedNode(SUB);
newcur = newcur->_next;
newcur->_sublink = _Copy(cur->_sublink);
}
cur = cur->_next;
}
return newhead;
}
protected:
GeneralizedNode* _head;
};
测试代码如下：
void test4()
{
Generalized a("(a,b)");
Generalized b("(a,(c,(f),d),b)");
Generalized c(a);
Generalized d(b);
c.print();
cout<< endl;
d.print();
cout << endl;
cout << d.Depth()<运行结果如下：
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
名称栏目：广义表的实现-创新互联
转载来源：http://bzwzjz.com/article/dodicg.html
