C++에서 연결된 목록 반전
이 기사에서는 C++에서 연결된 목록 데이터 구조를 반전하는 방법을 보여줍니다.
반복 함수를 사용하여 C++에서 연결된 목록 반전
대상 개체가 단일 연결 목록이라고 가정하고 그에 따라 코드 조각을 구현합니다. 먼저 예제를 보여주기 위해 구현 된 드라이버 코드의 기본 기능 유틸리티를 살펴볼 필요가 있습니다.
링크드리스트 노드는 단일string데이터 오브젝트와 다음 노드에 대한 포인터가있는 단순한struct입니다. 또한 두 개의 인수,Node*및string에 대한 참조를 취하는addNewNode함수도 있습니다. addNewNode함수는main루틴에서 여러 번 호출되어 새 목록 오브젝트를 구성하고data_set벡터에서 문자열을 저장합니다. 이 함수는 동적 메모리에 각 노드를 할당하고 새로 생성 된 노드에 대한 포인터를 반환합니다.
링크드리스트 데이터 구조를위한 또 다른 유용한 기능은 모든 노드에서cout스트림으로 데이터를 출력하는 데 사용되는printNodes입니다. 후자는 반전 기능의 정확성을 느슨하게 확인하는 데 도움이됩니다. printNodes는 목록 순회 중에 노드 수를 유지하고 각 요소에 대한 색인을 인쇄합니다. 마지막으로, 프로그램이 종료되기 전에 모든 노드를 할당 해제해야합니다. 이 단계는 반전 기능 데모에 필요하지 않지만 실제 프로젝트에서 런타임 중에 할당 된 모든 메모리를 정리하는 것이 중요합니다.
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct Node {
struct Node *next{};
string data;
};
struct Node *addNewNode(struct Node *node, string &data) {
auto new_node = new Node;
if (node) node->next = new_node;
new_node->next = nullptr;
new_node->data = data;
return new_node;
}
void freeNodes(struct Node *node) {
struct Node *tmp = nullptr;
while (node) {
tmp = node;
node = node->next;
delete tmp;
}
}
void printNodes(struct Node *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct Node *tmp, *head = nullptr;
vector<string> data_set = {"Rocket Lake", "Alder Lake", "Tiger Lake",
"Meteor Lake"};
head = addNewNode(head, data_set.at(0));
tmp = head;
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
tmp = addNewNode(tmp, *it);
}
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
출력:
node 0 - data: Rocket Lake
node 1 - data: Alder Lake
node 2 - data: Tiger Lake
node 3 - data: Meteor Lake
새 연결 목록을 초기화하고 목록의 헤드를 별도의 포인터에 저장하면이를 사용하여 내용을 반전 할 수 있습니다. 이 경우 단일Node*인수를 받아들이고 새 루트 노드를 반환하는reverseList함수를 구현했습니다. 처음에는 전달 된 포인터를 복제하여head변수로 저장합니다. 또한while루프 동안 내부 부기 관리를 수행하려면 두 개의 추가Node유형 포인터가 필요합니다.
반전 알고리즘은 다음과 같이 설명 할 수 있습니다. 다음 노드 포인터를 임시 변수 (next)에 저장하고nullptr값을 원래 변수에 할당합니다. 결과적으로 원래head노드는 목록에서 다음 노드로nullptr를 가리 킵니다. 다음으로head변수를 업데이트하여 다음 (두 번째) 노드를 원래 목록에 저장하고 원래 헤드 노드의 주소를 별도의 임시 변수에 저장합니다.
head포인터가nullptr로 평가 될 때까지 이전 단계를 반복합니다. 이는 목록의 끝에 도달했음을 의미합니다. 결국n임시 변수에 저장된 새 헤드 노드의 주소를 반환합니다. 결과적으로main프로그램은 사용자가 수정 된 링크 목록 내용을 비교할 수 있도록printNodes함수를 호출합니다.
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct Node {
struct Node *next{};
string data;
};
struct Node *addNewNode(struct Node *node, string &data) {
auto new_node = new Node;
if (node) node->next = new_node;
new_node->next = nullptr;
new_node->data = data;
return new_node;
}
void freeNodes(struct Node *node) {
struct Node *tmp = nullptr;
while (node) {
tmp = node;
node = node->next;
delete tmp;
}
}
void printNodes(struct Node *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
Node *reverseList(struct Node *node) {
auto head = node;
Node *n = nullptr;
Node *next = nullptr;
while (head) {
next = head->next;
head->next = n;
n = head;
head = next;
}
return n;
}
int main() {
struct Node *tmp, *head = nullptr;
vector<string> data_set = {"Rocket Lake", "Alder Lake", "Tiger Lake",
"Meteor Lake"};
head = addNewNode(head, data_set.at(0));
tmp = head;
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
tmp = addNewNode(tmp, *it);
}
printNodes(head);
cout << " ----------------------------------- " << endl;
printNodes(reverseList(head));
freeNodes(head);
return EXIT_SUCCESS;
}
출력:
node 0 - data: Rocket Lake
node 1 - data: Alder Lake
node 2 - data: Tiger Lake
node 3 - data: Meteor Lake
-----------------------------------
node 0 - data: Meteor Lake
node 1 - data: Tiger Lake
node 2 - data: Alder Lake
node 3 - data: Rocket Lake
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