"Invalid pointer operation" - Stack

[nahkillo94]

Hallo,

ich bin dabei ein eigenen Stack zu erstellen, habe allerdings Probleme mit pointern.

Beim kompilieren gibt es keinen Fehler, doch wenn ich das Programm ausführe und etwas auf den stack legen will kommt "Invalid pointer operation".

Delphi-Quellcode:

type
  PStackItem = ^TStackItem;
  TStackItem = record
    data: integer;
    next: PStackItem;
  end;

  TStack = class
    private
    public
      first : PStackItem;
      constructor create();
      procedure push(data : integer);
      function pop() : integer;
      function peek() : integer;
    end;

constructor TStack.create();
begin
  inherited;
  first := nil;
end;

procedure TStack.push(data : integer);
var
  node : PStackItem;
begin
  node^.data := data;
  node^.next := first;
  first := node;
end;

function TStack.pop() : integer;
var
  content : integer;
  old : PStackItem;
begin
  content := 0;
  if (first <> nil) then
  begin
    old := first;
    first := first^.next;
    content := old^.data;
    old := nil;
  end;
  result := content;
end;

Der Fehler wird in push() durch

Code:

node^.next := first;

verursacht. Ich vermute es fehlt irgendwo ein Dach, oder?

[himitsu]

Zitat:

Delphi-Quellcode:

procedure TStack.push(data : integer);
var
  node : PStackItem;
begin
  node^.xxx

Wer hat denn der Variable "node" einen Wert zugewiesen, bevor damit was gemacht wird?


Also, das Objekt in "node" wurde nicht erstellt.
und

Delphi-Quellcode:

 := nil;

gibt keine Objekte frei.

PS: Welche Delphi-/Lazarus-Version nutzt du denn?

[BUG]

Zitat:

Zitat von nahkillo94 (Beitrag 1147860)

Ich vermute es fehlt irgendwo ein Dach, oder?

Ich vermute node ist kein gültiger Zeiger (wird nie initialisiert und nie Speicher reserviert).
Schau dir mal new und dispose an oder löse das Ganze mit Klassen.

[nahkillo94]

Vielen Dank! :thumb: Es fehlte nur:

Code:

new(node);

Ich nutze Delphi 7. Wieso?

[DeddyH]

Für jedes New() ein Dispose(), das hast Du hoffentlich berücksichtigt.

[nahkillo94]

ja, hab ich beachtet

[himitsu]

Zitat:

Zitat von nahkillo94 (Beitrag 1147963)

Vielen Dank! :thumb: Es fehlte nur:

Code:

new(node);

Nur?
Das ist nur die Erstellung und wo wird es wieder freigegeben?
[edit] hätte nicht vergessen sollen es abzusenden :oops:

Zitat:

Zitat von nahkillo94 (Beitrag 1147963)

Ich nutze Delphi 7. Wieso?

Um die Antwort an deine Version anzupassen? Denn es gibt nicht alles in jeder Version, bzw. Manches funktioniert nicht immer gleich. (Darum gibt es im Profil auch die Möglichkeit das direkt anzugeben.)
So gibt es z.B. schon fertige Sachen, wie TStack (Unit Contnrs) und in neueren Delphis machen sich die Generics ganz nett, wie z.B. mit TStack<Integer> (ein Stack für Integer), wo alles schon fertig ist und man es selber somit schwieriger hat neue Fehler einzubauen.

[nahkillo94]

Die Freigabe ist in pop(), da wo vorher old := nil stand steht jetzt dispose(old);

Werde es gleich mal im Profil einstellen, allerdings wollte ich kein fertiges Stack nutzen sondern der Sinn der Sache war, es selbst zu probieren. Und jetzt funktioniert es auch.

[himitsu]

Zum Probieren und Verstehen ist es natürlich gut geeignet.
Für eine "produktive" Nutzung hab ich zwar früher zwar auch Vieles selber gemacht, aber erfahrungsgemäß hat es sich dann als Nachteil herausgestellt.
* Der Code wird damit größer und fehleranfälliger.
* Man hat mehr Arbeit, als eigentlich nötig.
* Und meistens bringt es keine so gravierenden/nötigen Geschwindigkeitsvorteile, welche den Mehraufwand rechtfertigen.


So, das war jetzt eine einfach verkettete Liste.
Nun kommen dann wohl die doppelt verketteten Listen, Hashlisten und dann die BTrees dran? :angle:

[nahkillo94]

Zitat:

* Der Code wird damit größer und fehleranfälliger.
* Man hat mehr Arbeit, als eigentlich nötig.
* Und meistens bringt es keine so gravierenden/nötigen Geschwindigkeitsvorteile, welche den Mehraufwand rechtfertigen.

ok :thumb:

ja, doppelt verkettet würde ich noch machen, aber Hashliste krieg ich noch nicht hin. Dazu muss ich das System ersteinmal richtig verstehen. Und von BTrees höre ich das erste mal. :?:

[himitsu]

Stichwort: [GOOGLE]binär Bäume[/GOOGLE]

Ganz einfach gesagt.

Willst du in einer Liste suchen, dann mußt du diese Liste durchsuchen.
Im schlimmsten Fall mußt du also jeden einzelnen Eintrag prüfen, wenn sich das Gesuchte ganz am Ende versteckt.
Im Durchschnitt muß man also die Hälfte aller Eintrage absuchen, um was zu finden.

Bei einer Hashlist wird ein Hash ('ne Art Quersumme) über die Einträge gebildet. Aus dem Gesuchten bildet man ebenfalls einen Hash.
Nun muß man nur noch den Hash finden und da der Hash kleiner ist, muß man weniger vergleichen, aber muß immernoch jeden einzelnen Eintrag durchsuchen, auch wenn das nun schneller geht.

Der BTree, bzw. der binäre Baum ist eine Art Pfad.
Man ordnert die Einträge dort ein und kann sie dann schneller finden, da man nicht alles durchsuchen muß.
Für den Apfel reicht z.B. schon ein einziger Vergleich.

Code:

      #                      #       #
     / \                     #      / \
    A   B----                #     A   B----
   /   / \    \              #    /   / \    \
  P   A   L    U             #   #   A   L    U
  |   |   |    |             #       |   |    |
  F   U   U    S---          #       #   #    S---
  |   |   |   / \  \         #               / \  \
  E   M   M  #  C   S        #              #  C   S
  |   |   |     |   |        #                 |   |
  L   #   E     H   i        #                 #   #
  |       |     |   |        #
  #       #     #   #        #
                             #
  #Apfel     #Bus            #   #Apfel     #Bus
      #Baum     #Busch       #       #Baum     #Busch
          #Blume    #Bussi   #           #Blume    #Bussi

[edit]
Wäre es nicht toll, wenn die Codeausrichtung irgendwann mal funktionieren würde?

[nahkillo94]

wow! Du machst ganz schön großen Aufwand um mir das zu erklären. :)

Also das mit der Hashliste klingt machbar. Aber das mit dem Baum nicht. Das suchen im Baum würde dann wahrscheinlich auf Backtracking hinauslaufen.

[jaenicke]

Zitat:

Zitat von nahkillo94 (Beitrag 1148039)

Aber das mit dem Baum nicht. Das suchen im Baum würde dann wahrscheinlich auf Backtracking hinauslaufen.

Nein, eben genau nicht. ;-)
An jeder Kreuzung schaut man welches die richtige ist und kommt so viel schneller zum Ergebnis. ;-)