Xóa tất cả các nút số nguyên tố khỏi danh sách liên kết đơn trong C++

Giới thiệu

Trong hướng dẫn này, chúng ta sẽ học cách xóa tất cả các nút có giá trị là số nguyên tố khỏi một danh sách liên kết đơn (singly linked list) bằng C++.

Các bước thực hiện

1. Định nghĩa cấu trúc Node với dữ liệu (data) và con trỏ tiếp theo (next).
2. Viết hàm chèn nút vào danh sách liên kết đơn.
3. Khởi tạo danh sách với dữ liệu mẫu.
4. Duyệt qua danh sách, kiểm tra xem dữ liệu của nút hiện tại có phải số nguyên tố hay không.
5. Nếu là số nguyên tố, xóa nút đó.
6. Viết hàm xóa nút, xử lý 3 trường hợp:
   • Nút là nút đầu (head): di chuyển head sang nút tiếp theo.
   • Nút là nút giữa: liên kết nút trước với nút sau.
   • Nút là nút cuối: xóa liên kết của nút trước.

Mã nguồn ví dụ

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

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

void insertNode(Node** head_ref, int new_data) {
    Node* new_node = (Node*)malloc(sizeof(struct 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 deleteNode(Node** head_ref, Node* del) {
    Node* temp = *head_ref;
    if (*head_ref == NULL || del == NULL) return;
    if (*head_ref == del) {
        *head_ref = del->next;
    } else {
        while (temp->next != del) temp = temp->next;
        temp->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 << "Danh sách trước khi xóa:" << endl;
    printLinkedList(head);
    deletePrimeNodes(&head);
    cout << "\nDanh sách sau khi xóa:" << endl;
    printLinkedList(head);
    return 0;
}

Kết quả đầu ra

Danh sách trước khi xóa: 6 -> 5 -> 4 -> 3 -> 2 -> 1 ->
Danh sách sau khi xóa: 6 -> 4 -> 1 ->

Kết luận

Chương trình đã xóa thành công các nút có giá trị là số nguyên tố (2, 3, 5) khỏi danh sách liên kết đơn. Nếu bạn có thắc mắc, hãy để lại bình luận bên dưới.