C++에서 연결 목록 정렬
이 간단한 프로그래밍 자습서는 C++의 연결 목록 데이터 구조에 대한 정렬 작업의 구현을 보여줍니다.
C++로 나열
목록 또는 연결 목록은 데이터 컨테이너 역할을 하고 데이터를 메모리에 저장할 수 있는 선형 데이터 구조입니다. 벡터나 배열과 달리 목록의 데이터에는 연속적인 메모리 위치가 필요하지 않습니다. 대신 데이터가 동적으로 증가하고 임의의 힙 메모리 위치에 할당될 수 있습니다.
목록의 각 요소를 노드라고 합니다. 목록의 각 노드에는 목록의 바로 다음 노드를 가리키는 포인터가 있습니다.
각 노드에 다음 요소에 대한 포인터를 포함하면 이전 노드를 통해 모든 다음 요소에 액세스할 수 있는 선형 연결을 용이하게 할 수 있습니다. 노드 간의 이러한 선형 연결은 이 구조에 연결 목록이라는 이름을 부여한 주된 이유입니다.
삽입, 삭제, 검색, 정렬과 같은 여러 ADT(추상 데이터 유형) 작업을 연결 목록에서 수행할 수 있습니다. 연결 목록의 기본 구조적 구현으로 시작한 다음 해당 클래스에서 정렬 알고리즘을 구현합니다.
C++에서 연결 목록 구현
이제 Linked List 구현을 시작하겠습니다. 이를 위해 먼저 Node에 대한 클래스를 다음과 같이 생성해야 합니다.
template <class T>
class Node {
public:
T data;
Node<T>* next;
Node() { next = 0; }
};
이 클래스에는 두 개의 멤버가 있습니다. 하나는 데이터, 즉 info를 저장하기 위한 것이고 다른 하나는 다음 노드의 주소를 저장하기 위한 클래스의 포인터입니다. 클래스는 모든 데이터 유형의 목록을 생성할 수 있도록 템플릿화됩니다.
이제 다음과 같은 Linked List 클래스를 생성합니다.
template <class T>
class LSLL {
private:
Node<T>* head;
public:
LSLL() { head = 0; }
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;
}
}
}
};
이 클래스에는 목록 노드를 삽입하고 표시하는 생성자와 두 개의 다른 멤버 함수가 있습니다.
C++에서 연결 목록 정렬
가장 간단한 정렬 알고리즘인 버블 정렬을 구현하여 연결 목록을 오름차순으로 정렬합니다. 이 정렬 알고리즘은 정렬되지 않은 순서로 배치된 경우 인접 요소를 반복적으로 교체합니다.
이 작업은 모든 요소가 올바른 정렬 위치에 올 때까지 반복적으로 수행됩니다. 이것은 다음과 같이 구현될 것입니다:
-
나중에 사용할 새 노드
temp를 만들고head를curr노드로 만듭니다. -
head가 NULL이면 반환합니다. -
그렇지 않으면
end노드(즉, NULL)에 도달할 때까지 루프를 만드십시오. -
각 반복에 대해 5-6단계를 반복해야 합니다.
-
temp에curr노드의 다음 노드를 저장합니다. -
curr노드의 데이터가 다음 노드의 데이터보다 큰지 확인하십시오. 더 큰 경우curr와temp를 바꿉니다.
void sortLinkedList() {
Node<T> *curr = head, *temp = NULL;
int t;
if (head == NULL) {
return;
} else {
while (curr != NULL) {
temp = curr->next;
while (temp != NULL) {
if (curr->info > temp->info) {
t = curr->info;
curr->info = temp->info;
temp->info = t;
}
temp = temp->next;
}
curr = curr->next;
}
}
}
드라이버 프로그램은 다음과 같습니다.
int main() {
LSLL<int> list;
list.insertAtHead(50);
list.insertAtHead(45);
list.insertAtHead(16);
cout << "Before sorting" << endl;
list.displayAll();
cout << "After Sorting: " << endl;
list.sortLinkedList();
list.displayAll();
return 0;
}
출력:
Before sorting
43
65
13
After Sorting:
13
43
65
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