ลบโหนดจำนวนเฉพาะทั้งหมดจาก Doubly Linked List ใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะเรียนรู้วิธีการลบโหนดที่มีค่าเป็นจำนวนเฉพาะ (Prime Number) ทั้งหมดออกจาก Doubly Linked List (รายการเชื่อมโยงสองทิศทาง) โดยใช้ภาษา C++

ขั้นตอนการแก้ปัญหา

1. สร้างโครงสร้าง (struct) Node ที่มีข้อมูล (data), ตัวชี้ก่อนหน้า (prev) และตัวชี้ถัดไป (next)
2. เขียนฟังก์ชันสำหรับแทรกโหนดใหม่เข้าไปใน Doubly Linked List
3. สร้าง Doubly Linked List ตัวอย่างพร้อมข้อมูลทดสอบ
4. วนลูปผ่านทุกโหนดในรายการ ตรวจสอบว่าข้อมูลของโหนดปัจจุบันเป็นจำนวนเฉพาะหรือไม่
5. หากเป็นจำนวนเฉพาะ ให้ลบโหนดนั้นออก
6. เขียนฟังก์ชันลบโหนดโดยพิจารณา 3 กรณีหลัก:
   • โหนดเป็นหัว (head) - ย้ายหัวไปที่โหนดถัดไป
   • โหนดอยู่กลาง - เชื่อมโหนดก่อนหน้ากับโหนดถัดไป
   • โหนดเป็นท้าย - ตัดการเชื่อมโยงของโหนดก่อนหน้า

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

#include <bits/stdc++.h>
using namespace std;

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

void insertNode(Node** head_ref, int new_data) {
    Node* new_node = (Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->prev = NULL;
    new_node->next = (*head_ref);
    if ((*head_ref) != NULL) {
        (*head_ref)->prev = new_node;
    }
    (*head_ref) = new_node;
}

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i = i + 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

void deleteNode(Node** head_ref, Node* del) {
    if (*head_ref == NULL || del == NULL) return;
    
    if (*head_ref == del) {
        *head_ref = del->next;
    }
    if (del->next != NULL) {
        del->next->prev = del->prev;
    }
    if (del->prev != NULL) {
        del->prev->next = del->next;
    }
    free(del);
}

void deletePrimeNodes(Node** head_ref) {
    Node* temp = *head_ref;
    Node* next;
    while (temp != NULL) {
        next = temp->next;
        if (isPrime(temp->data)) {
            deleteNode(head_ref, temp);
        }
        temp = next;
    }
}

void printLinkedList(Node* head) {
    while (head != NULL) {
        cout << head->data << " -> ";
        head = head->next;
    }
}

int main() {
    Node* head = NULL;
    insertNode(&head, 1);
    insertNode(&head, 2);
    insertNode(&head, 3);
    insertNode(&head, 4);
    insertNode(&head, 5);
    insertNode(&head, 6);
    
    cout << "Linked List before deletion:" << endl;
    printLinkedList(head);
    
    deletePrimeNodes(&head);
    
    cout << "\nLinked List after deletion:" << endl;
    printLinkedList(head);
    return 0;
}

ผลลัพธ์

Linked List before deletion: 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 
Linked List after deletion: 6 -> 4 -> 1 ->

สรุป

หากมีคำถามเกี่ยวกับบทช่วยสอนนี้ สามารถถามได้ในส่วนความคิดเห็นครับ