Segmentation fault and exitcode 216

Привет всем. Пишу на паскале программу сортировки чисел произвольной длины. Числа храню в списках поциферно. Начинал писать программу на TP, но вскоре столкнулся с проблемой нехватки памяти (сортировал, например, 1000 чисел, в каждом из которых 1000 цифр). Вследствие этого перешел на FP. Тут наблюдаю следующее: все вроде работает, но на некоторых не длинных последовательностях довольно коротких чисел FP выдает ошибку компиляции с exitcode 216, в то время, как в турбопаскале эта же программа данную последовательность сортирует. Еще раз напомню, что на TP не могу вернуться, т.к.не хватает памяти при сортировке больших последовательностей, с которыми успешно справляется freePascal.Т.е ситуация плохая - и там и там скажем так БАГ. При debug'e выяснилось, что ошибка в процедуре сравнения чисел, причем выскакивает ошибка Segmentation fault не на первых же числах при сортировке. Недоумеваю, как это победить. Что может быть не так? Ошибку пишет на строке: if x.ch^.c<y.ch^.c then fl:=false else fl:=true - в данной строке сравниваю чиса покоординатно, т.е. x.ch - ссылка на один из разрядов числа (описал, чтобы вкратце стало понятно). Вроде бы "странностей" с указателями не допускаю... Подскажите что-нибудь, пожалуйста. А то такой ступор уже долго...

ошибка в 84й строке
то есть, просим код в студию.

код всей программы ??

Добавлено 18.04.10, 18:05

program sortirovki;
{$s-}
{$r-}
type
     list=^zveno;
 
     zveno=record
     c:byte;
     next:list
     end;
 
     elem=record
     sgn:boolean;
     n:integer;
     zero:boolean;
     ch:list;
     kz:integer
     end;
 
     structure=array [1..1500] of elem;
 
var
    B:structure;
    i,N,hs,M,l,prc,src,prh,srh,T:longint;
    c:char;
    p:list;
    vsgn:boolean;
function compare(var x,y:elem):boolean;  {true, esli x>y}
var px,py:list;
    fl:boolean;
begin
if x.sgn <> y.sgn then
 if x.sgn=false then compare:=true else compare:=false else
   if x.n<>y.n then
     if x.n < y.n then
       if x.sgn=false then compare:=false else compare:=true else
        if x.sgn=false then compare:=true else compare:=false else
       begin
         new(px);
         new(py);
         px:=x.ch;
         py:=y.ch;
         if x.ch^.c=0 then
         begin
           repeat
             x.ch:=x.ch^.next;
           until x.ch^.c<>0;
         end;
         if y.ch^.c=0 then
         begin
           repeat
             y.ch:=y.ch^.next;
           until y.ch^.c<>0;
         end;
         if x.ch^.c < y.ch^.c then fl:=false else fl:=true;
         while (x.ch^.c = y.ch^.c) and (x.ch<>nil) and (y.ch<>nil) do
         begin
           x.ch:=x.ch^.next;
           y.ch:=y.ch^.next;
           if x.ch^.c < y.ch^.c then fl:=false else fl:=true;
         end;
         x.ch:=px;
         y.ch:=py;
        if (x.sgn=false) and fl  then compare:=true else
         if (x.sgn=false) and not fl then compare:=false else
           if (x.sgn=true) and fl then compare:=false else compare:=true;
       end;
srh:=srh+1;
src:=src+1;
end;
procedure swap(var x,y:elem);
var z:elem;
begin
  new(z.ch);
  z.n:=x.n;
  z.kz:=x.kz;
  z.sgn:=x.sgn;
  z.zero:=x.zero;
  z.ch:=x.ch;
  x.n:=y.n;
  x.kz:=y.kz;
  x.sgn:=y.sgn;
  x.zero:=y.zero;
  x.ch:=y.ch;
  y.n:=z.n;
  y.kz:=z.kz;
  y.sgn:=z.sgn;
  y.zero:=z.zero;
  y.ch:=z.ch;
  prh:=prh+1;
  prc:=prc+1;
end;
 
procedure heapify(var B:structure;j:integer);
var max:integer;
begin
  if (2*j <= hs) and (not compare(B[j],B[2*j])) then max:=2*j else max:=j;
  if  (2*j+1 <= hs) and (not compare(B[max],B[2*j+1])) then max:=2*j+1;
  if j <> max then begin
    swap(B[j],B[max]);
    heapify(B,max);
  end
end;
 
procedure heapsort(var B:structure);
var i,l:integer;
begin
  for i:=hs div 2 downto 1 do
    heapify(B,i);
    {for l:=1 to N do
     write(a[l],' ');}
  for i:=hs downto 2 do
  begin
    swap(B[1],B[i]);
    dec(hs);
    heapify(B,1);
  end;
end;
 
procedure chsort(var B:structure);
var i,j:integer;
begin
  i:=1;
  while i<N do
  begin
    if compare(B[i],B[i+1]) then
      begin
       j:=i;
       while (not compare(B[j+1],B[j])) and (j <> 0) do
       begin
         swap(B[j],B[j+1]);
         dec(j);
       end;
       inc(i);
      end else inc(i);
  end;
end;
 
function vvod(var B:structure):string;
var s:char;
    fl:boolean;
    i:integer;
    p:list;
    cp:boolean;
begin
  i:=0;
  repeat
    inc(i);
    fl:=true;
    read(s);
    if (s<>' ') and (s<>'.') then
    begin
      if s='-' then begin read(s);B[i].sgn:=true; end else B[i].sgn:=false;
      if (s='0') and fl then B[i].kz:=B[i].kz+1 else
      begin
        B[i].n:=B[i].n+1;
        fl:=false
      end;
      if s<>'0' then B[i].zero:=false else B[i].zero:=true;
        new(B[i].ch);
        B[i].ch^.c:=ord(s)-ord('0');
        B[i].ch^.next:=nil;
        new(p);
        p:=B[i].ch;
      repeat
        read(s);
        if (s<>' ') and (s<>'.') then
        begin
          if s='0' then B[i].zero:=B[i].zero and true else B[i].zero:=false;
          if (s='0') and fl then B[i].kz:=B[i].kz+1
          else
          begin
            B[i].n:=B[i].n+1;
            fl:=false
          end;
          new(B[i].ch^.next);
          B[i].ch:=B[i].ch^.next;
          B[i].ch^.c:=ord(s)-ord('0');
          B[i].ch^.next:=nil
        end;
      until (s=' ') or (s='.');
      B[i].ch:=p;
      T:=T+1;
    end;
  until (s='.');
vvod:='';
end;
 
begin
T:=0;
assign(input,'input.txt');
assign(output,'output.txt');
reset(input);
rewrite(output);
src:=0;
prc:=0;
srh:=0;
prh:=0;{
  writeln('Vvedite razmer massiva');
  read(N);
  writeln('Vvedite elementi massiva');
  for i:=1 to N do
  begin
    read(x[i]);
    y[i]:=x[i];
  end;
    chsort(x);
    writeln;}
     {
  writeln('Kolichestvo sravnenii i prisvaivanii dlya chelnok ',src,' ',prc);
  writeln('Kolichestvo sravnenii i prisvaivanii dlya heapsort ',srh,' ',prh);
  writeln('Rezultati sortirovki: 1)chelnok for X, 2)heapsort for Y');
  for i:=1 to N do
    write(x[i],' ');
    writeln;
  for i:=1 to N do
    write(y[i],' '); }
  {probi vivoda}
  vvod(B);
  hs:=T;
  N:=T;
  heapsort(B);
  {chsort(B);}
  {writeln(prh,' ',srh);}
  {writeln(B[1].ch^.c);}
  {writeln(compare(B[1],B[2]));}
  {writeln(B[1].n,' ',B[2].n);}
  {writeln(B[1].ch^.next^.next^.c);}
  {writeln(compare(B[1],B[3]));}
  {writeln(T);}
  for i:=1 to T do
  begin
    new(p);
    p:=B[i].ch;
    vsgn:=true;
    while (B[i].ch<>nil) do
    begin
      if (B[i].sgn=true) and vsgn then begin vsgn:=false; write('-') end;
      write(B[i].ch^.c);
      B[i].ch:=B[i].ch^.next;
    end;
    write(' ');
    B[i].ch:=p;
  end;
  {end probi}
readln;
readln;
close(input);
close(output);
end.

хотя бы код модуля, где генерируешь строку, и код модуля, который вырает ошибку.
кстати, вроде как 216 это не код компиляции, а ошибка периода исполнения, поиск выдал GPF (ошибка доступа по ссылке), скорее всего у тебя в каком-то месте x.ch=NIL

MacClaus, файл данных присоедини... Если так не прилепится - то заархивируй.

Кстати,, если используешь FPC, подключи первыми модули heaptrc и lineinfo, и получишь точное указание места. где произошла ошибка. Будет гораздо проще искать причину...

Цитата MacClaus @ 18.04.10, 17:59

new(p); p:=B[i].ch;

во-первых у тебя здесь утечка памяти. Ты выделяешь память для P, и тут же присваиваешь P чему-то еще. Это у тебя в трех местах, во внешнем коде, внутри compare и внутри vvod(B)

Цитата MacClaus @ 18.04.10, 17:59

procedure swap(var x,y:elem); var z:elem; begin new(z.ch);

здесь не нужен new(z.ch) - тебе не нужно выделять какую-то память для обмена местами двух ссылок на данные. Ты на некоторое время получаешь две ссылки на одно и то же место в куче, и всё.

Цитата MacClaus @ 18.04.10, 17:59

vvod:='';

зачем тебе объявлять vvod функцией? достаточно объявить её процедурой, все равно ты не используешь значение, возвращаемое из vvod(B).

Цитата MacClaus @ 18.04.10, 17:59

if s='0' then B[i].zero:=B[i].zero and true else B[i].zero:=false;

индийский код. Правильно (по смыслу, ты пытаешься вынести признак нуля в B[i ].zero) так: if s<>'0' then b[i ].zero:=false; Кроме того, отсутствует проверка на принадлежность прочитанного символа множеству цифр. Если там что-то вроде #13, #9, #26 или просто буквы, или даже еще один минус, у тебя в разряде появится несусветная величина.

Цитата MacClaus @ 18.04.10, 17:59

new(B[i].ch^.next);
B[i].ch:=B[i].ch^.next;
B[i].ch^.c:=ord(s)-ord('0');
B[i].ch^.next:=nil

Это правильный кусок, с учетом того, что ты сохранил первый элемент списка в P, хотя и не совсем обычный способ использования переменных.

Цитата MacClaus @ 18.04.10, 17:59

repeat inc(i); fl:=true; read(s); if (s<>' ') and (s<>'.') then begin

Для приличия нужно очистить (инициализировать, заполнить стартовыми значениями) всю запись B[i ]. В некоторых реализациях компилятора начальный сегмент данных может не заполняться нулями в начале работы программы, и тогда в переменных будет жуткий мусор, а ты опираешься по меньшей мере в двух местах на то, что в начале работы с записью в B[i ].поле лежит ноль.

Теперь процедура сравнения. Если x.n меньше нуля, а y.n больше нуля, понятно, что сравнивать нечего - и так ясно, что больше используй конструкцию exit для выхода из процедуры со значением.

if x.sgn <> y.sgn then begin
 if x.sgn=false then compare:=true else compare:=false;
 exit;
end else ....

Счетчик сравнений ты так или иначе увеличиваешь, поэтому логичнее их увеличивать сразу после входа в функцию. Раз вошел, значит сравнил. И вообще, внимательно разберись с ветвлениями в этом месте. У тебя минимум шесть вложенных if'ов, в части из которых идет присвоение значения результату compare, которое имеет смысл сразу же обозначить и выдать наружу (присвоил и сразу exit) - и нагляднее, и удобнее баги ловить.

Vesper, советы учту. Просто, несмотря на все недочеты, вводится все нормально и даже сортируется в турбо. Но вот во freepascal он при дебаге обнаруживает через некоторое время ошибку Segmentation fault в строке if x.ch^.c < y.ch^.c then fl:=false else fl:=true почти в конце процедуры compare, просто я не могу понять, что ему не нравится, если данные введены корректно, в турбопаскале этот же алгоритм сортирует данную последовательность, а во freepascal'e нет. Просто в чем может быть причина ??

Цитата MacClaus @ 18.04.10, 18:52

в турбопаскале этот же алгоритм сортирует данную последовательность, а во freepascal'e нет

Программа на Турбо-Паскале компилировалась со всеми включенными опциями? (контроль индексов? контроль переполнения? контроль стека?)

Ты файл с данными, которые "прошли сортировку" (именно в кавычках, потому что если ты портишь какую-то информацию, что очень часто встречается при отключенных опциях в Турбо-Паскале; FPC такого не позволяет - он тут же вылетает с SF) привел? Как же ты тогда можешь утверждать, что TP код сортирует? Так и пиши: "МНЕ КАЖЕТСЯ, что У МЕНЯ код сортирует данные". Не надо обобщать...

Не хочешь помощи - ищи проблему сам... Я ЗА ТЕБЯ подбирать данные, на которых программа вылетает, не собираюсь...

MacClaus, прикрепи файл входных данных.

кстати, MacClaus, поймал твою ошибку. Она возникает, если ты сравниваешь два равных числа, не равных нулю, программа доходит до последнего знака, сравнивает, они равны, потом идет переход по next, а там уже nil, и ты следующим оператором пытаешься получить nil^, здесь и вылетает GPF. Турбо-Паскаль не имеет GPF как такового, поэтому что-то он у тебя "сортирует". Вот этот кусок:

         while (x.ch^.c = y.ch^.c) and (x.ch<>nil) and (y.ch<>nil) do
         begin
           x.ch:=x.ch^.next;
           y.ch:=y.ch^.next;
           if x.ch^.c < y.ch^.c then fl:=false else fl:=true;
         end;

переписываешь так:

         while (x.ch<>nil) and (y.ch<>nil) do
         begin
           if x.ch^.c<>y.ch^.c then begin
             if x.ch^.c < y.ch^.c then fl:=false else fl:=true;
             break {выход из цикла while. Учись, кстати, пользоваться}
           end;
           x.ch:=x.ch^.next;
           y.ch:=y.ch^.next;
         end;
         if (x.ch=nil) or (y.ch=nil) then begin
           compare:=false;
           exit
         end;
{числа равны, а делать что-то надо. В этом случае оба указателя будут nil, а если только один,
то ты напортачил при вводе чисел в память или при вычислении значений B[i].n}

В общем случае, если ты переходишь на следующее звено списка, сначала должна идти проверка на NIL, а потом доступ к значениям.