实现广义表

实现广义表，我们运用一个三维表来存储广义表节点的相关信息，然后运用链表的形式把广义表中的每个节点连起来，代码如下：

让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：国际域名空间、网络空间、营销软件、网站建设、镇平网站维护、网站推广。

enum Type

{

HEAD,

VALUE,

SUB,

};

struct GeneralizedNode

{

Type _type;

GeneralizedNode *_next;

union

{

char _value;

GeneralizedNode *_sublink;

};

GeneralizedNode(Type type = HEAD, char value = 0)

:_type(type)

, _next(NULL)

{

if (_type == VALUE)

{

_value = value;

}

else if (_type == SUB)

{

_sublink = NULL;

}

}

};

class Generalized

{

protected:

GeneralizedNode *_head;

public:

Generalized()

:_head(new GeneralizedNode(HEAD))

{}

Generalized(const char *str)

:_head(NULL)

{

_head = _createlized(str);

}

bool _isvalue(char ch)

{

if ((ch >= '0'&&ch <= '9') || (ch >= 'a'&&ch <= 'z') || (ch >= 'A'&&ch <= 'Z'))

return true;

else  

return false;

}

GeneralizedNode *_createlized(const char *&str)

{

assert(str && *str == '(');

++str;

GeneralizedNode *head = new GeneralizedNode(HEAD);

GeneralizedNode *cur = head;

while (*str)

{

if (_isvalue(*str))

{

cur->_next = new GeneralizedNode(VALUE, *str);

cur = cur->_next;

str++;

}

else if (*str == '(')

{

cur->_next = new GeneralizedNode(SUB);

cur = cur->_next;

cur->_sublink = _createlized(str);

}

else if (*str == ')')

{

str++;

return head;

}

else

{

str++;

}

}

//assert(false);

return head;

}

void print()

{

_print(_head);

}

size_t size()

{

GeneralizedNode *cur = _head;

static int count = 0;

while (cur)

{

if (cur->_type == VALUE)

{

count++;

}

else if (cur->_type == SUB)

{

_head = cur->_sublink;

size();

}

cur = cur->_next;

}

return count;

}

size_t Depth()

{

size_t depth = _Depth(_head);

return depth;

}

~Generalized()

{

_D(_head);

}

Generalized (const Generalized &g)

{

_head = _copy(g._head);

}

protected:

GeneralizedNode *_copy(GeneralizedNode *head)

{

GeneralizedNode *cur = head;

GeneralizedNode *newhead = new GeneralizedNode(HEAD);

cur = cur->_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;

}

size_t _Depth(GeneralizedNode *head)

{

size_t depth = 1;

GeneralizedNode *cur = head;

cur = cur->_next;

size_t sdepth = depth;

while (cur)

{

if (cur->_type == SUB)

{

int sdepth = _Depth(cur->_sublink);

if (sdepth + 1 > depth)

depth = sdepth+1;

}

cur = cur->_next;

}

return depth;

}

void _D(GeneralizedNode *head)

{

GeneralizedNode *cur = head;

while (cur)

{

GeneralizedNode *del = cur;

cur = cur->_next;

if (del->_type == SUB)

{

_D(del->_sublink);

}

delete del;

}

}

void _print(GeneralizedNode *head)

{

GeneralizedNode *cur = head;

while (cur)

{

if (cur->_type == VALUE)

{

cout << cur->_value;

if (cur->_next)

cout << ",";

}

else if (cur->_type == HEAD)

{

cout << "(";

}

else if (cur->_type == SUB)

{

_print(cur->_sublink);

if (cur->_next)

cout << ",";

}

else if ((cur->_type == SUB) && (cur->_next))

{

cout << ",";

}

cur = cur->_next;

}

cout << ")";

}

};

void Test()

{

Generalized g("(a,b,(c,d,(c,d)))");

/*Generalized g1;

g1 = g;

g1.print();*/

cout << g.Depth();

}

int main()

{

Test();

getchar();

return 0;

}