GeneralList-广义表
广义表是非线性的结构，是线性表的一种扩展，是有n个元素组成有限序列。
广义表的定义是递归的，因为在表的描述中又得到了表，允许表中有表。
<1> A = ()
<2> B = (a,b)
<3> C = (a,b,(c,d))
<4> D = (a,b,(c,d),(e,(f),h))
<5> E = (((),()))
#define _CRT_SECURE_NO_WARNINGS 1
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <assert.h>
using namespace std;
enum Type
{
HEAD,
VALUE,
SUB
};
struct GeneralizedNode
{
Type _type;//类型
GeneralizedNode* _next;//指向同层下一个结点
union
{
//int _value;
char _value;
GeneralizedNode* _subLink;//指向子表的指针
};
GeneralizedNode(Type type = VALUE, const int value = 0)
:_type(type)
,_next(NULL)
,_value(value)
{}
};
class Generalized
{
public:
Generalized()
:_head(NULL)
{}
Generalized(const char* str)
:_head(NULL)
{
_head = _CreateList(str);
}
void Print() const
{
_Print(_head);
cout<<endl;
}
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<<cur->_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<<g.Size()<<endl;
cout<<g.Depth()<<endl;
cout<<"============"<<endl;
char* str2 = "(a,b,(c,d),(e,(f),h))";
Generalized g2(str2);
g2.Print();
cout<<g2.Size()<<endl;
cout<<g2.Depth()<<endl;
cout<<"============"<<endl;
Generalized g3(g2);
g3.Print();
cout<<g3.Size()<<endl;
cout<<g3.Depth()<<endl;
cout<<"============"<<endl;
Generalized g4;
g4 = g2;
g4.Print();
cout<<g4.Size()<<endl;
cout<<g4.Depth()<<endl;
}
int main()
{
test_G_chuangjian();
return 0;
}