ЛИНЕЙНЫЕ И ЦИКЛИЧЕСКИЕ СПИСКИ
ЛИНЕЙНЫЙ СПИСОК
Линейный список представляет собой упорядоченный набор элементов, в котором включение новых элементов и исключение существующих могут выполняться в любом месте списка. Каждый элемент списка характеризуется одним и тем же набором полей. Логическая структура линейного списка приведена на рис. 2.1.
|
А |
D |
F |
В |
С |
Начало
Т
Рис. 2.1. Логическая структура линейного списка
Число элементов списка не ограничено. Список, в котором нет ни одного элемента, называется пустым.
Стеки, очереди и деки, рассмотренные в теме 1, являются частными случаями линейного списка, поскольку имеют ограниченную дисциплину обслуживания.
Списковые структуры находят широкое применение при решении следующих задач: топологическая сортировка, сетевое планирование, арифметические действия с многочленами, операции с длинными числами, построение таблиц имен в трансляторах, моделирование ситуаций реального мира и т.д.
ОПЕРАЦИИ НАД ЛИНЕЙНЫМ СПИСКОМ
Над линейным списком L могут быть выполнены все операции, определенные для стека, очереди и дека (тема 1), а также следующие операции:
- 1) включение элемента со значением v в список после элемента с заданным адресом р — InsertAfter(L, р, v);
- 2) включение элемента со значением v в список L перед элементом с заданным адресом р — InsertBefore(L, р, v);
- 3) исключение из списка L элемента с адресом р — Delete(L, р);
- 4) исключение из списка L элемента, следующего за элементом с адресом р — DeleteAfter(L, р);
- 5) поиск в списке Ь элемента с заданным значением V — ЗеагсЬЦЬ, V) и возвращение его адреса.
