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

Chào mừng trở lại với series blog về C++! Hôm nay, chúng ta sẽ khám phá một kỹ thuật cực kỳ mạnh mẽ và phổ biến trong lập trình: kết hợp Struct với Danh sách liên kết (Linked List). Tại sao lại cần kết hợp chúng? Đơn giản là bởi vì Struct giúp chúng ta đóng gói dữ liệu có liên quan lại với nhau thành một thể thống nhất, còn Danh sách liên kết lại cung cấp một cấu trúc dữ liệu động và linh hoạt, cho phép chúng ta thêm bớt phần tử một cách hiệu quả mà không bị giới hạn bởi kích thước cố định như mảng.

Khi kết hợp hai thứ này, chúng ta có thể tạo ra các danh sách mà mỗi phần tử (hay còn gọi là node) không chỉ đơn thuần là một số hay một ký tự, mà là một đối tượng phức tạp chứa nhiều thông tin khác nhau. Nghe hấp dẫn đúng không? Hãy cùng đi sâu vào chi tiết!

Struct trong C++: Nhóm Gói Dữ liệu

Trước khi kết hợp, chúng ta hãy nhắc lại một chút về Struct. Struct trong C++ (tương tự như struct trong C hoặc lớp đơn giản trong C++) cho phép bạn định nghĩa một kiểu dữ liệu tùy chỉnh bằng cách nhóm nhiều biến có kiểu dữ liệu khác nhau lại dưới một tên duy nhất.

Ví dụ, nếu bạn muốn lưu trữ thông tin về một sinh viên, bạn cần tên, tuổi, mã số sinh viên, điểm trung bình, v.v. Thay vì quản lý từng biến riêng lẻ, bạn có thể gom chúng lại trong một Struct:

#include <string>

struct SV {
    string t;
    int tu;
    string ma;
    double d;
};

Giải thích: Đoạn code này định nghĩa một khuôn mẫu tên là SV. Mỗi biến kiểu SV sẽ chứa bốn thành phần (t, tu, ma, d). Điều này giúp mã nguồn của bạn trở nên có tổ chức và dễ đọc hơn rất nhiều.

Bạn có thể tạo và sử dụng các biến kiểu SV như sau:

#include <iostream>
#include <string>

struct SV {
    string t;
    int tu;
    string ma;
    double d;
};

int main() {
    SV s1;

    s1.t = "Nguyen Van A";
    s1.tu = 20;
    s1.ma = "SV001";
    s1.d = 8.5;

    cout << "Thong tin Sinh vien:" << endl;
    cout << "Ten: " << s1.t << endl;
    cout << "Tuoi: " << s1.tu << endl;
    cout << "Ma so: " << s1.ma << endl;
    cout << "Diem trung binh: " << s1.d << endl;

    return 0;
}

Output:

Thong tin Sinh vien:
Ten: Nguyen Van A
Tuoi: 20
Ma so: SV001
Diem trung binh: 8.5

Giải thích: Chúng ta tạo một biến s1 kiểu SV, sau đó dùng toán tử dấu chấm (.) để truy cập và gán giá trị cho từng thành phần bên trong nó. Việc truy xuất cũng tương tự. Đơn giản phải không nào?

Danh sách liên kết: Cấu trúc Động và Linh hoạt

Danh sách liên kết là một cấu trúc dữ liệu trong đó các phần tử (gọi là node) được liên kết với nhau bằng các con trỏ. Mỗi node thường chứa hai phần: phần dữ liệu và một con trỏ trỏ đến node tiếp theo trong danh sách. Node cuối cùng sẽ có con trỏ nullptr (hoặc NULL trong C) để đánh dấu điểm kết thúc.

Ưu điểm lớn nhất của danh sách liên kết so với mảng là khả năng thay đổi kích thước động. Bạn không cần biết trước số lượng phần tử tối đa. Việc thêm hoặc xóa phần tử ở vị trí bất kỳ (đặc biệt là ở đầu danh sách) có thể hiệu quả hơn so với mảng.

Về mặt cấu trúc, một node cơ bản trong danh sách liên kết đơn sẽ trông như thế này:

struct Node {
    int dl;
    Node* tiep;
};

Giải thích: dl là nơi lưu trữ thông tin thực tế của node, và tiep là con trỏ đặc biệt chỉ đến node "hàng xóm" đứng sau nó.

Sức mạnh khi Kết hợp: Struct là Dữ liệu của Node!

Đây chính là lúc mọi thứ trở nên thú vị. Chúng ta đã biết Struct có thể nhóm nhiều loại dữ liệu, và Danh sách liên kết cần dữ liệu trong mỗi node. Vậy tại sao không dùng chính Struct làm phần dữ liệu của Node?

Thay vì int data; trong Struct Node cơ bản ở trên, chúng ta sẽ thay thế nó bằng Struct SV mà chúng ta đã định nghĩa!

#include <string>

struct SV {
    string t;
    int tu;
    string ma;
    double d;
};

struct Node {
    SV dl;
    Node* tiep;

    Node(SV s) : dl(s), tiep(nullptr) {}
};

Giải thích:

  • Struct SV vẫn giữ nguyên vai trò nhóm thông tin sinh viên.
  • Struct Node bây giờ có một thành phần tên là dl với kiểu là SV.
  • Thành phần tiep vẫn là con trỏ Node*, dùng để liên kết các node lại với nhau.
  • Constructor Node(SV s) là một tiện ích nhỏ, cho phép chúng ta tạo một Node mới và khởi tạo ngay phần dl của nó bằng một đối tượng SV, đồng thời đặt tiep ban đầu là nullptr.

Bây giờ, mỗi node trong danh sách liên kết của chúng ta không chỉ chứa một giá trị đơn lẻ mà là cả một bộ thông tin đầy đủ về một sinh viên!

Xây dựng và Duyệt Danh sách Liên kết (với Struct)

Hãy xem cách chúng ta có thể tạo ra một danh sách liên kết đơn giản chứa thông tin sinh viên và sau đó duyệt qua nó.

#include <iostream>
#include <string>

struct SV {
    string t;
    int tu;
    string ma;
    double d;
};

struct Node {
    SV dl;
    Node* tiep;

    Node(SV s) : dl(s), tiep(nullptr) {}
};

int main() {
    SV s1 = {"Nguyen Van A", 20, "SV001", 8.5};
    SV s2 = {"Tran Thi B", 21, "SV002", 9.0};
    SV s3 = {"Le Van C", 22, "SV003", 7.8};

    Node* dau = new Node(s1);
    Node* hai = new Node(s2);
    Node* ba = new Node(s3);

    dau->tiep = hai;
    hai->tiep = ba;
    ba->tiep = nullptr;

    Node* hienTai = dau;
    cout << "--- Danh sach Sinh vien ---" << endl;
    while (hienTai != nullptr) {
        cout << "Ten: " << hienTai->dl.t
                  << ", Tuoi: " << hienTai->dl.tu
                  << ", Ma so: " << hienTai->dl.ma
                  << ", Diem: " << hienTai->dl.d << endl;

        hienTai = hienTai->tiep;
    }
    cout << "-------------------------" << endl;

    hienTai = dau;
    Node* tiepTheo = nullptr;
    while (hienTai != nullptr) {
        tiepTheo = hienTai->tiep;
        delete hienTai;
        hienTai = tiepTheo;
    }
    dau = nullptr;

    return 0;
}

Output:

--- Danh sach Sinh vien ---
Ten: Nguyen Van A, Tuoi: 20, Ma so: SV001, Diem: 8.5
Ten: Tran Thi B, Tuoi: 21, Ma so: SV002, Diem: 9
Ten: Le Van C, Tuoi: 22, Ma so: SV003, Diem: 7.8
-------------------------

Giải thích:

  1. Chúng ta khởi tạo ba đối tượng SV với dữ liệu cụ thể.
  2. Sử dụng new để cấp phát bộ nhớ động cho ba Node mới. Mỗi Node được tạo ra và ngay lập tức chứa dữ liệu của một SV nhờ vào constructor.
  3. Các con trỏ tiep được gán để liên kết các node theo đúng thứ tự: dau trỏ đến hai, hai trỏ đến ba. ba->tiep mặc định là nullptr nhờ constructor.
  4. Để duyệt, chúng ta dùng một con trỏ phụ hienTai, bắt đầu từ dau. Vòng lặp while (hienTai != nullptr) sẽ chạy cho đến khi hienTai vượt ra ngoài node cuối cùng.
  5. Bên trong vòng lặp, chúng ta truy cập dữ liệu SV trong node hiện tại bằng hienTai->dl. Vì hienTai->dl là một Struct SV, chúng ta dùng toán tử . (chấm) để truy cập các thành phần của nó: hienTai->dl.t, hienTai->dl.tu, v.v.
  6. Sau khi xử lý node hiện tại, hienTai = hienTai->tiep; di chuyển con trỏ đến node tiếp theo.
  7. Cuối cùng, chúng ta phải giải phóng bộ nhớ đã cấp phát bằng new sử dụng delete. Vì danh sách liên kết là động, việc giải phóng cần được thực hiện cẩn thận, thường bằng cách đi qua từng node và gọi delete cho nó. Đoạn code giải phóng sau vòng lặp while thực hiện đúng điều này. Đừng bỏ qua bước này trong các ứng dụng thực tế!

Thêm Node vào Danh sách (với Struct)

Một thao tác phổ biến với danh sách liên kết là thêm node mới. Hãy viết một hàm nhỏ để thêm một sinh viên mới vào đầu danh sách.

#include <iostream>
#include <string>

struct SV {
    string t;
    int tu;
    string ma;
    double d;
};

struct Node {
    SV dl;
    Node* tiep;

    Node(SV s) : dl(s), tiep(nullptr) {}
};

void themDau(Node*& dau, SV s) {
    Node* moi = new Node(s);
    moi->tiep = dau;
    dau = moi;
}

void inDS(Node* dau) {
    Node* hienTai = dau;
    while (hienTai != nullptr) {
        cout << "Ten: " << hienTai->dl.t
                  << ", Tuoi: " << hienTai->dl.tu
                  << ", Ma so: " << hienTai->dl.ma
                  << ", Diem: " << hienTai->dl.d << endl;
        hienTai = hienTai->tiep;
    }
}

void giaiPhong(Node*& dau) {
    Node* hienTai = dau;
    Node* tiepTheo = nullptr;
    while (hienTai != nullptr) {
        tiepTheo = hienTai->tiep;
        delete hienTai;
        hienTai = tiepTheo;
    }
    dau = nullptr;
}

int main() {
    Node* dau = nullptr;

    themDau(dau, {"Le Van C", 22, "SV003", 7.8});
    themDau(dau, {"Tran Thi B", 21, "SV002", 9.0});
    themDau(dau, {"Nguyen Van A", 20, "SV001", 8.5});

    cout << "--- Danh sach Sinh vien sau khi them ---" << endl;
    inDS(dau);
    cout << "--------------------------------------" << endl;

    giaiPhong(dau);

    return 0;
}

Output:

--- Danh sach Sinh vien sau khi them ---
Ten: Nguyen Van A, Tuoi: 20, Ma so: SV001, Diem: 8.5
Ten: Tran Thi B, Tuoi: 21, Ma so: SV002, Diem: 9
Ten: Le Van C, Tuoi: 22, Ma so: SV003, Diem: 7.8
--------------------------------------

Giải thích:

  • Hàm themDau nhận con trỏ dau bằng tham chiếu (Node*&). Điều này rất quan trọng vì hàm cần thay đổi giá trị của con trỏ dau gốc (trong hàm main) để nó trỏ đến node mới.
  • Hàm tạo một moi bằng new.
  • Con trỏ tiep của moi được gán bằng giá trị dau hiện tại. Điều này làm cho moi trỏ đến node mà trước đây là đầu danh sách.
  • Cuối cùng, dau được cập nhật để trỏ đến moi. Bây giờ moi chính là đầu danh sách mới.
  • Lưu ý thứ tự xuất hiện trong inDS sẽ ngược lại với thứ tự gọi themDau vì chúng ta luôn thêm vào đầu.
  • Hàm inDS và giaiPhong được thêm vào để giúp quản lý danh sách một cách có cấu trúc hơn. Hàm giaiPhong nhận dau bằng tham chiếu để có thể đặt nó về nullptr sau khi giải phóng.

Tại sao lại Kết hợp?

Việc kết hợp Struct và Danh sách liên kết mang lại những lợi ích đáng kể:

  1. Tổ chức dữ liệu: Struct giúp gom nhóm các thông tin liên quan của mỗi phần tử danh sách, làm cho code sạch sẽ và dễ quản lý hơn nhiều so với việc lưu trữ dữ liệu trong các mảng song song hoặc cấu trúc phẳng.
  2. Linh hoạt về kích thước: Danh sách liên kết cho phép bạn xử lý số lượng phần tử thay đổi mà không cần cấp phát trước một lượng bộ nhớ lớn không cần thiết.
  3. Hiệu quả cho các thao tác chèn/xóa (ở đầu/giữa): Đối với danh sách liên kết đơn, việc chèn hoặc xóa ở đầu danh sách là cực kỳ nhanh (thường là O(1)). Chèn/xóa ở giữa cũng hiệu quả hơn mảng vì bạn chỉ cần điều chỉnh vài con trỏ thay vì dịch chuyển toàn bộ phần tử còn lại.
  4. Nền tảng cho cấu trúc dữ liệu khác: Sự kết hợp này là cơ sở để xây dựng nhiều cấu trúc dữ liệu phức tạp hơn như Stack, Queue, danh sách liên kết đôi (doubly linked list), danh sách liên kết vòng (circular linked list), và thậm chí cả các cấu trúc dựa trên con trỏ khác như cây (trees) hoặc đồ thị (graphs), nơi mỗi "đỉnh" hoặc "nút" có thể chứa dữ liệu phức tạp được định nghĩa bằng Struct.

Comments

There are no comments at the moment.