HOWTO · C++
C++에서 연결 목록 정렬
이 프로그래밍 자습서는 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
