Zapełnianie dynamicznej struktury, błąd w assemblerze SIGSEGV

0

Witam. Pracuję nad problemem komiwojażera, piszę go w Lazarusie. W podanym kodzie w miejscu zapełniania zarezerwowanej pamięci (wiersze 78-88) po inkrementacji licznika pętli (do wartości 1) występują poniższe błędy zamieszczone na załączniku.
Kod:

program project1;

{$mode objfpc}{$H+}

uses
  {$IFDEF UNIX}{$IFDEF UseCThreads}
  cthreads,
  {$ENDIF}{$ENDIF}
  Classes
  { you can add units after this };

type
    wsk_li=^li;
    wsk_miasto=^miasto;

    li=record	{lista wskaznikow}
       next:wsk_li;
       odleglosc:real;
       sasiad:wsk_miasto;
    end;

    miasto=record	{rekord miasta}
       nazwa:string;
       x,y:integer;
       stan:boolean;  {false}
       li:wsk_li;    {nil}
     end;

     tab=array[0..5] of miasto;
     wsk_tab=^tab;

 var
    p_miast, p_sasiedzi:text;
    tmp, tmp2:string;
    l_miast,i,skala:byte;
    tab_miast:wsk_tab;
    start:wsk_miasto;
    dalej:boolean;
    delay_time:word;

procedure policzMiasta(var p_miast:text; var l_miast:byte);
          begin
             while not eof(p_miast) do
             begin
                 readln(p_miast);
                 inc(l_miast);
             end;
             reset(p_miast);
          end;

{rozbija linie teksu pobrana z pliku miasta.txt}
procedure miasto_dane(var tmpM, nazwa:string; var x,y:integer);
          var
            i,sr:byte;
            tmp,tmp2:string;
            blad:word;
          begin
              sr:=pos(';', tmpM);
              nazwa:=copy(tmpM, 0, sr-1);

              tmp:=copy(tmpM, sr+1, length(tmpM)-1);
              sr:=pos(';', tmp);

              tmp2:=copy(tmp, 0, sr-1 );
              val(tmp2, x, blad);

              tmp:=copy(tmp, sr+1, length(tmp)-1);
              val(tmp, y, blad);
          end;

{laduje wszystkie informacje o miastach do pamieci}
procedure ladujMiasta(var p_miast, p_sasiedzi:text; var tab_miast:wsk_tab; const l_miast:byte);
          var
            tmpM, tmpS, nazwa:string;
            x,y:integer;
          begin
          i:=0;
             while not eof(p_miast) do
             begin
                 readln(p_miast, tmpM);
                 miasto_dane(tmpM, nazwa, x,y);
                 tab_miast^[i].nazwa:=nazwa;
                 tab_miast^[i].x:=x;
                 tab_miast^[i].y:=y;
                 tab_miast^[i].stan:=false;
                 tab_miast^[i].li:=nil;
                 inc(i);
             end;
             i:=0;
             {while not eof(p_sasiedzi) do
             begin
                readln(p_sasiedzi, tmpS);

                miasto_sasiedzi(tab_miast, tmpS, i, l_miast);
                inc(i);
             end;}
          end;

begin
  assign(p_miast, 'c:\pliki\miasta.txt');
  assign(p_sasiedzi, 'c:\pliki\sasiedzi.txt');
  reset(p_miast);
  reset(p_sasiedzi);
  policzMiasta(p_miast, l_miast);
  writeln(l_miast);
  getmem(tab_miast, l_miast*sizeof(miasto));
  ladujMiasta(p_miast, p_sasiedzi, tab_miast, l_miast);

  writeln('koniec');
  readln;
end.
 
0

Zacznij od ograniczenia ilości zmiennych których używasz, ile linijek ma twój plik tekstowy, bo jeżeli więcej niż 6 to wychodzisz poza tablice?
eof dla readln liczy #13#10 czy na odwrót w pliku nie wiem czy to rozumiesz może ktoś inny ci wytłumaczy lepiej

0

Plik tekstowy ma jedynie 4 wiersze. Jakich konkretnie zmiennych? Nie, nie rozumiem o co chodzi z eof dla readln, niech ktoś wytłumaczy ;) Chociaż nie wiem czy to ma sens, ponieważ 'zerowy' obieg pętli się wykonuje, dopiero przy następnym aplikacja wywala błędy.

1

Tak powinien wyglądać twój kod, ogranicz ilość używanych zmiennych do minimum, po co tyle wskaźników, i zmiennych przekazywanych w var'ach skoro i tak zadeklarowane są globalnie powiedz czy nie jest czytelniejszy ten kod?
I jak by tego było mało to sobie sam dodaje kolejny element tablicy w zależności od liczby wierszy w pliku.

program proj;
 
{$mode objfpc}{$H+}
 
uses
  {$IFDEF UNIX}{$IFDEF UseCThreads}cthreads,{$ENDIF}{$ENDIF}
  Classes;

type
    RCity=record        {rekord miasta}
       Name:String;
       X,Y:Integer;
       Status:Boolean;  {false}
       Dist:Real;
       Neighbor:Integer;
     end;

 var
    FileCity:Text;

    TAB:array of RCity;


procedure ReadCityData(Str:String);
var ErrorCode:Integer;
begin
 TAB[High(TAB)].Name:=Copy(Str,1,POS(';',Str)-1);
 Delete(Str,1,POS(';',Str));
 Val(Copy(Str,1,POS(';',Str)-1),TAB[High(TAB)].X,ErrorCode);
 Delete(Str,1,POS(';',Str));
 Val(Copy(Str,1,POS(';',Str)-1),TAB[High(TAB)].Y,ErrorCode);
 Delete(Str,1,POS(';',Str));
 WriteLn(Format('Miasto [%s] X:Y [%d:%d]',[TAB[High(TAB)].Name,TAB[High(TAB)].X,TAB[High(TAB)].Y]))
end;

procedure LoadData;
var
 Count:Integer;
 DataPart:String;
begin
 Count:=0;
 WriteLn('Ladowanie danych');
 while not eof(FileCity) do begin
  ReadLN(FileCity, DataPart);
  if Length(DataPart)<4 then Continue;
  SetLength(TAB,High(TAB)+2);
  ReadCityData(DataPart);
  INC(Count);
 end;
 WriteLn('Zaladowano ',Count,' miast');
end;

begin
  Assign(FileCity, 'c:\miasta.txt');
  ReSet(FileCity);
  LoadData;
  {
   Tutaj algorytm do zliczania odległości i najkrótszej trasy :D
  }
  WriteLN('Koniec');
  ReadLn;
end.

Co do mojego poprzedniego postu chodzi o to że ReadLN przesuwa wskaźnik od ostatniej pozycji do pierwszej napotkanej #13 (Tak zwany Enter na klawirze) nawet jak by była pusta linia to on by chciał czytać z niej dane do twojej tablicy, mogło to powodować błędy w twoim kodzie, musisz nauczyć się przewidywać takie ewentualności i eliminować je.
Błąd SIGSEGV to Access Violation (pod UNIX Segmentation fault) mówi ze program chce się odwołać do pamięci która nie istnieje/nie ma do niej dostępu. np gdy masz tablice 2-elementową chcesz odwołać się do 3 elementu

0

Szczerze? To mój (jak i pewnie większości początkujących programistów) błąd - zaśmiecanie kodu na wszelakie możliwe sposoby. To co mi pokazałeś hzmzp jest świetne, pełne przejrzystości ;) I oczywiście problem już nie występuje. Bardzo mi pomogłeś, wielkie dzięki!

Mam jednak pytanie - jak rekord miasta połączyć z listą jego sąsiadów?

0

nie ma sensu (ja nie widzę) tworzyć listy połączeń z każdym miastem, ujmując to prościej
zakładamy że pierwsze miasto w indeksie tabeli nie może być połączeniem z innego miasta i ostatnie miasto z tabeli nie może mieć połączenia do innego miasta (prościej index Low(TAB) nie może być zawarte w żadnym Neighbor i w żadnym Neighbor nie może być index High(TAB)), w pętli sprawdzamy które miasto jest najbliżej miasta z Indeksem X (poczynając od 0) i jego index przypisujemy do Neighbor oraz przekazujemy index tego miasta do X tak w kółko do końca wykluczając tych, którzy mają już sąsiadów przypisanych (if TAB[Index].Neighbor >0 then Continue; ) żeby pominąć ich;
jak chcesz mogę podać ci gotowca, aczkolwiek to zepsuje trochę zabawę w algorytmikę XD

0

rozumiem o co Ci chodzi, ale dla potrzeb algorytmu który chcę zastosować (siłowy) wydaje mi się że lepiej by było dla każdego połączenia z sąsiadem zastosować rekordy które podałem na samym początku wątku, chociaż to co napisałeś jest temu bliskie. szczerze? zerknąć na gotowca nie zaszkodzi, bo dobra struktura to chyba największa (poza głównym unitem) zagadka całego projektu ;p

0

Owszem, jeżeli ci nie przeszkadza fakt zajmowania dużej ilości pamięci to można trzymać takie dane w rekordach, nawet jest to wskazane jeżeli będziesz faktycznie je wykorzystywał, jeżeli nie należy tego unikać.
Jeżeli jednak się upierasz przy tym to należy to zrobić tak,
w

type
    RCity=record        {rekord miasta}
       Name:String;
       X,Y:Integer;
       Status:Boolean;  {false}
       Dist:Real;
       Neighbor:Integer;
     end;
 

Neighbor:Integer; zamienić na Neighbor:array of TNeighbors; i usunąć zmienną Dist

oraz dodać nowy typ

type TNeighbors = record      
       Dist:Real;
       Neighbor:Integer;
end;

tylko w tym przypadku zajmuje to ogromne ilości pamięci bo dla każdego miasta tworzy się tablica TNeighbors o ilości indeksów High(TAB)-1 (-1 bo nie bierzemy pod uwagę tego samego rekordu)
o ile się nie mylę to przyrost użytej pamięci na to jest równy (High(TAB)-2)*High(Tab) tego co było by użyte przy moim rozwiązaniu

0

Chyba jednak masz rację.. nie pomyślałem o ilości zajmowanej pamięci.
Jeżeli chciałbym wykorzystać dynamiczną strukturę wyglądającą np tak:

type
p_city=^RCity;

  RCity=record
       Name:String;
       X,Y:Integer;
       Status:Boolean;
    end;

var
  tab:p_city;

w jaki sposób mam zarezerwować w pamięci 4 elementy tej tablicy? Nie mogę w Lazarusie wykonać tego ani SetLength(), ani GetMem().. może zwykły 'array of'? Czy może rozwiązanie które podałeś jest już dynamiczną strukturą? Problem pojawia się gdy chcę przypisać coś elementowi z indeksem 1 i większym, np

tab^[1].nazwa:='przykład';

dodanie znaczników <code class="delphi"> - fp

0

Pomieszałeś sobie pojęcia.
To co podałem to jest już dynamiczna struktura.
Pointery służą do czegoś zupełnie innego
Dla przykładu masz tablice która zajmuje 2,5GB RAM'u i chcesz żeby twoja aplikacja wielowątkowa z niej korzystała. Prościej jest przekazać Pointer (punkt pamięci w którym jest zaalokowana tablica) niż stworzyć jej duplikat i przekazać jako parametr.
Pointery mają przewagę, gdyż nie jest istotne gdzie została przypisana zmienna, np w formie Form1 w sekcji private, normalnie nie masz dostępu z innego miejsca w aplikacji, ale używając pointera do tej zmiennej można nią manipulować gdzie chcesz, ten fakt jest wykorzystywany do tworzenia bot'ów/cheat'ów do gier.
Jak tego używać dokładniej jest napisane tu
Rozdział 2

0

Dobrze, pomagasz mi, już mi się wszystko rozjaśniło ;D powiedz my czy dla takiej struktury funkcja 'znajdz_droge' którą napisałem jest poprawnym algorytmem siłowym?
Struktura:

 type
    wsk_li=^li;
    wsk_miasto=^miasto;

    li=record	{lista wskaznikow}
       next:wsk_li;
       odleglosc:real;
       sasiad:wsk_miasto;
    end;

    miasto=record	{rekord miasta}
       nazwa:string;
       x,y:integer;
       stan:boolean;  {false}
       li:wsk_li;    {nil}
     end;

     wsk_tab=array of miasto;

 var
    tab_miast:wsk_tab;

A tak wygląda główna funkcja:

 function znajdz_droge(const startowe:wsk_miasto;var m:wsk_miasto;const l_miast,skala:byte;licznik:byte;var dtime:word):boolean;
          var
            tmpLi:wsk_li;
            tmpx, tmpy:integer;
          begin
             tmpLi:=m^.li;
             m^.stan:=true;
              if keypressed then begin
               if dtime > 650  then dtime:=650
               else dtime := 0;
              end;
              while tmpLi <> nil do
              begin
                 if tmpLi^.sasiad^.stan <> true then
                 begin
                   delay(dtime);
                   setColor(red);
                   FillEllipse(m^.x*skala+155,  m^.y*skala, 2,2);
                   rysuj_polaczenie(m^.x, m^.y, tmpLi^.sasiad^.x, tmpLi^.sasiad^.y  ,skala, true);
                   if znajdz_droge(startowe,tmpLi^.sasiad, l_miast, skala, licznik+1, dtime) then
                   begin
                     znajdz_droge:=true;
                     exit;
                   end else
                   begin
                      tmpx := tmpLi^.sasiad^.x;
                      tmpy:= tmpLi^.sasiad^.y;
                      delay(dtime);
                      rysuj_polaczenie(m^.x, m^.y, tmpx, tmpy  ,skala, false);
                      setColor(yellow);
                      FillEllipse(m^.x*skala+155,  m^.y*skala, 2,2);
                   end;
                 end else if ( tmpLi^.sasiad^.nazwa = start^.nazwa) and (licznik = l_miast)then
                 begin
                    delay(dtime);
                    rysuj_polaczenie(m^.x, m^.y, startowe^.x, startowe^.y  ,skala, true);
                    setColor(red);
                    FillEllipse(m^.x*skala+155,  m^.y*skala, 2,2);
                    outtextxy(5, GetMaxY-70, 'Zadanie rozwiazane');
                    outtextxy(5, GetMaxY-60, 'pomyslnie!');
                    znajdz_droge:=true;
                    exit;
                 end;
                 tmpLi:= tmpLi^.next;
               end;
                m^.stan:=false;

             znajdz_droge:=false;
          end;

dodanie znaczników <code class="delphi"> - fp

0
  1. Powinieneś rozdzielić sobie szukanie drogi a jej rysowanie na osobne procedury/funkcje tzn jak masz
    szukanie to jej szuka, jak znalazł i chce rysować to przekazujesz mu tylko x1,x2,y1,y2,kolor,skale i co tam jeszcze chcesz.
    2.Teoretycznie to nie widzę błędów, ale ciężko stwierdzić czy ich nie ma. Powinieneś przeprowadzić tak z 30 testów z 100 miast i zobaczyć czy się gdzieś nie gubi/zapętla, do tego wyłącz sobie opóźniacz (zakładam że do tego służy delay(dtime);)

--
Pokusiłem się napisać taki programik na szybko, demko jest w załączniku i można wygenerować ścieżkę z 800 miast bo tyle zawiera tbl_citys.db
Co ciekawe spodziewałem się większych błędów obliczeniowych, najlepiej je widać kiedy liczba przekroczy 700

0
  1. masz rację
  2. no to super ;) w zasadzie chciałem się upewnić czy dobrze zrozumiałem teorię założeń tego algorytmu, ale chyba jest ok ;p

Dzięki wielkie! ;)

EDIT: no i dupa zbita.. nie znam się na takich algorytmach, ale mnie trochę zdziwiło odnajdywanie drogi w kilkuset miastach w tak krótkim czasie.. no nic, ALGORYTM JEST NIEPOPRAWNY, nie kopiujcie tego.

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