tailieunhanh - Bài giảng Cấu trúc dữ liệu: Chương 6 - Nguyễn Xuân Vinh

Bài giảng Cấu trúc dữ liệu - Chương 6: Tập hợp (Set) trình bày về conllections, khái niệm tập hợp, phân loại tập hợp, set và các phép toán trên nó, hiện thực set. Hy vọng đây là tài tài liệu tham khảo hữu ích cho bạn. | TẬP HỢP (SET) Teacher: Nguyễn Xuân Vinh Email: nguyenxuanvinh@ CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] Nội dung Nhắc lại Collection Tập hợp là gì? Phân loại tập hợp Set (tập hợp) và các phép toán trên nó Hiện thực Set Bằng mảng Bằng danh sách liên kết Collection Collection là một cấu trúc gồm nhiều phần tử. Có nhiều kiểu collection: Stack, Queue, List, Set, Graph, Tree, Hashtable Nó được phân thành 2 nhóm: Linear: stack, queue, set, hashtable Non-Linear: tree, graph Linear collection Non-Linear collection Collection Việc tổ chức các phần tử bên trong 1 collection thường dựa trên các yếu tố sau: Order: Thứ tự các phần tử thêm vào vật chứa Mối quan hệ giữa các phần tử Unique: tính duy nhất Ví dụ: danh sách người có thể được sắp xếp dựa trên thứ tự tên (alphabetical) hay được lưu trữ phụ thuộc vào thứ tự thêm vào Tập hợp (Set) Tập hợp là một nhóm các phần tử mà trong đó mối quan hệ giữa các phần tử không được xét đến. Giống như bạn ném tất cả các phần tử vào trong 1 . | TẬP HỢP (SET) Teacher: Nguyễn Xuân Vinh Email: nguyenxuanvinh@ CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] Nội dung Nhắc lại Collection Tập hợp là gì? Phân loại tập hợp Set (tập hợp) và các phép toán trên nó Hiện thực Set Bằng mảng Bằng danh sách liên kết Collection Collection là một cấu trúc gồm nhiều phần tử. Có nhiều kiểu collection: Stack, Queue, List, Set, Graph, Tree, Hashtable Nó được phân thành 2 nhóm: Linear: stack, queue, set, hashtable Non-Linear: tree, graph Linear collection Non-Linear collection Collection Việc tổ chức các phần tử bên trong 1 collection thường dựa trên các yếu tố sau: Order: Thứ tự các phần tử thêm vào vật chứa Mối quan hệ giữa các phần tử Unique: tính duy nhất Ví dụ: danh sách người có thể được sắp xếp dựa trên thứ tự tên (alphabetical) hay được lưu trữ phụ thuộc vào thứ tự thêm vào Tập hợp (Set) Tập hợp là một nhóm các phần tử mà trong đó mối quan hệ giữa các phần tử không được xét đến. Giống như bạn ném tất cả các phần tử vào trong 1 cái hộp. Và từng phần tử là duy nhất. Tập hợp là một cấu trúc dạng phi tuyến nhưng chúng ta vẫn có thể dùng một cấu trúc dạng tuyến tính để hiện thực nó. Các phép toán trên Collection Mỗi 1 collection đều định nghĩa 1 tập hợp các phép toán giúp chúng ta tương tác với nó. Các phép toán này thông thường là: Thêm, xóa các phần tử. Kiểm tra xem collection đó có rỗng hay không. Tính kích thước của collection. Iterator, xử lý từng phần tử trong collection đó. Các phép toán dùng để tương tác với các collection khác. Phép toán Mô tả add Thêm 1 phần tử vào trong tập hợp addAll Thêm tất cả các phần tử của 1 tập hợp vào trong 1 tập hợp khác removeRandom Xóa 1 phần tử ngẫu nhiên trong tập hợp remove Xóa 1 phần tử ra khỏi tập hợp union Hợp các phần tử của 2 tập hợp vào 1 tập hợp thứ 3 contains Xác định xem 1 phần tử có nằm trong tập hợp hay không equals Xác định xem 2 tập hợp có chứa các phần tử giống nhau hay không isEmpty Xác định xem tập hợp có rỗng hay không size Xác định số phần tử trong tập hợp