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