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



         

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


Указатель newh является указателем на начало выходного списка, исходно - пустого. Во входном списке ищется максимальный элемент. Найденный элемент исключается из входного списка и включается в начало выходного списка. Работа алгоритма заканчивается, когда входной список станет пустым. Обратим внимание читателя на несколько особенностей алгоритма. Во-первых, во входном списке ищется всякий раз не минимальный, а максимальный элемент. Поскольку элемент включается в начало выходного списка (а не в конец выходного множества, как было в программном примере 3.7), элементы с большими ключами оттесняются к концу выходного списка и последний, таким образом, оказывается отсортированным по возрастанию ключей. Во-вторых, при поиске во входном списке сохраняется не только адрес найденного элемента в списке, но и адрес предшествующего ему в списке эле- мента - это впоследствии облегчает исключение элемента из списка (вспомните пример 5.4). В-третьих, обратите внимание на то, что у нас не возникает никаких проблем с пропуском во входном списке тех элементов, которые уже выбраны - они просто исключены из входной структуры данных.

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

В программном примере 5.10 - иллюстрации сортировки вставками - из входного списка выбирается (и исключается) первый элемент и вставляется в выходной список "на свое место" в соответствии со значениями ключей.


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