แปลงรายการเชื่อมโยงเดี่ยวเป็นรายการเชื่อมโยงแบบวงกลมใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมที่แปลงรายการเชื่อมโยงเดี่ยว (Singly Linked List) เป็นรายการเชื่อมโยงแบบวงกลม (Circular Linked List)

เราจะได้รับรายการเชื่อมโยงเดี่ยวมา ภารกิจของเราคือการนำองค์ประกอบของรายการนั้นไปแปลงเป็นรายการเชื่อมโยงแบบวงกลม

ตัวอย่างโค้ด

#include <bits/stdc++.h>
// โครงสร้างโหนดของรายการเชื่อมโยง
struct Node {
    int data;
    struct Node* next;
};

// แปลงรายการเชื่อมโยงเดี่ยวเป็นรายการเชื่อมโยงแบบวงกลม
struct Node* circular(struct Node* head) {
    struct Node* start = head;
    while (head->next != NULL)
        head = head->next;
    // กำหนด start ให้กับ head->next
    // หาก head->next ชี้ไปที่ NULL
    head->next = start;
    return start;
}

void push(struct Node** head, int data) {
    // สร้างโหนดใหม่
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    // ใส่ข้อมูลในโหนดใหม่
    newNode->data = data;
    newNode->next = (*head);
    (*head) = newNode;
}

// แสดงองค์ประกอบของรายการเชื่อมโยงแบบวงกลม
void print_list(struct Node* node) {
    struct Node* start = node;
    while (node->next != start) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("%d ", node->data);
}

int main() {
    struct Node* head = NULL;
    push(&head, 15);
    push(&head, 14);
    push(&head, 13);
    push(&head, 22);
    push(&head, 17);
    circular(head);
    printf("Display list: \n");
    print_list(head);
    return 0;
}

ผลลัพธ์

Display list: 17 22 13 14 15

คำอธิบาย

ฟังก์ชัน circular() ทำงานโดยการเดินทางไปยังโหนดสุดท้ายของรายการ (ซึ่ง next ชี้ไปที่ NULL) จากนั้นกำหนดให้ next ของโหนดสุดท้ายนี้ชี้กลับไปที่โหนดแรก (start) ทำให้เกิดโครงสร้างวงกลม

ฟังก์ชัน push() ใช้สำหรับเพิ่มโหนดใหม่ที่ด้านหน้าของรายการ (Head Insertion) ซึ่งทำให้ลำดับข้อมูลในตัวอย่างเป็น 17, 22, 13, 14, 15

ฟังก์ชัน print_list() แสดงข้อมูลโดยเริ่มจากโหนดแรกและวนลูปจนกว่าจะกลับมาที่โหนดแรกอีกครั้ง