История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Топ:
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Интересное:
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Дисциплины:
2018-01-30 | 227 |
5.00
из
|
Заказать работу |
|
|
Структура данных, в которой объекты расположены в линейном порядке, называется связным списком. Однако в отличие от массива, в котором этот порядок определяется индексами, порядок в связном списке определяется указателями на объекты.
Элемент (узел) связного списка, помимо полей с данными, имеет поле next, в котором содержится указатель на следующий элемент списка. Если это последний элемент списка, поле next принимает нулевое значение. Помимо своих элементов, каждый список содержит указатель head на первый элемент списка. Если этот указатель равен 0, значит, список пуст. Поскольку этот указатель относится к списку в целом и не содержит в себе данных, на рис. 14.18, на котором схематически показан односвязный список, указатель не заключен в прямоугольник.
Данные | next |
head
т | |||||||
Рис. 14.18. Односвязный список
Односвязный список отличается тем, что пройти по нему можно только в одном направлении — от начала в конец списка. Это оказывается достаточно неудобно, поэтому гораздо большее распространение получили двусвязные списки (рис. 14.19), отличающиеся тем, что их узлы содержат по два указателя — на следующий (next) и на предыдущий (prev) элементы списка. Помимо указателя head на первый элемент списка, может существовать также указатель tail на последний элемент списка.
prev | Данные | next |
head |
Рис. 14.19. Двусвязный список
, Частный случай двусвязного списка — замкнутый (кольцевой) список, указатель next последнего элемента которого указывает на первый элемент, а указатель prev первого элемента — на последний элемент списка.
Глава 14. Основы теории алгоритмов
|
Главная особенность списка — быстрое выполнение операций вставки и удаления в произвольном месте списка. Эти операции требуют модификации указателей максимум у трех узлов: узла, над которым выполняется операция, и двух окружающих узлов. Схематично эти операции и изменения значений указателей показаны на рис. 14.20.
Вставка |
Удаление Рис. 14.20. Вставка и удаление в двусвязных списках
Алгоритм этих операций, приведенный на рис. 14.21 и 14.22, показывает, насколько простыми являются алгоритмические операции со списками.
Q Начало) | |||
/ Вводах /- | |||
x.nexf = Lhead | ----- | ||
false /^ r-4—<^L.hea | true | ||
Lhead. prev = x | ----- | ||
1----------- ► | |||
Lhead = x | ----- | ||
x.prev = 0 | ----- | ||
/ Вывод L /- | |||
(Конец) |
Входные данные:
L — список
X — вставляемый элемент (узел)
Поле next элемента х теперь указывает на первый элемент списка, поскольку мы присвоили ему значение указателя head
Список не пустой,
и указатель head указывает
На следующий узел?
Указатель prev бывшего первого элемента списка теперь указывает на вставляемый элемент х
Указатель head списка теперь указывает на вставленный элемент х
Поскольку х в списке первый, его указатель prev не указывает ни на какой элемент
Выходные данные:
L — список со вставленным
элементом х
Рис. 14.21. Вставка элемента в начало списка
14.4. Представление и обработка данных разного типа
Начало
Ввод L, х
Входные данные:
L — список
x — удалямый элемент (узел)
Удаляемый элемент не последний в списке? Если да (true), то полю prev следующего за х элемента присваивается значение поля prev удаляемого элемента |
true Г | ^x.prev = | ||
x.prev.next = | x.next | Lhead = | x.nexf |
|
Удаляемый элемент не первый в списке? Если да (true), то полю next предыдущего элемента присваивается значение поля next удаляемого элемента. Если удаляемый элемент в списке первый (false), то поле head списка направляется на следующий за удаляемым элемент
x.next.prev = x.prev
Вывод L
Выходные данные:
L — список с удаленным
элементом х
(Конец)
Рис. 14.22. Удаление элемента списка
|
|
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!