Problem mit Zeigern

[Macci]

Der Sinn eines Kellers ist es ja gerade, möglichst schnell den Kram reinschmeissen zu können (Aufwand O(1)) und möglichst schnell an des LETZTE eingelagerte Element dranzukommen (Aufwand O(1)).

Diese beide Punkte würdest du zunichte machen, wenn du immer absichtlich den Keller bis zum Ende hin durchforstest (jeweils Aufwand O(n)). Kannst du deinem Lehrer auch so sagen ;-)

[praesident]

Zitat:

Zitat von Macci

Schau mal, so klappts:

Delphi-Quellcode:

PROCEDURE push(VAR zkopf:tzeiger;inhalt:Char);
var zhilf:tzeiger;
BEGIN
new(zhilf);
zhilf^.inhalt:=inhalt;
zhilf^.next:=zkopf;
zkopf:=zhilf
END;

FUNCTION pop(VAR zkopf:tzeiger):char;
BEGIN
result:=zkopf^.inhalt;
zkopf := zkopf^.next
END;

Hab ich erfolgreich gesetet mit:

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var tmp:tzeiger;
begin
push(tmp,'a');
push(tmp,'b');
push(tmp,'c');
showmessage(pop(tmp));   //c
showmessage(pop(tmp));   //b
showmessage(pop(tmp));   //a
end;

aber nein, ich seh ja grad, dass deine pop funktion ja wieder das erste element entfernt...wollte ich ja nicht

eigentlich ist das mit der 2. liste ja eh sinnlos...müsste ja einfach immer nur das erste wegnehmen, ich weiß nicht, warum wir das unbedingt von hinten abbauen sollen

[praesident]

Zitat:

Zitat von Macci

Der Sinn eines Kellers ist es ja gerade, möglichst schnell den Kram reinschmeissen zu können (Aufwand O(1)) und möglichst schnell an des LETZTE eingelagerte Element dranzukommen (Aufwand O(1)).

Diese beide Punkte würdest du zunichte machen, wenn du immer absichtlich den Keller bis zum Ende hin durchforstest (jeweils Aufwand O(n)). Kannst du deinem Lehrer auch so sagen ;-)

gut, das aufbauen nach hinten würde in meinem fall noch sinn machen...aber das abbauen von vorne wäre dann eher angebrachter, weil ich gleich an das erste element wieder ran muss...

werd jetzt einfach von vorne die elemente weg nehmen...is schon spät und ich hab keine lust mehr :wall:

[Macci]

Zitat:

Zitat von praesident

aber nein, ich seh ja grad, dass deine pop funktion ja wieder das erste element entfernt...wollte ich ja nicht

Wenn du bei meiner Funktion
push a
push b
push c

machst, und darauf hin 3 pop's folgen, liefern diese in dieser Reihenfolge: c b a (!)
Also immer das LETZTE Element wird ZUERST entfernt.

Genau das erwartet man von einem Keller auch.

Was du meinst ist vielleicht eine Schlange. Dann heißen die entsprechenden Befehle aber nicht push und pop, sondern enqueue und dequeue.

Bist du dir da sicher, dass du eine Schlange willst, und keinen Keller?
Welches Ergebnis möchtest du haben, wenn man die von mir oben aufgeführten 3 push's durchführt und dannach 3 pop's ?

[praesident]

Zitat:

Zitat von Macci

Zitat:

Zitat von praesident

aber nein, ich seh ja grad, dass deine pop funktion ja wieder das erste element entfernt...wollte ich ja nicht

Wenn du bei meiner Funktion
push a
push b
push c

machst, und darauf hin 3 pop's folgen, liefern diese in dieser Reihenfolge: c b a (!)
Also immer das LETZTE Element wird ZUERST entfernt.

Genau das erwartet man von einem Keller auch.

Was du meinst ist vielleicht eine Schlange. Dann heißen die entsprechenden Befehle aber nicht push und pop, sondern enqueue und dequeue.

Bist du dir da sicher, dass du eine Schlange willst, und keinen Keller?
Welches Ergebnis möchtest du haben, wenn man die von mir oben aufgeführten 3 push's durchführt und dannach 3 pop's ?

ich möchte schon c b a als ergebnis haben...

aber das würde meiner meinung nach nicht herauskommen, wenn ich deine pop funktion verwende...zumindest nicht mit meiner push funktion...

meine push funktion baut sich ja so auf, das nach dem pushen von a b c der zeiger zkopf immernoch auf a steht...

[Macci]

Joa, dann benutze sowohl meine PUSH als auch meine POP Funktion.

Hier nochmal:

Delphi-Quellcode:

PROCEDURE push(VAR zkopf:tzeiger;inhalt:Char); 
var zhilf:tzeiger; 
BEGIN 
new(zhilf); 
zhilf^.inhalt:=inhalt; 
zhilf^.next:=zkopf; 
zkopf:=zhilf 
END; 

FUNCTION pop(VAR zkopf:tzeiger):char; 
BEGIN 
result:=zkopf^.inhalt; 
zkopf := zkopf^.next 
END;

Damit klappt es genau so, wie du es möchtest. Garantiert :-)
Und beides in der Laufzeit O(1), also in konst. Laufzeit. Besser gehts nicht.

[praesident]

Zitat:

Zitat von Macci

Joa, dann benutze sowohl meine PUSH als auch meine POP Funktion.

Hier nochmal:

Delphi-Quellcode:

PROCEDURE push(VAR zkopf:tzeiger;inhalt:Char); 
var zhilf:tzeiger; 
BEGIN 
new(zhilf); 
zhilf^.inhalt:=inhalt; 
zhilf^.next:=zkopf; 
zkopf:=zhilf 
END; 

FUNCTION pop(VAR zkopf:tzeiger):char; 
BEGIN 
result:=zkopf^.inhalt; 
zkopf := zkopf^.next 
END;

Damit klappt es genau so, wie du es möchtest. Garantiert :-)
Und beides in der Laufzeit O(1), also in konst. Laufzeit. Besser gehts nicht.

die pop funktion erzeugt bei mir bei

Delphi-Quellcode:

result:=zkopf^.inhalt;

einen fehler

wieder diese exeption fehlermeldung sobald ich nen wert eingebe und auf berechnen klicke...

[Macci]

Dann versuchst du einmal irgendwo von einem leeren Stack zu poppen. Das geht natürlich nicht ;-)
Zeig doch mal den restlichen Code.

Mir fällt grade auf: Etwas sauberer wäre es natürlich, bei der POP-Funktion mit Dispose den verwendeten Speicher freizugeben.

edit: Also so:

Delphi-Quellcode:

FUNCTION pop(VAR zkopf:tzeiger):char;
var zhilf:tzeiger;
BEGIN
result:=zkopf^.inhalt;
zhilf:=zkopf;
zkopf:=zkopf^.next;
Dispose(zhilf)
END;

[alzaimar]

Sollte man nicht auch auf lesbaren Code unter Beachtung der einfachsten Richtlinien achten?

Delphi-Quellcode:

Function Pop(Var Zkopf : TZeiger) : Char;
// Liefert den Inhalt des obersten Kellerelementes und gibt den Speicher frei.
Var 
  zHilf : TZeiger;

Begin
  Result := zkopf^.inhalt;
  zHilf := zKopf;
  zKopf := zKopf^.next;
  Dispose(zHilf)
End;

Ansonsten ist das:

Zitat:

Zitat von Macci

Etwas sauberer wäre es natürlich, bei der POP-Funktion mit Dispose den verwendeten Speicher freizugeben.

Nicht etwas sauberer, sondern unabdingbar. :zwinker:

[inherited]

Warum benutzt du nicht die tolle Fähigkeit von Delphi, ObjektOrientiert zu sein?
Erstell dir eine TStack-Klasse die eine (unterklasse) TStackElement oä hat.
Dann gibst du der Stack-Klasse die Funktionen Create, Pop: Integer, Push(a: integer), isEmpty: Boolean, evtl auch Count: integer und den TStackElements Create, read/write-property next: TStackElement sowie irgendein value. Das kann auch ein Pointer sein, das ist dann universeller einsetzbar!