다음 연습문제들은 모두 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회독 때 ..