Задача поиска в таблице
В данном пособии основное внимание уделено задаче поиска данных в таблице по заданному значению ключа.
Под таблицеймы будем понимать совокупность записей, в которой каждая запись состоит изполя ключаиполя данных.
Задачу поиска в таблицеможно сформулировать следующим образом. Дано значение ключа. Требуется определить, имеется ли в таблице запись с этим ключом. Если такая запись есть, то требуется получить к ней доступ. При этом в одних случаях достаточно только получить значение поля данных (доступ на чтение), в других случаях нужна также возможность изменять поля записи или удалять запись (доступ на изменение).
Если искомый ключ отсутствует в таблице, то можно потребовать, чтобы процедура поиска определила место, куда может быть вставлена новая запись с этим ключом. В этом случае говорят о задаче поиска со вставкой.
Самым распространенным представлением таблицы в памяти является массив записей (рис. 1.1, а). Однако массив – не единственная возможная форма представления таблицы. Иногда более удобным или более эффективным может оказаться представление таблицы в виде линейного списка, дерева или более сложной структуры (например, дерева массивов, массива списков и т.п.). Кроме того, весьма важен случай таблиц, хранящихся в файлах на внешнем носителе, при этом размещение записей в файле не обязательно должно быть последовательным.
Некоторые представления таблиц показаны на рис. 1.1.
Рис. 1.1. Варианты представления таблиц: а – массив; б – бинарное дерево; в – массив списков
Конечно, на самом деле записи таблицы могут иметь более сложную структуру. Данные часто занимают не одно поле, а несколько полей, однако это никак не сказывается на выполнении поиска. Более существенно то, что ключевых полей тоже может быть несколько, при этом выбор ключа для поиска определяется видом конкретного запроса. В данном пособии этот вопрос будет затронут лишь кратко, основное же внимание будет уделено поиску по единственному ключу.
Возникают также вопросы, связанные с уникальностью или неуникальностью ключа. Ключ называется уникальным, если таблица не может содержать двух или более записей с одинаковыми значениями ключа. В случае неуникального ключа следует точно оговорить, что должно считаться результатом успешного поиска: одна из записей с искомым значением ключа (и какая именно) или множество всех таких записей.
На практике вопрос уникальности ключа не столь существен для большинства алгоритмов, а потому этот вопрос будет затрагиваться только в случае необходимости.
Сделаем одно существенное упрощение. Чтобы не загромождать примеры обозначениями полей записи, мы в дальнейшем не будем выделять в записях таблицы поле ключа и поле данных. Будем считать, что таблица состоит из простых элементов, которые сравниваются и переставляются как единое целое. Такую упрощенную таблицу можно назвать просто массивом, однако при этом не надо забывать, что элементы не обязательно расположены последовательно, они могут образовывать списки, деревья и другие структуры данных.
Запишем некоторые определения данных, которые будут использоваться в дальнейшем изложении.
const
N = ...; {Размер таблицы (произвольная константа)}
type
KeyType = ...;
{Здесь может быть любой тип данных, допускающий
операции сравнения и присваивания; например,
Integer}
RecordType = KeyType;
{Как сказано выше, мы не будем отличать запись от ее
ключа}
TableType = array [1..N] of RecordType;