C++/Fundamentals of Data Structures in C++(Horowitz)

C++ Fundamentals of Data Structures(C++ 자료구조론) 4.11 일반화된 연결리스트(Generalized Lists)

꾸준함. 2017. 8. 25. 11:00

/*

일반화된 리스트 Generalized Lists

*/

#include <iostream>

using namespace std;

 

template <typename T>

class GenList;

 

enum GenListNodeType { HEAD, DATA, LIST }; //타입: dummy, 데이터, 리스트

 

template <typename T>

class GenListNode

{

public:

        GenListNodeType type; //타입

        T data;

        GenList<T> *list;

        GenListNode<T> *next;

        GenListNode<T>()

        {

               type = HEAD;

               data = 0;

               list = NULL;

               next = NULL;

        }

        ~GenListNode<T>()

        {

               if (list)

                       delete list;

        }

};

 

template <typename T>

class GenList

{

private:

        GenListNode<T> *first;

public:

        GenList()

        {

               first = new GenListNode<T>; //더미노드 삽입

               first->next = NULL;

        }

        ~GenList()

        {

               GenListNode<T> *p;

               while (first->data>0) //유효데이터일 때

               {

                       p = first;

                       first = first->next;

                       delete p;

               }

        }

        void Insert(const T &item)

        {

               GenListNode<T> *temp = new GenListNode<T>;

               temp->data = item;

               temp->type = DATA;

               temp->next = first->next;

               first->next = temp; //더미노드 다음에 삽입

        }

        void Insert(const GenList<T> &gl) //리스트를 추가하는 경우

        {

               GenList<T> *temp1 = new GenList<T>(gl);

               GenListNode<T> *item = new GenListNode<T>;

               item->type = LIST;

               item->list = temp1;

               item->next = first->next;

               first->next = item;

        }

        int Depth() const

        {

               int depth = 0;

               GenListNode<T> *p = first->next;

               while (p)

               {

                       if (p->type == LIST)

                       {

                              int p_depth = p->list->Depth(); //리스트가 두개 이상인 경우를 위해

                              if (p_depth > depth)

                                      depth = p_depth;

                       }

                       p = p->next;

               }

               return ++depth;

        }

        void PrintList() const

        {

               GenListNode<T> *p = first->next;

               while (p)

               {

                       if (p->type == DATA)

                       {

                              cout << p->data;

                              if (p->next)

                                      cout << "->";

                       }

                       if (p->type == LIST) //리스트가 둘 이상일 경우 재귀식으로 출력한다

                       {

                              p->list->PrintList();

                              if (p->next)

                                      cout << "->";

                       }

                       p = p->next;

               }

        }

};

 

int main(void)

{

        GenList<int> intG;

        for (int i = 0; i < 5; i++)

               intG.Insert(i + 1);

        intG.PrintList();

        cout << endl;

 

        GenList<int> intG2;

        for (int i = 5; i < 10; i++)

               intG2.Insert(i + 1);

        intG.Insert(intG2);

        intG.PrintList();

        cout << endl;

        cout << "깊이: " << intG.Depth() << endl;

        return 0;

}



[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서, https://github.com/WolfogreRecycleBin/ObjectOrientedGeneralizedList/tree/master/GenList


*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.

*Generalized Lists 페이지는 이해가 부족해서 위 링크에 있는 코드를 그대로 작성했습니다.

*다음에 시간이 나면 책에 있는 코드를 기반으로 재작성해보겠습니다!



반응형