Сортировка списка очереди

@Dikoobraz · Регистрация: 25.04.2013

Author24 — интернет-сервис помощи студентам

Задача заключается в том, что есть динамический список и нужно его отсортировать по возрастанию, но при этом нужно переставлять не значения, а сами ячейки памяти в списке.
Вот пытался сделать, но не работает.

Pascal

program Sort;
 
uses CRT;
 
Type pelem=^elem;
     elem=record
          data:integer;
          next:pelem;
        end;
 
procedure Vvod(var beg:pelem);
var p,kon:pelem;
    dat:integer;
begin
    beg:=nil;
    kon:=nil;
    read(dat);
    if dat=0 then
    else
    new(beg);
    kon:=beg;
    beg^.data:=dat;
    kon^.next:=nil;
    read(dat);
    While dat <> 0 do
    begin
        new(p);
        kon^.next:=p; kon:=p;
        p^.data:=dat;
        p^.next:=nil;
       Read(dat);
     end;
   readln;
end;
 
procedure Vyvod(var p:pelem);
var pn:pelem;
begin
    pn:=p;
       while pn<>nil do
       begin
          write(pn^.data:4);
          pn:=pn^.next;
       end;
end;
 
procedure Sorti(var z:pelem);
var zn,n,k,kn,e,l:pelem;
i,c:integer;
begin
    If z<>nil then
       begin
          c:=1;
          e:=z;
          While e^.next <> nil do
             begin
                e:=e^.next;
                c:=c+1
             end;
 
       If z^.next<>nil then
       For i:=0 to c do
          begin
             zn:=z^.next;
             if z^.data > zn^.data then
                begin
                   k:=z;
                   kn:=zn;
                   k^.next:=kn^.next;
                   kn^.next:=z;
                   z:=kn;
                   zn:=k;
                   l:=z;
                 end;
                 n:=z;
                 If zn^.next <> nil then
                    begin
                       z:=z^.next;
                       zn:=zn^.next;
                          While zn<>nil do
                             If z^.data > zn^.data then
                             begin
                                k:=z;
                                kn:=zn;
                                k^.next:=kn^.next;
                                kn^.next:=z;
                                z:=kn;
                                zn:=k;
                                l^.next:=z;
                                l:=l^.next;
                                z:=z^.next;
                                zn:=zn^.next;
                             end;
 
                    end;
          end;
       end;
z:=n;
end;
 
var d:pelem;
 
Begin
CLRSCR;
    d:=nil;
    Vvod(d);
    Sorti(d);
    Writeln('============================');
    Vyvod(d);
end.

@Kitayets · 26.04.2013, 12:12

как то так:

Кликните здесь для просмотра всего текста

Delphi

program sorting_list;
 
{Решаем задачу с [url]https://www.cyberforum.ru/free-pascal/thread848624.html[/url]
по заданию:
есть динамический список и нужно его отсортировать по возрастанию,
но при этом нужно переставлять не значения, а сами ячейки памяти в списке.}
{$mode objfpc}{$H+}
 
uses {$IFDEF UNIX} {$IFDEF UseCThreads}
  cthreads, {$ENDIF} {$ENDIF}
  Classes { you can add units after this };
 
type
  pelem = ^elem;
 
  elem = record
    Data: integer;
    Next: pelem;
  end;
 
  procedure Vvod(var beg: pelem);
  var
    p, kon: pelem;
    dat: integer;
  begin
    beg := nil;
    kon := nil;
    Read(dat);
    if dat = 0 then
    else
      new(beg);
    kon := beg;
    beg^.Data := dat;
    kon^.Next := nil;
    Read(dat);
    while dat <> 0 do
    begin
      new(p);
      kon^.Next := p;
      kon := p;
      p^.Data := dat;
      p^.Next := nil;
      Read(dat);
    end;
    readln;
  end;
 
  procedure Vyvod(var p: pelem);
  var
    pn: pelem;
  begin
    pn := p;
    while pn <> nil do
    begin
      Write(pn^.Data: 4);
      pn := pn^.Next;
    end;
  end;
 
 
  //сортировка выбором O(n)= n^2
  procedure srt(var z: pelem);
  //функция сравнения элементов
  function isBigger(var el1, el2: pelem): boolean;
  begin
    result:= el1^.Data > el2^.Data;
  end;
  //процедура обмена элементами
  procedure exchangeElm(var el1, el2: pelem);
  var
    tElem: pelem;
  begin
    tElem^:= el1^;
    el1^:= el2^;
    el1^.Next:= tElem^.Next;
    tElem^.Next:= el2^.Next;
    el2^:=tElem^;
  end;
 
  var
    cur: pelem; //указатель на 1-ый не отсортированный элемент
    min: pelem; //указатель на минимальный эл. в хвосте
    test: pelem;//тестируемый эл. в хвосте
  begin
    if not Assigned(z) then exit;
    cur:= z;
 
    while  assigned(cur^.Next) do begin
      min:= cur;
      test:= cur;
 
      //поиск минимума в хвосте
      while true do begin
        if isBigger(min, test) then
            min:= test;
        if not Assigned(test^.Next) then
            break;
        test:= test^.Next;
      end;
 
      if isBigger(cur, min) then
        exchangeElm(cur, min);
      cur:= cur^.Next;
    end;
  end;
 
var
  d: pelem;
 
begin
  //CLRSCR;
  d := nil;
  Vvod(d);
  srt(d);
  Writeln('============================');
  Vyvod(d);
  readln;
end.

и надо переработать процедуру ввода - если ввести 0 то падает по AV.

	26.04.2013, 12:12

Опции темы