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
Husnain is a professional Software Engineer and a researcher who loves to learn, build, write, and teach. Having worked various jobs in the IT industry, he especially enjoys finding ways to express complex ideas in simple ways through his content. In his free time, Husnain unwinds by thinking about tech fiction to solve problems around him.
LinkedIn