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 <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;

}