Полная версия

Главная arrow Информатика arrow Алгоритмы и структуры данных

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

ЛИНЕЙНЫЕ И ЦИКЛИЧЕСКИЕ СПИСКИ

ЛИНЕЙНЫЙ СПИСОК

Линейный список представляет собой упорядоченный набор элементов, в котором включение новых элементов и исключение существующих могут выполняться в любом месте списка. Каждый элемент списка характеризуется одним и тем же набором полей. Логическая структура линейного списка приведена на рис. 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) и возвращение его адреса.
 
<<   СОДЕРЖАНИЕ   >>