Выборка

Поиск

Неупорядоченная таблица

Реализация данных с помощью двунаправленного списка

Операциям дека соответствуют операции удаления и добавление элементов в начало и конец списков. Условно выбирается соответственно левая и правая сторона дека, т.е. начало или конец списка и устанавливается соответствие операции.

3.9 Таблицы

Таблица – структура данных, в которой информация идентифицируется некоторым значением, называемым ключом. Элементы таблицы состоят обычно из поля ключа и поля информации. Для таблицы определены следующие операции: выборка, добавление и удаление.

1. Выборка. Аргумент: <значение ключа>, результат: [информация из записи с заданным ключом]. Операция завершается с ошибкой, если нет записи с заданным ключом.

2. Добавление. Аргумент: <значение нового ключа, соответствующая информация>, результат: [ - ]. Производится добавление новой записи с заданным ключом и информацией. Операция завершается с ошибкой, если в таблице уже есть запись с заданным ключом. При программной реализации из-за ограничений на число записей также может возникнуть ошибка переполнения.

3. Удаление. Аргумент: <значение ключа>, результат: [ - ]. Выполняется удаление информации с заданным ключом из таблицы. Операция завершается с ошибкой, если нет записи с заданным ключом.

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

Ключ может быть:

· простым;

· частичным;

· составным.

Простой ключ представляет собой значение некоторого поля таблицы.

Частичный ключ представляет собой значение части поля.

Составной ключ: значение получается из конкатенации (присоединения) нескольких полей или их частей.

Поскольку при выполнении всех операций с таблицей требуется найти запись с заданным ключом (выборка или удаление) или удостовериться, что записи с заданным ключом в таблице нет, то при выполнении операций нужно выполнять операцию поиска с заданным ключом.

Различные способы реализации таблицы отличаются способом реализации поиска записи и выполнения операции.

Это таблица, в которой ключи никаким образом не упорядочены.

Таблица реализуется с помощью массива записей или списка.

Поскольку ключи не упорядочены, то необходимо просматривать все ключи последовательно.

Tп = С/2 – ключ найден

Т’п = С – ключ не найден

- Поиск элемента, если элемент не найден, то завершение с ошибкой.

- Выборка информации с заданной записи

С/2 + 1 = Тв = Тп+1- трудоемкость выборки