}
size_t Size() const
{
return _Size(_head);
}
size_t Depth() const
{
return _Depth(_head);
}
//===========新加的
Generalized(const Generalized& g);
Generalized& operator=(Generalized g); // 现代写法
~Generalized();
protected:
GeneralizedNode* _CreateList(const char*& str);
void _Print(GeneralizedNode* head) const;
bool _IsValue(char ch);
size_t _Size(GeneralizedNode* head) const;
size_t _Depth(GeneralizedNode* head) const;
GeneralizedNode* _Copy(const GeneralizedNode* head);
void _Destory(GeneralizedNode* head);
protected:
GeneralizedNode* _head;
};
bool Generalized:: _IsValue(char ch)
{
if ((ch >= '0' && ch <= '9')
|| (ch >= 'a' && ch <= 'z')
|| (ch >= 'A' && ch <= 'Z'))
{
return true;
}
else
{
return false;
}
}
GeneralizedNode* Generalized::_CreateList(const char*& str)//注意&
{
assert(str);
assert(*str == '(');
// D = (a,b,(c,d),(e,(f),h))
GeneralizedNode* head = new GeneralizedNode(HEAD);
GeneralizedNode* cur = head;
++str;
while (*str != '\0')
{
if (*str == '(')// 有子层
{
cur->_next = new GeneralizedNode(SUB);
cur = cur->_next;
cur->_subLink = _CreateList(str);//下一层
}
else if(_IsValue(*str))
{
cur->_next = new GeneralizedNode(VALUE, *str);
cur = cur->_next;
++str;
}
else if (*str == ')')
{
++str;// **********更新上一层的str
break;
}
else // 其他情况 *str为 逗号 空格 制表符 等
{
++str;
}
}
return head;
}
void Generalized::_Print(GeneralizedNode* head)const
{
assert(head && head->_type == HEAD);
GeneralizedNode* cur = head->_next;
cout<<"(";
while(cur)
{
if (cur->_type == VALUE)
{
cout<_value;
cur = cur->_next;
if (cur != NULL)
{
cout<<",";
}
}
else if (cur->_type == SUB)
{
_Print(cur->_subLink);
cur = cur->_next;
if (cur != NULL)
{
cout<<",";
}
}
}
cout<<")";
}
size_t Generalized::_Size(GeneralizedNode* head) const
{
assert(head && head->_type == HEAD);
GeneralizedNode* cur = head->_next;
size_t count = 0;
while(cur)
{
if (cur->_type == VALUE)
{
count++;
}
else if(cur->_type == SUB)
{
count += _Size(cur->_subLink);
}
cur = cur->_next;
}
return count;
}
// 有问题
//size_t Generalized::_Depth(GeneralizedNode* head) const
//{
//assert(head && head->_type == HEAD);
//GeneralizedNode* cur = head->_next;
//size_t depth = 1;
//while(cur)
//{
//if (cur->_type == SUB)
//{
//depth += _Depth(cur->_subLink);
//}
//
//cur = cur->_next;
//}
//
//return depth;
//}
size_t Generalized::_Depth(GeneralizedNode* head) const
{
assert(head && head->_type == HEAD);
GeneralizedNode* cur = head->_next;
size_t depth = 1;
while (cur)
{
if (cur->_type == SUB)
{
size_t SubDepth = _Depth(cur->_subLink);
if (depth < 1 + SubDepth) // 找最大的 depth 注意 不要用 depth = depth + SubDepth
{
depth = 1 + SubDepth;
}
}
cur = cur->_next;
}
return depth;
}
Generalized:: Generalized(const Generalized& g)
{
_head = _Copy(g._head);
}
GeneralizedNode* Generalized::_Copy(const GeneralizedNode* head)
{
assert(head && head->_type == HEAD);
const GeneralizedNode* cur = head->_next;
GeneralizedNode* retHead = new GeneralizedNode(HEAD);
GeneralizedNode* newNode = retHead;
while (cur)
{
if (cur->_type == VALUE)
{
newNode->_next = new GeneralizedNode(VALUE, cur->_value);
newNode = newNode->_next;
}
else if (cur->_type == SUB)
{
newNode->_next = new GeneralizedNode(SUB);
newNode = newNode->_next;
newNode->_subLink = _Copy(cur->_subLink);
}
cur = cur->_next;
}
return retHead;
}
Generalized& Generalized::operator=(Generalized g) // 现代写法
{
swap(_head, g._head);
return *this;
}
Generalized::~Generalized()
{
_Destroy(_head);
}
void Generalized::_Destory(GeneralizedNode* head)
{
GeneralizedNode* cur = head;
while (cur)
{
GeneralizedNode* del = cur;
cur = cur->_next;
if (del->_type == SUB)
{
_Destory(del->_subLink);
}
delete del;
del = NULL;
}
}
void test_G_chuangjian()
{
char* str = "(a,b,(c,d))";
Generalized g(str);
g.Print();
cout<cout< cout<<"============"< char* str2 = "(a,b,(c,d),(e,(f),h))";
Generalized g2(str2);
g2.Print();
cout<cout< cout<<"============"<Generalized g3(g2);
g3.Print();
cout<cout< cout<<"============"<Generalized g4;
g4 = g2;
g4.Print();
cout<cout<}
int main()
{
test_G_chuangjian();
return 0;
}
本文题目：C++数据结构广义表
文章链接：http://cdkjz.cn/article/pisooe.html
