원형 연결 리스트를 활용한 C 언어 정렬 코드 작성 가이드

원형 연결 리스트를 활용한 C 언어 정렬 코드 작성 가이드

원형 연결 리스트(Circular Linked List)는 마지막 노드가 첫 번째 노드를 가리키도록 연결된 데이터 구조입니다. 이 자료구조는 다양한 알고리즘 문제 해결에서 유용하게 사용될 수 있으며, 이번 포스팅에서는 C 언어로 원형 연결 리스트를 활용하여 데이터를 정렬하는 방법을 단계별로 설명하겠습니다.

1. 원형 연결 리스트란?

원형 연결 리스트는 일반 연결 리스트와 유사하지만, 마지막 노드가 첫 번째 노드를 가리키는 차이가 있습니다. 이를 통해 리스트의 끝과 시작을 쉽게 순환할 수 있습니다.

2. C 언어에서 원형 연결 리스트 구현

노드 구조 정의

먼저, 원형 연결 리스트의 노드를 정의합니다. 노드는 데이터를 저장하고 다음 노드를 가리키는 포인터를 포함합니다.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

typedef struct Node Node;

노드 삽입 함수

리스트의 끝에 노드를 삽입하는 함수를 구현합니다.

void insertEnd(Node** head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    Node* temp = *head;
    newNode->data = data;
    newNode->next = *head;

    if (*head == NULL) {
        *head = newNode;
    } else {
        while (temp->next != *head) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

리스트 출력 함수

리스트의 모든 노드를 순회하여 데이터를 출력하는 함수를 구현합니다.

void printList(Node* head) {
    Node* temp = head;
    if (head != NULL) {
        do {
            printf("%d ", temp->data);
            temp = temp->next;
        } while (temp != head);
    }
}

3. 원형 연결 리스트 정렬

정렬 알고리즘 선택

정렬 알고리즘으로 버블 정렬을 사용합니다. 버블 정렬은 인접한 두 노드를 비교하여 교환하는 방식으로, 원형 연결 리스트에서도 쉽게 구현할 수 있습니다.

버블 정렬 함수 구현

다음은 원형 연결 리스트에 버블 정렬을 적용하는 코드입니다.

void sortList(Node* head) {
    if (head == NULL) {
        return;
    }

    Node* current;
    Node* next;
    int tempData;
    int swapped;

    do {
        swapped = 0;
        current = head;

        while (current->next != head) {
            next = current->next;

            if (current->data > next->data) {
                tempData = current->data;
                current->data = next->data;
                next->data = tempData;
                swapped = 1;
            }
            current = current->next;
        }
    } while (swapped);
}

4. 전체 코드

전체 코드를 하나로 합쳐 봅니다.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

typedef struct Node Node;

void insertEnd(Node** head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    Node* temp = *head;
    newNode->data = data;
    newNode->next = *head;

    if (*head == NULL) {
        *head = newNode;
    } else {
        while (temp->next != *head) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

void printList(Node* head) {
    Node* temp = head;
    if (head != NULL) {
        do {
            printf("%d ", temp->data);
            temp = temp->next;
        } while (temp != head);
    }
    printf("\n");
}

void sortList(Node* head) {
    if (head == NULL) {
        return;
    }

    Node* current;
    Node* next;
    int tempData;
    int swapped;

    do {
        swapped = 0;
        current = head;

        while (current->next != head) {
            next = current->next;

            if (current->data > next->data) {
                tempData = current->data;
                current->data = next->data;
                next->data = tempData;
                swapped = 1;
            }
            current = current->next;
        }
    } while (swapped);
}

int main() {
    Node* head = NULL;

    insertEnd(&head, 4);
    insertEnd(&head, 2);
    insertEnd(&head, 8);
    insertEnd(&head, 1);
    insertEnd(&head, 5);

    printf("Original List: ");
    printList(head);

    sortList(head);

    printf("Sorted List: ");
    printList(head);

    return 0;
}

결론

원형 연결 리스트는 일반 연결 리스트와 달리 마지막 노드가 첫 번째 노드를 가리키는 특성이 있습니다. C 언어를 사용하여 원형 연결 리스트를 구현하고, 버블 정렬 알고리즘을 적용하여 데이터를 정렬하는 방법을 알아보았습니다. 이 가이드를 통해 원형 연결 리스트를 효과적으로 활용하여 다양한 문제를 해결할 수 있기를 바랍니다.

더 많은 정보를 원하시면 GeeksforGeeks와 Programiz와 같은 리소스를 참조하세요.