Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
This chapter provides knowledge of sets. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Sets and Multimaps 3/19/14 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Sets and Multimaps © 2014 Goodrich, Tamassia, Goldwasser Sets and Multimaps 1 Definitions ! A set is an unordered collection of elements, without duplicates that typically supports efficient membership tests. n Elements of a set are like keys of a map, but without any auxiliary values. ! A multiset (also known as a bag) is a set-like container that allows duplicates. ! A multimap is similar to a traditional map, in that it associates values with keys; however, in a multimap the same key can be mapped to multiple values. n For example, the index of a book maps a given term to one or more locations at which the term occurs. © 2014 Goodrich, Tamassia, Goldwasser Sets and Multimaps 2 1 Sets and Multimaps 3/19/14 Set ADT © 2014 Goodrich, Tamassia, Goldwasser Sets and Multimaps 3 Storing a Set in a List ! We can implement a set with a list ! Elements are stored sorted according to some canonical ordering ! The space used is O(n) Nodes storing set elements in order List ∅ Set elements © 2014 Goodrich, Tamassia, Goldwasser Sets and Multimaps 4 2 Sets and Multimaps 3/19/14 Generic Merging ! Generalized merge Algorithm genericMerge(A, B) ! ! of two sorted lists A and B Template method genericMerge Auxiliary methods n n n aIsLess bIsLess bothAreEqual ! Runs in O(nA + nB) time provided the auxiliary methods run in O(1) time © 2014 Goodrich, Tamassia, Goldwasser S ← empty sequence while ¬A.isEmpty() ∧ ¬B.isEmpty() a ← A.first().element(); b ← B.first().element() if a < b aIsLess(a, S); A.remove(A.first()) else if b < a bIsLess(b, S); B.remove(B.first()) else { b = a } bothAreEqual(a, b, S) A.remove(A.first()); B.remove(B.first()) while ¬A.isEmpty() aIsLess(a, S); A.remove(A.first()) while ¬B.isEmpty() bIsLess(b, S); B.remove(B.first()) return .
