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

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

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

                                               Таблица 1

№ п/п	Фамилия	Имя	Отчество	Номер зачетной книжки	Домашний адрес
1	Строков	Иван	Иванович	02343	ул. Красная, 9 - 2
2	Скворцов	Олег	Иванович	02544	пр. Мира, 45 - 3
3	Соколов	Юрий	Кузьмич	01278	ул. Леонова, 23 - 98

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

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

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

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

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

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

                                                       Таблица 2

№ п/п	Фамилия	Имя	Отчество	Номер зачетной книжки	Домашний адрес
1	Скворцов	Олег	Иванович	02544	пр. Мира, 45 - 3
2	Соколов	Юрий	Кузьмич	01278	ул. Леонова, 23 - 98
3	Строков	Иван	Иванович	02343	ул. Красная, 9 - 2

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

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

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

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

Последовательное сканирование

Это единственный способ доступа, в котором элементы линейного списка могут быть неупорядочены по ключу. Для обозначения значения ключевого поля элемента в запросе введем запись К_доступ. Последовательно, начиная с первого элемента, сравнивается ключ каждого элемента списка К_э с ключом доступа К_доступ.

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

• для неупорядоченного списка сравнение повторяется до достижения конца списка. В этом случае, если совпадения ключей так и не было, делается вывод об отсутствии нужного элемента в списке;

• для упорядоченного списка проверяется условие, например, превышения значения ключа доступа К_доступ  значения ключа К_э: если список упорядочен по возрастанию, поиск продолжается; если по убыванию – поиск прекращается ввиду отсутствия нужного элемента.

Пример 1. Для списка из таблицы 1 требуется просмотреть адрес студента по фамилии Скворцов, т.е. q^{просмотр} = (Фамилия = Скворцов, Домашний адрес), а К_доступ = Скворцов (здесь и далее значение ключа доступа выделяется курсивом).

Доступ осуществляется последовательным выполнением шагов:

1. выбирается первый элемент списка;

1. ключевое поле элемента К_э = Строков сравнивается с ключом доступа: Строков = Скворцов;

1. поскольку поля не равны, выбирается следующий  - второй - элемент списка;

1. ключевое поле элемента сравнивается с ключом доступа:  Скворцов = Скворцов;

1. поскольку поля равны, выводится адрес: пр. Мира, 45 – 3; алгоритм заканчивает работу.

Пример 2.  Пусть требуется просмотреть домашний адрес студента, отсутствующего в списке, например,  по фамилии Сидоров, т.е. q^{просмотр} = (Фамилия = Сидоров, Домашний адрес), где К_доступ = Сидоров.

Работа алгоритма для неупорядоченного списка (таблица 1):

1. выбирается первый элемент списка;

1. ключевое поле элемента сравнивается с ключом доступа: Строков = Сидоров;

1. поскольку поля не равны, выбирается следующий  - второй - элемент списка;

1. ключевое поле элемента сравнивается с ключом доступа:  Скворцов = Сидоров;

1. вследствие того, что поля не равны, выбирается следующий  - третий - элемент списка;

1. ключевое поле элемента сравнивается с ключом доступа:  Соколов = Сидоров;

1. из-за того, что поля не равны, делается попытка обратиться к следующему элементу списка;

1. поскольку список закончен, выдается диагностическое сообщение об отсутствии искомого элемента в списке; алгоритм заканчивает работу.

Работа алгоритма для упорядоченного списка из таблицы 2 (список упорядочен по возрастанию первичного ключа – фамилии):

1. выбирается первый элемент списка;

1. ключевое поле элемента сравнивается с ключом доступа: Скворцов = Сидоров;

1. поскольку поля не равны, определяется возможность присутствия искомого элемента в продолжении списка. Для этого проверяется другое условие: Скворцов < Сидоров (напомним, что список упорядочен по алфавиту фамилий – первичных ключей);

1. условие не выполняется, поэтому выдается диагностическое сообщение об отсутствии искомого элемента в списке, и алгоритм заканчивает работу.

Таким образом, для определения отсутствия искомого элемента в списке во втором случае потребовалось только одно обращение к списку, а в первом – три. Уменьшение числа обращений к списку определяет лучший способ организации хранения данных.

Для задачи добавления при равенстве обоих ключей размещаемый элемент уже присутствует в списке, а потому выводится соответствующее диагностическое сообщение. Если же равенство не выполняется, последующие шаги алгоритма различаются для упорядоченного и неупорядоченного списка:

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

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