Xóa tất cả các nút số nguyên tố khỏi danh sách liên kết đôi 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 đôi (doubly 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), con trỏ trước (prev) và con trỏ sau (next).
2. Viết hàm chèn nút vào danh sách liên kết đôi.
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 *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 << "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 đôi. Nếu bạn có thắc mắc, hãy để lại bình luận bên dưới.