Ấ Ữ Ệ
C U TRÚC D LI U DATA STRUCTURES [214331]
H N I V N Â U X N Ễ Y U G N
:
V G
T P H P Ậ Ợ (SET)
U Ệ I L Ữ D C Ú R T U Ấ C
:
N Ô M
/
ễ
4 1 2 1
/
6
X X
/
1
Teacher: Nguy n Xuân Vinh Email: nguyenxuanvinh@hcmuaf.edu. vn
N i dung
ộ
i Collection
H N I V N Â U X N Ễ Y U G N
:
V G
ạ ậ ợ
ệ
• Nh c l ắ ạ • 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 ế ằ
ả
U Ệ I L Ữ D C Ú R T U Ấ C
:
N Ô M
/
4 1 2 1
/
6
X X
/
2
Collection
H N I V N Â U X N Ễ Y U G N
• 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,
:
V G
• Nó được phân thành 2 nhóm:
– Linear: stack, queue, set, hashtable… – Non-Linear: tree, graph…
Tree, Hashtable…
U Ệ I L Ữ D C Ú R T U Ấ C
:
Non-Linear collection
N Ô M
/
4 1 2 1
/
6
Linear collection
X X
/
3
Collection
• Vi c t
ch c các ph n t bên trong 1 collection th ầ ử ườ ng d a trên ự
H N I V N Â U X N Ễ Y U G N
:
V G
các ph n t ầ ử ứ ự thêm vào v t ch a ứ ậ
ố ầ ử
ệ ổ ứ sau: các y u t ế ố – Order: Th t – M i quan h gi a các ph n t ệ ữ – Unique: tính duy nh tấ
• Ví d : danh sách ng (alphabetical) hay đ
c s p x p d a trên th t tên ụ
i có th đ c l u tr ph thu c vào th t ứ ự thêm vào ườ ượ ư ể ượ ắ ế ự ữ ụ ứ ự ộ
U Ệ I L Ữ D C Ú R T U Ấ C
:
N Ô M
/
4 1 2 1
/
6
X X
/
4
T p h p (Set) ợ
ậ
• T p h p là m t nhóm các ph n t ộ không đ
ậ
mà trong đó m i quan h gi a ệ ữ ố t c các ợ ầ ử ầ ử ế ượ ư ạ ố
H N I V N Â U X N Ễ Y U G N
:
là duy nh t.
V G
• T p h p là m t c u trúc d ng phi tuy n nh ng chúng ta v n có
c xét đ n. Gi ng nh b n ném t ấ ả ấ ừ
ộ ấ ế ẫ
vào trong 1 cái h p. Và t ng ph n t ầ ử ộ ư ạ th dùng m t c u trúc d ng tuy n tính đ hi n th c nó. ể ệ ộ ấ ự ế ạ các ph n t ph n t ầ ử ậ ợ ể
U Ệ I L Ữ D C Ú R T U Ấ C
:
N Ô M
/
4 1 2 1
/
6
X X
/
5
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 ớ
H N I V N Â U X N Ễ Y U G N
:
V G
ng là:
–
ể ỗ
U Ệ I L Ữ D C Ú R T U Ấ C
:
ề ng tác v i nó. ươ • Các phép toán này thông th ườ . – Thêm, xóa các ph n t ầ ử – Ki m tra xem collection đó có r ng hay không. c c a collection. – Tính kích th ướ ủ ừ ử – Các phép toán dùng đ t trong collection đó. ng tác v i các collection khác. Iterator, x lý t ng ph n t ầ ử ể ươ ớ
N Ô M
/
4 1 2 1
/
6
X X
/
6
Các phép toán trên Set
Phép toán
Mô tả
H N I V N Â U X N Ễ Y U G N
:
Thêm 1 ph n t
vào trong t p h p
add
ầ ử
ậ
ợ
V G
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
addAll
ấ ả
ầ ử ủ
ậ
ậ
ợ
ợ
removeRandom
Xóa 1 ph n t
ng u nhiên trong t p h p
ầ ử
ẫ
ậ
ợ
Xóa 1 ph n t
remove
ầ ử
ra kh i t p h p ỏ ậ
ợ
H p các ph n t
c a 2 t p h p vào 1 t p h p th 3
union
ầ ử ủ
ứ
ậ
ậ
ợ
ợ
ợ
Xác đ nh xem 1 ph n t
contains
ầ ử
ị
có n m trong t p h p hay không ậ
ằ
ợ
gi ng nhau hay không
equals
Xác đ nh xem 2 t p h p có ch a các ph n t ợ
ầ ử ố
ứ
ậ
ị
U Ệ I L Ữ D C Ú R T U Ấ C
:
isEmpty
Xác đ nh xem t p h p có r ng hay không ợ
ậ
ỗ
ị
N Ô M
Xác đ nh s ph n t
size
ầ ử
ố
ị
trong t p h p ậ
ợ
Đ a ra 1 cách duy t t
t c các ph n t
iterator
ệ ấ ả
ầ ử
ư
trong t p h p ậ
ợ
/
toString
Đ a ra 1 cách hi n th cho t p h p ể
ư
ậ
ợ
ị
4 1 2 1
/
6
X X
/
7
Mô hình UML c a l p SetADT
ủ ớ
H N I V N Â U X N Ễ Y U G N
:
<
V G
U Ệ I L Ữ D C Ú R T U Ấ C
:
N Ô M
/
4 1 2 1
/
6
X X
/
add() addAll() removeRandom() remove() union() contains() equals() isEmpty() size() iterator() toString()
8
SetADT.java
H N I V N Â U X N Ễ Y U G N
:
V G
U Ệ I L Ữ D C Ú R T U Ấ C
:
N Ô M
/
4 1 2 1
/
6
X X
/
9
SetADT.java
H N I V N Â U X N Ễ Y U G N
:
V G
U Ệ I L Ữ D C Ú R T U Ấ C
:
N Ô M
/
4 1 2 1
/
6
X X
/
0 1
Iterator
•
ng cho phép ng ườ i dùng tri u g i và s ử ệ ọ
H N I V N Â U X N Ễ Y U G N
:
V G
ị
trong collection. t k đ xác đ nh: . Iterator là m t đ i t ộ ố ượ d ng t ng ph n t ừ ầ ử ụ ng trình thi • Ch ứ ự ủ
ự
ng h p c a Set không có 1 th t đ c bi ế ế ể ươ c a các ph n t – Th t ầ ử – Cách mà iterator s hi n th c. ẽ ệ ợ ủ
ườ nên s s p x p c a các ph n t ệ ứ ự ặ trong iterator là ng u ự ắ ế ủ t nào cho các ẫ ầ ử
U Ệ I L Ữ D C Ú R T U Ấ C
• Trong tr ph n t ầ ử nhiên.
:
N Ô M
/
4 1 2 1
/
6
X X
/
1 1
Iterator
• Các collection h tr Iterator th
ng có ph ườ ươ ng th c iterator() tr ả ứ
ỗ ợ ể
H N I V N Â U X N Ễ Y U G N
:
•
V G
• Các ph
ố ượ ự ng ki u Iterator. ộ ộ ư ệ ị
trong iterator. v 1 đ i t ề Iterator th c ra là m t interface đ nh nghĩa trong b th vi n chu n c a Java. ẩ ủ ứ ươ ả ề ầ ử ế
–
ng th c trong Iterator: – hasNext(): tr v true n u còn ph n t – next(): tr v ph n t k ti p trong iterator. ả ề
U Ệ I L Ữ D C Ú R T U Ấ C
remove(Object obj): xóa m t ph n t trong collection. ầ ử ầ ử ế ế ộ
:
N Ô M
/
4 1 2 1
/
6
X X
/
2 1
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
ề ấ ả ố
H N I V N Â U X N Ễ Y U G N
:
V G
ỏ ả ậ ầ ử
ra kh i danh sách r ng. t k ra các collection có nhi m v quy t đ nh cách ế ị ỗ ụ ệ 1 cách th t c n th n. ậ ẩ – Ví d : xóa 1 ph n t ế ế
• Ng ườ i quy t cho nh ng v n đ này. gi ữ ả – Ta có th đ nh nghĩa ph ể ị
ụ i thi ế ấ
ề ươ ể ể
tr ướ c khi th c hi n xóa ph n t ệ
U Ệ I L Ữ D C Ú R T U Ấ C
ự – Ta cũng có th ném ra ngo i l ể ng th c isEmpty() dùng đ ki m tra ứ . ầ ử ạ ệ ế n u tình hu ng này x y ra. ố ả
:
N Ô M
/
4 1 2 1
/
6
X X
/
3 1
Cài đ t t p h p ặ ậ
ợ
H N I V N Â U X N Ễ Y U G N
:
V G
• Có nhi u cách đ hi n th c
ự ể ệ
ợ
ề t p h p. ậ – Dùng m ngả – Dùng danh sách liên k tế
U Ệ I L Ữ D C Ú R T U Ấ C
:
N Ô M
/
4 1 2 1
/
6
X X
/
Danh sách liên k tế
M ngả
4 1
1. Dùng m ng: Qu n lý s c ch a
ứ
ứ
ả
ả
• M t m ng khi kh i t o c n bi
c kích th c c a nó, g i là ở ạ ầ t tr ế ướ ướ ủ ọ
H N I V N Â U X N Ễ Y U G N
:
V G
ả ộ 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 ầ ử ậ ố
ỉ
U Ệ I L Ữ D C Ú R T U Ấ C
h p đã đ y: ầ ợ t l . – Ném bi ệ ệ – Tr v 1 tr ng thái ch th . ị ạ ả ề – T đ ng m r ng kích th ướ ở ộ ự ộ c m ng. ả
:
N Ô M
/
4 1 2 1
/
6
X X
/
5 1
1. Dùng m ng: Qu n lý s c ch a
ứ
ứ
ả
ả
ộ ậ ầ ự ườ ả ả ợ
và gi
H N I V N Â U X N Ễ Y U G N
:
V G
• S c ch a là m t v n đ c a hi n th c, không nên giao cho
• Hai cách l a ch n đ u bu c ng ọ i quy t v i các tình hu ng x y ra. ố ế ớ t là h tr chúng ta trong vi c tách r i t h n, đ c bi ặ ứ ố ơ ệ ớ ự ứ
ả • Cách th 3 t i dùng t p h p ph i c nh giác ả ỗ ợ ệ ệ ờ
ề ủ ự
i quy t n u không có lý do nào đ c bi i dùng gi t. ph n hi n th c và l p interface. ệ ộ ấ ả ầ ứ ng ườ ế ế ệ ặ
U Ệ I L Ữ D C Ú R T U Ấ C
:
N Ô M
/
4 1 2 1
/
6
X X
/
6 1
1. Dùng m ng: Hi n th c t p h p
ự ậ
ợ
ệ
ả
• Các ph n t m ng.ả
trong t p h p đ ậ ợ ượ ư c l u tr k nhau ữ ế ở 1 đ u c a ầ ủ ầ ử
H N I V N Â U X N Ễ Y U G N
:
V G
• Chúng ta c n:ầ
– 1 bi n count đ l u tr t ng s ph n t
– M t m ng content dùng đ ch a n i dung c a t p h p
hi n có trong t p ể ư ữ ổ ầ ử ệ ậ ố
ế h p.ợ ộ ể ứ ộ ủ ậ ả ợ
U Ệ I L Ữ D C Ú R T U Ấ C
:
N Ô M
/
4 1 2 1
/
6
X X
/
Các ph n t
đ ầ ử ượ ư
c l u tr k nhau ữ ề
7 1
ươ
ng th c c n cài ứ ầ
1. Dùng m ng: Các ph ả đ tặ
H N I V N Â U X N Ễ Y U G N
:
V G
U Ệ I L Ữ D C Ú R T U Ấ C
:
N Ô M
/
4 1 2 1
/
6
X X
/
8 1
1. Dùng m ng: Demo ả
H N I V N Â U X N Ễ Y U G N
:
V G
• SetADT.java • ArraySet.java • ArrayIterator.java • EmptySetException.java • ElementNotFoundException.java
U Ệ I L Ữ D C Ú R T U Ấ C
:
N Ô M
/
4 1 2 1
/
6
X X
/
9 1
ả
ộ
ủ
ứ ạ
: O(1). ầ ử
ậ
H N I V N Â U X N Ễ Y U G N
:
V G
ị ỉ
c ch đ nh ra kh i t p h p: O(n). ỏ ậ ợ
ợ
1. Dùng m ng: Đ ph c t p c a các phép toán • N u t p h p ch a đ y, phép thêm 1 ph n t ợ ư ầ ế ậ • M r ng 1 t p h p: O(n). ợ ở ộ đ • Lo i b m t ph n t ợ ầ ử ượ ạ ỏ ộ • 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) ậ ậ • 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. ứ
U Ệ I L Ữ D C Ú R T U Ấ C
:
N Ô M
/
4 1 2 1
/
6
X X
/
0 2
2. Dùng Linked List: Hi n th c t p h p
ự ậ
ợ
ệ
hi n có c a t p h p ủ ậ ể ư ợ
H N I V N Â U X N Ễ Y U G N
:
V G
– M t bi n count đ l u tr s ph n t – M t bi n contents dùng đ l u tr node đ u tiên c a t p h p
• Chúng ta c n:ầ ộ ộ
ế ế ầ ừ ệ ầ ữ ữ ố ể ư ủ ậ ợ
U Ệ I L Ữ D C Ú R T U Ấ C
:
N Ô M
/
4 1 2 1
/
6
X X
/
1 2
2. Dùng Linked List: UML
H N I V N Â U X N Ễ Y U G N
:
V G
U Ệ I L Ữ D C Ú R T U Ấ C
:
N Ô M
/
4 1 2 1
/
6
X X
/
2 2
2. Dùng Linked List: Đ ph c t p
ứ ạ
ộ
, do đó đ ph c t p khi thêm 1 ế ứ ự ộ ứ ạ
ph n t
H N I V N Â U X N Ễ Y U G N
:
V G
ầ ử • Xóa 1 ph n t ộ ứ ạ ướ ệ ả
• Xóa 1 ph n t
• Vì ta không quan tâm đ n th t vào t p h p là O(1) ậ ợ cho tr ầ ử qua danh sách đ tìm ph n t ể b t kì cũng có đ ph c t p là O(n) ầ ử ấ
c có đ ph c t p là O(n) vì ph i duy t ầ ử
ộ ứ ạ
U Ệ I L Ữ D C Ú R T U Ấ C
:
N Ô M
/
4 1 2 1
/
6
X X
/
3 2
3. Set implementations in Java
• Set is an interface; you can't say new Set() • There are two implementations:
H N I V N Â U X N Ễ Y U G N
:
V G
– java.util.HashSet is best for most purposes – we won't use the other one: TreeSet – Java's set implementations have been optimized so that it is very
• contains method runs in constant time! (How?!)
fast to search for elements in them
U Ệ I L Ữ D C Ú R T U Ấ C
:
N Ô M
• Preferred: Set s = new HashSet();
Not: HashSet s = new HashSet();
/
4 1 2 1
/
6
X X
/
4 2
24
Limitations of Sets
• Why are these methods missing from Set?
H N I V N Â U X N Ễ Y U G N
:
V G
– get(int index) – add(int index, Object o) – remove(int index)
• How do we access the elements of the set? • How do we get a particular element out of the set, such as element 0
or element 7?
U Ệ I L Ữ D C Ú R T U Ấ C
:
• What happens when we print a Set? Why does it print what it
N Ô M
does?
/
4 1 2 1
/
6
X X
/
5 2
25
Iterators for Sets
• A set has a method iterator to create an iterator over the
elements in the set
H N I V N Â U X N Ễ Y U G N
:
V G
• The iterator has the usual methods: – boolean hasNext() – Object next() – void remove()
U Ệ I L Ữ D C Ú R T U Ấ C
:
N Ô M
/
4 1 2 1
/
6
X X
/
6 2
26
Typical set operations
• Sometimes it is useful to compare sets:
– subset: S1 is a subset of S2 if S2 contains every element from
H N I V N Â U X N Ễ Y U G N
:
S1.
V G
• Many times it is useful to combine sets in the following
ways: – union: S1 union S2 contains all elements that are in S1 or S2.
–
intersection: S1 intersect S2 contains only the elements that are in both S1 and S2.
U Ệ I L Ữ D C Ú R T U Ấ C
:
– difference: S1 difference S2 contains the elements that are in S1
N Ô M
that are not in S2.
/
• How could we implement these operations using the
4 1 2 1
/
6
methods in Java's Set interface?
X X
/
7 2
27
How does a HashSet work?
• every object has a reasonably-unique associated
H N I V N Â U X N Ễ Y U G N
:
V G
number called a hash code – public int hashCode() in class Object • HashSet stores its elements in an array a such
that a given element o is stored at index o.hashCode() % array.length – any element in the set must be placed in one exact
index of the array
U Ệ I L Ữ D C Ú R T U Ấ C
– searching for this element later, we just have
:
to check that one place to see if it's there (O(1))
N Ô M
• "Tom Katz".hashCode() % 10 == 6 • "Sarah Jones".hashCode() % 10 == 8 • "Tony Balognie".hashCode() % 10 == 9
/
4 1 2 1
/
• you don't need to understand this...
6
X X
/
8 2
28
Membership testing in HashSets • When testing whether a HashSet contains a given
H N I V N Â U X N Ễ Y U G N
:
V G
–
object: – Java computes the hashCode for the given object looks in that index of the HashSet's internal array
• Java compares the given object with the object in the HashSet's array
using equals; if they are equal, returns true
• Hence, an object will be considered to be in the set only
if both:
U Ệ I L Ữ D C Ú R T U Ấ C
:
–
It has the same hash code as an element in the set, and
N Ô M
– The equals comparison returns true
• an object that is put into a HashSet works best if it has
/
4 1 2 1
/
6
a public int hashCode()method defined – String, Integer, Double, etc. have this already
X X
/
9 2
29
