tailieunhanh - Bài giảng Cấu trúc dữ liệu giải thuật: Các kiểu dữ liệu trừu tượng cơ bản - Tập hợp

Bài giảng Cấu trúc dữ liệu giải thuật: Các kiểu dữ liệu trừu tượng cơ bản - Tập hợp trình bày khái niệm tập hợp, phép toán trên tập hợp, cài đặt tập hợp, từ điển, bảng băm. Mời các bạn tham khảo bài giảng để bổ sung thêm kiến thức về lĩnh vực này. | CÁC KIỂU DỮ LIỆU TRỪU TƯỢNG CƠ BẢN TẬP HỢP Đỗ Thanh Nghị dtnghi@ NỘI DUNG • Khái niệm tập hợp • Phép toán trên tập hợp • Cài đặt tập hợp • Từ điển • Bảng băm 2 KHÁI NIỆM TẬP HỢP • Là tập hợp các thành viên hoặc phần tử • Các phần tử của tập hợp phải khác nhau • Các phần tử của tập hợp có quan hệ tuyến tính • Liệt kê các phần tử trong cặp dấu ngoặc {} x∈ S : x là một thành viên của tập hợp S x∉ S : x không là một thành viên của tập hợp S ∅ : tập hợp rỗng, không có thành viên VD: A={1,2} B= {1,2,3} 3 BIỂU DIỄN TẬP HỢP • Cho hai tập hợp A và B: – A là 1 bộ phận của B, kí hiệu A ⊆ B: nếu mọi thành viên của A đều là thành viên của B • VD: A ⊆ B – Tập hợp A và B bằng nhau, kí hiệu A = B: nếu A⊆ B và B⊆ A – Hợp của hai tập hợp: A∪B={x| x⊆A hoặc x∈B} – Giao của hai tập hợp: A∩B={x| x∈A và x∈B} – Hiệu của hai tập hợp: A\B={x| x∈A và x∉B} 4 PHÉP TOÁN TẬP HỢP Tên hàm/thủ tục MAKENULLSET(A) EMPTY(A) MEMBER(x, A) INSERTSET(x, A) DELETESET(x, A) ASSIGN(A, B) MIN(A) EQUAL(A,B) UNION(A,B,C) INTERSECTION(A,B,C) DIFFERENCE(A,B,C) MERGE(A,B,C) Diễn giải Tạo tập A rỗng Kiểm tra xem tập A có rỗng? Kiểm tra xem x có thuộc A? Thêm x vào tập A Xóa x khỏi tập A Gán B=A Trả về phần tử nhỏ nhất trong tập hợp Trả về TRUE nếu A=B C=A∪B C=A∩B C=A\B C=A∪B, nhưng có quan tâm thứ .