|
|
Glossary |
Abstract Class
An abstract class is a class that has one or more pure virtual functions in it. Instances of an abstract class cannot be created, and will result in compiler errors if it is attempted.
Abstract Data Type [p. 111, 6/27/97]A programmer-defined data type that has a set of valid values and a group of operations that act on those values
Abstraction [6/27/97]
An idealization that focuses on the essential qualities while disregarding the details; emphasis on the what rather than the how (specification vs. implementation)
Access Function [7/2/97]
A function used to get a copy of a data member from a class, or to set the value of a data member. Access functions are often named by a Get or Set followed by the name or type of the data they modify, for example, GetName to get a copy of the name from a record.
Activation Records [7/16/97]
A data structure created on the stack by every function call. Each activation record contains separate copies of local variables, parameters, and the return address of the function. Activation records are automatically created and destroyed by the compiler.
Address [p. 287, 7/11/97]
A number indicating a location in memory, like a post office box number. Pointers contain addresses.
Address-Of operator [p. 298, 7/9/97]
The & operator in C++, used to get the address of (a pointer to) an instance of a variable.
Append [7/2/97]
Add to the end, for example the AddLast function of a list.
Allocate [p. 312, 7/11/97]
The act of reserving space. Static allocation involves using the program stack, and dynamic allocation (using new) occurs on the heap.
Array [p. 168, 7/2/97]
A collection ADT that is a linear collection of elements of the same type that can be directly accessed.
Assertion [p. 31, 6/25/97]
Form of program documentation that describes state of program execution at some point. Can be in the form of documentation or the assert macro.
Asymptotic Complexity [7/18/97]
The complexity (running-time) of an algorithm as the input size (usually N) increases without limit. The complexity may be for the best, worst, or average case, though the worst case is the most common.
Balanced Tree [p. 619]
A balanced tree is a tree such that picking a different root node and shuffling around the other nodes would not reduce the tree's height. Alternately, it is a tree with balanced subtrees that each have about the same number of nodes. If a binary tree is balanced, operations like traversal, searching, adding, and removing run in O(log N) for N nodes in the tree, instead of O(N) for a degenerate tree.
Base Class [p. 493]
A base class, also known as a superclass, is a more general class than any derived classes (subclasses). A base class should have all common functionality and data that any derived classes should share.
Big-O Notation [p. 545, 7/18/97]
Notation indicating the order (complexity function) of an algorithm. Written as O(f), where f is a function in terms of the input size or other attribute. f must be simplified to the full extent possible using the rules of arithmetic for Big-O expressions, I.E., all constants are discarded, and all terms except the highest order term are discarded.
Binary Search [p. 557, 7/21/97]
A search algorithm that runs in O(log N) time, by starting in the middle of a sorted array and discarding half of the array at each iteration, based on whether the searched-for element is bigger or smaller than the middle one. It must be used on a sorted array to run in O(log N) time.
Binary Expression Tree [p. 624]
A binary tree that contains a representation of a mathematical expression. Travering one in preorder produces a prefix-notation expression, an inorder traversal produces an infix-notation expression, and a postorder traversal produces a postfix-notation expression. To evaluate a binary expression tree, use a postorder traversal. Evaluate each subtree first, and then combine the results using the operator at the node, and return the result.
Binary Search Tree [p. 615]
A binary search tree is a binary tree that has the additional property that all values in the left subtree are less than the value in the root, and all values in the right subtree are greater than the root. This property is applied recursively to the entire tree. A search of a binary search tree runs in O(log N) time for N nodes in the best case, or O(N) time for a degenerate tree. Not all binary trees are binary search trees.
Binary Tree [p. 606]
A binary tree is a tree whose nodes have zero, one, or two children. Not all trees are binary trees.
Chaining [p. 570]
Chaining is one method of dealing with collisions in hash tables. Every entry in the hash table array (called a bucket) is actually a linked list (called a chain). When adding an element to a hash table using chaining, the data element is added to the chain in the bucket corresponding to the hash function's value for the data. Removing or finding operations take place on the chain, as well.
Class [p. 111, 6/27/97]
A C++ construct similar to a struct, but that allows for public and private members, which may be functions and data. Very useful when creating ADT's.
Class Scope [p. 116, 6/27/97]
The scope of members of a class. Private class members are visible only to other class members. Public class members are visible to other class members and to clients, and clients must use specify the class instance followed by the selection operator ('.') to access public members.
Classification Hierarchy [p. 492]
Also known as a inheritance hierarchy, a classification hierarchy is a diagram which shows what classes are base classes and which classes are subclasses of which superclasses. It illustrates the inheritance relationships between classes.
Collision [p. 565]
A collision is the term for two different pieces of data have the same hash value.
Complexity Function [pp. 542-3, 7/18/97]
A complexity function measures the efficiency of an algorithm. It also indicates how quickly the running time (in steps) grows as the input size (often N) increases. Common complexity functions include (in increasing order of complexity): O(1) for constant time, O(log N) for logarithmic, O(N) for linear, O(N log N), O(N2) for quadratic, O(N3) for cubic, O(Nk) for polynomial, and O(2N) for exponential.
Concrete ClassA concrete class is a class that has no pure virtual functions in it, unlike an abstract class.
Constructor[p. 121, 6/30/97]
A special member function of a class that is invoked automatically when an instance of a class is created. It is used to perform initialization of a class automatically, and is often overloaded to provide the ability to pass parameters to be used in initialization.
Copy Constructor [p. 321, 7/14/97]
A special constructor that takes a reference to an instance of the same class as its parameter and initializes the invoking instance to be a copy of the parameter.
Dangling Pointer [p. 317, 7/11/97]
A pointer that no longer points to a valid box of memory. For example, a pointer after delete has been used on it but before it has been reassigned.
Deep Copy [p. 327, 7/14/97]
The act of making a duplicate of a class or struct that contains dynamic data so that the copy contains separate memory, unlike a shallow copy.
Degenerate Tree [p. 619]
A degenerate tree is a tree that has height proportional to the number of nodes. For example, a binary tree with only left children is a degenerate tree. Most tree operations take O(N) time on a degenerate tree, instead of O(log N) as for a balanced tree.
Dereference operator [p. 290, 7/9/97]
The * operator, used to access the box (memory) a pointer points to.
Derived Class [p. 493]
A derived class, also known as a subclass, is a more specific class than its base classe or classes (superclass). A derived class automatically inherits all data and functions from the base class. It can add new functions and data, and also override any functions from the base class to do something more appropriate to the derived class.
Destructor [p. 323, 7/14/97]
A special class member function that is used to automatically deallocate (free) any dynamic memory associated with a class when the class is deleted or goes out of scope. It has the same name as the class but is preceeded by a tilde (~), and never takes any parameters. It should never be invoked directly.
Direct Access [p. 170, 7/2/97]
The ability to access an element in a collection ADT directly, without needing to access other elements. An array is a collection ADT that is direct access as the [] operator can be used to directly index an element.
Direct Addressing [p. 290, 7/9/97]
Accessing a variable directly, through its name, as opposed to indirectly, through a pointer.
Divide and Conquer [7/21/97]
A description for a type of algorithm that is characterized by dividing the input into smaller pieces, conquering (solving) the pieces separately, and then putting them back together again if necessary. Many divide and conquer algorithms have a complexity that has a logarithmic component, such as the O(log N) running time of binary search, or O(N log N) of Quicksort.
Dynamic Dispatching
The use of virtual functions in C++ to cause the run-time (dynamic) type of what a pointer or reference points to when determining which version of a function to call. It involves looking up the object's actual type in a table at run-time and then calling the appropriate function.
Dynamic Memory [p. 311, 7/9/97]
Memory allocated on the heap through the new operator, and returned to the heap through the delete operator.
Encapsulation [p. 58, 6/25/97]
Grouping together and hiding of information
Hash Function [p. 564]
A hash function is a function that computes a numeric value for the data given it, and returns an integer between 0 and N-1 for a hash table with N buckets in its array. Hash functions must return the same value for the same input, and should be fast to compute.
Hash Table [p. 565]
A hash table is a data structure designed to store large numbers of elements and provide efficient access. Hash tables consist of an array of buckets (if using chaining), and all have a hash function that returns an integer between 0 and N-1, where N is the array size. With a good hash function and a large enough array, all hash table operations take O(1) time on average.
Heap [7/11/97]
A portion of memory that contains all dynamic memory, allocated using new.
Heterogenous [p. 173, 7/2/97]
Not all of the same type, often used when characterizing the data contained in a collection ADT. Fields of a record are heterogenous, as they may be of different types.
Homogenous [p. 171, 7/2/97]
Of the same type, often used when characterizing the data contained in a collection ADT. Elements of an array or list are homogenous, as they must be of the same type.
Implementation [6/25/97]
Private portion of module that does what the specification says it does, I.E., the "how". Found in .cpp files in C++.
Indirect Addressing [p. 291, 7/9/97]
Accessing a variable through a pointer, as opposed to directly through its name.
Inheritance [p. 493]
Inheritance is the process by which derived classes automatically gain all public and protected functions and all data members of their base class. The derived class can add more functions or data, or override functions from the base class, but cannot remove any of them. Constructors and destructors are never inherited.
Inorder Traversal [p. 621]
A form of tree traversal that only applies to binary trees. The left subtree is recursively traversed in inorder order, then the node is visited, and then the right subtree is recursively traversed in inorder order.
Instance [p. 111, 6/27/97]
A particular case or occurrance of a type; can have many instaces of a type in a program. x and y are instances of the int type in the statement int x, y;
Instantiate [p.114, 6/27/97]
The act of creating an instance of a type.
Interface [p. 58, 6/25/97]
Describes services a module provides to clients, "what" a module does. Found in .h files in C++. Information in the interface is public.
Interior Node
A node of a tree that has any children.
Invariant [p. 124, 6/30/97]
An assertion that describes what characteristics must be true at all times about a class. It is essentially a precondition and postcondition for all functions.
Invoke
The act of calling a function
Leaf Node [p. 606]
A node of a tree that has no children.
Linear [p. 170, 7/2/97]
Characterization of a data structure whose elements form a line, I.E., there is a unique first element, a unique last element, every element except the first has a unique predecessor, and every element except the last has a unique successor. An array is an example of a linear data structure.
Linear Search [p. 556, 7/21/97]
A search algorithm that starts at the first element and iterates through each one in turn until the desired element is found or all elements have been examined. It runs in O(N) time, and can be used on an array or linked list, sorted or unsorted, without changing its performance.
Linked List [p. 341, 7/9/97]
A list of blocks known as nodes that consist of two fields (data of some sort and a pointer next to another node). Nodes are connected together by the next pointers. A special pointer known as the Head points to the first node, and another pointer known as the Cursor indicates the current node. Nodes are allocated dynamically, so a linked list can contain any number of nodes. Clients often have direct access to all parts of a linked list, so a linked list is not really an ADT as such. Linked lists are often used when implementing a List ADT.
List [p. 174, 7/2/97]
A collection ADT that contains a number of elements of the same type, can vary in length, and whose access is sequential. Operations include IsEmpty, IsFull, and Size for testing the list's state, Start, NextElement, IsEnd, and Data to manipulate the list's cursor (current item), AddBefore, AddAfter, AddFirst, and AddLast for inserting elements into the list, and Remove for removing the current element from the list and returning its value.
Member [p. 113, 6/27/97]
Part of a definition or type, like a field in a struct. In a C++ class, members can be functions and data, and may be private or public.
Memory Leak [p. 319, 7/11/97]
A block of memory allocated on the heap that has no pointers pointing to it, or no method to access it. Leaked memory cannot be deallocated (freed) until the program exits, and may result in the heap becoming full.
Modularization [p. 57, 6/25/97]
The process of breaking a larger problem or program into smaller units
Module [p. 57, 6/25/97]
Collection of related items (data and functions) packaged together
Nonlinear [p. 170, 7/2/97]
Characterization of a data structure whose elements don't have a linear ordering. A mathematical set and a bag of marbles are examples of nonlinear data structures.
NULL pointer [p. 290, 7/9/97]
A special pointer that is a pointer-to-nothing. Any pointer of any type can be set equal to NULL, and pointers can be compared with NULL. In particular, the last node in a linked list has a NULL next pointer.
Object-Oriented Design
Object-oriented design is a design methodology in which the problem is thought about and solved from the point of view of the objects (data and operations on that data) as opposed to the control flow. Object-oriented designs tend to be robust to changes, can be tested and evaluated early on through the use of prototyping, and may be a more appropriate approach to solving many types of problems.
Object-Oriented Programming [p. 491]
Object-oriented programming (or OOP) is the use of abstract data types, plus inheritance, plus dynamic dispatching to write a program.
Overloading [6/30/97]
Multiple functions with the same name, but different numbers and types of parameters.
Perfect Hash Function [p. 565]
A perfect hash function is a hash function that minimizes the number of collisions that occur, by providing a uniform distribution for any data.
Pointer [p. 287, 7/9/97]
A handle or alternate name for a box of memory. All pointers have a type, for example, Pointer-to-Int. Declared by the name of the type, then a *, then the variable name. For example, int *A; declares a pointer named A that points to an integer.
Postorder Traversal [p. 622]
A form of tree traversal. First, the children are traversed in any order in a postorder fashion, and then the node is visited. For a binary tree, the left subtree is traversed before the right one.
Preorder Traversal [p. 622]
A form of tree traversal. First, the node is visited, and then the children are traversed in any order in a preorder fashion. For a binary tree, the left subtree is traversed before the right one.
Prepend [7/2/97]
Add at the beginning, for example the AddFirst member function of a List.
Private [p. 113, 6/27/97]
Keyword used in the definition of a C++ class to specify which parts of the interface are hidden to the client. Class member functions (both public and private) can still access private data and functions.
Public [p. 113, 6/27/97]
Keyword used in the definition of a C++ class to specify which parts of the interface are visible (accessable) by clients and class member functions.
Pure Virtual Function
A pure virtual function is a virtual class member function that acts as a placeholder. The function cannot be implemented for that class, but all subclasses must either declare and implement the function, or declare the function as a pure virtual function themselves. If a class has any pure virtual functions, it is known as an abstract class, and no instances of it can be created.
Queue [p. 181, 7/7/97]
A collection ADT consisting of varying amounts of data of the same type. All additions to a queue are to the back and all removals come from the front. The Enqueue function is used to add an element to the queue, and Dequeue to remove the first element and return it. Front is used to return a copy of the first element from the queue.
Quicksort [p. 579, 7/21/97]
A sorting routine that chooses a pivot value from some position in the array, partitions the array so that all values less than the pivot are in the lower portion of the array and all greater are in the upper portion, with the pivot in between, and then recursively calls itself on the two portions of the array. It runs in O(N log N) time on average, but has a worst case time of O(N2) if the input is sorted or reverse-sorted.
Record [p. 172, 7/2/97]
A collection ADT that consists of a group of elements known as fields that may be of different types. Record operations include getting or setting the value of a field. The struct or class is commonly used when implementing a record ADT in C++.
Recursion [p. 237, 7/16/97]
Something defined in terms of itself. The two aspects of recursion that are dealt with most frequently are recursive functions, that call themselves, and recursive data structures, that contain pointers to other instances of the data structure.
Recursive Data Structures [7/16/97]
Data structures that contain pointers to other instances of the same data structure, such as the Node in a linked list that contains a pointer to the next node.
Recursive Function [p. 244, 7/16/97]
A recursive function is a function that calls itself. All recursive functions must contain two parts, one or more base case(s) that are non-recursive in nature, and one or more recursive calls that operate on a smaller or simpler form of the input. The base case(s) must be tested before the recursive calls, or infinite recursion results.
Root [p. 603]
The root is a special node in a tree that is the base of the tree. All trees except the empty tree have exactly one root; the empty tree has no root and no nodes. The root node is the only node in a tree that has no parent.
Scope [6/27/97]
The part of a program where a name (variable, constant, parameter, etc.) is visible.
Scope Resolution Operator [p. 119, 6/27/97]
The double-colon ('::') operator. When implementing class member functions, the class name followed by :: must come before the function name.
Selection Sort [p. 573, 7/21/97]
A simple sorting algorithm that always runs in O(N2) time.
Sequential Access [p. 170, 7/2/97]
A characteristic of data structures where accessing an element may require accessing other elements first, such as stepping through the elements in a list.
Set [p. 185, 7/7/97]
A collection ADT that consists of a group of elements of the same type. There is no ordering among the elements, and no duplicates are allowed. Operations consist of Add, Remove, and IsMemeber to add or remove an element and to test if an element is in the set, as well as aggregate operations of Union, Intersection, and Difference that act on pairs of sets.
Shallow Copy [p. 327, 7/14/97]
Also known as a bitwise copy, a shallow copy of a struct or class is a copy where any pointers in the copy of the object point to memory in the original, as opposed to separate blocks of memory as in a deep copy.
Specification [p. 58, 6/25/97]
Synonym for interface
Stack [p. 177, 7/7/97]
A collection ADT consisting of data of the same type, that is accessed only from one end. The Push function is used to add an element to the top of the stack, the Pop function removes and returns the top element from the stack, and the Top function returns a copy of the top element of the stack.
Subtree [p. 605]
A subtree is any tree that is part of a larger tree.
Table [7/7/97]
A collection ADT that holds a group of key-value pairs. All keys are of the same type and all values are of the same type. Operations include Fetch, to get the value (data) associated with a key (index), Store, to associate some value with a key, Remove to remove a key and its associated value from the table, and IsMember to test if a key is in a table.
Tail Recursion [p. 268, 7/16/97]
Tail recursion is any recursing where the recursive call comes at the end of the recursive function. It is usually easy to write an interative (loop-based) version of a tail-recursive function.
Tree [p. 603]
A tree is a hierarchical data structure made out of nodes. Each node may have zero or more children, and all nodes except the root node have exactly one parent. Trees are recursive data structures.
Virtual Function [p. 521]
When a virtual function is called from a pointer or reference to an object, dynamic dispatching is used to determine which version of the function to actually call. Functions are specified as virtual by using the virtual keyword at the beginning of the function's definition in the interface.