BÀI GIẢNG: CẤU TRÚC DỮ LIỆU SET TRONG C++

1. Khái niệm và Đặc điểm của Set

std::set là một container trong thư viện chuẩn STL của C++, dùng để lưu trữ các phần tử duy nhất (không trùng lặp) và tự động sắp xếp theo một thứ tự nhất định (mặc định là tăng dần).

• Thư viện: #include <set>
• Cấu trúc bên dưới: Thường được cài đặt bằng Cây nhị phân tìm kiếm cân bằng (Red-Black Tree).
• Đặc điểm chính:
• Tính duy nhất: Mỗi giá trị chỉ xuất hiện một lần duy nhất.
• Tính sắp xếp: Các phần tử luôn được duy trì theo thứ tự.
• Tính bất biến của phần tử: Bạn không thể sửa trực tiếp một phần tử trong set (vì sẽ làm hỏng cấu trúc cây), bạn phải xóa đi và chèn lại.

2. Các thao tác cơ bản (Độ phức tạp )

3. Phân biệt Set với các kiểu dữ liệu khác

Đây là phần quan trọng để học sinh tư duy chọn cấu trúc dữ liệu đúng cho bài toán.

Lời khuyên sư phạm:
* Dùng Set khi: Cần tính duy nhất và cần các phần tử luôn được sắp xếp (để in ra hoặc dùng lower_bound).
* Dùng Unordered_set khi: Chỉ cần tính duy nhất và ưu tiên tốc độ tối đa (), không quan tâm thứ tự.
* Dùng Vector khi: Cần lưu mọi giá trị, chấp nhận trùng lặp và truy cập qua chỉ số.

4. Các biến thể của Set

1. std::multiset: Cho phép các phần tử trùng nhau nhưng vẫn tự động sắp xếp.
2. std::unordered_set: Duy nhất nhưng không sắp xếp, tốc độ nhanh hơn set thường.

5. Bài tập ứng dụng (Từ cơ bản đến nâng cao)

Bài 1: Đếm số lượng giá trị phân biệt

Đề bài: Cho mảng gồm số nguyên. Hãy đếm xem có bao nhiêu giá trị khác nhau trong mảng.

• Hướng dẫn: Duyệt mảng, mỗi phần tử s.insert(A[i]). Kết quả là s.size().

Bài 2: Tìm phần tử lớn nhất nhỏ hơn X

Đề bài: Cho một tập hợp số nguyên. Với mỗi truy vấn , hãy tìm số lớn nhất trong tập hợp mà nhỏ hơn hoặc bằng .

• Hướng dẫn: Sử dụng hàm s.upper_bound(X). Sau đó lấy iterator trả về lùi lại một đơn vị (--it).

Bài 3: Kiểm tra xâu ký tự (Pangram)

Đề bài: Một xâu được gọi là Pangram nếu nó chứa đầy đủ các chữ cái từ 'a' đến 'z'.

• Hướng dẫn: Duyệt xâu, nếu là ký tự chữ cái thì đưa vào set<char>. Nếu s.size() == 26 thì đó là Pangram.

Bài 4: Hợp và Giao của hai mảng

Đề bài: Cho hai mảng và . Liệt kê các phần tử xuất hiện trong cả hai mảng theo thứ tự tăng dần.

• Hướng dẫn:
• Đưa mảng vào set1.
• Duyệt mảng , với mỗi , kiểm tra nếu set1.count(x) thì đưa vào set_result.
• In set_result.

6. Ví dụ Code minh họa (C++11)

#include <iostream>
#include <set>
#include <vector>

using namespace std;

int main() {
    set<int> s;

    // Thêm phần tử
    s.insert(10);
    s.insert(5);
    s.insert(20);
    s.insert(10); // Sẽ bị bỏ qua vì đã tồn tại

    cout << "Cac phan tu trong set (tu dong sap xep): ";
    for (int x : s) {
        cout << x << " "; // In ra: 5 10 20
    }
    cout << endl;

    // Tìm kiếm
    if (s.find(10) != s.end()) {
        cout << "Tim thay 10" << endl;
    }

    // Xóa
    s.erase(10);
    cout << "Kich thuoc sau khi xoa: " << s.size() << endl;

    return 0;
}

Luyện tập về Set với bộ câu hỏi trắc nghiệm nào!