[C++ Fundamentals of Data Structures/C++ 자료구조론(이석호)] 4.2 C++에서의 체인 표현 연습 문제

다음 연습문제들은 모두 4.2.4.절의 정의들을 기반으로 하고 있다. 모든 함수들은 클래스 Chain의 멤버 함수로 구현되는데, 그래서 이들은 ChainNode의 데이타 멤버들에 접근할 수 있다고 가정한다.

 

1. 체인에 있는 노드의 수를 계산하는 C++ 함수 length를 작성하라. 이 함수의 시간 복잡도는 얼마인가?

* 시간 복잡도 : O(n)

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

 

 

2. x를 체인에 있는 임의의 노드를 지시하는 포인터라고 하자. 체인으로부터 이것을 삭제하는 C++ 함수를 작성하라.

만일 x == first라고 하면, first는 체인에서 새로 첫 번째가 된 노드를 가리키도록 반드시 재설정 되어야 한다. 이 함수의 시간 복잡도는 얼마인가?

 

* 시간 복잡도 : O(x-1)

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

 

 

3. first가 가르키는 노드부터 시작하여, 하나 건너 노드를 모두 삭제하는 C++ 함수를 작성하라.(즉, 함수는 체인의 첫 번째,  세 번째, 다섯 번째, 이런 순서로 계속되는 노드들을 삭제한다.) 이 함수의 시간 복잡도는 얼마인가?

 

* 시간복잡도 : O(n) //노드의 개수만큼 반복

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

 

#include <iostream>
using namespace std;

class Chain;

class ChainNode {
public:
	ChainNode(int element = 0, ChainNode* next = 0) {
		data = element;
		link = next;
	}
	int getData() {
		return data;
	}

	ChainNode* Link() {
		return link;
	}

	friend class Chain;
	friend ostream& operator<<(ostream& os, Chain& c); //ChainNode의 getData가 있어야 데이터 출력 가능

private:
	int data;
	ChainNode* link;
};

class Chain {
private:
	ChainNode* first;
public:
	Chain() { first = NULL; }

	ChainNode* getFirst() {
		return first;
	}

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

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

	void Delete(ChainNode* x) { //2번
		if (x == first)
			first = first->link;
		else {
			ChainNode* ptr;
			for (ptr = first; ptr->link != x; ptr = ptr->link);
			ptr->link = x->link;
		}
		delete x;
	}

	void AcrossDelete() { //3번
		if (first == NULL) {
			cout << "체인은 비어있습니다." << endl;
			return;
		}
		else {
			ChainNode* ptr;
			for (ptr = first; ptr->link != NULL; ptr = ptr->link) {
				if ((ptr->link->link) == NULL) {
					delete[](ptr->link);
					ptr->link = NULL;
					break;
				}
				Delete(ptr->link);
			}
		}
	}

	friend ostream& operator<<(ostream& os, Chain& c);
};

ostream& operator<<(ostream& os, Chain& c) {
	ChainNode* temp = c.first;
	while (temp != NULL) {
		os << temp->getData();
		if (temp->link != NULL)
			cout << "->";
		temp = temp->link;
	}
	return os;

}

int main() {
	Chain chain;
	ChainNode* 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;
	cout << "체인에 있는 노드의 수 : " << chain.length() << endl;

	ChainNode* del = chain.getFirst();
	int x;
	cout << endl << "삭제할 노드의 번호를 입력하세요 : ";
	cin >> x;

	for (int i = 1; i < x; i++)
		del = del->Link();
	chain.Delete(del);
	cout << chain << endl;

	cout << endl << "<홀수 번째 노드 삭제>" << endl;
	chain.AcrossDelete();
	cout << chain << endl;

	return 0;
}

//출력 결과

 

 

* 4,5,6번은 2회독 때 ..