Page 144 - Data Structures Handout_Neat
P. 144
arrays or hash tables, depending on the requirements for speed and memory usage.
Understanding tables is essential for applications such as database indexing, symbol tables in
compilers, and information management systems.
11.2.1 Definition of Tables (ADT)
A table is an abstract data type (ADT) that stores data in a structured format, typically
as key-value pairs or in tabular form. Each entry in a table consists of a key (used for
identification) and a value (the associated data). Tables allow efficient insertion, deletion, and
search operations, making them a fundamental component of many software systems.
11.2.2 Relations to Arrays and Hash Tables
Tables can be implemented using arrays, where each row corresponds to an index in
the array. However, this approach may be inefficient when dealing with large datasets or
sparse data. A more efficient implementation uses hash tables, where keys are mapped to
indices using a hash function. This allows faster access times and reduces memory overhead.
Thus, tables serve as a conceptual bridge between arrays and hash tables.
11.2.3 Applications in Databases and Information Systems
Tables are widely used in databases to store structured records such as student
information, employee data, or product inventories. They are also used in compilers to
maintain symbol tables, which track variable names and their associated attributes. In
operating systems, tables are used for process management and resource allocation. Their
versatility makes them one of the most important data structures in computing.
11.2.4 Example Implementation in C++
The following program demonstrates a simple table implementation using arrays,
where each entry stores a student ID and name.
144
