Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Топ:
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Интересное:
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Дисциплины:
2018-01-30 | 234 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!