[p202-5]이중 연결 원형 리스트 C++ 자료구조론

헤더 노드를 가진 이중 연결 원형 리스트에 대한 C++ 템플릿 클래스를 구현하라.
newDblListTemplate.cpp



#include<iostream>
using std::cout;
using std::endl;

template<class T>
class DblList;

template<class T>
class DblListNode {
friend class DblList<T>;
public:
DblListNode(T element=NULL, DblListNode<T> *lNode=NULL, DblListNode<T> *rNode=NULL)
: data(element), left(lNode), right(rNode)
{}
void setData(const T& temp)
{
data = temp;
}
private:
T data;
DblListNode *left, *right;
};

template<class T>
class DblList {
public:
DblList(); // 생성자
DblList(const DblList &temp); // 복사생성자
~DblList(); // 소멸자
void printList(); // 출력
void Insert(DblListNode<T> *p, DblListNode<T> *x=NULL); // 삽입
void Delete(DblListNode<T> *x); // 삭제

class iterator { // 양방향 반복자
public:
iterator(DblListNode<T> *node=0) : current(node)
{}
iterator operator++(int) // 오른쪽으로 이동
{
iterator temp = *this;
current = current->right;
return temp;
}
iterator operator--(int) // 왼쪽으로 이동
{
iterator temp = *this;
current = current->left;
return temp;
}
bool operator!=(const iterator& temp) const
{
return current!=temp.current;
}
DblListNode<T>* operator&() const // 소멸자에서 사용
{
return current;
}
DblListNode<T>* operator->() const // data 접근에 사용
{
return current;
}
private:
DblListNode<T> *current;
}; // 양방향 반복자 끝

iterator begin() const // first의 right노드의 iterator 리턴
{
return iterator(first->right);
}
iterator end() const // first노드의 iterator 리턴
{
return iterator(first);
}

private:
DblListNode<T> *first; // 헤더 노드를 가리킴
};

template<class T>
DblList<T>::DblList()
{
first = new DblListNode<T>;
first->left = first;
first->right = first;
}

template<class T>
DblList<T>::DblList(const DblList<T> &temp)
{
first = new DblListNode<T>;
first->left = first;
first->right = first;

DblList::iterator copy(temp.begin());

for(; copy != temp.end() ; copy++)
{ // 헤더의 다음부터 헤더 전까지 data를 복사
// Insert 함수를 이용하여 링크
Insert(new DblListNode<T>(copy->data));
}
}

template<class T>
DblList<T>::~DblList()
{
if(begin() != end()) // 노드가 2개 이상인 경우
{
DblList::iterator it;
DblList::iterator next(begin());
while(next != end())
{
it = next;
next++;
delete &it;
}
}

delete first;
}

template<class T>
void DblList<T>::printList()
{
DblList::iterator temp(begin());
cout<<"RIGHT: header";
for(; temp != end() ; temp++)
cout<<" -> "<<temp->data;
cout<<endl;

temp--;
cout<<"LEFT : ";
for(; temp != end() ; temp--)
cout<<temp->data<<" -> ";
cout<<"header"<<endl;
cout<<endl;
}

template<class T>
void DblList<T>::Insert(DblListNode<T> *p, DblListNode<T> *x)
{
if(x==NULL) // x가 주어지지 않으면,
{ // 끝(헤더의 왼쪽)에 p를 삽입
p->left = first->left;
p->right = first;
first->left->right = p;
first->left = p;
}
else // x의 오른쪽에 p를 삽입
{
p->left = x;
p->right = x->right;
x->right->left = p;
x->right = p;
}
}

template<class T>
void DblList<T>::Delete(DblListNode<T> *x)
{
if(x==first)
throw "Deletion of header node not permitted";
else {
x->left->right = x->right;
x->right->left = x->left;
delete x;
}
}

void main(void)
{
// int형 테스트
DblList<int> intTest;

DblListNode<int> *it1 = new DblListNode<int>(1);
DblListNode<int> *it2 = new DblListNode<int>(2);
DblListNode<int> *it3 = new DblListNode<int>(3);
DblListNode<int> *it4 = new DblListNode<int>(4);

intTest.Insert(it1);
intTest.Insert(it2);
intTest.Insert(it3);
intTest.Insert(it4, it1);
intTest.printList();

intTest.Delete(it2);
intTest.printList();

// char형 테스트
DblList<char> charTest;

DblListNode<char> *ct1 = new DblListNode<char>('a');
DblListNode<char> *ct2 = new DblListNode<char>('b');
DblListNode<char> *ct3 = new DblListNode<char>('c');
DblListNode<char> *ct4 = new DblListNode<char>('d');

charTest.Insert(ct1);
charTest.Insert(ct2);
charTest.Insert(ct3);
charTest.Insert(ct4, ct2);
charTest.printList();

charTest.Delete(ct2);
charTest.printList();

// 복사생성자 테스트
DblList<char> copyConTest(charTest);
copyConTest.printList();
}


iterator로 많은 고민을...ㅠㅠ 제대로 한건진 모르겠다... 아졸려


덧글

댓글 입력 영역