[Pascal]Sortowanie prze kopcowanie

Odpowiedz Nowy wątek
2006-12-14 14:32
moczulinf
0

Mam do wykonania program ktorego zadaniem bedzie posortowac liczby metoda sortowania prze kopcowanie, program kompiluje sie poprawnie jednak w czasie wykonywania programu pascal sie zawiesza nie wiem gdzie moze lezec przyczyna. Prosze o pomoc w odnalezieniu bledu

program heap_sort;
uses crt;
type
   Wsk = ^TLiczba;
   TLiczba = record
             dane        : integer;
             lewy, prawy : Wsk;
             end;
const N = 20;
var
  d         : array[1..N] of integer;
  i,j,l,poz : integer;
   korzen, tmp, poprz, akt : Wsk;

  PROCEDURE WstawTabliceDoDrzewa(k  : integer);
  begin
  l:=1;{odpowiada za przemienne wstawianie do prawej i lewej galezi}
{tworzenie drzewa}
  New(korzen); {pierwszy element}
  korzen^.dane:=d[1];
  korzen^.lewy:=nil;
  korzen^.prawy:=nil;

  for i := 2 to k do
  begin

{wstawiamy na wierzcholek}
    if d[i]>korzen^.dane then
    begin

            tmp:=korzen;
            New(korzen);
        korzen^.dane:=d[i];
      if l=1 then
      begin
        korzen^.lewy:=tmp;
            l:=0;
        end;
        if l=0 then
      begin
        korzen^.prawy:=tmp;
            l:=1;
        end;
      end ;
      if d[i]<=korzen^.dane then
      begin
      if l=1 then
      begin
        tmp:=korzen^.lewy;
        while d[i]<tmp^.dane do {szukam miejsca gdzie wstawic kolejny element po lewej}
        begin
            poprz:=tmp;
          tmp:=tmp^.lewy;
        end;
        New(akt); {wstawiam element}
        akt^.dane:=d[i];
        akt^.lewy:=tmp;
        akt^.prawy:=nil;
        poprz^.lewy:=akt;
        l:=0;
        write(i);
      end;
      if l=0 then
      begin
        tmp:=korzen^.prawy;
        while d[i]<tmp^.dane do     {szukam miejsca gdzie wstawic kolejny element po prawej}
        begin
            poprz:=tmp;
          tmp:=tmp^.prawy;
        end;
        New(akt); {wstawiam element}
        akt^.dane:=d[i];
        akt^.prawy:=tmp;
        akt^.lewy:=nil;
        poprz^.prawy:=akt;
        l:=1;
      end;
  end;end;
  end;{koniec procedury wstawiania do drzewa}

  PROCEDURE WstawDrzewoDoTablicy(wstawiany:Wsk);
    begin
        d[poz]:=wstawiany^.dane;
        poz:=poz+1;
        if wstawiany^.lewy<>nil then
          WstawDrzewoDoTablicy(wstawiany^.lewy);
        if wstawiany^.prawy<>nil then
          WstawDrzewoDoTablicy(wstawiany^.prawy);
        dispose(wstawiany);
  end;{koniec wstawiania drzewa do tablicy}
 begin
  clrscr;
  writeln;
  writeln('Przed sortowaniem:'); writeln;

{wstawianie elementów losowych do tablicy}
  randomize;
  for i := 1 to N do
  begin
    d[i] := random(100); write(d[i] : 4);
  end;
  for j:=0 to N-1 do {czesc odpowiedzialna za sortowanie}
  begin
    WstawTabliceDoDrzewa(N-j); {wstawiam N-j pierwszych elementów do drzewa reszta jest juz posortowana}
    poz:=1;
    write(j);
    d[N-j]:=korzen^.dane; {wstawiam najwyzszy element z wierzcholka drzewa na poczatek posortowanej czesci tablicy}
    if korzen^.lewy<>nil then
          WstawDrzewoDoTablicy(korzen^.lewy);{wstawiam lewa czesc drzewa z powrotem do tablicy}
        if korzen^.prawy<>nil then
          WstawDrzewoDoTablicy(korzen^.prawy);{wstawiam prawa czesc drzewa z powrotem do tablicy}
        dispose(korzen);
  end;
end;

  writeln('Po sortowaniu:'); writeln;
  for i := 1 to N do write(d[i] : 4);
  readln;
  writeln;
  writeln('Nacisnij Enter...');
  readln;
end.

Pozostało 580 znaków

2006-12-15 04:19
Mgr.Dobrowolski
0

A po co to drzewo? Jak już zasadziłeś drzewo, to niech będzie z gatunku BST, raz przenieś do niego wszystko, następnie w odpowiednim porządku (in-order) przenieś do tablicy i będzie posortowana.
Idea kopcowania jest inna, zapytaj choćby Wiki, poczytasz po polsku, a jeszcze lepiej po angielsku. Robi się to w miejscu, bez przeprowadzek do rozrastającego się lasu dziwnych drzew. Sprawdź ile razy robisz NEW, a ile DISPOSE.
Napisałeś, że Pascal się zawiesza, myślę, że nie Pascal ale cały komputer. Tak to bywa w pierwszych bojach z wskaźnikami.

Tu jest za słaby warunek: WHILE D[i] < TMP^.DANE DO, bo skąd pewność, że TMP wskazuje cokolwiek? Po coś w końcu używałeś NIL.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0