- •1 Линейные двусвязные списки
- •2 Основные операции над списком
- •2.1 Добавление элемента в список
- •2.2 Удаление элемента из списка
- •2.3 Вставка элемента внутри списка
- •3 СоЗдание, просмотр и уничтожение списка
- •Упражнения
- •4 Поиск элемента в списке
- •5 Перемещение элементов списка
- •Упражнения
- •6 Примеры обработки списка
- •Упражнение
- •Упражнение
- •Упражнения
- •Литература
Упражнения
3.1 Описать процедуру создания линейного двусвязного списка, используя процедуру First_El создания первого элемента списка и процедуру DAdd_last1 добавления в конец непустого списка (см. раздел 2). Информация содержится в текстовом файле.
3.2 Описать процедуру просмотра линейного двусвязного списка в обратном порядке, то есть проходом от последнего до первого элемента списка.
3.3 Создать на основе программы Dlist новую программу, заменив процедуру DCreate процедурой создания списка упражнения 3.1 и добавив просмотр списка в обратном порядке, используя процедуру упражнения 3.2.
4 Поиск элемента в списке
Пример 4.1 Найти элемент с заданным значением x информационного поля. Результат поиска – указатель на первый из элементов с указанным свойством или пустая ссылка nil , если в списке такого элемента нет.
function DSearch(first:link; x:integer):link;
var fl:boolean; {признак отсутствия элемента в списке}
begin
fl:=true;
while (first<>nil)and fl do
if first^.inf=x then fl:=false
else first:=first^.next;
DSearch:=first
end;
5 Перемещение элементов списка
Пример 5.1 Переместить последний элемент в начало списка. Предполагается, что список не пуст и содержит не менее двух элементов. При выполнении перемещения операции выделения и освобождения памяти не использовать, информационные поля не менять.
procedure El_Ef(var first,last:link);
begin
{закольцевать список:}
first^.prev:=last; last^.next:=first;
{передвинуть first и last:}
first:=first^.prev; last:=last^.prev;
{''занулить'' связи первого и последнего элементов:}
first^.prev:=nil; last^.next:=nil
end;
Контрольные примеры
1) Список (значения информационных полей списка): 1 3 7 1 3 5
Результат:
просмотр от первого до последнего элемента : 5 1 3 7 1 3
просмотр в обратном порядке : 3 1 7 3 1 5
2) Список из двух элементов: 1 3
Результат:
просмотр от первого до последнего элемента : 3 1
просмотр в обратном порядке : 1 3
Пример 5.2 Поменять местами первый и последний элементы списка. Предполагается, что список не пуст и содержит не менее двух элементов. При выполнении обмена операции выделения и освобождения памяти не использовать, информационные поля не менять.
procedure Exchange_f_l(var first, last: link);
var p, q: link; {указатели на второй и предпоследний элементы}
begin
p:=first^.next; q:=last^.prev;
{связи первого элемента}
first^.prev:=q;
first^.next:=nil;
q^.next:=first;
{связи последнего элемента}
last^.next:=p;
last^.prev:=nil;
p^.prev:=last;
{новые первый и последний элементы}
first:=last;
last:=q^.next
end;
Контрольные примеры
1) Список (значения информационных полей списка): 1 3 7 1 3 5
Результат:
просмотр от первого до последнего элемента : 5 3 7 1 3 1
просмотр в обратном порядке : 1 3 1 7 3 5
2) Список из двух элементов: 1 3
Результат:
просмотр от первого до последнего элемента : 3 1
просмотр в обратном порядке : 1 3