GeneralList-廣義表

站在用戶的角度思考問題，與客戶深入溝通，找到陽原網(wǎng)站設(shè)計(jì)與陽原網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶體驗(yàn)好的作品，建站類型包括：成都做網(wǎng)站、網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、域名與空間、網(wǎng)頁空間、企業(yè)郵箱。業(yè)務(wù)覆蓋陽原地區(qū)。

廣義表是非線性的結(jié)構(gòu)，是線性表的一種擴(kuò)展，是有n個(gè)元素組成有限序列。

廣義表的定義是遞歸的，因?yàn)樵诒淼拿枋鲋杏值玫搅吮恚试S表中有表。

<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;//指向同層下一個(gè)結(jié)點(diǎn)

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;

}