VPF::сортировка методом вставок связных списков

spanchbob

Дата 1.6.2006, 01:06 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 22.4.2006

Репутация: нет
Всего: нет

вообщем у меня задачка, отсортировать связный список методом вставки и пузырька. Пузырьком сделано, а вот со вставкой проблемки. Есть вариант(см. ниже), но если у кого-то есть идейки получше или весь исходный текст, это было бы отлично

Код


{ Сортировка вставками на 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;

M
volvo877

Тегами пользуемся ...

Это сообщение отредактировал(а) volvo877 - 1.6.2006, 08:08

volvo877

Дата 1.6.2006, 08:10 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 2
Всего: 116

Вообще-то, сортировка списка методом вставки делается так:

Код

type { узел списка }
  plist=^node;
  node=record
    data: integer;
    next:plist;
  end;

function insert_sort(l: plist): plist;

  function insert(a: plist; l: plist): plist;
  begin
    a^.next := nil;
    if l = nil then insert := a
    else
      if a^.data < l^.data then begin
        a^.next := l; insert := a;
      end
      else begin
        l^.next := insert(a, l^.next);
        insert := l;
      end;
  end;

begin
  if l = nil then insert_sort := nil
  else insert_sort := insert(l, insert_sort(l^.next));
end; { Конец функции сортировки }

Вызывать так:

Код

Var first: plist;
...
  { Заполнение списка }
  first := insert_sort(first);
...

Hidrag

Дата 31.1.2007, 00:19 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 877
Регистрация: 9.4.2005
Где: JDK

Репутация: нет
Всего: 25

volvo877, а как нибудь изменится алгоритм, если список будет двусвязным и кольцевым?

--------------------

volvo877

Дата 31.1.2007, 01:49 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 2
Всего: 116

Цитата(Hidrag @ 30.1.2007, 23:19

)

если список будет двусвязным и кольцевым

то я бы делал сортировку вот так:

Код


procedure sort(var first: plist);
var
  i, j, root: plist;
  T: integer;
begin
  root := first;

  i := first^.next;
  while i <> root do begin
    T := i^.data;
    j := i^.prev;
    while (j^.next <> root) and (T < j^.data) do begin
      j^.next^.data := j^.data;
      j := j^.prev;
    end;

    if j^.next = root then first^.data := T
    else j^.next^.data := T;

    i := i^.next;
  end;
end;

(если есть указатель на предыдущий элемент - то зачем заморачиваться с рекурсией?)

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Object Pascal: кроссплатформенные технологии \| Следующая тема »