Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Помогите!!!! Трехпутевое слияние

14K
09 января 2006 года
Shelby
5 / / 09.01.2006
Товарищи!!! ПОМОГИТЕ, пожалуйста!!! очень нужна прога, реализующая алгоритм трехпутевого слияния на Delphi или хотя б ее алгоритм... Как?! Заранее благодарю...
2.0K
10 января 2006 года
integral
86 / / 12.11.2005
Я Delphi не знаю, но писал такую прогу на С. Алгоритм смотри в 5-ой главе третего тома Кнута
15K
12 января 2006 года
Squier
5 / / 10.01.2006
Вот реализация алгоритмя трёхпутевого слияния (сортировка на 3х лентах) однонаправленных списков. Запара ещё та...
Код:
program Sort;

{$APPTYPE CONSOLE}

uses
  SysUtils;

Type
  PList=^List;
  List=Record
        inf:Integer;
        next:PList;
       End;

Var
  a,b,c:PList;

//Add element to list
Procedure pAddToList(Var elem:PList; i:Integer);
Var
  q,p:PList;
Begin
New(q);
q^.inf:=i;
q^.next:=nil;

  IF elem=nil Then elem:=q
              Else
                Begin
                  p:=elem;
                    While p^.next<>nil Do p:=p^.next;
                  p^.next:=q;
                End;

End;

//Split lists
Procedure pSplitting(Var a,b,c:PList);
Var
  p,bfin,cfin:PList;
  flag:Boolean;
Begin
bfin:=b;
cfin:=c;
flag:=True;

//Flag is use for detect the number of list
  While a<>nil Do
    Begin
      p:=a;
        While (p^.next<>nil)and(p^.next^.inf>=p^.inf) Do p:=p^.next;
        IF flag Then
          Begin
              IF bfin=nil Then b:=a
                          Else bfin^.next:=a;
            bfin:=p;
            a:=p^.next;
            flag:=false;
          End
               Else
          Begin
             IF cfin=nil Then c:=a
                          Else cfin^.next:=a;
            cfin:=p;
            a:=p^.next;
            flag:=True;
          End;
    End;

  IF cfin<>nil then cfin^.next:=nil;

bfin^.next:=nil;
End;

//Mix lists
Procedure pMix(Var a,b,c:PList);
Var
  p1,p2,afin:PList;
Begin
afin:=a;

  While (b<>nil)and(c<>nil) Do
    Begin
      p1:=b;
        While (p1^.next<>nil)and(p1^.next^.inf>=p1^.inf) Do p1:=p1^.next;
      p2:=c;
        While (p2^.next<>nil)and(p2^.next^.inf>=p2^.inf) Do p2:=p2^.next;
        While (b<>p1^.next)and(c<>p2^.next) Do
          Begin
            IF b^.inf<c^.inf Then
              Begin
                  IF afin=nil Then a:=b
                              Else afin^.next:=b;
                afin:=b;
                b:=b^.next;
              End
                             Else
              Begin
                  IF afin=nil Then a:=c
                              Else afin^.next:=c;
                afin:=c;
                c:=c^.next;
              End;
          End;

        IF (b=p1^.next)and(c<>p2^.next) Then
          Begin
            afin^.next:=c;
            afin:=p2;
            c:=p2^.next;
          End
                                        Else
        IF (b<>p1^.next)and(c=p2^.next) Then
          Begin
            afin^.next:=b;
            afin:=p1;
            b:=p1^.next;
          End;
    End;

  IF (b=nil)and(c<>nil) Then
    Begin
       IF afin=nil Then a:=c
                   Else afin^.next:=c;
      c:=nil;
    End;

  IF (c=nil)and(b<>nil) Then
    Begin
        IF afin=nil Then a:=b
                    Else afin^.next:=b;
      b:=nil;
    End;

End;

Var
  i,n,tmp:integer;
  p:PList;
Begin
Randomize;
Write('Input data{'+#10#13+'Enter number of elements: ');
ReadLn(n);
Write('Input list:');

  For i:=1 To n Do
    Begin
      tmp:=Random(8)+1;
      Write(' ',tmp);
      pAddToList(a,tmp);
    End;

pSplitting(a,b,c);

  While c<>nil Do
    Begin
      pMix(a,b,c);
      pSplitting(a,b,c);
    End;

pMix(a,b,c);
p:=a;
i:=0;
Write(#10#13+'Output data{'+#10#13+'Sorted list:');

  While p<>nil Do
    Begin
      Write(' ',p^.inf);
      p:=p^.next;
      Inc(i);
    End;

WriteLn(#10#13+'}');

ReadLn;

End.

end.


P.S. Это была одна из задач моей лабы по сортировкам...
14K
17 января 2006 года
Shelby
5 / / 09.01.2006
Спасибо огромное!!!! Жаль, что увидела твой ответ слишком поздно...(((
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог