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.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Cấu trúc dữ liệu: Chương 6 - Nguyễn Xuân Vinh
- GV: NGUYỄN XUÂN VINH
CẤU TRÚC DỮ LIỆU
DATA STRUCTURES
[214331]
TẬP HỢP
MÔN: CẤU TRÚC DỮ LIỆU
(SET)
Teacher: Nguyễn Xuân Vinh
6/12/14
Email:
nguyenxuanvinh@hcmuaf.edu.
/XX
vn
1
- GV: 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ết
6/12/14
/XX
2
- GV: NGUYỄN XUÂN VINH
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…
MÔN: CẤU TRÚC DỮ LIỆU
–
–
Non-Linear: tree, graph…
Non-Linear
collection
6/12/14
Linear
collection
/XX
3
- GV: 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ất
MÔ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ào
6/12/14
/XX
4
- GV: 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ỆU
6/12/14
/XX
5
- GV: 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
/XX
6
- GV: 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ợp
MÔ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
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
iterator Đưa ra 1 cách duyệt tất cả các phần t ử trong t ập h ợp
6/12/14
toString Đưa ra 1 cách hiển thị cho tập hợp
/XX
7
- GV: NGUYỄN XUÂN VINH
Mô hình UML của lớp SetADT
SetADT
add()
MÔN: CẤU TRÚC DỮ LIỆU
addAll()
removeRandom()
remove()
union()
contains()
equals()
isEmpty()
size()
6/12/14
iterator()
/XX
toString()
8
- 9 /XX 6/12/14 MÔN: CẤU TRÚC DỮ LIỆU GV: NGUYỄN XUÂN VINH
SetADT.java
- 10 /XX 6/12/14 MÔN: CẤU TRÚC DỮ LIỆU GV: NGUYỄN XUÂN VINH
SetADT.java
- GV: NGUYỄN XUÂN VINH
Iterator
•
Iterator là một đối tượng cho phép người dùng triệu gọi và sử
dụng từng phần tử trong collection.
•
Chương trình thiết kế để xác định:
–
Thứ tự của các phần tử.
Cách mà iterator sẽ hiện thực.
MÔN: CẤU TRÚC DỮ LIỆU
–
•
Trong trường hợp của Set không có 1 thứ tự đặc biệt nào cho các
phần tử nên sự sắp xếp của các phần tử trong iterator là ngẫu
nhiên.
6/12/14
/XX
11
- GV: NGUYỄN XUÂN VINH
Iterator
•
Các collection hỗ trợ Iterator thường có phương thức iterator() trả
về 1 đối tượng kiểu Iterator.
•
Iterator thực ra là một interface định nghĩa trong bộ thư viện
chuẩn của Java.
•
Các phương thức trong Iterator:
MÔN: CẤU TRÚC DỮ LIỆU
–
hasNext(): trả về true nếu còn phần tử trong iterator.
–
next(): trả về phần tử kế tiếp trong iterator.
–
remove(Object obj): xóa một phần tử trong collection.
6/12/14
/XX
12
- GV: NGUYỄN XUÂN VINH
Các lỗi trên Tập hợp (Set)
•
Các collection phải luôn quản lý các vấn đề trong các tình huống
1 cách thật cẩn thận.
–
Ví dụ: xóa 1 phần tử ra khỏi danh sách rỗng.
•
Người thiết kế ra các collection có nhiệm vụ quyết định cách
giải quyết cho những vấn đề này.
MÔN: CẤU TRÚC DỮ LIỆU
–
Ta có thể định nghĩa phương thức isEmpty() dùng để kiểm tra
trước khi thực hiện xóa phần tử.
–
Ta cũng có thể ném ra ngoại lệ nếu tình huống này xảy ra.
6/12/14
/XX
13
- GV: NGUYỄN XUÂN VINH
Cài đặt tập hợp
•
Có nhiều cách để hiện thực
tập hợp.
MÔN: CẤU TRÚC DỮ LIỆU
–
Dùng mảng
–
Dùng danh sách liên kết
6/12/14
/XX
Danh sách liên kết Mảng
14
- GV: NGUYỄN XUÂN VINH
1. Dùng mảng: Quản lý sức chứa
•
Một mảng khi khởi tạo cần biết trước kích thước của nó, gọi là
sức chứa (capacity).
•
Sức chứa của mảng cũng chính là sức chứa của tập hợp.
•
Chúng ta nên làm gì khi người dùng cố thêm 1 phần tử vào tập
hợp đã đầy:
MÔN: CẤU TRÚC DỮ LIỆU
–
Ném biệt lệ.
–
Trả về 1 trạng thái chỉ thị.
–
Tự động mở rộng kích thước mảng.
6/12/14
/XX
15
- GV: NGUYỄN XUÂN VINH
1. Dùng mảng: Quản lý sức chứa
•
Hai cách lựa chọn đầu buộc người dùng tập hợp phải cảnh giác
và giải quyết với các tình huống xảy ra.
•
Cách thứ 3 tốt hơn, đặc biệt là hỗ trợ chúng ta trong việc tách rời
phần hiện thực và lớp interface.
•
Sức chứa là một vấn đề của hiện thực, không nên giao cho
MÔN: CẤU TRÚC DỮ LIỆU
người dùng giải quyết nếu không có lý do nào đặc biệt.
6/12/14
/XX
16
- GV: NGUYỄN XUÂN VINH
1. Dùng mảng: Hiện thực tập hợp
•
Các phần tử trong tập hợp được lưu trữ kế nhau ở 1 đầu của
mảng.
•
Chúng ta cần:
–
1 biến count để lưu trữ tổng số phần tử hiện có trong tập
hợp.
MÔN: CẤU TRÚC DỮ LIỆU
–
Một mảng content dùng để chứa nội dung của tập hợp
6/12/14
/XX
Các phần tử được lưu trữ kề nhau
17
- 18 /XX 6/12/14 MÔN: CẤU TRÚC DỮ LIỆU GV: NGUYỄN XUÂN VINH
đ ặt
1. Dùng mảng: Các phương thức cần cài
- GV: NGUYỄN XUÂN VINH
1. Dùng mảng: Demo
•
SetADT.java
•
ArraySet.java
•
ArrayIterator.java
•
EmptySetException.java
MÔN: CẤU TRÚC DỮ LIỆU
•
ElementNotFoundException.java
6/12/14
/XX
19
- GV: NGUYỄN XUÂN VINH
1. Dùng mảng: Độ phức tạp của các phép
toán tập hợp chưa đầy, phép thêm 1 phần tử: O(1).
•
Nếu
•
Mở rộng 1 tập hợp: O(n).
•
Loại bỏ một phần tử được chỉ định ra khỏi tập hợp: O(n).
•
Loại bỏ một phần tử bất kỳ ra khỏi tập hợp: O(1).
•
Thêm 1 tập hợp vào tập hợp này: O(n)
MÔN: CẤU TRÚC DỮ LIỆU
•
Phép hợp hai tập hợp: O(m+n) với m là kích thước của tập hợp
thứ hai.
6/12/14
/XX
20
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
