type uk=^elem;
elem=record
inf:string; {информация конкретного элемента списка}
next:uk; {указатель на следующий элемент}
end;
var beg:uk; {это первый элемент списка}
Сортировка списка в динамической области
Суть в следующем: имеется односвязный список в динамической области. Необходимо отсортировать его по информационному полю. КАк возможно это выполнить на turbo pascal? Создавать второй список нельзя. Подскажите, пожалуйста, или дайте ссылки на подобные задачки. Спасибо.
Отсортировать - это в смысле по возрастанию/убыванию?
Да. Нужно отсортировать список по возрастанию/убыванию элементы по информационному полю. Вот описание типа элементов:
/COLOR]
Код:
вообще-то, очень просто - также как одномерный массив: операции сравнения применяются к данным (в вашем случае inf), а для списка требуется функция смены узлов местами (необходимо подменить ссылки в поле uk).
Код:
procedure sort(var x:list);
var p,q,m:list; s:string;
begin
p:=list;
while p<>nil do
begin
q:=p;m:=q;
while q<>nil do
begin
if m^.inf<q^.inf then m:=q;
q:=q^.next
end;
s:=p^.inf; p^.inf:=m^.inf; m^.inf:=s;
p:=p^.next
end
end;
var p,q,m:list; s:string;
begin
p:=list;
while p<>nil do
begin
q:=p;m:=q;
while q<>nil do
begin
if m^.inf<q^.inf then m:=q;
q:=q^.next
end;
s:=p^.inf; p^.inf:=m^.inf; m^.inf:=s;
p:=p^.next
end
end;
мне кажется этот метод лучше всего подойдет (проще всего) для сортировки однонаправленного списка
кажется сортировка простым выбором
а если при сортировке по алгоритму нужно двигаться в обе стороны то имхо поиск предыдущего элемента(многократный) убъет преимущества сортировки