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