Полная версия

Главная arrow Информатика arrow Алгоритмы и структуры данных

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

ПОИСК И РАССТАНОВКА

ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

Совокупность элементов, среди которых ведется поиск, назовем таблицей, каждый элемент — записью. Для каждой записи определен ключ, используемый для того, чтобы отличать одну запись от другой.

Ключ может быть полем внутри записи — внутренний ключ.

Ключом может быть относительная позиция записи внутри таблицы, либо существует таблица ключей, содержащая указатели на записи. Такой ключ называется внешним.

Первичный ключ — ключ, уникальный для каждой записи.

Вторичный ключ — не являющийся уникальным. Несколько записей могут иметь одинаковое значение ключа.

Алгоритм поиска — алгоритм, воспринимающий некоторый аргумент х и локализующий запись с ключом х. Успешный поиск называется извлечением. В случае неудачи алгоритм возвращает или пустую запись, или пустой указатель, или флаг.

Алгоритм поиска и вставки — включает в таблицу новую запись с аргументом х в качестве ключа, если поиск был неудачным.

Для представления элемента таблицы хорошо подходит такая структура данных, как запись, одной из компонент которой является ключ Key элемента, а другими компонентами являются все существенные данные об элементе. Таблицу при этом можно описать как массив av а2,.., ап из п записей-элементов или как связанный список таких элементов с указателем на первый элемент Head.

Замечание, во всех приведенных ниже алгоритмы поиска предполагается, что таблица не пуста и установлена директива компилятора {$В-}.

 
<<   СОДЕРЖАНИЕ   >>