Bài 32.3: Sắp xếp danh sách bằng Struct trong C++

Chào mừng các bạn quay trở lại với series bài viết về C++ của FullhouseDev!

Chúng ta đã làm quen với việc sắp xếp các kiểu dữ liệu đơn giản như số nguyên (int), số thực (double) hay chuỗi (string) bằng cách sử dụng các thuật toán có sẵn hoặc tự xây dựng. Tuy nhiên, trong thế giới lập trình thực tế, dữ liệu của chúng ta thường phức tạp hơn nhiều. Chúng ta cần quản lý thông tin về sinh viên (gồm tên, điểm, mã số), về sản phẩm (tên, giá, số lượng tồn kho), hay về nhân vật trong game (tên, cấp độ, điểm kinh nghiệm)... Làm thế nào để sắp xếp một danh sách các đối tượng phức tạp như vậy?

Đây chính là lúc Struct và khả năng tùy chỉnh việc sắp xếp phát huy sức mạnh của nó! Trong bài viết này, chúng ta sẽ khám phá cách hiệu quả để sắp xếp một danh sách (cụ thể là vector) chứa các đối tượng struct trong C++.

Tại sao cần sắp xếp danh sách Struct?

Hãy tưởng tượng bạn có một danh sách sinh viên. Bạn có thể muốn:

Sắp xếp danh sách đó theo điểm số từ cao đến thấp để tìm thủ khoa.
Sắp xếp theo tên theo thứ tự bảng chữ cái để dễ tra cứu.
Sắp xếp theo mã số sinh viên.

Mỗi sinh viên là một tập hợp dữ liệu (tên, điểm, mã số...). Một struct trong C++ là cách hoàn hảo để nhóm các thông tin liên quan này lại thành một đơn vị duy nhất.

Định nghĩa Struct cho dữ liệu của chúng ta

Trước hết, hãy định nghĩa một struct đơn giản để đại diện cho một Sinh Viên:

#include <string>

struct SinhVien {
    string ten;
    double diem;
    int maSo; // Ví dụ thêm mã số

    // Constructor (tùy chọn, giúp khởi tạo dễ dàng hơn)
    SinhVien(string t, double d, int m) : ten(t), diem(d), maSo(m) {}

    // Constructor mặc định (quan trọng nếu bạn không cung cấp giá trị khi khai báo)
    SinhVien() = default;
};

Trong ví dụ này, struct SinhVien có ba thành viên: ten, diem, và maSo. Chúng ta cũng thêm một constructor để tiện khởi tạo đối tượng.

Biểu diễn danh sách Struct: `vector`

Cách phổ biến và linh hoạt nhất để lưu trữ một danh sách các đối tượng cùng kiểu trong C++ hiện đại là sử dụng vector.

#include <vector>
#include <string>
#include <iostream> // Để in kết quả

// Định nghĩa Struct SinhVien như trên...
struct SinhVien {
    string ten;
    double diem;
    int maSo;

    SinhVien(string t, double d, int m) : ten(t), diem(d), maSo(m) {}
    SinhVien() = default;

    // Hàm tiện ích để in thông tin sinh viên
    void inThongTin() const {
        cout << "Ma so: " << maSo << ", Ten: " << ten << ", Diem: " << diem << endl;
    }
};

int main() {
    vector<SinhVien> danhSachSV;

    // Thêm vài sinh viên vào danh sách
    danhSachSV.push_back(SinhVien("Nguyen Van A", 8.5, 101));
    danhSachSV.push_back(SinhVien("Le Thi B", 9.2, 105));
    danhSachSV.push_back(SinhVien("Tran Van C", 7.8, 102));
    danhSachSV.push_back(SinhVien("Pham Thi D", 8.5, 104)); // Cung diem voi Van A
    danhSachSV.push_back(SinhVien("Hoang Van E", 9.2, 103)); // Cung diem voi Thi B

    cout << "Danh sach ban dau:" << endl;
    for (const auto& sv : danhSachSV) {
        sv.inThongTin();
    }
    cout << endl;

    return 0;
}

Đoạn code này chỉ đơn thuần tạo một vector và thêm dữ liệu vào. Bây giờ, làm sao để sắp xếp danhSachSV theo điểm số hoặc tên?

Thử thách: `sort` không "biết" cách so sánh Struct của bạn!

Hàm sort trong thư viện <algorithm> là công cụ mạnh mẽ để sắp xếp. Đối với kiểu dữ liệu cơ bản, nó hoạt động mặc định vì C++ đã biết cách so sánh chúng (ví dụ: int < int, string < string).

Tuy nhiên, khi bạn gọi sort trên vector<SinhVien>, trình biên dịch sẽ "bối rối". Nó không có quy tắc mặc định nào để so sánh hai đối tượng SinhVien. Liệu SinhVien A có "nhỏ hơn" SinhVien B không? Dựa vào điểm số? Dựa vào tên? Hay mã số?

Chúng ta cần phải chỉ cho sort biết cách so sánh hai đối tượng SinhVien. Có một vài cách để làm điều này.

Phương pháp 1: Sử dụng Hàm So Sánh (Comparison Function)

Cách phổ biến và linh hoạt nhất là viết một hàm riêng biệt chỉ dùng để so sánh hai đối tượng thuộc struct của bạn. Hàm này sẽ trả về bool và nhận hai đối tượng const tham chiếu làm đối số.

Hàm so sánh phải có cấu trúc bool tenHam(const Kieu& a, const Kieu& b).
Hàm sẽ trả về true nếu a nên đứng trước b trong danh sách đã sắp xếp, và false nếu ngược lại.

Ví dụ: Sắp xếp theo điểm số từ cao đến thấp

Để sắp xếp theo điểm giảm dần, chúng ta muốn sinh viên có điểm cao hơn đứng trước.

#include <vector>
#include <string>
#include <iostream>
#include <algorithm> // Can bo sung thu vien nay!

// Dinh nghia Struct SinhVien nhu tren...
struct SinhVien {
    string ten;
    double diem;
    int maSo;

    SinhVien(string t, double d, int m) : ten(t), diem(d), maSo(m) {}
    SinhVien() = default;

    void inThongTin() const {
        cout << "Ma so: " << maSo << ", Ten: " << ten << ", Diem: " << diem << endl;
    }
};

// **Ham so sanh theo diem giam dan**
bool soSanhTheoDiemGiamDan(const SinhVien& sv1, const SinhVien& sv2) {
    // Tra ve true neu sv1 co diem cao hon sv2 (sv1 nen dung truoc sv2)
    return sv1.diem > sv2.diem;
}

int main() {
    vector<SinhVien> danhSachSV;
    danhSachSV.push_back(SinhVien("Nguyen Van A", 8.5, 101));
    danhSachSV.push_back(SinhVien("Le Thi B", 9.2, 105));
    danhSachSV.push_back(SinhVien("Tran Van C", 7.8, 102));
    danhSachSV.push_back(SinhVien("Pham Thi D", 8.5, 104));
    danhSachSV.push_back(SinhVien("Hoang Van E", 9.2, 103));

    cout << "Danh sach ban dau:" << endl;
    for (const auto& sv : danhSachSV) {
        sv.inThongTin();
    }
    cout << endl;

    // **Goi sort voi ham so sanh**
    sort(danhSachSV.begin(), danhSachSV.end(), soSanhTheoDiemGiamDan);

    cout << "Danh sach sau khi sap xep theo diem giam dan:" << endl;
    for (const auto& sv : danhSachSV) {
        sv.inThongTin();
    }
    cout << endl;

    return 0;
}

Giải thích:

Chúng ta định nghĩa hàm soSanhTheoDiemGiamDan nhận hai const SinhVien& (sv1 và sv2).
return sv1.diem > sv2.diem; nghĩa là: nếu điểm của sv1 lớn hơn điểm của sv2, hàm trả về true. Điều này báo cho sort biết rằng sv1 nên đứng trước sv2 trong kết quả cuối cùng (sắp xếp giảm dần).
Chúng ta truyền tên hàm soSanhTheoDiemGiamDan làm đối số thứ ba cho sort.

Kết quả sẽ là danh sách sinh viên được sắp xếp từ điểm cao nhất đến thấp nhất.

Phương pháp 2: Sử dụng Biểu thức Lambda (Lambda Expression)

Trong C++ hiện đại (từ C++11 trở lên), lambda expression là một cách rất tiện lợi để viết các hàm nhỏ, ẩn danh (không có tên) ngay tại chỗ cần sử dụng. Điều này rất hữu ích cho các hàm so sánh chỉ dùng một lần.

Lambda expression có cấu trúc [capture](parameters) -> return_type { body }. Đối với hàm so sánh cho sort, nó thường có dạng [](const Kieu& a, const Kieu& b){ return ...; }.

Ví dụ: Sắp xếp theo điểm số từ thấp đến cao bằng Lambda

#include <vector>
#include <string>
#include <iostream>
#include <algorithm> // Can bo sung thu vien nay!

// Dinh nghia Struct SinhVien nhu tren...
struct SinhVien {
    string ten;
    double diem;
    int maSo;

    SinhVien(string t, double d, int m) : ten(t), diem(d), maSo(m) {}
    SinhVien() = default;

    void inThongTin() const {
        cout << "Ma so: " << maSo << ", Ten: " << ten << ", Diem: " << diem << endl;
    }
};

int main() {
    vector<SinhVien> danhSachSV;
    danhSachSV.push_back(SinhVien("Nguyen Van A", 8.5, 101));
    danhSachSV.push_back(SinhVien("Le Thi B", 9.2, 105));
    danhSachSV.push_back(SinhVien("Tran Van C", 7.8, 102));
    danhSachSV.push_back(SinhVien("Pham Thi D", 8.5, 104));
    danhSachSV.push_back(SinhVien("Hoang Van E", 9.2, 103));

    cout << "Danh sach ban dau:" << endl;
    for (const auto& sv : danhSachSV) {
        sv.inThongTin();
    }
    cout << endl;

    // **Goi sort voi lambda expression de sap xep theo diem tang dan**
    sort(danhSachSV.begin(), danhSachSV.end(), [](const SinhVien& sv1, const SinhVien& sv2) {
        // Tra ve true neu sv1 co diem thap hon sv2 (sv1 nen dung truoc sv2)
        return sv1.diem < sv2.diem;
    });

    cout << "Danh sach sau khi sap xep theo diem tang dan (bang lambda):" << endl;
    for (const auto& sv : danhSachSV) {
        sv.inThongTin();
    }
    cout << endl;

    // **Mot lambda khac de sap xep theo ten tang dan**
     sort(danhSachSV.begin(), danhSachSV.end(), [](const SinhVien& sv1, const SinhVien& sv2) {
        // Tra ve true neu ten sv1 dung truoc ten sv2 theo thu tu bang chu cai
        return sv1.ten < sv2.ten;
    });

    cout << "Danh sach sau khi sap xep theo ten tang dan (bang lambda):" << endl;
    for (const auto& sv : danhSachSV) {
        sv.inThongTin();
    }
    cout << endl;


    return 0;
}

Giải thích:

Thay vì định nghĩa một hàm riêng, chúng ta viết lambda expression [](const SinhVien& sv1, const SinhVien& sv2) { return sv1.diem < sv2.diem; } ngay tại vị trí đối số thứ ba của sort.
[] là capture clause (ở đây trống vì lambda không cần truy cập biến bên ngoài).
(const SinhVien& sv1, const SinhVien& sv2) là danh sách tham số, giống như hàm thông thường.
{ return sv1.diem < sv2.diem; } là thân hàm, chứa logic so sánh. sv1.diem < sv2.diem trả về true nếu điểm của sv1 nhỏ hơn sv2, tức là sv1 nên đứng trước (sắp xếp tăng dần).
Lambda expression thường làm cho code ngắn gọn và dễ đọc hơn khi hàm so sánh chỉ được sử dụng một lần duy nhất.

Phương pháp 3: Nạp chồng toán tử `<` (Operator Overloading)

Nếu struct của bạn có một tiêu chí sắp xếp tự nhiên hoặc mặc định (ví dụ: luôn muốn sắp xếp sinh viên theo mã số tăng dần), bạn có thể nạp chồng (overload) toán tử so sánh < cho struct đó.

Khi bạn nạp chồng operator< bên trong struct, bạn đang chỉ cho C++ cách so sánh hai đối tượng cùng kiểu đó một cách mặc định. Sau đó, bạn có thể gọi sort mà không cần cung cấp đối số thứ ba.

Ví dụ: Sắp xếp theo mã số tăng dần bằng nạp chồng `operator<`

#include <vector>
#include <string>
#include <iostream>
#include <algorithm> // Can bo sung thu vien nay!

struct SinhVien {
    string ten;
    double diem;
    int maSo;

    SinhVien(string t, double d, int m) : ten(t), diem(d), maSo(m) {}
    SinhVien() = default;

    void inThongTin() const {
        cout << "Ma so: " << maSo << ", Ten: " << ten << ", Diem: " << diem << endl;
    }

    // **Nap chong toan tu < de sap xep mac dinh theo ma so tang dan**
    bool operator<(const SinhVien& other) const {
        return this->maSo < other.maSo;
    }
};

int main() {
    vector<SinhVien> danhSachSV;
    danhSachSV.push_back(SinhVien("Nguyen Van A", 8.5, 101));
    danhSachSV.push_back(SinhVien("Le Thi B", 9.2, 105));
    danhSachSV.push_back(SinhVien("Tran Van C", 7.8, 102));
    danhSachSV.push_back(SinhVien("Pham Thi D", 8.5, 104));
    danhSachSV.push_back(SinhVien("Hoang Van E", 9.2, 103));

    cout << "Danh sach ban dau:" << endl;
    for (const auto& sv : danhSachSV) {
        sv.inThongTin();
    }
    cout << endl;

    // **Goi sort KHONG can doi so thu ba (su dung operator< da nap chong)**
    sort(danhSachSV.begin(), danhSachSV.end());

    cout << "Danh sach sau khi sap xep theo ma so tang dan (bang operator<):" << endl;
    for (const auto& sv : danhSachSV) {
        sv.inThongTin();
    }
    cout << endl;

    return 0;
}

Giải thích:

Chúng ta định nghĩa hàm thành viên bool operator<(const SinhVien& other) const bên trong struct SinhVien.
Hàm này nhận một tham chiếu const đến một đối tượng SinhVien khác (other).
return this->maSo < other.maSo; so sánh maSo của đối tượng hiện tại (this->maSo) với maSo của đối tượng other. Nó trả về true nếu maSo của đối tượng hiện tại nhỏ hơn (<) của đối tượng kia. Điều này định nghĩa thứ tự "nhỏ hơn" mặc định dựa trên mã số.
Từ khóa const cuối hàm cho biết hàm này không thay đổi trạng thái của đối tượng hiện tại, rất quan trọng cho tính const-correctness.
Khi bạn gọi sort(danhSachSV.begin(), danhSachSV.end()); mà không có đối số thứ ba, sort sẽ tự động tìm và sử dụng operator< đã được nạp chồng cho kiểu SinhVien.

Lưu ý quan trọng: Nạp chồng operator< chỉ định nghĩa một tiêu chí sắp xếp mặc định duy nhất. Nếu bạn thường xuyên cần sắp xếp theo các tiêu chí khác nhau (lúc theo điểm, lúc theo tên), thì sử dụng hàm so sánh riêng hoặc lambda là linh hoạt hơn. Nạp chồng operator< phù hợp khi có một thứ tự "tự nhiên" cho kiểu dữ liệu của bạn.

Sắp xếp theo nhiều tiêu chí

Thường thì việc sắp xếp cần phức tạp hơn một chút. Ví dụ: Sắp xếp sinh viên theo điểm giảm dần, nhưng nếu hai sinh viên có cùng điểm, thì sắp xếp họ theo tên tăng dần theo thứ tự bảng chữ cái.

Logic này cần được xây dựng bên trong hàm so sánh (hoặc lambda):

So sánh tiêu chí chính (điểm).
Nếu tiêu chí chính bằng nhau, chuyển sang so sánh tiêu chí phụ (tên).

Ví dụ: Sắp xếp theo Điểm giảm dần, sau đó theo Tên tăng dần

Sử dụng lambda expression sẽ rất gọn gàng trong trường hợp này:

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

// Dinh nghia Struct SinhVien nhu tren...
struct SinhVien {
    string ten;
    double diem;
    int maSo;

    SinhVien(string t, double d, int m) : ten(t), diem(d), maSo(m) {}
    SinhVien() = default;

    void inThongTin() const {
        cout << "Ma so: " << maSo << ", Ten: " << ten << ", Diem: " << diem << endl;
    }
};

int main() {
    vector<SinhVien> danhSachSV;
    danhSachSV.push_back(SinhVien("Nguyen Van A", 8.5, 101));
    danhSachSV.push_back(SinhVien("Le Thi B", 9.2, 105));
    danhSachSV.push_back(SinhVien("Tran Van C", 7.8, 102));
    danhSachSV.push_back(SinhVien("Pham Thi D", 8.5, 104)); // Cung diem voi Van A
    danhSachSV.push_back(SinhVien("Hoang Van E", 9.2, 103)); // Cung diem voi Thi B

    cout << "Danh sach ban dau:" << endl;
    for (const auto& sv : danhSachSV) {
        sv.inThongTin();
    }
    cout << endl;

    // **Lambda de sap xep theo Diem giam dan, Ten tang dan khi diem bang nhau**
    sort(danhSachSV.begin(), danhSachSV.end(), [](const SinhVien& sv1, const SinhVien& sv2) {
        // 1. So sanh theo diem (giam dan)
        if (sv1.diem != sv2.diem) {
            return sv1.diem > sv2.diem; // Diem cao hon thi dung truoc
        }
        // 2. Neu diem bang nhau, so sanh theo ten (tang dan)
        return sv1.ten < sv2.ten; // Ten dung truoc trong bang chu cai thi dung truoc
    });

    cout << "Danh sach sau khi sap xep theo Diem giam dan, Ten tang dan:" << endl;
    for (const auto& sv : danhSachSV) {
        sv.inThongTin();
    }
    cout << endl;

    return 0;
}

Giải thích:

Lambda expression trước hết kiểm tra xem điểm của hai sinh viên có khác nhau không (sv1.diem != sv2.diem).
Nếu điểm khác nhau, nó trả về kết quả so sánh điểm theo thứ tự giảm dần (sv1.diem > sv2.diem).
Nếu điểm bằng nhau, khối if bị bỏ qua, và hàm sẽ chuyển sang câu lệnh return sv1.ten < sv2.ten;. Lệnh này so sánh tên theo thứ tự tăng dần (bảng chữ cái). Tên nào "nhỏ hơn" (đứng trước trong bảng chữ cái) thì sv1 sẽ đứng trước sv2.
Logic này đảm bảo tiêu chí điểm được ưu tiên trước, và tên chỉ được dùng để phân xử khi điểm trùng nhau.

Bài tập ví dụ: C++ Bài 19.A3: Messi vs Ronaldo

Messi vs Ronaldo

FullHouse Dev đang tổ chức một cuộc tranh luận về ai là cầu thủ xuất sắc hơn giữa Messi và Ronaldo. Họ quyết định so sánh điểm số của hai cầu thủ này trong mùa giải hiện tại.

Ở FullHouseLand, một cầu thủ bóng đá nhận được 2 điểm cho mỗi bàn thắng và 1 điểm cho mỗi đường kiến tạo.

Messi có A bàn thắng và B đường kiến tạo mùa này, trong khi Ronaldo có X bàn thắng và Y đường kiến tạo. Hãy giúp FullHouse Dev xác định cầu thủ nào có nhiều điểm hơn trong mùa giải này.

INPUT FORMAT

Dòng đầu tiên và duy nhất chứa bốn số nguyên cách nhau bởi dấu cách A, B, X và Y, lần lượt là số bàn thắng và đường kiến tạo của Messi, và số bàn thắng và đường kiến tạo của Ronaldo.

OUTPUT FORMAT

In ra một dòng duy nhất chứa:

Messi, nếu Messi có nhiều điểm hơn Ronaldo.
Ronaldo, nếu Ronaldo có nhiều điểm hơn Messi.
Equal, nếu cả hai có số điểm bằng nhau.

Bạn có thể in mỗi ký tự in hoa hoặc in thường. Ví dụ, các chuỗi Messi, MESSI, messi và MeSSi được coi là giống nhau.

CONSTRAINTS

0 ≤ A, B, X, Y ≤ 100

Ví dụ

Input 1

40 30 50 10

Output 1

Equal

Giải thích 1: Messi có 40 bàn thắng và 30 đường kiến tạo. Vì vậy, tổng điểm của anh ấy là 40 2 + 30 = 110. Ronaldo có 50 bàn thắng và 10 đường kiến tạo. Vì vậy, tổng điểm của anh ấy là 50 2 + 10 = 110. Cả hai đều có 110 điểm.

Input 2

91 22 60 30

Output 2

Messi

Giải thích 2: Messi có 91 bàn thắng và 22 đường kiến tạo. Vì vậy, tổng điểm của anh ấy là 91 2 + 22 = 204. Ronaldo có 60 bàn thắng và 30 đường kiến tạo. Vì vậy, tổng điểm của anh ấy là 60 2 + 30 = 150. Messi có 204 điểm, trong khi Ronaldo có 150 điểm.

Input 3

60 30 80 20

Output 3

Ronaldo

Giải thích 3: Messi có 60 bàn thắng và 30 đường kiến tạo. Vì vậy, tổng điểm của anh ấy là 60 2 + 30 = 150. Ronaldo có 80 bàn thắng và 20 đường kiến tạo. Vì vậy, tổng điểm của anh ấy là 80 2 + 20 = 180. Messi có 150 điểm, trong khi Ronaldo có 180 điểm. Tuyệt vời! Đây là hướng dẫn để bạn giải bài tập "Messi vs Ronaldo" bằng C++ một cách ngắn gọn và sử dụng std khi có thể, mà không cung cấp code hoàn chỉnh:

Đọc dữ liệu đầu vào:
- Bạn cần đọc bốn số nguyên A, B, X, Y từ dòng input duy nhất.
- Sử dụng cin để thực hiện việc này. Đơn giản chỉ cần đọc lần lượt bốn biến.
Tính điểm cho mỗi cầu thủ:
- Nhớ rằng mỗi bàn thắng được 2 điểm, mỗi kiến tạo được 1 điểm.
- Tính tổng điểm của Messi: diem_messi = A * 2 + B * 1.
- Tính tổng điểm của Ronaldo: diem_ronaldo = X * 2 + Y * 1.
- Lưu kết quả vào các biến kiểu số nguyên (ví dụ: int).
So sánh điểm và in kết quả:
- Sử dụng cấu trúc điều kiện if-else if-else để so sánh diem_messi và diem_ronaldo.
- Trường hợp 1: Nếu diem_messi lớn hơn diem_ronaldo, in ra chuỗi "Messi".
- Trường hợp 2: Ngược lại, nếu diem_ronaldo lớn hơn diem_messi, in ra chuỗi "Ronaldo".
- Trường hợp 3: Nếu cả hai trường hợp trên đều không đúng, nghĩa là điểm của hai cầu thủ bằng nhau, in ra chuỗi "Equal".
- Sử dụng cout để in các chuỗi kết quả.
- Nhớ thêm endl hoặc '\n' sau mỗi lần in để kết thúc dòng output.
Bao gồm thư viện cần thiết:
- Bạn cần include thư viện <iostream> để sử dụng cin và cout.

Toàn bộ logic này sẽ nằm bên trong hàm main() của chương trình C++. Hãy kết hợp các bước trên để viết code của riêng bạn!

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.