Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
| dynamic | the type of sets manipulated by algorithms. They can grow, shrink, or otherwise change over time.
(See page 197)
|
 |
|
|
| dictionary | A dynamic set that supports the operations to insert elements into, delete elements from, and test membership in a set.
(See page 197)
|
|
|
|
| key | In a typical implementation of a dynamic set, each element is represented by an object whose fields can be examined and manipulated if we have a pointer to the object. Some kinds of dynamic sets assume that one of the object's fields is an identifying key field. If the keys are all different, we can think of the dynamic set as being a set of key values.
(See page 197)
|
|
|
|
| satellite data | An object may contain satellite data, which are carried around in other object fields but are otherwise unused by the set implementation.
(See page 197)
|
|
|
|
| queries | operations on a dynamic set which simply return information about the set
(See page 198)
|
|
|
|
| modifying operations | operations on a dynamic set which change the set
(See page 198)
|
|
|
|
| stack | In a stack, the element deleted from the set is the one most recently inserted: the stack implements a last-in, first-out, or LIFO, policy.
(See page 200)
|
|
|
|
| queue | In a queue, the element deleted is always the one that has been in the set for the longest time: the queue implements a first-in, first-out, or FIFO, policy.
(See page 200)
|
|
|
|
| empty | the stack contains no elements, top[S] = 0
(See page 201)
|
|
|
|
| underflows | If an empty stack is popped, we say the stack underflows, which is normally an error.
(See page 201)
|
|
|
|
| overflows | If top[S] exceeds n, the stack overflows.
(See page 201)
|
|
|
|
| tail | In a FIFO queue when an element is enqueued, it takes its place at the tail of the queue.
(See page 202)
|
|
|
|
| head | In a FIFO queue when an element is dequeued it is always the one at the head of the queue.
(See page 202)
|
|
|
|
| linked list | a data structure in which the objects are arranged in a linear order
(See page 204)
|
|
|
|
| doubly linked list | a object with a key field and two other pointer fields: next and prev.
(See page 204)
|
|
|
|
| singly linked list | If a list is singly linked, we omit the prev pointer in each element.
(See page 204)
|
|
|
|
| sorted list | If a list is sorted, the linear order of the list corresponds to the linear order of keys stored in elements of the list; the minimum element is the head of the list, and the maximum element is the tail.
(See page 204)
|
|
|
|
| unsorted list | If the list is unsorted, the elements can appear in any order.
(See page 204)
|
|
|
|
| circular list | In a circular list, the prev pointer of the head of the list points to the tail, and the next pointer of the tail of the list points to the head.
(See page 204)
|
|
|
|
| sentinel | a dummy object that allows us to simplify boundary conditions. For example, suppose that we provide with list L an object nil[L] that represents NIL but has all the fields of the other list elements. Whenever we have a reference to NIL in list code, we replace it by a reference to the sentinel nil[L].
(See page 206)
|
|
|
|
| circular, doubly linked list with a sentinel | the sentinel nil[L] is placed between the head and tail; the field
next[nil[L]] points to the head of the list, and prev[nil[L]] points to the tail. Similarly, both the next field of the tail and the prev field of the head point to nil[L]. Since next[nil[L]] points to the head, we can eliminate the attribute head[L] altogether, replacing references to it by references to next[nil[L]]. An empty list consists of just the sentinel, since both next[nil[L]] and prev[nil[L]] can be set to nil[L].
(See page 206)
|
|
|
|
| garbage collector | responsible for determining which objects are unused.
(See page 210)
|
|
|
|
| free list | singly linked list containing free objects. The free list uses only the next array, which stores the next pointers within the list. The head of the free list is held in the global variable free. When the dynamic set represented by linked list L is nonempty, the free list may be intertwined with list L. Each object in the representation is either in list L or in the free list, but not in both. The free list is a stack: the next object allocated is the last one freed.
(See page 211)
|
|
|
|
| left-child, right-sibling representation | a clever scheme for using binary trees to represent trees with arbitrary numbers of children. It has the advantage of using only O(n) space for any n-node rooted tree. Each node contains a parent pointer p, and root[T] points to the root of the tree T. Each node x has only two pointers: 1. left-child[x] points to the leftmost child of node x, and 2. right-sibling[x] points to the sibling of x immediately to the right. If node x has no children, then left-child[x] = NIL, and if node x is the rightmost child of its parent, then right-sibling[x] = NIL.
(See page 214)
|
2002 McGraw-Hill Higher Education