C++ Fundamentals of Data Structures(C++ 자료구조론) 4.3 연습문제

[Exercises 1]

/*

Write a C++ template function to output all elements of a chain by overloading the output operator<<.

<< 연산자를 오버로드해서 체인 안에 있는 모든 요소들을 출력하는 템플릿 함수를 작성한다.

Assume that the operator << has been overloaded for the data type T

<< 연산자가 T 데이터 타입에 대해 오버로드되어있다고 가정한다

*/

#include <iostream>

using namespace std;

 

template <typename T> class Chain;

 

template <typename T>

class 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 class Chain<T>;

        template <typename T>

        friend ostream &operator<<(ostream &os, Chain<T> &c); //출력

};

 

template <typename T>

class Chain

{

private:

        ChainNode<T> *first;

        ChainNode<T> *last;

public:

        Chain()

        {

               first = NULL;

        }

        ChainNode<T> *getFirst() //처음 노드 반환

        {

               return first;

        }

        ChainNode<T> *Insert(ChainNode<T> *x, T i) //노드 추가

        {

               if (first)

               {

                       ChainNode<T> *temp = new ChainNode<T>(i, x->link);

                       x->link = temp; //x가 temp를 가르키도록

                       return x->link; //위치를 반환해야 그 다음 위치에 값을 대입

               }

               else //기존 노드가 없을 경우

               {

                       first = new ChainNode<T>(i);

                       return first;

               }

        }

        int Length()

        {

               int len = 0;

               ChainNode *temp = first;

 

               while (temp != NULL)

               {

                       temp = temp->link;

                       len++;

               }

               return len;

        }

        void Delete(ChainNode<T> *x)

        {

               if (first == NULL)

               {

                       cout << "체인은 비어있다" << endl;

                       return;

               }

               if (x == first)

                       first = first->link; //다음 노드를 가리킨다

               else

               {

                       ChainNode<T> *temp = first;

                       while (temp->link != x)

                       {

                              temp = temp->link; //x 전 노드를 찾아간다

                       }

                       temp->link = x->link; //x 다음을 temp와 연결시켜 자연스럽게 x가 없어지도록 한다

               }

               delete x;

        }

        void InsertBack(const T &item)

        {

               if (first)

               {

                       last->link = new ChainNode<T>(item);

                       last = last->link;

                       last->link = NULL;

               }

               else

               {

                       first = last = new ChainNode<T>(item);

                       first->link = NULL;

               }

        }

        void Concatenate(Chain<T> &b) //합치다

        {

               if (first)

               {

                       last->link = b.first;

                       last = b.last;

               }

               else

               {

                       first = b.first;

                       last = b.last;

               }

        }

        void Reverse() //거꾸로

        {

               ChainNode<T> *current = first, *previous = NULL; //previous는 current 전 노드

 

               while (current)

               {

                       ChainNode<T> *r = previous; //previous의 위치를 기억해두었다가

                       previous = current;

                       current = current->link;

                       previous->link = r; //이전의 current가 이전의 previous를 가르키도록 한다

               }

               first = previous;

        }

        class ChainIterator

        {

        private:

               ChainNode<T> *current;

        public:

               ChainIterator(ChainNode<T> *startNode = NULL)

               {

                       current = startNode;

               }

               T getData()

               {

                       return current->data;

               }

               T &operator*() const

               {

                       return current->data;

               }

               T *operator->()

               {

                       return &current->data;

               }

               ChainIterator &operator++() //++c

               {

                       current = current->link;

                       return *this;

               }

               ChainIterator operator++(int) //c++

               {

                       ChainIterator old = *this;

                       current = current->link;

                       return old;

               }

               bool operator!=(const ChainIterator right) const

               {

                       return current != right.current;

               }

               bool operator==(const ChainIterator right) const

               {

                       return current = right.current;

               }

               template <typename T>

               friend ostream &operator<<(ostream &os, Chain<T> &c); //출력

        };

        ChainIterator begin()

        {

               return ChainIterator(first);

        }

        ChainIterator end()

        {

               return ChainIterator(0);

        }

        template <typename T>

        friend ostream &operator<<(ostream &os, Chain<T> &c); //출력

};

 

template <typename T>

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

{

        Chain<T>::ChainIterator i = c.begin();

        while (i != c.end())

        {

               os << i.getData() << "->";

               i++;

        }

        os << i.getData();

        os << endl;

        return os;

}

 

int main(void)

{

        Chain<int> intChain;

        ChainNode<int> *CN = intChain.getFirst();

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

               CN = intChain.Insert(CN, i + 1);

        cout << "체인 출력" << endl;

        cout << intChain << endl;

        return 0;

}

[Exercises 2]

/*

Write a C++ function to compute the minimum of all elements of a chain of integers

모든 요소 중에 최솟값을 찾는 함수를 작성한다

*/

#include <iostream>

using namespace std;

 

template <typename T> class Chain;

 

template <typename T>

class 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 class Chain<T>;

        template <typename T>

        friend ostream &operator<<(ostream &os, Chain<T> &c); //출력

};

 

template <typename T>

class Chain

{

private:

        ChainNode<T> *first;

        ChainNode<T> *last;

public:

        Chain()

        {

               first = NULL;

        }

        ChainNode<T> *getFirst() //처음 노드 반환

        {

               return first;

        }

        ChainNode<T> *Insert(ChainNode<T> *x, T i) //노드 추가

        {

               if (first)

               {

                       ChainNode<T> *temp = new ChainNode<T>(i, x->link);

                       x->link = temp; //x가 temp를 가르키도록

                       return x->link; //위치를 반환해야 그 다음 위치에 값을 대입

               }

               else //기존 노드가 없을 경우

               {

                       first = new ChainNode<T>(i);

                       return first;

               }

        }

        int Length()

        {

               int len = 0;

               ChainNode *temp = first;

 

               while (temp != NULL)

               {

                       temp = temp->link;

                       len++;

               }

               return len;

        }

        void Delete(ChainNode<T> *x)

        {

               if (first == NULL)

               {

                       cout << "체인은 비어있다" << endl;

                       return;

               }

               if (x == first)

                       first = first->link; //다음 노드를 가리킨다

               else

               {

                       ChainNode<T> *temp = first;

                       while (temp->link != x)

                       {

                              temp = temp->link; //x 전 노드를 찾아간다

                       }

                       temp->link = x->link; //x 다음을 temp와 연결시켜 자연스럽게 x가 없어지도록 한다

               }

               delete x;

        }

        void InsertBack(const T &item)

        {

               if (first)

               {

                       last->link = new ChainNode<T>(item);

                       last = last->link;

                       last->link = NULL;

               }

               else

               {

                       first = last = new ChainNode<T>(item);

                       first->link = NULL;

               }

        }

        void Concatenate(Chain<T> &b) //합치다

        {

               if (first)

               {

                       last->link = b.first;

                       last = b.last;

               }

               else

               {

                       first = b.first;

                       last = b.last;

               }

        }

        void Reverse() //거꾸로

        {

               ChainNode<T> *current = first, *previous = NULL; //previous는 current 전 노드

 

               while (current)

               {

                       ChainNode<T> *r = previous; //previous의 위치를 기억해두었다가

                       previous = current;

                       current = current->link;

                       previous->link = r; //이전의 current가 이전의 previous를 가르키도록 한다

               }

               first = previous;

        }

        class ChainIterator

        {

        private:

               ChainNode<T> *current;

        public:

               ChainIterator(ChainNode<T> *startNode = NULL)

               {

                       current = startNode;

               }

               T getData()

               {

                       return current->data;

               }

               T &operator*() const

               {

                       return current->data;

               }

               T *operator->()

               {

                       return &current->data;

               }

               ChainIterator &operator++() //++c

               {

                       current = current->link;

                       return *this;

               }

               ChainIterator operator++(int) //c++

               {

                       ChainIterator old = *this;

                       current = current->link;

                       return old;

               }

               bool operator!=(const ChainIterator right) const

               {

                       return current != right.current;

               }

               bool operator==(const ChainIterator right) const

               {

                       return current = right.current;

               }

               template <typename T>

               friend ostream &operator<<(ostream &os, Chain<T> &c); //출력

        };

        ChainIterator begin()

        {

               return ChainIterator(first);

        }

        ChainIterator end()

        {

               return ChainIterator(last);

        }

        T Min()

        {

               T min;

               Chain<T>::ChainIterator i = begin();

               min = i.getData();

               while (i != end())

               {

                       //cout << "작동" << endl;

                       ++i;

                       if (i.getData() < min)

                       {

                              min = i.getData();

                              //cout << min << endl;

                       }

                       //cout << "끝" << endl;

               }

               //cout << "ch작동" << endl;

               return min;

        }

        template <typename T>

        friend ostream &operator<<(ostream &os, Chain<T> &c); //출력

};

 

template <typename T>

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

{

        Chain<T>::ChainIterator i = c.begin();

        while (i != c.end())

        {

               os << i.getData() << "->";

               i++;

        }

        os << i.getData();

        os << endl;

        return os;

}

 

int main(void)

{

        Chain<int> intChain;

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

               intChain.InsertBack(10 - i);

        cout << "체인 출력" << endl;

        cout << intChain << endl;

        cout << "최소 요소: " << intChain.Min() << endl;

        return 0;

}

[Exercises 3]

/*

Write a C++ function to copy the elements of a chain into an array.

체인에 있는 요소들을 배열에 복사하는 함수를 작성한다

Use the STL function copy together with array and chain iterators

이 때 STL 함수 copy를 사용한다

*/

#include <iostream>

using namespace std;

 

template <typename T> class Chain;

 

template <typename T>

class 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 class Chain<T>;

        template <typename T>

        friend ostream &operator<<(ostream &os, Chain<T> &c); //출력

};

 

template <typename T>

class Chain

{

private:

        ChainNode<T> *first;

        ChainNode<T> *last;

public:

        Chain()

        {

               first = NULL;

        }

        ChainNode<T> *getFirst() //처음 노드 반환

        {

               return first;

        }

        ChainNode<T> *Insert(ChainNode<T> *x, T i) //노드 추가

        {

               if (first)

               {

                       ChainNode<T> *temp = new ChainNode<T>(i, x->link);

                       x->link = temp; //x가 temp를 가르키도록

                       return x->link; //위치를 반환해야 그 다음 위치에 값을 대입

               }

               else //기존 노드가 없을 경우

               {

                       first = new ChainNode<T>(i);

                       return first;

               }

        }

        int Length()

        {

               int len = 0;

               ChainNode *temp = first;

 

               while (temp != NULL)

               {

                       temp = temp->link;

                       len++;

               }

               return len;

        }

        void Delete(ChainNode<T> *x)

        {

               if (first == NULL)

               {

                       cout << "체인은 비어있다" << endl;

                       return;

               }

               if (x == first)

                       first = first->link; //다음 노드를 가리킨다

               else

               {

                       ChainNode<T> *temp = first;

                       while (temp->link != x)

                       {

                              temp = temp->link; //x 전 노드를 찾아간다

                       }

                       temp->link = x->link; //x 다음을 temp와 연결시켜 자연스럽게 x가 없어지도록 한다

               }

               delete x;

        }

        void InsertBack(const T &item)

        {

               if (first)

               {

                       last->link = new ChainNode<T>(item);

                       last = last->link;

                       last->link = NULL;

               }

               else

               {

                       first = last = new ChainNode<T>(item);

                       first->link = NULL;

               }

        }

        void Concatenate(Chain<T> &b) //합치다

        {

               if (first)

               {

                       last->link = b.first;

                       last = b.last;

               }

               else

               {

                       first = b.first;

                       last = b.last;

               }

        }

        void Reverse() //거꾸로

        {

               ChainNode<T> *current = first, *previous = NULL; //previous는 current 전 노드

 

               while (current)

               {

                       ChainNode<T> *r = previous; //previous의 위치를 기억해두었다가

                       previous = current;

                       current = current->link;

                       previous->link = r; //이전의 current가 이전의 previous를 가르키도록 한다

               }

               first = previous;

        }

        class ChainIterator

        {

        private:

               ChainNode<T> *current;

        public:

               ChainIterator(ChainNode<T> *startNode = NULL)

               {

                       current = startNode;

               }

               T getData()

               {

                       return current->data;

               }

               T &operator*() const

               {

                       return current->data;

               }

               T *operator->()

               {

                       return &current->data;

               }

               ChainIterator &operator++() //++c

               {

                       current = current->link;

                       return *this;

               }

               ChainIterator operator++(int) //c++

               {

                       ChainIterator old = *this;

                       current = current->link;

                       return old;

               }

               bool operator!=(const ChainIterator right) const

               {

                       return current != right.current;

               }

               bool operator==(const ChainIterator right) const

               {

                       return current = right.current;

               }

               template <typename T>

               friend ostream &operator<<(ostream &os, Chain<T> &c); //출력

        };

        ChainIterator begin()

        {

               return ChainIterator(first);

        }

        ChainIterator end()

        {

               return ChainIterator(last);

        }

        T Min()

        {

               T min;

               Chain<T>::ChainIterator i = begin();

               min = i.getData();

               while (i != end())

               {

                       ++i;

                       if (i.getData() < min)

                       {

                              min = i.getData();

                       }

                }

               return min;

        }

        void Copy(T *arr)

        {

               //copy(begin(), end(), arr);

               //무슨 이유에서인지 위에 STL copy는 작동하지 않습니다

               //Error C2794 iterator_category: 직접 또는 간접 기본 클래스 'std::iterator_traits<_Iter>'의 멤버가 아닙니다라는 메시지가 뜹니다

               //한번 알아보고 나중에 코드 수정하겠습니다

               int idx = 0;

               Chain<T>::ChainIterator index = begin();

               while (index != end())

               {

                       arr[idx++] = index.getData();

                       index++;

               }

               arr[idx] = index.getData();

        }

        template <typename T>

        friend ostream &operator<<(ostream &os, Chain<T> &c); //출력

};

 

template <typename T>

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

{

        Chain<T>::ChainIterator i = c.begin();

        while (i != c.end())

        {

               os << i.getData() << "->";

               i++;

        }

        os << i.getData();

        os << endl;

        return os;

}

 

int main(void)

{

        Chain<int> intChain;

        int arr[20] = { 0, }; //복사할 배열

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

               intChain.InsertBack(i+1);

        cout << "체인 출력" << endl;

        cout << intChain << endl;

        intChain.Copy(arr);

        cout << "배열 출력" << endl;

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

               cout << arr[i] << " ";

        cout << endl;

        return 0;

}

[Exercises 4]

/*

Let x1, x2, ..., x(n) be the elements of a chain.

x1, x2, ..., x(n)이 체인의 요소라고 한다.

Write a C++ function to compute the expression 시그마(i=1~(n-5)) (x(i)*x(i+5))

시그마(i=1~(n-5)) (x(i)*x(i+5))를 계산하도록 C++ 함수를 작성한다

*/

#include <iostream>

using namespace std;

 

template <typename T> class Chain;

 

template <typename T>

class 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 class Chain<T>;

        template <typename T>

        friend ostream &operator<<(ostream &os, Chain<T> &c); //출력

};

 

template <typename T>

class Chain

{

private:

        ChainNode<T> *first;

        ChainNode<T> *last;

public:

        Chain()

        {

               first = NULL;

        }

        ChainNode<T> *getFirst() //처음 노드 반환

        {

               return first;

        }

        ChainNode<T> *Insert(ChainNode<T> *x, T i) //노드 추가

        {

               if (first)

               {

                       ChainNode<T> *temp = new ChainNode<T>(i, x->link);

                       x->link = temp; //x가 temp를 가르키도록

                       return x->link; //위치를 반환해야 그 다음 위치에 값을 대입

               }

               else //기존 노드가 없을 경우

               {

                       first = new ChainNode<T>(i);

                       return first;

               }

        }

        int Length()

        {

               int len = 0;

               ChainNode<T> *temp = first;

 

               while (temp != NULL)

               {

                       temp = temp->link;

                       len++;

               }

               return len;

        }

        void Delete(ChainNode<T> *x)

        {

               if (first == NULL)

               {

                       cout << "체인은 비어있다" << endl;

                       return;

               }

               if (x == first)

                       first = first->link; //다음 노드를 가리킨다

               else

               {

                       ChainNode<T> *temp = first;

                       while (temp->link != x)

                       {

                              temp = temp->link; //x 전 노드를 찾아간다

                       }

                       temp->link = x->link; //x 다음을 temp와 연결시켜 자연스럽게 x가 없어지도록 한다

               }

               delete x;

        }

        void InsertBack(const T &item)

        {

               if (first)

               {

                       last->link = new ChainNode<T>(item);

                       last = last->link;

                       last->link = NULL;

               }

               else

               {

                       first = last = new ChainNode<T>(item);

                       first->link = NULL;

               }

        }

        void Concatenate(Chain<T> &b) //합치다

        {

               if (first)

               {

                       last->link = b.first;

                       last = b.last;

               }

               else

               {

                       first = b.first;

                       last = b.last;

               }

        }

        void Reverse() //거꾸로

        {

               ChainNode<T> *current = first, *previous = NULL; //previous는 current 전 노드

 

               while (current)

               {

                       ChainNode<T> *r = previous; //previous의 위치를 기억해두었다가

                       previous = current;

                       current = current->link;

                       previous->link = r; //이전의 current가 이전의 previous를 가르키도록 한다

               }

               first = previous;

        }

        class ChainIterator

        {

        private:

               ChainNode<T> *current;

        public:

               ChainIterator(ChainNode<T> *startNode = NULL)

               {

                       current = startNode;

               }

               T getData()

               {

                       return current->data;

               }

               T &operator*() const

               {

                       return current->data;

               }

               T *operator->()

               {

                       return &current->data;

               }

               ChainIterator &operator++() //++c

               {

                       current = current->link;

                       return *this;

               }

               ChainIterator operator++(int) //c++

               {

                       ChainIterator old = *this;

                       current = current->link;

                       return old;

               }

               bool operator!=(const ChainIterator right) const

               {

                       return current != right.current;

               }

               bool operator==(const ChainIterator right) const

               {

                       return current = right.current;

               }

               template <typename T>

               friend ostream &operator<<(ostream &os, Chain<T> &c); //출력

        };

        ChainIterator begin()

        {

               return ChainIterator(first);

        }

        ChainIterator end()

        {

               return ChainIterator(last);

        }

        T Min()

        {

               T min;

               Chain<T>::ChainIterator i = begin();

               min = i.getData();

               while (i != end())

               {

                       ++i;

                       if (i.getData() < min)

                       {

                              min = i.getData();

                       }

               }

               return min;

        }

        void Copy(T *arr)

        {

               //copy(begin(), end(), arr);

               //무슨 이유에서인지 위에 STL copy는 작동하지 않습니다

               //Error C2794 iterator_category: 직접 또는 간접 기본 클래스 'std::iterator_traits<_Iter>'의 멤버가 아닙니다라는 메시지가 뜹니다

               //한번 알아보고 나중에 코드 수정하겠습니다

               int idx = 0;

               Chain<T>::ChainIterator index = begin();

               while (index != end())

               {

                       arr[idx++] = index.getData();

                       index++;

               }

               arr[idx] = index.getData();

        }

        void Compute()

        {

               Chain<T>::ChainIterator index=begin();

               T Sum = 0;

               int count = 0;

               if (Length() < 10)

               {

                       cout << "최소 10개의 요소가 있어야 계산 가능하다" << endl;

                       return;

               }

               while (count < Length() - 5)

               {

                       Chain<T>::ChainIterator temp = index;

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

                              temp++;

                       cout << count+1 << ":index: " << index.getData() << "\ttemp: " << temp.getData() << endl;

                       Sum += index.getData()*temp.getData();

                       index++;

                       count++;

               }

               cout << "결과: " << Sum << endl;

        }

        template <typename T>

        friend ostream &operator<<(ostream &os, Chain<T> &c); //출력

};

 

template <typename T>

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

{

        Chain<T>::ChainIterator i = c.begin();

        while (i != c.end())

        {

               os << i.getData() << "->";

               i++;

        }

        os << i.getData();

        os << endl;

        return os;

}

 

int main(void)

{

        Chain<int> intChain;

        int arr[20] = { 0, }; //복사할 배열

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

               intChain.InsertBack(i + 1);

        cout << "체인 출력" << endl;

        cout << intChain << endl;

        intChain.Compute();

        return 0;

}

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

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

*3번 문제는 STL copy 함수를 사용하면 컴파일에러가 뜨기 때문에 직접 copy를 했습니다