2.1 Informal Definition

If you've written even a few programs, you've probably noticed the necessity for searchable collections of data. Compilers search their symbol tables for identifiers and network servers often search tables to match up data with users. Many applications with graphical user interfaces deal with mouse and keyboard activity by searching a table of possible actions. In fact, just about every nontrivial program, regardless of application domain, needs to maintain and search tables of some kind.

In this book, the term “table” does not refer to any particular data structure. Rather, it is the name for a abstract data structure or ADT, defined in terms of the operations that can be performed on it. A table ADT can be implemented in any number of ways. Later chapters will show how to implement tables in terms of various binary tree data structures.

The purpose of a table is to keep track of a collection of items, all of the same type. Items can be inserted into and deleted from a table, with no arbitrary limit on the number of items in the table. We can also search a table for items that match a given item.

Other operations are supported, too. Traversal is the most important of these: all of the items in a table can be visited, in sorted order from smallest to largest, or from largest to smallest. Traversals can also start from an item in the middle, or a newly inserted item, and move in either direction.

The data in a table may be of any C type, but all the items in a table must be of the same type. Structure types are common. Often, only part of each data item is used in item lookup, with the rest for storage of auxiliary information. A table that contains two-part data items like this is called a “dictionary” or an “associative array”. The part of table data used for lookup, whether the table is a dictionary or not, is the key. In a dictionary, the remainder is the value.

Our tables cannot contain duplicates. An attempt to insert an item into a table that already contains a matching item will fail.

Exercises: