На этом шаге мы рассмотрим однонаправленные списки.

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

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

    Связанные списки могут иметь одиночные или двойные связи.

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

Однонаправленные списки

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

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

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

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

    Каждая компонента списка определяется ключом. Обычно ключ - это либо число, либо строка символов. Ключ располагается в поле данных компоненты, он может занимать как отдельное поле записи, так и быть частью информационного поля записи.

    Рассмотрим схематичное изображение однонаправленного списка:

Рис.1. Схематичное изображение однонаправленного списка без заглавного звена

Над списками выполняются следующие операции:
• начальное формирование списка (запись первой компоненты);
• добавление компоненты в конец списка;
• определение первого элемента в линейном списке;
• чтение компоненты с заданным ключом; с заданным свойством;
• вставка компоненты в заданное место списка (обычно до компоненты с заданным ключом или после неё);
• исключение компоненты с заданным ключом из списка.
• упорядочивание узлов линейного списка в определенном порядке.

    Описание компоненты однонаправленного списка дадим следующим образом:

    Type
       PtrRec = ^Rec;
       Rec = Record
             Element : TypeElement;   {Информационное поле}
             pNext   : PtrRec;        {Ссылка на следующую компоненту}
         End;

    Для формирования однонаправленного списка и работы с ним необходимо описать четыре переменных типа указатель на запись. Договоримся, что pBegin определяет начало списка, а pCKey, pPredRec, pAux определим как вспомогательные (указатель на компоненту с заданным ключем, указатель на компоненту перед заданным ключем, временный указатель):

    Var
      pBegin, pCKey, pPredRec, pAux : PtrRec;

    На следующем шаге мы рассмотрим формирование списка с сохранением порядка поступающих элементов.

Предыдущий шаг Содержание Следующий шаг