Линейный двусвязный список.
Begin
Отсортированный список.
Слияние двух отсортированных списков в третий
Begin
Begin
Begin
Begin
New(s); { создали новый узел, ссылка на него в s }
s^.i := a; { a à в новый узел }
t := h; {встали на начало списка}
p := Nil; { p - указатель на предыдущий узел}
{ Цикл поиска и вставки узла в надлежащее место списка }
While t < > Nil Do{ пока не достигнут конец списка }
If t^.i > a { поиск места вставки }
Then { если место вставки найдено }
If p = Nil{ и если р не успел измениться ,то}
Then Begin s^.L := h; h := s; Exit; End{ вставка в начало списка}
Else Begin s^.L := t; p^.L := s; Exit; End { вставка в середину списка }
Else Begin p := t; t := t^.L; End;{ место вставки не найдено и переход к след. узлу }
{ конец цикла While }
If h = Nil Then Begin h := s; s^.L := Nil; End { вставка в пустой список }
Else Begin s^.L := Nil; p^.L := s; End; { вставка в конец списка }
End;
Процедуру InsList удобно использовать для создания отсортированного списка. Действительно, начав с пустого списка, каждое очередное значение аi вставляется и коммутируется в надлежащее в ему место в списке.
Procedure CreateSortList (Var h :u; k :integer); {k – длина списка}
Var j :Integer;
h := Nil;
Forj := 1 To k Do InsList ( h, Random(50) );
End;
Для того, чтобы упростить алгоритмы операций вставки и удаления и свести их к однотипным операциям часто список снабжают дополнительным узлом, например, в начале списка - его называют заглавным узлом (звеном). В информационном поле заглавного узла может помещаться, например, количество узлов в списке или некоторая другая информация. Ниже приведены процедуры удаления и вставки, по ним видно - на сколько упрощается логика алгоритмов этих операций со списком.
Procedure DelListZ( h :u; a :Integer);
Var p,t :u;
p:=h; t:=h^.L;
Whilet <> Nil Do
If t^.i = a Then Beginp^.L := t^.L; Dispose(t); Exit; End
Else Begin p := t; t := t^.L; End;
Writeln('такого элемента нет');
End;
ProcedureInsListZ( h :u; a :Integer);
Var p, t, s :u;
New(s); s^.i := a;
p:=h; t:=h^.L;
While (t<>Nil) And (t^.i <= a) Do
Begin p := t; t := t^.L; End;
p^.L := s; s^.L := t;
End;
Пусть заданы два непустых и отсортированных по возрастанию спискаh1и h2. Получить объединенный отсортированный список за счет перекоммутации ссылок между узлами списков. Голова объединенного списка будет h1.
Procedure AddList ( Var h1, h2 :u);
Var p, t1, t2 :u;
If h1^.i > h2^.i { добиваемся, чтобы h1 указывал на первый элемент с
Then Begin t1:=h1; h1:=h2; h2:=t1; End; меньшим значением}
t1 := h1; p :=Nil; t2 := h2;
Repeat {цикл объединения списков}
While ( t1< > Nil ) And ( t1^.i <= t2^.i ) Do Begin
p :=t1; t1 := t1^.L; { продвижение по текущему списку пока не
End; нужна перекоммутация }
p1^.L := t2; t2 := t1; t1 := p^.L;{ коммутация двух узлов из разных списков }
Until t2 = Nil; { если достигли конца одного из списков – задача выполнена }
End;
Рассмотренные ЛС являются структурами с последовательным доступом. Еще их называют односвязными, поскольку связи между узлами однонаправлены и просматривать элементы списка можно только от начала к концу. В некоторых практических задачах более эффективной структурой для представления данных являются двусвязные ЛС, где каждый элемент (узел) содержит ссылку не только на следующий, но и на предыдущий элементы. Обычно их еще называют R– правой ссылкой и L – левой ссылкой. В таких ЛС можно продвигаться как в прямом, так и обратном направлениях. Далее приведены соответствующие основные объявления и процедуры демонстрирующие работу с двусвязными ЛС.
