Связанные списки

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

Простейшим связанным списком является однонаправленный линейный список, представленный на Рис.3.

Рис.3. Пример линейного однонаправленного связанного списка

Доступ к первой записи списка осуществляется с помощью дополнительного указателя "начало". Поле указателя последней записи содержит значение константы NIL.

Различают:

- линейные и циклические связанные списки

- одно- и двунаправленные списки.

В линейном списке возникают алгоритмические трудности при движении по списку в обратном направлении. Этот недостаток устраняется в двунаправленном списке (Рис.4), каждый элемент которого содержит ссылки на следующий и предыдущий элементы. Указатель первой записи на предыдущий и указатель последней записи на следующий элемент равны значению NIL.

Рис.4. Пример линейного двунаправленного списка

В циклическом однонаправленном списке (Рис.5) указатель последней записи вместо константы NIL содержит адрес первого элемента списка. В этом случае указатель "начало" содержит адрес последнего элемента списка.

Рис.5. Пример циклического однонаправленного списка

Для создания линейного связанного списка в программе необходимо объявить тип записи, в котором одно из полей должно быть ссылочного типа, например:

type ZapDin = ^Zap;

Zap = record

Ukaz: ZapDin;

Info: integer;

end;

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

Просмотр элементов стека осуществляется по принципу LIFO - "последний пришел - первый вышел", т.е. в первую очередь обрабатывается последний элемент, помещенный в список. Просмотр элементов очереди выполняется по принципу FIFO - "первый пришел - первый вышел".

Дата добавления: 2014-01-06