Файл: Динамические структуры данных (списки).pdf

{

-> = ->; // меняем нового узла

-> = ;

->-> = ; // меняем соседних узлов

-> = ;

}

}

Добавление узла заданным выполняется .

Поиск узла в .

Проход по двусвязному может выполняться двух направлениях – головы к (как для ) или от к голове.

Удаление

Эта процедура также ссылки на и хвост , поскольку они измениться при крайнего элемента . На первом этапе ссылки соседних (если они ) так, как бы удаляемого не было . Затем узел удаляется память, которую занимает, освобождается. Эти показаны на внизу. Отдельно проверяется, является ли узел первым последним узлом .

Рисунок 10

( &, &, )
{
( == ) {
= ->; // удаляем элемент
( )
-> = ;
= ; // удалили элемент
}
{
->-> = ->;
( -> )
->-> = ->;
= ; // последний элемент
}
;
}

2.11 Циклические списки

Иногда список (односвязный или двусвязный) замыкают в кольцо, то есть указатель next последнего элемента указывает на первый элемент, и (для двусвязных списков) указатель prev первого элемента указывает на последний. В таких списках понятие «хвоста» списка не имеет смысла, для работы с ним надо использовать указатель на «голову», причем «головой» можно считать любой элемент.

ЗАКЛЮЧЕНИЕ

Таким образом, подводя итог проделанной работе, отметим, что динамические структуры данных в процессе нахождения в памяти могут изменять не только количество составляющих их элементов, но и характер связей между элементами. Он не учитывает изменения содержимого самих элементов данных. Такая особенность динамических структур, такая как непостоянство их размера и характер взаимосвязи между элементами, приводит к тому, что на этапе создания машинного кода программа компилятора не может выделить память фиксированного размера для всей структуры в целом, а также нельзя сравнивать его с отдельными компонентами структуры конкретных адресов. Для решения проблемы обращения к динамическим структурам данных используется метод, называемый динамическим распределением памяти, то есть память для отдельных элементов выделяется в момент, когда они «начинают существовать» во время выполнения программы, а не во время компиляции. Компилятор в этом случае выделяет фиксированный объем памяти для хранения адреса динамически выделяемого элемента, а не самого элемента.