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

บทนำ

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

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

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

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

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

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

void insertNode(Node** head_ref, int new_data) {
    Node* new_node = new Node;
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*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 deleteNonPrimeNodes(Node** head_ref) {
    Node* ptr = *head_ref;
    
    // ลบโหนดหัวที่ไม่ใช่จำนวนเฉพาะ
    while (ptr != NULL && !isPrime(ptr->data)) {
        Node *temp = ptr;
        ptr = ptr->next;
        delete(temp);
    }
    *head_ref = ptr;
    
    if (ptr == NULL) return;
    
    Node *curr = ptr->next;
    while (curr != NULL) {
        if (!isPrime(curr->data)) {
            ptr->next = curr->next;
            delete(curr);
            curr = ptr->next;
        } else {
            ptr = curr;
            curr = curr->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);
    
    deleteNonPrimeNodes(&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: 5 -> 3 -> 2 ->

สรุป

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