广义表：非线性结构，是线性表的一种扩展，是有n个元素组成有限序列，是递归的，因为在表的描述中又得到了表，允许表中有表。
让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：域名与空间、雅安服务器托管、营销软件、网站建设、岑巩网站维护、网站推广。
#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()<运行结果如下：
本文名称：广义表的实现
网页路径：http://cdxtjz.cn/article/ijpjjp.html
