apmatrix: A C++ templated class used to represent two dimensional arrays.
apqueue: (AB only): A C++ templated class used to represent queues ( first-in-first-out data structures ).
apstack: (AB only): A C++ templated class used to represent stacks ( first-in-last-out data structures ).
apstring: A C++ class used to represent strings ( sequences of characters ).
apvector: A C++ templated class used to represent arrays.
argument: Same as "actual parameter".
arithmetic operators: + - * / % ( addition, subtraction, multiplication, division, and modulus ).
arrow operator: (AB only): Used to access a field or struct or a data member of a class or a member function of a class pointed to by a pointer. For example, p -> data.
assert: Defined in standard library assert.h; permits a runtime check of an assertion (a condition that should hold at a particular point in a program). For example: assert( x >= 0 );.
assignment operators: =, +=, -=, *=, /=, %= ( plain assignment, add then assign, subtract then assign, multiply then assign, divide then assign, modulus then assign ).
average-case time/space: (AB only): The amount of time or space that an algorithm will require on average.
base case: Every recursive function must have a base case, a condition under which the function does not call itself.
big-O: (AB only):Notation used for expressing the time or space required by an algorithm.
binary search: An efficient technique for finding the value in a sorted array; a value can be found in an array of N elements in time proportional to log base 2 of N ( see also "sequential search" ).
binary search tree: (AB only):A data structure that supports efficient insertion and look-up of ordered values ( O(log n) if the tree is balanced ).
binary tree: A tree in which every node has at the most two children.
break statement: a statement that can only appear inside a loop or in the case of a switch statement; it causes control to be transferred outside the loop, or to the end of the switch.
casting: Used to convert one data type to another. for example, int(3.5) converts the floating point value 3.5 to an integer ( by truncating it to 3 ).
cin: The standard input stream.
circular linked list: (AB only)A linked list in which the last node points back to the first node.
class: One mechanism provided by C++ ( and other object oriented languages ) to support abstract data types ( see also "struct" ).
compound assignment: +=, -=, *=, /=, %= ( add then assign, subtract then assign, multiply then assign, divide then assign, modulus then assign ).
const: Part of a variable, parameter, or class member function declaration. The value of a const variable can only be initialized, it cannot be changed in the body of a function; a const member function cannot change the values of the data of the members of the class.
constant time/space: (AB only): The amount of time or space required by an algorithm or data structure is independent of the amount of data; if the amount of data doubles, the amount of time or space will stay the same.
constructor function: A class's constructor function(s) should initialize the data members of the class.
copy constructor: (AB only): A class's copy constructor makes a copy of a class object; it is called when a class object is passed by value to a function, is returned by value from a function, or is used to initialize another newly declared object of the same class.
cout: The standard output stream.
dangling pointer: (AB only): A pointer that points to memory that has been returned to free storage.
data member: A variable associated with each instance of a class.
decrement operator: -- ( subtracts one from its operand ).
default: A switch statement can end with a default case, which will execute if none of the case labels matches the value of the switch expression.
delete operator: (AB only): Used to return memory to free storage.
dequeue: (AB only): One of the operations provided for the apqueue class; one version just removes the item at the front of the queue; another version removes that item and also returns it via a reference parameter.
dereferencing operator: (AB only): The * operator; used to access the object pointed to by a pointer. For example, *p = 5.
destructor function: (AB only): A class should have a destructor function if it includes any pointer data members; the destructor function should return the storage pointed to by the pointer data members to free storage.
do loop: A loop of the form do statement while ( expression ). A do loop always executes at least once ( see also "while loop" ).
doubly-linked list: (AB only): A linked list in which each node has two pointers: one that points to the next node in the list and one that points to the previous node in the list( see also "singly-linked list" ).
efficiency: How much time and/or space is required by an algorithm or data structure.
enqueue: (AB only): One of the operations required for the apqueue class; it adds a given item to the end of the queue.
equality operators: == and != ( equal and not equal to ).
exponential time/space: (AB only): If the amount of the data increases by one, the amount of time/space required by the algorithm will double.
find: One of the operations provided for the apstring class; it returns the starting position of the first occurence of a given string.
for loop: A loop of the form: for( init-expression; test-expression; update-expression ) statement.
formal parameter: One of the identifiers listed in a function header that corresponds to the values passed when the function is called ( see also "actual parameter" )
front: (AB only): One of the operations provided for the apqueue class; it returns the item at the front of the queue without removing it from the queue.
hashtable: (AB only):A data structure used to support efficient insert and look-up operations ( can have a O(1) average-case time ).
if statement: A statement of the form if ( expression ) statement or if ( statement ) else statement.
ifstream: The type of an input file stream.
implementation: The part of a class definition that includes its private data members, its private member functions, and the bodies of all member functions. Clients of the class do not need to know anything about its implementation. ( see also "interface" )
increment operator: ++ ( adds one to the operand )
indirect assignment: (AB only): Assign a value to a memory location pointed to by a pointer using the star operator. For example, *p=5.
inorder traversal: (AB only): Visit all nodes of a binary tree using the following algorithm: Visit the left subtree in order, visit the root, visit the right subtree in order.
insertion sort: A sorting algorithm that takes time proportional to N^2.
interface: The part of a class definition needed by a client of the class; the declarations of the public data members and member functions ( see also "implementation" ).
isEmpty: (AB only): One of the operators provided for the apstack class; it returns true if the stack is empty and otherwise returns false. Also one of the operators provided for the apqueue class; it returns true if the queue is empty and otherwise returns false.
istream: The type of an input stream ( e.g., cin ).
iteration: One execution of the body of a loop.
length: One of the operations provided for the apstring class; it returns the number of characters in the string. Also, one of the operations provided for the apvector class; it returns the size of the array.
linear time/space: (AB only):If the amount of data doubles, the amount of time or space required by the algorithm or data structure will also double.
linked list: (AB only): A common data structure used to represent an ordered collection of objects ( see also "doubly-linked list, circular linked list, singly-linked list." )
logarithmic time/space: (AB only): If the amount of data doubles, the amount of time or space required by the algorithm or data structure will increase by 1.
logical operators: ! && || ( logical NOT, logical AND, logical OR )
main function: Every program must include a function named main.
makeEmpty: (AB only): One of the operators provided for the apstack class; it makes the stack empty. Also one of the operations provided for the apqueue class; it makes the queue empty.
matrix: A two-dimensional array.
member function: One of the functions associated with a class.
member initialization list: One way for a class's constructors to initialize its data members.
merge sort: A sorting algorithm that takes time proportional to log2N to sort N items.
new operator: (AB only): Used to allocate memory from free storage.
NULL: (AB only): A special value used for a pointer that doesn't point to any address.
numcols: One of the operations provided for the apmatrix class; it returns the number of columns in the array.
numrows: One of the operations provided for the apmatrix class; it returns the number of rows in the matrix.
ofstream: the type of an output stream.
operator=: (AB only): The name of the assignment operator ( used when overloading the operator ).
orphan: (AB only): Memory that has been allocated from free storage and not returned but that is no longer pointed to by any pointer.
ostream: The type of an output stream ( e.g., cout ).
overloading Defining two versions of a function with the same name but different numbers or types of parameters.
parameter: same as "formal parameter"
pointer: (AB only): A variable whose value is a memory location.
pointer equality: (AB only): When two pointers are compared using == or !=, they are considered to be equal only if they point to the same address; if they point to different addresses that contain the same value, the pointers are considered not equal.
pointer parameters: (AB only): When a pointer is passed as a value parameter, the pointer itself cannot be changed by the function, but the contents of the location that it points to can be changed.
pop: (AB only): One of the operations provided for the apstack class; one version just removes the top item from the stack; another version removes the top item and returns it via a reference parameter.
postcondition: A function's postcondition specifies what will be true when the function returns, assuming that the function's preconditions are satisfied when it is called.
postorder traversal: (AB only): Visit all nodes of a binary tree using the following algorithm: Visit the left subtree in postorder; visit the right subtree in postorder; visit the root.
pow: Defined in the standard library math.h; pow (x,y) returns x to the y power
precondition: A function's precondition specifies what is expected to be true whenever the function is called.
preorder traversal: (AB only): Visit all nodes of a binary tree using the following algorithm: Visit the root; visit the left subtree in inorder; visit the right subtree in inorder.
private: One of the levels of access that can be specified for a class's data members and function; private members can be accessed only from the class's member functions ( see also "public" ).
public: One of the levels of access that can be specified for a class's data members and member functions: public functions can be accessed from outside the class ( see also "private" ).
push: (AB only): One of the operations provided for the apstack class; adds a given item to the top of the stack.
quadratic time/space: (AB only): If the amount of data doubles, the amount of time or space required by the algorithm or data structure will quadruple.
quick sort: A sorting algorithm that takes time proportional to log2N to sort N items if good choices are made for the pivot items and otherwise takes time proportional to N^2.
recursive function: A function that calls itself ( either directly or indirectly ).
reference parameter: When a formal parameter is a reference parameter, any changes made to the formal parameter by the function are applied to the corresponding actual parameter (see also "value parameter")
relational operators: < <= > >= (less than, less than or equal to, greater than, greater than or equal to).
resize: One of the operations provided for the apmatrix class; it changes the size of the array to the given number of rows and columns. Also one of the operations provided for the apvector class; it changes the size of the array to the given number of elements.
return statement: Executing a return statement causes control to be transferred from the currently executing function to the calling function; for a non-void function, a return statement is used to return a value.
return type: The type returned by a non-void function.
selection sort: A sorting algorithm that takes time proportional to N^2 to sort N items.
sequential sort: An algorithm that looks for a value in an array by starting with the first element and examining each element in turn; it requires time proportional to the size of the array on average ( see also "binary search" ).
shallow copy: (AB only): A copy of a data structure ( e.g., a class ) that includes pointers, in which the values of the pointers are copied rather than copying the objects pointed to.
short-circuit evaluation: Evaluation in which expressions involving the logical AND and OR operators are guaranteed to be evaluated from left to right, and evaluation stops as soon as the final value is known.
singly-linked list: (AB only): A linked list in which each node has only one pointer, which points to the next node in the list ( see also "doubly-linked list, circular-linked list ).
sqrt: Defined in the standard library math.h; sqrt(x) returns the square root of x.
star operator: (AB only): same as "dereferencing operator".
storage leak: (AB only): A program that fails to deallocate memory that has been allocated from free storage and is no longer accessible has storage leaks ( see also "orphan" ).
struct: The same as a class except that the default access for data members and member functions is public instead of private.
substr: One of the operations provided for the apstring class; returns the substring of the given length, starting with the character in the given position.
switch statement: A statement of the form switch( expression ) { case value1: statement-list break; case value2: statement-list break;....case valueN: statement-list break;}
templated class: A class that can be instantiated for different data types. For example apvector, apmatrix, apstack, and apqueue are templated classes.
top: (AB only): One of the operations provided for the apstack class; it returns the top element of the stack ( without popping it ).
traversal: (AB only): An algorithm for visiting all nodes of a binary tree ( see also "inorder traversal" "postorder traversal" "preorder traversal" ).
tree height: (AB only): the height of an empty tree is 0; the height of a non-empty tree is the number of nodes in the longest path from the root to a leaf.
tree leaf: (AB only): A tree node with no outgoing edges.
tree parent: (AB only): If a tree includes an edge from node n to node m then n is the parent of m.
tree root: (AB only): A tree node with no incoming edges.
value parameter: When a formal parameter is a value parameter, changes made to the formal parameter by the function do not change the corresponding actual parameter ( see also "reference parameter" ).
void: (AB only): The type of a function that performs an action rather than computing ( and returning ) a result.
while loop: A loop of the form while (expression) statement. A while loop may execute zero times. ( see also "do loop" ).
worst-case time/space: (AB only): The amount of time or space that an algorithm or data structure will require in the worst case.