Таблица - некоторый (вообще говоря неупорядоченный) набор именованных записей. Имена могут выбираться достаточно произвольным образом, но чтобы можно было организовать эффективный поиск записи по ее имени, нужно сравнивать любые два имени записей и устанавливать, какое из них больше, а какое меньше. Имя записи в таблице называется ключом записи.

Часто в качестве ключей используются целые положительные числа. Можно использовать строки. Над типом данных, используемым для представления ключа, должны быть определены операции сравнения. Если встроенных операций нет, можно разработать функции, сравнивающие ключи.

Операции, определенные над таблицей, как структурой данных:

Существует несколько способов организации таблицы. Выбор того или иного способа определяется характером использования таблицы:

1. Односвязный список.

Простейший способ представления таблицы.


Достоинства:
• кроме полезной информации присутствует только один указатель на следующую запись, следовательно, память ЭВМ используется достаточно эффективно;
• алгоритм перебора при поиске очень прост;
• включение в таблицу заведомо новой записи можно сделать максимально эффективно, помещая новую запись в фиксированое место таблицы, например, в начало или в конец.



Недостатки:
• основной недостаток заключается в том, что поиск может оказаться длительным, так как для неупорядоченного списка возможен (практически) только последовательный поиск. В среднем случае просматривается половина записей, а в худьшем - все. Если число записей N невелико, то неэффективностью поиска можно принебречь, отдав предпочтение простоте алгоритма и быстродействию. Если N велико - то наоборот;
• даже если исконной записи нет, то для установления этого факта при поиске придется пересмотреть всю таблицу.

2. Упорядоченный список.

Записи в таблице расположены в порядке возрастания или убывания ключей. В этом случае неудачный поиск можно прекратить при достижении записи с ключем больше (если ключи отсортированы в порядке возрастания) заданного.
Усложняется процедура включения новой записи в таблицу, так как должна поддерживаться упорядоченность, а следовательно, предворительнонужно найти соответствующее место для вставки записи.


Достоинство:
• упорядоченнй список позволяет использовать двоичный поиск.

3. Массив записей.

В каждой записи хранится ключ и указатель на полезную информацию. Так как размер записей одинаков, их можно объединить в массив, упорядочив по-возрастанию ключей. Следовательно, массив - это упорядоченный список с разорванными связями.


Достоинства:
• двоичный поиск;
• очень быстрый доступ при индексации массива.



Недостатки:
• плохо подходит для включения и удаления записей, так как связи разорваны и приходится сдвигать все элементы массива;
• может применяться лишь для таблиц фиксированного размера.

4. Двоичное дерево.

Достоинство:
• Наиболее эффективная реализация операций.



Недостаток:
• Сложность некоторых операций (поддержание сбалансированного дерева, удаление узла из дерева).