C++에서 순환 연결 목록 데이터 구조 구현
- 멤버 함수를 사용하여 순환 단일 연결 목록을 구현하여 끝에 새 요소를 추가하고 C++에서 요소를 인쇄합니다
- 소멸자 및 멤버 함수를 구현하여 C++의 목록 시작 부분에 새 요소 삽입
이 기사에서는 C++에서 순환 연결 목록 데이터 구조를 구현하는 방법을 설명합니다.
멤버 함수를 사용하여 순환 단일 연결 목록을 구현하여 끝에 새 요소를 추가하고 C++에서 요소를 인쇄합니다
순환 연결 목록은 마지막 노드가 목록의 머리를 가리키는 연결 목록으로 특성화 될 수 있습니다. 기본적으로 목록의 노드는 원을 형성하며 목록의 끝을 구분하는nullptr가 없습니다. 순환 연결 목록을 활용하여 큐 스타일 데이터 구조를 구축 할 수 있습니다. 순환 성 기능은 이중 연결 목록과 단일 연결 목록 모두에 추가 할 수 있습니다.
이 경우 후자를 구현할 것입니다. 다음 노드에 대한 포인터를 포함하는 노드 구조와 단일 연결 목록을 구성하는 데이터 요소를 정의해야합니다. struct ListNode객체는 구현을위한 단일 노드를 나타내고data라는 이름의 단일string객체를 저장합니다.이 객체는이 예제의 요소 데이터 역할을합니다. 노드에 사용자 정의 개체를 저장할 수 있으며 개체가 상대적으로 더 크면 포인터로 포함하는 것이 좋습니다.
단일 노드의 구조를 가지게되면 스타터 용 멤버 함수가 두 개 뿐인CircularList클래스를 정의 할 수 있습니다. 일반적으로 순환 연결 목록은 목록의 머리 부분이나 끝 부분을 추적해야합니다. 그러나 구현자는 일반적으로 필요에 따라 클래스 디자인 결정을 자유롭게 내릴 수 있습니다. 또한CircularList클래스는 목록의 머리와 끝을 나타내는 두 개의 개별 포인터를 저장합니다.
목록의 머리 / 끝을 저장하는 포인터는 더미 노드이거나 데이터가있는 실제 노드 일 수 있습니다. 이 예제에서는 더미 포인터가 없도록CircularList클래스를 디자인하도록 선택했습니다. 순환 목록의 첫 번째 노드를 초기화하기 위해string매개 변수를 허용하는 생성자를 정의했습니다. 클래스 정의 중 디자인 선택은 일반적으로 다른 변수에 영향을 미치므로 근본적인 문제를 기반으로 고려해야합니다. 따라서 다음 구현은 순환 연결 목록의 개념을 설명하기위한 간단한 구현 일뿐입니다.
생성자를 사용하여CircularList객체가 초기화되면insertNodeEnd멤버 함수를 사용하여 새 요소를 추가 할 수 있습니다. 후자는string매개 변수를 받아들이고 목록 끝에 새 요소를 생성합니다. insertNodeEnd함수는new연산자로 새 요소를 할당하고 그에 따라 포인터를 수정하여 목록 끝 바로 뒤에 노드를 삽입합니다. 또한 새로 할당 된 노드를 가리 키도록end데이터 멤버를 업데이트합니다.
다음 샘플에 정의 된 또 다른 멤버 함수는printNodes로, 목록을 반복하여 내용을 인쇄하고 인수를 사용하지 않습니다. 이제이 구조의 사용법을 더 잘 보여주기 위해main함수에 드라이버 코드가 필요합니다. 나중에for루프를 사용하여CircularList객체에 삽입 할 임의의 문자열의벡터를 초기화하도록 선택했습니다. 마지막으로printNodes함수를 호출하여 목록 내용을 터미널에 표시합니다.
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class CircularList {
public:
explicit CircularList(string data) {
head = new ListNode;
head->next = head;
head->data = std::move(data);
end = head;
};
ListNode *insertNodeEnd(string data);
void printNodes();
private:
ListNode *head = nullptr;
ListNode *end = nullptr;
};
ListNode *CircularList::insertNodeEnd(string data) {
auto new_node = new ListNode;
new_node->next = end->next;
new_node->data = std::move(data);
end->next = new_node;
end = end->next;
return new_node;
}
void CircularList::printNodes() {
auto count = 0;
auto tmp = head;
while (tmp != end) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
cout << "node " << count << " - data: " << tmp->data << endl;
}
int main() {
vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};
CircularList clist("Xenial");
for (const auto &item : data_set) {
clist.insertNodeEnd(item);
}
clist.printNodes();
return EXIT_SUCCESS;
}
출력:
node 0 - data: Xenial
node 1 - data: Precise
node 2 - data: Quantal
node 3 - data: Saucy
node 4 - data: Raring
소멸자 및 멤버 함수를 구현하여 C++의 목록 시작 부분에 새 요소 삽입
이전 코드 조각에는 소멸자가 정의되어 있지 않다는 큰 문제가 있습니다. 이것은 동적 메모리에 생성 된 노드가 프로그램이 종료 될 때까지 해제되지 않기 때문에CircularList클래스를 사용하는 프로그램이 메모리를 누수한다는 것을 의미합니다.
이 문제에 대한 해결책은 전체 목록을 순회하고delete연산자를 사용하여 모든 노드를 할당 해제하는 소멸자를 구현하는 것입니다. 따라서 목록 메모리를 수동으로 해제하는 것에 대해 걱정할 필요가 없습니다. CircularList개체가 범위의 끝에 도달하면 자동으로 해제됩니다.
구현할 또 다른 유용한 기능은 목록의 맨 위에 새 요소를 삽입하는 기능입니다. insertNodeHead명령은이를 수행하도록 설계되었습니다. string인수 만 저장하고 새로 할당 된 노드에 대한 포인터를 리턴합니다. insertNodeEnd및insertNodeHead함수의 반환 값은 프로그래머가 결정하는대로 다르게 구현되는 또 다른 디자인 선택 사항입니다. 다음 코드 스 니펫은CircularList클래스 사용을 테스트하고 보여주기 위해main함수에 유사한 드라이버 코드를 포함합니다.
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class CircularList {
public:
explicit CircularList(string data) {
head = new ListNode;
head->next = head;
head->data = std::move(data);
end = head;
};
ListNode *insertNodeEnd(string data);
ListNode *insertNodeHead(string data);
void printNodes();
~CircularList();
private:
ListNode *head = nullptr;
ListNode *end = nullptr;
};
ListNode *CircularList::insertNodeEnd(string data) {
auto new_node = new ListNode;
new_node->next = end->next;
new_node->data = std::move(data);
end->next = new_node;
end = end->next;
return new_node;
}
ListNode *CircularList::insertNodeHead(string data) {
auto new_node = new ListNode;
new_node->next = end->next;
new_node->data = std::move(data);
end->next = new_node;
head = end->next;
return new_node;
}
CircularList::~CircularList() {
while (head != end) {
auto tmp = head;
head = head->next;
delete tmp;
}
delete head;
}
void CircularList::printNodes() {
auto count = 0;
auto tmp = head;
while (tmp != end) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
cout << "node " << count << " - data: " << tmp->data << endl;
}
int main() {
vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};
CircularList clist("Xenial");
for (const auto &item : data_set) {
clist.insertNodeEnd(item);
}
clist.printNodes();
cout << " ----------------------------------- " << endl;
clist.insertNodeHead("Bionic");
clist.insertNodeEnd("Zeisty");
clist.printNodes();
return EXIT_SUCCESS;
}
출력:
node 0 - data: Xenial
node 1 - data: Precise
node 2 - data: Quantal
node 3 - data: Saucy
node 4 - data: Raring
-----------------------------------
node 0 - data: Bionic
node 1 - data: Xenial
node 2 - data: Precise
node 3 - data: Quantal
node 4 - data: Saucy
node 5 - data: Raring
node 6 - data: Zeisty
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook