GeneralList-廣義表

我們提供的服務(wù)有：做網(wǎng)站、成都網(wǎng)站建設(shè)、微信公眾號開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、西充ssl等。為超過千家企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的西充網(wǎng)站制作公司

廣義表是非線性的結(jié)構(gòu)，是線性表的一種擴展，是有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;//指向同層下一個結(jié)點

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);   //  現(xiàn)代寫法

  ~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)   //  現(xiàn)代寫法

{

  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;

}

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

網(wǎng)頁名稱：C++數(shù)據(jù)結(jié)構(gòu)廣義表-創(chuàng)新互聯(lián)
本文URL：http://weahome.cn/article/didhdh.html