Основы программирования. Указатели. Динамические структуры данных. Абстрактные типы данных. Классы - 24 стр.

UptoLike

ВУЗ: 

ЮФУ | Ростов-на-Дону

Составители: 

Рубрика: 

26
места вставки. Сортировка вставками в списке имеет такую же производитель-
ность, что и простые виды сортировок для массивов (например, пузырьковая сор-
тировка или сортировка выбором).
Таким образом, если в задаче требуется структура с частыми операциями
вставки и удаления в середине, следует предпочесть список, если же важнее бы-
стрый доступ по
индексу – следует выбрать массив. При выборе структуры следу-
ет также учитывать, что для организации односвязного списка на каждый элемент
требуется одно поле связи, занимающее 4 байта (для массива подобные наклад-
ные расходы отсутствуют). С другой стороны, список может динамически расши-
ряться во время работы программы, в то время как под массив отводится
фикси-
рованное количество элементов, которое необходимо указать на этапе компиля-
ции.
2.4 Двусвязные линейные списки
Двусвязный линейный список состоит из элементов, каждый из которых хра-
нит адреса следующего и предыдущего. Для удобства работы со списком поддер-
живаются указатели first и last на первый и последний элемент соответст-
венно:
first
last
В структуру Node добавляется указатель prev на предыдующий элемент списка:
type
PNode=^Node;
Node=record
data: integer;
prev,next: PNode;
end;
Вспомогательная функция NewNode при этом изменяется очевидным образом:
function NewNode(data: integer; prev, next: PNode):
PNode;
begin
New(Result);
Result^.data:=data;
Result^.next:=next;
Result^.prev:=prev;
end;
Рассмотрим основные операции с двусвязным списком, реализация которых
отличается от односвязного. После выполнения каждой операции first и last

Страницы