HOWTO · C++
C++의 연결 목록 복사 생성자
C++를 사용하여 연결 목록 데이터 구조에서 복사 생성자를 사용하는 방법에 대한 간단한 프로그래밍 자습서입니다.
이 페이지의 내용
이 간단한 기사는 깊은 복사 생성자가 있는 연결 목록의 C++ 기반 구현에 관한 것입니다.
C++의 복사 생성자
동일한 클래스의 다른 객체를 사용하여 객체를 초기화하기 위해 복사 생성자가 호출됩니다. 복사 생성자는 다음과 같은 여러 상황에서 호출됩니다.
- 다른 개체를 사용하여 개체를 복사하는 경우.
- 객체가 함수에서 값으로 반환될 때.
- 객체가 함수에 값으로 전달될 때.
모든 클래스에는 항상 기본 복사 생성자가 있지만 전체 복사를 수행하지 않고 얕은 복사를 수행합니다. 포인터의 주소만 얕은 복사로 복사되고 두 개체(예: 호출자 및 전달된 개체)가 동일한 메모리를 가리킵니다.
반대로 전체 복사에서는 데이터 구성원의 값이 대상 개체 데이터 구성원에 복사됩니다.
C++의 연결 리스트
연결 목록 데이터 구조는 동적으로 성장할 수 있는 데이터 노드 형태로 데이터를 저장합니다. 연속 메모리가 필요하지 않으므로 메모리의 어느 위치에나 효율적으로 저장할 수 있습니다.
C++의 연결 목록 구현
연결 리스트를 구현해 봅시다. 먼저 데이터 노드를 가져오기 위한 클래스를 만들어야 합니다.
template <class T>
class Node {
public:
T info;
Node<T>* next;
Node() { next = 0; }
Node(T val) {
info = val;
next = 0;
}
};
Node 클래스에는 두 개의 멤버가 있습니다. 하나는 데이터(즉, info)를 저장하기 위한 것이고 다른 하나는 다음 노드의 주소를 저장하기 위한 클래스 자체에 대한 포인터입니다. 클래스는 모든 데이터 유형의 목록을 생성할 수 있도록 템플릿화됩니다.
위의 구현은 두 개의 생성자를 제공합니다. 첫 번째는 기본 생성자이고 다른 하나는 매개변수화됩니다.
연결 목록의 템플릿 클래스를 살펴보겠습니다.
template <class T>
class LSLL {
private:
Node<T>* head;
public:
LSLL() { head = 0; }
};
LSLL 클래스에는 Node 클래스에 대한 포인터가 하나만 있으며 연결 목록의 첫 번째 노드 주소를 보유하는 데 사용됩니다.
사용자에게 하나의 연결 목록 개체를 다른 개체에 깊이 복사하는 기능을 제공하려면 아래와 같이 사용자 정의 복사 생성자 구현을 제공해야 합니다.
LSLL(LSLL& PassedObj) {
if (PassedObj.head == NULL) {
head = NULL;
} else {
// copy all nodes of PassedObj to the caller object
// attach first node to the head of the caller object
Node<T>* newNode = new Node<T>();
newNode->info = PassedObj.head->info;
newNode->next = NULL;
head = newNode;
// Now deep-copy all the remaining nodes of the Passed linked list object
Node<T>* PassedItr = PassedObj.head->next;
Node<T>* CallerItr = head;
while (PassedItr != NULL) {
CallerItr->next = new Node<T>();
CallerItr->next->info = PassedItr->info;
CallerItr->next->next = NULL;
CallerItr = CallerItr->next; // move to newly added node
PassedItr = PassedItr->next; // move one node further
}
}
}
위의 코드 세그먼트는 전달된 객체의 첫 번째 노드의 전체 복사본을 생성하고 이를 호출자 목록 객체의 head에 첨부합니다. 그 후, 전달된 객체의 나머지 모든 노드는 깊이 복사되어 호출자 연결 목록 노드에 연결됩니다.
전체 구현에 대한 인지적 관점을 살펴보겠습니다.
#include <iostream>
using namespace std;
template <class T>
class Node {
public:
T info;
Node<T>* next;
Node() { next = NULL; }
Node(T val) {
info = val;
next = NULL;
}
};
template <class T>
class LSLL {
private:
Node<T>* head;
public:
LSLL() { head = NULL; }
LSLL(LSLL& PassedObj) {
if (PassedObj.head == NULL) {
head = NULL;
} else {
// copy all nodes of PassedObj to the caller object
// attach first node to the head of the caller object
Node<T>* newNode = new Node<T>();
newNode->info = PassedObj.head->info;
newNode->next = NULL;
head = newNode;
// Now deep-copy all the remaining nodes of the Passed linked list object
Node<T>* PassedItr = PassedObj.head->next;
Node<T>* CallerItr = head;
while (PassedItr != NULL) {
CallerItr->next = new Node<T>();
CallerItr->next->info = PassedItr->info;
CallerItr->next->next = NULL;
CallerItr = CallerItr->next; // move to newly added node
PassedItr = PassedItr->next; // move one node further
}
}
}
void insertAtHead(T val) {
Node<T>* x = new Node<T>(val);
x->next = head;
head = x;
}
void displayAll() {
Node<T>* x = head;
{
while (x != 0) {
cout << x->info << endl;
x = x->next;
}
}
}
int isEmpty() {
if (head == 0) return 1;
return 0;
}
void insetAtTail(T val) {
Node<T>* x = head;
if (isEmpty()) {
insertAtHead(val);
return;
}
while (x->next != 0) {
x = x->next;
}
x->next = new Node<T>(val);
}
void insertAfter(T key, T val) {
if (isEmpty()) return;
Node<T>* x = head;
while (x != 0 && x->info == key) x = x->next;
if (!x) return;
Node<T>* temp = new Node<T>(val);
temp->next = x->next;
x->next = x;
}
};
int main() {
LSLL<int> list;
list.insertAtHead(200);
list.insertAtHead(100);
list.insetAtTail(300);
list.displayAll();
LSLL<int> list2(list);
cout << "List2: " << endl;
list2.displayAll();
return 0;
}
메인 드라이버 코드는 먼저 list 객체를 생성하고 여기에 3개의 노드를 삽입하고 displayAll 함수를 호출합니다. 그런 다음 새 연결 목록 개체 list2를 만들고 list를 인수로 사용하여 매개 변수화된 복사 생성자를 호출합니다.
list2 개체는 호출자 개체이고 list는 전달된 개체입니다.
출력:
100
200
300
List2:
100
200
300
