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.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu: Chương 6 - Nguyễn Xuân VinhGV: NGUYỄN XUÂN VINH CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] TẬP HỢPMÔN: CẤU TRÚC DỮ LIỆU (SET) Teacher: Nguyễn Xuân Vinh6/12/14 Email: nguyenxuanvinh@hcmuaf.edu./XX vn1GV: NGUYỄN XUÂN VINH 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óMÔN: CẤU TRÚC DỮ LIỆU • Hiện thực Set – Bằng mảng – Bằng danh sách liên kết6/12/14/XX2GV: NGUYỄN XUÂN VINH Collection • Collectionlàmộtcấutrúcgồmnhiềuphầntử. • Cónhiềukiểucollection:Stack,Queue,List,Set,Graph, Tree,Hashtable… • Nóđượcphânthành2nhóm: Linear: stack, queue, set, hashtable…MÔN: CẤU TRÚC DỮ LIỆU – – Non-Linear: tree, graph… Non-Linear collection6/12/14 Linear collection/XX3GV: NGUYỄN XUÂN VINH 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ấtMÔN: CẤU TRÚC DỮ LIỆU – • 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ào6/12/14/XX4GV: NGUYỄN XUÂN VINH 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ó.MÔN: CẤU TRÚC DỮ LIỆU6/12/14/XX5GV: NGUYỄN XUÂN VINH 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.MÔN: CẤU TRÚC DỮ LIỆU – – 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.6/12/14/XX6GV: NGUYỄN XUÂN VINH Các phép toán trên Set 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ợpMÔN: CẤU TRÚC DỮ LIỆU 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 ...