/*
일반화된 리스트 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 페이지는 이해가 부족해서 위 링크에 있는 코드를 그대로 작성했습니다.
*다음에 시간이 나면 책에 있는 코드를 기반으로 재작성해보겠습니다!