[C++ Fundamentals of Data Structures/C++ 자료구조론(이석호)] 4.3 템플릿 클래스 체인 연습 문제

1.  연산자 <<를 다중화하여 체인의 모든 원소를 출력하는 C++ 템플릿 함수를 작성하라. 연산자<<는 데이타 타입 T를 위해 다중화되었다고 가정하라.

 

#include <iostream>
using namespace std;

template <class T> class Chain;

template <class T>
class ChainNode {
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 <class T>
	friend ostream& operator<<(ostream& os, Chain<T>& c); //ChainNode의 getData가 있어야 데이터 출력 가능

private:
	T data;
	ChainNode* link;
};

template <class T>
class Chain {
private:
	ChainNode<T>* first;
	ChainNode<T>* last;
public:
	Chain() { first = NULL; }

	ChainNode<T>* getFirst() {
		return first;
	}

	int length() {
		ChainNode* ptr;
		int length = 0;
		for (ptr = first; ptr != NULL; ptr = ptr->link)
			length++;
		return length;
	}

	ChainNode<T>* Insert(T element, ChainNode<T>* x) { //1번
		if (first) {
			ChainNode<T>* n = new ChainNode<T>(element, x->link);
			x->link = n;
			return x->link; //위치를 반환해야 그 다음 위치에 값을 대입
		}
		else { //연결 리스트가 공백인 경우
			first = new ChainNode<T>(element);
			return first;
		}
	}

	void Delete(ChainNode<T>* x) { //2번
		if (first == NULL) {
			cout << "체인은 비어있다." << endl;
			return;
		}
		if (x == first)
			first = first->link;
		else {
			ChainNode<T>* ptr;
			for (ptr = first; ptr->link != x; ptr = ptr->link);
			ptr->link = x->link;
		}
		delete x;
	}

	void InsertBack(const T& e) {
		if (first) {
			last->link = new ChainNode<T>(e);
			last = last->link;
		}
		else
			first = last = new ChainNode<T>(e);
	}

	void Concatenate(Chain<T>& b) {
		if (first) {
			last->link = b.first;
			last = b.last;
		}
		else {
			first = b.first;
			last = b.last;
		}
		b.first = b.last = 0;
	}

	void Reverse() {
		ChainNode<T>* current = first, * previous = 0;
		while (current) {
			ChainNode<T>* r = previous;
			previous = current;
			current = current->link;
			previous->link = r;
		}
		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->() const { return &current->data; }

		ChainIterator& operator++() {
			current = current->link;
			return *this;
		}
		ChainIterator operator++(int) {
			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 <class T>
		friend ostream& operator<<(ostream& os, Chain<T>& c);
	};

	ChainIterator begin() { return ChainIterator(first); }
	ChainIterator end() { return ChainIterator(0); }

	template <class T>
	friend ostream& operator<<(ostream& os, Chain<T>& c);
};

template <class T>
ostream& operator<<(ostream& os, Chain<T>& c) { //1번
	typename Chain<T>::ChainIterator i = c.begin();
	while (i != c.end()) {
		os << i.getData() << "->";
		i++;
	}
	os << i.getData();
	os << endl;
	return os;

}

int main() {
	Chain<int> chain;
	ChainNode<int>* ch = chain.getFirst();
	int n;

	cout << "연결 리스트 원소의 개수 : ";
	cin >> n;
	for (int i = 0; i < n; i++) {
		int element;
		cout << "원소를 입력하세요 : ";
		cin >> element;
		ch = chain.Insert(element, ch);
	}

	cout << endl << chain << endl;
	
	return 0;
}

 

* 왜 예외 발생하는지 도무지 모르겟음

* 2번은 2회독 때, 3,4,5번은 안 함.

* 참고 : https://jaimemin.tistory.com/160