Модели и структуры данных



         

Применение линейных списков - часть 4


Сортировка включением на векторной структуре в примере 3.11 требовала большого числа перемещений элементов в памяти. Обратите внимание на то, что в двух последних примерах пересылок данных не происходит, все записи таблиц остаются на своих местах в памяти, меняются только связи между ними - указатели.

{==== Программный пример 5.10 ====} { Сортировка вставками на 1-связном списке } type data = integer; Function Sort(head : lptr) : lptr; var newh, cur, sel : lptr; begin newh:=nil; { выходной список - пустой } while head <> nil do begin { цикл, пока не опустеет входной список } sel:=head; { эл-т, который переносится в выходной список } head:=head^.next; { продвижение во входном списке } if (newh=nil) or (sel^.key < newh^.key) then begin {выходной список пустой или элемент меньше 1-го-вставка в начало} sel^.next:=newh; newh:=sel; end else begin { вставка в середину или в конец } cur:=newh; { до конца выходного списка или пока ключ следующего эл-та не будет больше вставляемого } while (cur^.next <> nil) and (cur^.next^.key < sel^.key) do cur:=cur^.next; { вставка в выходной список после эл-та cur } sel^.next:=cur^.next; cur^.next:=sel; end; end; Sort:=newh; end;




Содержание  Назад  Вперед