Bài 33.5: Bài tập thực hành danh sách liên kết trong C++

Chào mừng quay trở lại với series C++!

Sau khi đã cùng nhau tìm hiểu lý thuyết đằng sau danh sách liên kết (Linked List) - một trong những cấu trúc dữ liệu cơ bản nhưng cực kỳ quan trọng, giờ là lúc chúng ta xắn tay áo lên và bắt tay vào thực hành! Lý thuyết chỉ là nền tảng, việc thao tác trực tiếp với các con trỏ, tạo, sửa, xóa các nút mới là cách tốt nhất để nắm vững khái niệm này.

Bài viết này sẽ tập trung vào một số bài tập thực tế và cơ bản nhất khi làm việc với danh sách liên kết đơn trong C++. Chúng ta sẽ đi qua từng bài tập, phân tích logic và cung cấp code minh họa chi tiết.

Trước khi bắt đầu, hãy nhắc lại cấu trúc cơ bản của một nút (Node) trong danh sách liên kết đơn mà chúng ta sẽ sử dụng:

#include <iostream>

struct Node {
    int gt;
    Node* tiep;

    Node(int g_tri) : gt(g_tri), tiep(nullptr) {}
};

Mỗi Node chứa dữ liệu (data) và một con trỏ (next) trỏ đến nút tiếp theo. Con trỏ next của nút cuối cùng trong danh sách sẽ trỏ đến nullptr để đánh dấu điểm kết thúc. Danh sách được quản lý bằng một con trỏ head (hoặc first) trỏ đến nút đầu tiên. Nếu danh sách trống, head sẽ là nullptr.

Bây giờ, hãy đi vào các bài tập thực hành!

Bài tập 1: Duyệt (Traversal) và In danh sách

Bài tập đầu tiên và cơ bản nhất là duyệt qua toàn bộ danh sách và in ra giá trị của từng nút. Điều này giúp chúng ta hình dung được trạng thái hiện tại của danh sách.

Logic:

Bắt đầu với một con trỏ tạm thời (ví dụ: current) trỏ đến nút đầu tiên (head).
Lặp lại quá trình:
- In ra giá trị của nút hiện tại (current->data).
- Di chuyển con trỏ tạm thời đến nút kế tiếp (current = current->next).
Dừng lại khi con trỏ tạm thời trở thành nullptr (nghĩa là đã đi qua nút cuối cùng).

Code minh họa:

void printList(Node* dau) {
    Node* ht = dau;
    cout << "Danh sach: ";
    while (ht != nullptr) {
        cout << ht->gt;
        if (ht->tiep != nullptr) {
            cout << " -> ";
        }
        ht = ht->tiep;
    }
    cout << " -> nullptr" << endl;
}

Giải thích code:

Hàm nhận vào con trỏ head (truyền theo giá trị vì ta không sửa đổi head gốc, chỉ duyệt).
Node* current = head;: Khởi tạo con trỏ current để đi theo danh sách, bắt đầu từ head.
while (current != nullptr): Vòng lặp tiếp tục miễn là current vẫn trỏ đến một nút hợp lệ (chưa phải là nullptr).
cout << current->data;: Truy cập và in ra dữ liệu của nút hiện tại.
if (current->next != nullptr): Kiểm tra xem có phải nút cuối cùng chưa để in mũi tên cho đúng.
current = current->next;: Đây là bước quan trọng để di chuyển đến nút kế tiếp. Ta gán current bằng giá trị của con trỏ next trong nút hiện tại.

Bài tập 2: Chèn một nút vào đầu danh sách

Chèn một nút mới vào vị trí đầu tiên là một thao tác khá đơn giản trong danh sách liên kết đơn.

Logic:

Tạo một nút mới với dữ liệu cần chèn.
Thiết lập con trỏ next của nút mới này trỏ đến nút hiện tại đang là đầu danh sách (head).
Cập nhật con trỏ head để trỏ đến nút mới này.

Code minh họa:

void insertAtBeginning(Node*& dau, int g_tri_moi) {
    Node* nut_moi = new Node(g_tri_moi);
    nut_moi->tiep = dau;
    dau = nut_moi;
    cout << "Da chen " << g_tri_moi << " vao dau danh sach." << endl;
}

Giải thích code:

Hàm nhận vào Node*& head: Đây là điểm mấu chốt! Chúng ta cần truyền con trỏ head theo tham chiếu (&) vì thao tác chèn vào đầu sẽ làm thay đổi chính giá trị của con trỏ head (nó sẽ trỏ đến một vị trí bộ nhớ khác). Nếu truyền theo giá trị, sự thay đổi chỉ xảy ra trong hàm và không ảnh hưởng đến con trỏ head bên ngoài.
Node* newNode = new Node(newData);: Tạo một đối tượng Node mới trên heap sử dụng new và khởi tạo dữ liệu cho nó.
newNode->next = head;: Con trỏ next của nút mới giờ đây sẽ trỏ đến nút mà head đang trỏ tới (nút đầu tiên cũ).
head = newNode;: Cập nhật con trỏ head toàn cục để nó trỏ đến newNode, biến newNode thành nút đầu tiên mới.

Bài tập 3: Chèn một nút vào cuối danh sách

Chèn vào cuối danh sách phức tạp hơn một chút so với chèn vào đầu, vì ta cần phải tìm đến nút cuối cùng hiện tại.

Logic:

Tạo một nút mới với dữ liệu cần chèn.
Kiểm tra xem danh sách có trống không (head == nullptr). Nếu có, nút mới chính là head.
Nếu danh sách không trống, duyệt qua danh sách bằng một con trỏ tạm thời cho đến khi tìm thấy nút cuối cùng (nút mà con trỏ next của nó là nullptr).
Thiết lập con trỏ next của nút cuối cùng này trỏ đến nút mới.

Code minh họa:

void insertAtEnd(Node*& dau, int g_tri_moi) {
    Node* nut_moi = new Node(g_tri_moi);

    if (dau == nullptr) {
        dau = nut_moi;
        cout << "Da chen " << g_tri_moi << " vao dau danh sach (danh sach ban dau trong)." << endl;
        return;
    }

    Node* cuoi = dau;
    while (cuoi->tiep != nullptr) {
        cuoi = cuoi->tiep;
    }

    cuoi->tiep = nut_moi;

    cout << "Da chen " << g_tri_moi << " vao cuoi danh sach." << endl;
}

Giải thích code:

Hàm nhận vào Node*& head (truyền tham chiếu) vì head có thể bị thay đổi nếu danh sách ban đầu trống.
if (head == nullptr): Xử lý trường hợp danh sách rỗng. Nút mới trở thành head duy nhất.
Node* last = head;: Khởi tạo con trỏ last để duyệt.
while (last->next != nullptr): Vòng lặp này duyệt cho đến khi last trỏ đến nút cuối cùng (nút mà con trỏ next của nó là nullptr).
last->next = newNode;: Gán con trỏ next của nút cuối cùng hiện tại trỏ đến newNode, thêm newNode vào cuối danh sách. Con trỏ next mặc định của newNode là nullptr, nên nó tự động trở thành nút cuối mới.

Bài tập 4: Xóa một nút theo giá trị

Xóa một nút là thao tác phức tạp nhất trong số các thao tác cơ bản, đòi đòi phải quản lý các con trỏ một cách cẩn thận để không làm mất phần còn lại của danh sách và giải phóng bộ nhớ đúng cách. Chúng ta sẽ xóa lần xuất hiện đầu tiên của một giá trị.

Logic:

Kiểm tra xem danh sách có trống không. Nếu trống, không làm gì cả.
Kiểm tra xem nút cần xóa có phải là nút đầu tiên (head) không. Nếu đúng:
- Lưu lại con trỏ head hiện tại vào một biến tạm.
- Cập nhật head trỏ đến nút kế tiếp (head->next).
- Giải phóng bộ nhớ của nút tạm đã lưu.
- Kết thúc hàm.
Nếu nút cần xóa không phải là head:
- Duyệt qua danh sách bằng hai con trỏ: current (nút hiện tại) và previous (nút ngay trước current).
- Trong khi duyệt, di chuyển previous theo sau current.
- Dừng lại khi current là nullptr (không tìm thấy giá trị) hoặc current->data bằng giá trị cần xóa.
Nếu không tìm thấy giá trị (current == nullptr), không làm gì cả.
Nếu tìm thấy giá trị (current->data == valueToDelete):
- Cập nhật con trỏ next của nút previous để trỏ đến nút kế tiếp của current (previous->next = current->next). Điều này làm nút current bị "bỏ qua" và loại khỏi danh sách.
- Giải phóng bộ nhớ của nút current.

Code minh họa:

void deleteNodeByValue(Node*& dau, int g_tri_xoa) {
    if (dau == nullptr) {
        cout << "Danh sach trống, khong the xoa." << endl;
        return;
    }

    if (dau->gt == g_tri_xoa) {
        Node* tam = dau;
        dau = dau->tiep;
        delete tam;
        cout << "Da xoa nut dau co gia tri " << g_tri_xoa << "." << endl;
        return;
    }

    Node* ht = dau;
    Node* truoc = nullptr;

    while (ht != nullptr && ht->gt != g_tri_xoa) {
        truoc = ht;
        ht = ht->tiep;
    }

    if (ht == nullptr) {
        cout << "Khong tim thay gia tri " << g_tri_xoa << " de xoa." << endl;
        return;
    }

    truoc->tiep = ht->tiep;
    delete ht;

    cout << "Da xoa nut co gia tri " << g_tri_xoa << "." << endl;
}

Giải thích code:

Hàm nhận Node*& head (tham chiếu) vì head có thể thay đổi nếu nút đầu tiên bị xóa.
Kiểm tra trường hợp danh sách trống và trường hợp nút cần xóa là head được xử lý riêng rẽ ở đầu hàm để đơn giản hóa logic xóa ở giữa/cuối.
Trong vòng while: Chúng ta dùng hai con trỏ current và previous. previous luôn trỏ đến nút ngay trước nút mà current đang trỏ tới. Điều này rất quan trọng để khi tìm thấy nút cần xóa (current), ta có thể nối nút previous với nút kế tiếp của current.
if (current == nullptr): Nếu vòng lặp kết thúc mà current là nullptr, nghĩa là ta đã duyệt hết danh sách nhưng không tìm thấy giá trị cần xóa.
previous->next = current->next;: Đây là bước then chốt để loại bỏ current khỏi danh sách. Con trỏ next của nút trước (previous) giờ đây trỏ đến nút mà current đang trỏ tới (current->next), bỏ qua current.
delete current;: Quan trọng! Sau khi nút đã bị loại khỏi danh sách, ta phải giải phóng bộ nhớ mà nó chiếm dụng bằng toán tử delete để tránh rò rỉ bộ nhớ (memory leak).

Bài tập 5: Đếm số nút trong danh sách

Đếm số lượng nút là một bài tập đơn giản, chỉ cần duyệt qua danh sách và tăng biến đếm.

Logic:

Khởi tạo biến đếm bằng 0.
Duyệt qua danh sách từ head đến cuối.
Với mỗi nút gặp, tăng biến đếm lên 1.
Trả về giá trị cuối cùng của biến đếm.

Code minh họa:

int countNodes(Node* dau) {
    int dem = 0;
    Node* ht = dau;

    while (ht != nullptr) {
        dem++;
        ht = ht->tiep;
    }

    return dem;
}

Giải thích code:

Hàm nhận Node* head (truyền giá trị) vì không cần thay đổi cấu trúc danh sách.
Sử dụng một vòng lặp while tương tự như duyệt để đi qua từng nút.
Biến count được tăng lên mỗi lần vòng lặp thực hiện, tức là mỗi lần xử lý một nút.
Khi current trở thành nullptr, vòng lặp kết thúc và giá trị count cuối cùng chính là số nút trong danh sách.

Ví dụ tổng hợp và Quản lý bộ nhớ

Để thấy rõ cách các hàm này hoạt động cùng nhau, chúng ta sẽ viết một hàm main nhỏ để thực hiện vài thao tác.

Một điều cực kỳ quan trọng khi làm việc với danh sách liên kết trong C++ là quản lý bộ nhớ. Khi chúng ta tạo các nút bằng new, chúng được cấp phát trên heap. Chúng ta phải giải phóng bộ nhớ này bằng delete khi không cần đến nữa để tránh rò rỉ bộ nhớ. Đối với danh sách liên kết, điều này thường có nghĩa là khi danh sách không còn được sử dụng, ta cần duyệt và delete từng nút.

int main() {
    Node* dau = nullptr;

    cout << "*** Chen vao cuoi ***" << endl;
    insertAtEnd(dau, 10);
    printList(dau);
    insertAtEnd(dau, 20);
    printList(dau);
    insertAtEnd(dau, 30);
    printList(dau);

    cout << "\n*** Chen vao dau ***" << endl;
    insertAtBeginning(dau, 5);
    printList(dau);
    insertAtBeginning(dau, 1);
    printList(dau);

    cout << "\n*** Dem nut ***" << endl;
    cout << "So nut trong danh sach: " << countNodes(dau) << endl;

    cout << "\n*** Xoa nut theo gia tri ***" << endl;
    deleteNodeByValue(dau, 20);
    printList(dau);

    deleteNodeByValue(dau, 1);
    printList(dau);

    deleteNodeByValue(dau, 30);
    printList(dau);

    deleteNodeByValue(dau, 5);
    printList(dau);

    deleteNodeByValue(dau, 10);
    printList(dau);

    deleteNodeByValue(dau, 100);
    printList(dau);

    cout << "\n*** Giai phong bo nho con lai (neu co) ***" << endl;
    Node* ht = dau;
    while (ht != nullptr) {
        Node* tiep_theo = ht->tiep;
        cout << "Dang giai phong nut co gia tri: " << ht->gt << endl;
        delete ht;
        ht = tiep_theo;
    }
    dau = nullptr;
    cout << "Da giai phong het bo nho." << endl;

    printList(dau);

    return 0;
}

Output:

*** Chen vao cuoi ***
Da chen 10 vao dau danh sach (danh sach ban dau trong).
Danh sach: 10 -> nullptr
Da chen 20 vao cuoi danh sach.
Danh sach: 10 -> 20 -> nullptr
Da chen 30 vao cuoi danh sach.
Danh sach: 10 -> 20 -> 30 -> nullptr

*** Chen vao dau ***
Da chen 5 vao dau danh sach.
Danh sach: 5 -> 10 -> 20 -> 30 -> nullptr
Da chen 1 vao dau danh sach.
Danh sach: 1 -> 5 -> 10 -> 20 -> 30 -> nullptr

*** Dem nut ***
So nut trong danh sach: 5

*** Xoa nut theo gia tri ***
Da xoa nut co gia tri 20.
Danh sach: 1 -> 5 -> 10 -> 30 -> nullptr
Da xoa nut dau co gia tri 1.
Danh sach: 5 -> 10 -> 30 -> nullptr
Da xoa nut co gia tri 30.
Danh sach: 5 -> 10 -> nullptr
Da xoa nut dau co gia tri 5.
Danh sach: 10 -> nullptr
Da xoa nut dau co gia tri 10.
Danh sach: nullptr
Khong tim thay gia tri 100 de xoa.
Danh sach: nullptr

*** Giai phong bo nho con lai (neu co) ***
Da giai phong het bo nho.
Danh sach: nullptr

Lưu ý về quản lý bộ nhớ: Trong ví dụ trên, các thao tác chèn và xóa đã được viết để quản lý bộ nhớ trong từng thao tác. Tuy nhiên, một cách tiếp cận chắc chắn hơn cho danh sách liên kết là có một hàm riêng (hoặc destructor nếu dùng class) để duyệt toàn bộ danh sách và xóa tất cả các nút còn lại khi không cần danh sách nữa. Phần cuối của hàm main minh họa cách thực hiện việc giải phóng bộ nhớ còn lại này bằng cách duyệt từ head đến cuối và gọi delete cho từng nút. Luôn nhớ giải phóng bộ nhớ đã cấp phát bằng new!

Comments

There are no comments at the moment.