C++ Fundamentals of Data Structures(C++ 자료구조론) 4.4 CircularList(원형리스트)

/*

기존에 풀었던 문제를 원형리스트로 다시 푸는 문제였기 때문에

간단하게 원형리스트(CircularList) 예제를 작성했습니다

*/

#include <iostream>

using namespace std;

 

template <typename T> class CircularList;

 

template <typename T>

class ChainNode //기존에 정의한 ChainNode 클래스 그대로 사용함

{

private:

        T data;

        ChainNode<T> *link;

public:

        ChainNode(T element = 0, ChainNode *next = NULL) :data(element), link(next)

        {

        }

        /*

        T getData()

        {

               return data;

        }

        ChainNode *Link()

        {

               return link;

        }

        */

        friend CircularList<T>; //link

        template <typename T>

        friend ostream &operator<<(ostream &os, CircularList<T> &c);

};

 

template <typename T>

class CircularList

{

private:

        ChainNode<T> *first; //더미노드가 있기 때문에 굳이 last 추가안해도 된다

public:

        CircularList()

        {

               first = new ChainNode<T>; //더미노드

               first->link = first;

        }

        ~CircularList()

        {

               ChainNode<T> *del = first->link; //더미노드 다음부터 차례대로 삭제

               while (del != first)

               {

                       first->link = del->link;

                       delete del;

                       del = first->link;

               }

        }

        bool isEmpty()

        {

               return first->link == first; //비어있는지 확인

        }

        int Length()

        {

               int len = 0;

               ChainNode<T> *cur = first->link;

               while (cur != first) //처음으로 돌아오기 전까지 길이 더함

               {

                       len++;

                       cur = cur->link;

               }

               return len;

        }

        void Search(const T &item)

        {

               ChainNode<T> *cur = first->link;

               int idx = 1;

               while (1)

               {

                       if (cur->data == item || cur == first) //다시 처음으로 돌아오거나, 찾았을 때

                              break;

                       cur = cur->link;

                       idx += 1;

               }

               if (cur == first)

                       cout << "존재하지 않는 데이터입니다" << endl;

               else

                       cout << idx << "번 째 노드에 있는 데이터입니다" << endl;

        }

        void InsertFront(const T &item)

        {

               ChainNode<T> *newNode = new ChainNode<T>(item);

               newNode->link = first->link; //더미 노드 다음을 가르키는 곳을 추가한 노드가 가리키게 하고

               first->link = newNode; //더미노드 다음을 추가한 노드로

        }

        void InsertRear(const T &item)

        {

               ChainNode<T> *newNode = new ChainNode<T>(item);

               ChainNode<T> *cur = first->link;

               while (cur->link != first) //끝까지 간다

               {

                       cur = cur->link;

               }

               cur->link = newNode; //끝의 다음을 추가한 노드로

               newNode->link = first; //추가한 노드는 first를 가르키게 한다

        }

        void Delete(int idx)

        {

               ChainNode<T> *cur = first->link;

               if (idx < 1)

               {

                       cout << "1 이상의 숫자를 입력하셔야합니다" << endl;

               }

               else if(idx==1)

               {

                       first->link = cur->link; //first가 기존에 가리키던 노드보다 하나 더 앞에 있는 노드를 가리키게 한다

               }

               else

               {

                       int count = 1;

                       ChainNode<T> *del = first->link;

                       while (count < idx)

                       {

                              del = del->link;

                              count++;

                       }

                       cur = del->link;

                       del->link = cur->link; //마찬가지로 del이 그 다음 노드를 가리키도록 한다

               }

               delete cur;

        }

        template <typename T>

        friend ostream &operator<<(ostream &os, CircularList<T> &c);

};

 

template <typename T>

ostream &operator<<(ostream &os, CircularList<T> &c)

{

        ChainNode<T> *cur;

        for (cur = c.first->link; cur != c.first; cur = cur->link)

        {

               os << cur->data;

               if (cur->link != c.first)

                       os << "->";

               else

                       os << " ";

        }

        os << endl;

        return os;

}

 

int main(void)

{

        CircularList<int> intCList;

        int idx;

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

               intCList.InsertFront(i + 1);

        cout << "원형리스트 출력" << endl;

        cout << intCList << endl;

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

               intCList.InsertRear((i + 1) * 2);

        cout << "원형리스트 출력" << endl;

        cout << intCList << endl;

        cout << "몇번 째 노드를 삭제하시겠습니까?";

        cin >> idx;

        intCList.Delete(idx-1); //idx는 0부터 시작하므로 -1

        cout << "원형리스트 출력" << endl;

        cout << intCList << endl;

        return 0;

}

[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서

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