广义表(Lists，又称列表)是一种非线性的数据结构，是线性表的一种推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。
让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：
域名注册、
虚拟主机、营销软件、网站建设、
闽侯网站维护、网站推广。
思想：广义表就类似下图的结构，他的大体（下图第一行）相当于一个带头结点的链表，
代码思想，首先要有一个头结点为HEAD类型，每一个广义表有且只有一个HEAD，而后每个节点如果有分支则把它定义为SUB类型，SUB便是它分支的一个新头他有一个sublink指针指向他的第一个元素，如果没有则是VALUE类型。
#pragma once
#include
#include
using namespace std;
enum Type
{
HEAD,
VALUE,
SUB
};
struct generalizelistNode
{
generalizelistNode * _next;
Type _type;
union
{
char _value;
generalizelistNode *sublink;
};
generalizelistNode(Type type=HEAD,char value=0)
:_type(type),
_value(value),
_next(NULL)
{
}
};
class Generalizelist
{
protected:
bool isvalue(char c)
{
if (c >= 'a'&&c<='z' || c>='A'&&c <= 'Z' || c>='0'&&c <= '9')
{
return true;
}
else
{
return false;
}
}
public:
Generalizelist(char *&str)
{
_head = generallist(str);
}
~Generalizelist()
{
Empty(_head);
}
void Print()
{
_Print(_head);
}
Generalizelist& operator=(Generalizelist g)
{
swap(_head, g._head);
}
Generalizelist(Generalizelist &g)
{
_head = copy(g._head);
}
int Size()
{
return _Size(_head);
}
int Depth()
{
return _Depth(_head);
}
protected:
generalizelistNode* generallist(char *&str)
{
assert(*str == '(');
generalizelistNode *head = new generalizelistNode(HEAD);
generalizelistNode *cur = head;
str++;
while (*str)
{
if (isvalue(*str))
{
generalizelistNode *Node = new generalizelistNode(VALUE,*str);
cur->_next = Node;
cur = Node;
str++;
}
else if (*str == '(')
{
generalizelistNode *sub = new generalizelistNode(SUB);
cur->_next = sub;
cur = sub;
sub->sublink = generallist(str);
}
else if (*str==')')
{
++str;
return head;
}
else
{
str++;
}
}
}
void _Print(generalizelistNode *head)
{
generalizelistNode *cur = head;
while (cur)
{
if (cur->_type == HEAD)
{
cout << '(';
}
else if (cur->_type == VALUE)
{
cout << cur->_value;
if (cur->_next)
{
cout << ",";
}
}
else
{
_Print(cur->sublink);
}
cur = cur->_next;
}
cout << ")";
}
generalizelistNode * copy(generalizelistNode *&_cur)
{
generalizelistNode *cur = _cur;
generalizelistNode *newhead = new generalizelistNode(HEAD);
generalizelistNode *tmp = newhead;
cur = cur->_next;
while (cur)
{
if (cur->_type == VALUE)
{
generalizelistNode *node = new generalizelistNode(VALUE, cur->_value);
tmp->_next = node;
tmp = node;
cur = cur->_next;
}
else
{
generalizelistNode *node = new generalizelistNode(SUB);
tmp->_next = node;
tmp = node;
tmp->sublink = copy(cur->sublink);
cur = cur->_next;
}
}
return newhead;
}
void Empty(generalizelistNode *&head)
{
generalizelistNode *tmp = head;
head = head->_next;
delete tmp;
while (head)
{
if (head->_type == VALUE)
{
generalizelistNode *tmp = head;
head = head->_next;
delete tmp;
}
else if (head->_type == SUB)
{
generalizelistNode *tmp = head;
Empty(tmp->sublink);
head = head->_next;
}
}
}
int _Size(generalizelistNode *&cur)
{
int count = 0;
generalizelistNode *tmp = cur;
while (tmp)
{
if (tmp->_type == VALUE)
{
count++;
tmp = tmp->_next;
}
else if (tmp->_type == SUB)
{
count += _Size(tmp->sublink);
tmp = tmp->_next;
}
else
{
tmp = tmp->_next;
}
}
return count;
}
int _Depth(generalizelistNode *&cur)
{
generalizelistNode *tmp = cur;
int depth = 1;
while (tmp)
{
int sub_depth=1;
if (tmp->_type == SUB)
{
sub_depth = _Depth(tmp->sublink);
tmp = tmp->_next;
if (sub_depth + 1 > depth)
{
depth += sub_depth;
}
}
else
{
tmp = tmp->_next;
}
}
return depth;
}
private:
generalizelistNode *_head;
};
void Test()
{
char *str1 = "(a,b,(c,d),e,f)";
Generalizelist T1(str1);
T1.Print();
Generalizelist T2(T1);
cout <创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
名称栏目：数据结构--广义表-创新互联
转载注明：http://bzwzjz.com/article/csiojg.html
