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!

[grenzgaenger]

Zitat:

Zitat von 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!

wieso erstellen? ist doch bei delphi schon dabei :-)

[mkinzler]

Da es eine Schulaufgabe ist, geht es dem Lehrer sicherlich darum, das die Schüler lernen, wie man soetwas implementiert und nicht wie man fertigen Code/Klassen/Komponenten benutzt

[praesident]

Zitat:

Zitat von mkinzler

Da es eine Schulaufgabe ist, geht es dem Lehrer sicherlich darum, das die Schüler lernen, wie man soetwas implementiert und nicht wie man fertigen Code/Klassen/Komponenten benutzt

genau so ist es...klappt bisher auch alles ganz gut

nur hab ich meinen Programmcode nicht ganz vollständig geschrieben, da ich davon ausgegangen war, dass in der postfix-notation maximal 2 zahlen nebeneinander stehen können...aber dem ist ja nicht so...

muss ich jetzt noch erweitern

[Macci]

@praesident:

Zeig doch bitte mal den restlichen Quelltext, wo du die Push und Pop Methoden verwendest. Würde mich persönlich mal interessieren. Freut mich natürlich, dass es klappt ;-)

@alzaimar:
Joa genau so isses. Ich hoffe du kannst mir verzeihen, dass ich diesen Code nur schnell schnell hingerotzt hab und an das Freigeben des Speichers zunächst gar nicht dachte. War halt schon spät. :angel2:

Viele Grüsse,
Macci

[praesident]

Zitat:

Zitat von Macci

@praesident:

Zeig doch bitte mal den restlichen Quelltext, wo du die Push und Pop Methoden verwendest. Würde mich persönlich mal interessieren. Freut mich natürlich, dass es klappt ;-)

@alzaimar:
Joa genau so isses. Ich hoffe du kannst mir verzeihen, dass ich diesen Code nur schnell schnell hingerotzt hab und an das Freigeben des Speichers zunächst gar nicht dachte. War halt schon spät. :angel2:

Viele Grüsse,
Macci

wenn ich dashinbekommen hab, dass mehrere zahlen nebeneinander stehen können, poste ich mal das prog...
...aber ich denke, das wird alles sehr unsauber für euch sein.

könntest du das mit dem speicher freigeben viellt. mal kurz näher erläutern?
noch etwas, was uns nicht gesagt wurde... :x

[Macci]

Zitat:

Zitat von praesident

könntest du das mit dem speicher freigeben viellt. mal kurz näher erläutern?
noch etwas, was uns nicht gesagt wurde... :x

Also Freigeben ist das Gegenteil von Reserverien (was du z.B. mit "new(zhilf)" machst). Wenn du das Element aus dem Keller holst, ist es nicht nötig, selbiges Element noch weiter im Speicher zu behalten. Deswegen gibt man diesen Speicher dann mit Dispose frei. Würde man auf dieses Freigeben verzichten, würde das Programm zwar trotzdem ganz normal funktionieren aber unter Umständen Unmengen an Speicher verbrauchen. Wenn du z.B. in deinen Keller 1 Million Elemente einlagerst, ist dein Keller ja ca. 5 MB groß (wenn ich die Defintion von TZeiger jetzt richtig im Kopf habe). Holst du anschließend diese Elemente aller wieder raus, wären aber immer noch 5 MB Müll im Hauptspeicher, was natürlich sehr hässlich ist. In Java gibt es dafür z.B. einen Garbage Collector, der diesen Müll automatisch aufsammelt, in Delphi muss man das von Hand machen (was ich übrigens besser finde, weil kein unnötiger Thread aktiv sein muss) - hier mit Dispose. Objekte dagegen müssen mit .Free freigegeben werden.

[praesident]

also ich komm leider i-wie nicht weiter...

wenn ich davon ausgehe, dass bei der postfix-notation natürlich auch mehrere zahlen nebeneinander stehen können...

...da hab ich mir gedacht, lese ich solange die zeichen aus dem stack heraus und schreibe sie in einen zweiten, bis ein operationszeichen kommt- das wird aber nicht in den 2. stack geschrieben..

danach hole ich die letzten beiden zeichen wieder aus dem 2. stack eraus, wandle sie in zahlen um und führe die entsprechende rechenoperation durch

das ergebnis schreibe ich wieder in den 2. stack

dann das ganze von vorne: werte werden von den 1. in den 2. stack geschrieben bis ein operationszeichen kommt....usw.

das problem ist, dass wenn ich ein ergebnis wieder in den 2. stack zurückgebe, dieses schnell 2-stellig wird,
dadurch entsteht widerum ein konflikt mit der char-deklaration des stacks

nun hab ich überlegt, die zeichen einfach in zahlen umzuwandeln und in den 2. stack nur zahlen vom typ double reinzuschreiben..

allerdings müsste ich ja dann auch neue pop und push prozeduren einfügen, die mit double und nicht mit char arbeiten...

habt ihr einen vorschlag, wie ich das umgehen kann?

danke für eure hilfe

[Macci]

Wieso verwendest du dann überhaupt "char" ? Ich würde an deiner Stelle eine eigene Klasse, z.B. TExpression mit der abstrakten Funktion eval() als Nachfahre von TObject anlegen. Und die Nachfahren dieser Klasse sind dann TZahl, TAdd, TSub, TMul und TDiv (ggf. noch weitere Rechenoperationen).

Dann verwendest du statt char einfach TExpression und du kannst wunderbar damit arbeiten.

PS: Benutze lieber extended statt double. Extended verwendet nämlich das native 80Bit Format deines Prozessors, während double umständlich hochgerechnet werden muss.

[alzaimar]

Zitat:

Zitat von Macci

@alzaimar:
Joa genau so isses. Ich hoffe du kannst mir verzeihen, dass ich diesen Code nur schnell schnell hingerotzt hab und an das Freigeben des Speichers zunächst gar nicht dachte. War halt schon spät. :angel2:

Ich verzeihe Dir, ausnahmsweise :mrgreen: .

Ansonsten ist das schon völlig korrekt, das mit der Idee der TExpression-Klasse. Aber hat der praesident das wirklich schon gelernt? Vielleicht reichen es ja, die Zahlen auf dem Stack zu packen. Klar ist das nicht OOP, aber für den Anfang schon ganz brauchbar.

Dann kann man ein kleines Programm schreiben, das den Stack in einer TListbox darstellt. Darunter ein Eingabefeld und ein Knopf, die Eigenschaft 'Default' ist True, damit der Knopf auf ENTER reagiert. Das ist sozusagen das Eingabefeld des UPN-Taschenrechners. Du tippst etwas ein und drückst ENTER.
Wenn der String in eine Zahl umgewandelt werden kann, dann kommt er auf den Stack.
Handelt es sich um einen Operator ('+', '-', '*', '/') dann werden die obersten beiden Zahlen vom Stack geholt und eben gerechnet. Das Ergebnis kommt wieder auf den Stack.

Das müsste doch hinzubekommen sein, oder?

[Macci]

Hab das jetzt mal für dich gemacht.

Hier der interface-Teil:

Delphi-Quellcode:

type
  TExpression = class
  public
    function eval:Extended; virtual; abstract;
  end;

  TZahl = class(TExpression)
  private
    Fzahl: Extended;
    procedure Setzahl(const Value: Extended);
  public
    constructor Create(zahl:Extended);
    function eval:Extended; override;
    property zahl:Extended read Fzahl write Setzahl;
  end;

  TAdd = class(TExpression)
  private
    FExpr1: TExpression;
    FExpr2: TExpression;
    procedure SetExpr1(const Value: TExpression);
    procedure SetExpr2(const Value: TExpression);
  public
    constructor Create(Expr1,Expr2:TExpression);
    property Expr1:TExpression read FExpr1 write SetExpr1;
    property Expr2:TExpression read FExpr2 write SetExpr2;
    function eval:Extended; override;
  end;

und hier die Implementation:

Delphi-Quellcode:

{ TZahl }

procedure TZahl.Setzahl(const Value: Extended);
begin
  Fzahl := Value;
end;

constructor TZahl.Create(zahl: Extended);
begin
  Fzahl := zahl
end;

function TZahl.eval: Extended;
begin
  result := FZahl
end;

{ TAdd }

constructor TAdd.Create(Expr1, Expr2: TExpression);
begin
 FExpr1 := Expr1;
 FExpr2 := Expr2
end;

function TAdd.eval: Extended;
begin
  result := FExpr1.eval + FExpr2.eval
end;

procedure TAdd.SetExpr1(const Value: TExpression);
begin
  FExpr1 := Value;
end;

procedure TAdd.SetExpr2(const Value: TExpression);
begin
  FExpr2 := Value;
end;

Was natürlich noch fehlt, aber ganz analog funktioniert, ist TSub, TDiv und TMul.

Um zu überprüfen, ob eine TExpression x eine TZahl ist, kannst du folgenden Code benutzen:

Delphi-Quellcode:

if x is TZahl then {.. ist eine Zahl ..}

Verwenden kannst du die Klasse ganz einfach so:

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var
  num1, num2: TZahl;
  add: TAdd;
begin
  num1:=TZahl.Create(10);
  num2:=TZahl.Create(20);
  add:=TAdd.Create(num1,num2);
  ShowMessage(FloatToStr(add.eval)); //gibt 30 aus
  add.Free;
  num1.Free;
  num2.Free
end;

Wenn du deinen Stack erstellst, weisst du natürlich noch nicht, wie die einzelnen Operationen zusammengehören, deshalb kannst du bei jeder Nicht-Zahl einfach im Create 2 nil's übergeben.
Auf deinem Stack liegen dann lauter TExpressions, die du beim Auslesen des Stacks nur noch richtig "zusammenstopfen" musst, d.h. also, die entsprechenden Properties setzen musst.
Zu guter letzt genügt EIN einziger Aufruf von eval und du hast das Ergebnis ^^

[Macci]

Hatte grad nix besseres zu tun, also hab ich dir mal so ein Ding programmiert ;-)
Kannst du gerne so oder abgeändert verwenden.

Viel Spass damit :-D
Macci

[praesident]

Zitat:

Zitat von Macci

Hab das jetzt mal für dich gemacht.

wow, danke für deine mühe!!!

aber alzaimar hat schon ganz recht TExpression haben wir noch nicht gelernt, werd mir aber mal probieren das anzulesen...

kopiere jetzt erst einmal deinen code in mein Programm...

dankee

[praesident]

Zitat:

Zitat von Macci

Hatte grad nix besseres zu tun, also hab ich dir mal so ein Ding programmiert ;-)
Kannst du gerne so oder abgeändert verwenden.

Viel Spass damit :-D
Macci

super, das ist ja noch besser...ich seh es mir gleich mal an

[praesident]

hmm, ich glaube das mit den Texpressions kann ich nicht lassen...da würde mein lehrer dann wohl doch stutzig werden

er lernt ja delphi selbst noch, und ob er das überhaupt kennt!?

ich werd wohl probieren müssen, das durch 2 stacks zu ersetzen...einen mit char und einen extended, auch wenn es ziemlich umständlich scheint

[Macci]

In welcher Klasse bist du denn?
Naja vielleicht hilft dir mein Code ja trotzdem ein bisschen, wenn du irgndwo nicht weiter weist ;-)

[praesident]

Zitat:

Zitat von Macci

In welcher Klasse bist du denn?
Naja vielleicht hilft dir mein Code ja trotzdem ein bisschen, wenn du irgndwo nicht weiter weist ;-)

öhm naja...12. Klasse, aber eben erst seit einer Woche Delphi...