C++数据结构广义表-创新互联

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

#include

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<

}

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;

}

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。