Data Structures: Difference between revisions
| Line 7: | Line 7: | ||
All data structures used to represent data in the memory of a computer are at essentially <span id='Set'></span>'''sets'''. Unlike a mathematical [[Set|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. | All data structures used to represent data in the memory of a computer are at essentially <span id='Set'></span>'''sets'''. Unlike a mathematical [[Set|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 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'' for a specific element is called a '''dictionary'''. | 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'''. | ||
Revision as of 02:31, 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.