实现广义表，我们运用一个三维表来存储广义表节点的相关信息，然后运用链表的形式把广义表中的每个节点连起来，代码如下：
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;
}
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
