Линейные списки

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

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

Таблица 1

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

Ключ, определяющий только один элемент в списке, называется первичным. Ключ, определяющий несколько элементов, называется вторичным.

Если в качестве ключа выступает одно поле, такой ключ называется простым. Если используются несколько полей в качестве ключа, такой ключ называется составным.

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

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

Различают два основных способа организации хранения элементов списка: в отсортированном и в неотсортированном виде (методы сортировки списков хорошо известны и в данном случае не приводятся). Причем возможна сортировка как по первичному, так и по вторичному ключу. Так, таблица 2 – это отсортированный по возрастанию первичного ключа (в данном случае – фамилии студента) исходный список из таблицы 1:

Таблица 2

Наиболее интересным с точки зрения практического использования линейного списка является вопрос организации доступа к его элементам. Как отмечалось ранее, доступ выполняется по запросу, в котором в обязательном порядке указывается ключ требуемого элемента (элементов). В роли ключа для структурированных данных выступает тройка <название поля><сравнение><значение поля>, где название поля – это указание на составляющую элемента (см. Операции над данными), например, Фамилия из таблицы 2, значение поля – это значение составляющей элемента (см. Операции над данными), например, Скворцов из таблицы 2, а сравнение означает некоторую операцию сравнения, например, «=» или «>».

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