Data Structures: Difference between revisions
| Line 9: | Line 9: | ||
Some dynamic sets assume that one of the element's attributes is an identifying '''key'''. If the keys are all different, we can think of the dynamic set as being a set of key values. Some dynamic sets assume that the keys are drawn from a ''totally ordered set'', such as the real numbers, or the set of all worlds under the usual alphabetic ordering. A total ordering allows defining a minimum element of the set, or to speak of the next element larger than the given element. | Some dynamic sets assume that one of the element's attributes is an identifying '''key'''. If the keys are all different, we can think of the dynamic set as being a set of key values. Some dynamic sets assume that the keys are drawn from a ''totally ordered set'', such as the real numbers, or the set of all worlds under the usual alphabetic ordering. A total ordering allows defining a minimum element of the set, or to speak of the next element larger than the given element. | ||
A dynamic set that allows ''insertion'' of new elements, ''deletion'' of existing elements and ''membership testing'' (or search) for a specific element is called a '''dictionary'''. Of these, the insertion and deletion modifies the set, and they are called | A dynamic set that allows ''insertion'' of new elements, ''deletion'' of existing elements and ''membership testing'' (or search) for a specific element is called a '''dictionary'''. Of these, the insertion and deletion modifies the set, and they are called ''modifying operations'', whereas the search does not. As such, the search operation belongs to the ''query'' category of operations. | ||
Revision as of 02:34, 10 August 2018
Internal
Overview
All data structures used to represent data in the memory of a computer are at essentially sets. Unlike a mathematical set, the sets manipulated by computers are finite, and their composition change in time, so they are called dynamic. We know from mathematics that the elements of a set are distinct. Data structure sets also consist of distinct elements, if we conceptualize the fact that the elements are maintained in distinct memory locations. In a typical implementation of a dynamic set, each element is represented by an object (memory location) whose attributes can be examined and manipulated if we have a pointer or a reference to the objects. Different objects have different references.
Some dynamic sets assume that one of the element's attributes is an identifying key. If the keys are all different, we can think of the dynamic set as being a set of key values. Some dynamic sets assume that the keys are drawn from a totally ordered set, such as the real numbers, or the set of all worlds under the usual alphabetic ordering. A total ordering allows defining a minimum element of the set, or to speak of the next element larger than the given element.
A dynamic set that allows insertion of new elements, deletion of existing elements and membership testing (or search) for a specific element is called a dictionary. Of these, the insertion and deletion modifies the set, and they are called modifying operations, whereas the search does not. As such, the search operation belongs to the query category of operations.