Entwickler-Ecke :: Thema anzeigen

PeeGee - Do 29.01.09 10:47

naa
das problem ist ich hab damit angefangen einen baum zu erstellen vom typ record

Delphi-Quelltext

1:
2:
3:
4:
5:
6:

Type
TElement = ^Element;
Element = record
left: TElement;
Data: integer;
right: TELement;

es muss aber mit zeiger geschehen ich weiß wie man den zeiger erstellt das rekursive prozeduren dazu notwendig sind aber das verständnis wie genau ich die rekursion nutze fehlt mehr
ich hab mir gedacht das ich per create button den baum erstelle mit 2 nil zeigern
dann per edit wird eine zahl eingefügt
per rekursiver prozedur wird die zahl an die richtige stelle im baum geschoben
also ein zeiger aufgestellt
der wert hinzugefügt
und 2 nil zeiger angesetzt
das hab ich auch gemacht

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:

procedure TForm1.AddItem(List: TElement; data: Integer);
var
AddElement : TElement;

begin
AddElement := List;

    {if data < AddElement^.data then
        begin
            while (AddElement^.left <> nil) and (AddElement^.left.data >= data) do
                AddElement := AddElement^.left;
            while (AddElement^.left <> nil) and (AddElement^.left.data < data) do
                New(AddElement^.left^.right);
                AddElement := AddElement^.left^.right;


            New(AddElement^.left);
            if data >= AddElement^.data then
            New(AddElement^.right);

            if data < AddElement^.data then
            begin
                AddElement^.left^.data := data;
                Listbox1.Items.Add(inttostr(Data));
            end
            else
            begin
                AddElement^.right^.data:= data;
                Listbox1.Items.Add(inttostr(Data));
            end;

            AddElement^.left^.left := nil;
            AddElement^.left^.right := nil;

        end
    else
        if data >= AddElement^.data  then
        begin
            while (AddElement^.right <> nil) and (AddElement.right^.data >= data) do
                AddElement := AddElement^.right^.left;
            while (AddElement^.right <> nil) and (AddElement.right^.data < data) do
                AddElement := AddElement^.left;

            New(AddElement^.right);
            if data < AddElement^.Data then
            New(AddElement^.left);

            if data >= AddElement^.data then
            begin
                AddElement^.right^.data := data;
                Listbox1.Items.Add(inttostr(Data));
            end
            else
            begin
                AddElement^.left^.data := data;
                Listbox1.Items.Add(inttostr(Data));
            end;

            AddElement^.right^.left := nil;
            AddElement^.right^.right := nil;
        end;}
end;

es kommt mir aber auch bisschen viel vor
ich bin die möglichkeiten durchgegangen dennoch funktioniert es nicht 100%
daher wollte ich nen ansatz haben, ob ich vllt die rekursion einfach nur falsch verstehe oder das ich einfach nur anders abfragen muss?

Moderiert von Narses: Delphi-Tags hinzugefügt
Moderiert von Narses: Code- durch Delphi-Tags ersetzt
Moderiert von Narses: Beitragsformatierung überarbeitet. Schonmal was von Satzzeichen und Groß-/Kleinschreibung gehört? :roll:

JayEff - Do 29.01.09 16:55

Hidden hat folgendes geschrieben :

Bei Klassen und records übernimmt übrigens Delphi für dich die Pointeroperationen, d.h. du kannst für left und right statt PElement auch genausogut TElement nehmen, das bereitet aufgrund von Compiler-Magic keine Probleme und referenzieren sowie dereferenzieren übernimmt der Compiler für dich, das ist vom kontext her immer eindeutig.

Meine persönliche Meinung hierzu, seit ich Bäume in ADA programmieren musste: Man sollte immer sofort erkennen, wo ein Pointer ist und wo nicht, darum habe ich auch in Ada generel die Dereferenzierung explizit vorgenommen obwohl das nicht nötig ist. Dadurch wusste ich halt auch vom Verständniss her auf anhieb was intern vorging.

Was die Handhabung eines Baumes betrifft:
Die meisten, wenn nicht alle Operationen die du auf die Elemente des Baumes anwendest, sollten rekursiv implementiert sein, da das einfach viel einfacher und übersichtlicher ist. Das große Problem an der Rekursion ist einfach dieses: Um Rekursion zu verstehen, muss man Rekursion verstehen.
Wenn du mit binären Bäumen arbeitest, schau dir auf jeden Fall die drei Traversierungsmethoden an: Preorder, Inorder, Postorder. Bei einem Binären Suchbaum erhälst du per Inorder-Traversierung btw immer eine sortierte Ausgabe.

Ich schließe mich übrigens Narses an: Du solltest dir angewöhnen, Punkte und Kommas zu setzen. Ich bin nämlich ob du's glaubst oder nicht freund ja sogar liebhaber natürlich das verstehst du sicher sofort nicht in diesem du weist schon sinne von und das meine ich ernst hochgradig so wie diesem verschachtelten sätzen aber und das betone ich explizit die machen recht schnell einfach keinen sinn mehr! :zustimm:

Ich muss aber sagen, ich finde, Bäume sind eine super Sache, die können unheimlich praktisch sein.

PeeGee - Do 29.01.09 18:08

Jaja, schon gut.
Ich war in Eile, daher wird alles klein und hintereinander geschrieben xD
Es war doch trotzdem verständlich? :D

Rekursion habe ich schon verstanden. Eine procedure, welche sich dann selber aufruft und durch den Baum geht, und das Item setzt. Ich frage ja auch noch, ob es vllt iwo schon so einen Baum gibt, der die Rekursion an dieser Stelle bestmöglichst wiedergibt. Weil warum sollte man ein Rad neu erfinden, sagt der Lehrer immer so schön.

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:

procedure TForm1.AddItem(List: TElement; data: Integer);
var
AddElement : TElement;

begin
AddElement := List;


    if data < AddElement^.data then
        begin
            while (AddElement^.left <> nil) do
                begin
                    if AddElement^.data > data
                    then
                        AddElement := AddElement^.left
                    else
                        begin
                        if AddElement^.right = nil then
                            begin
                            New(AddElement^.right);
                            AddElement^.right^.left := nil;
                            AddElement^.right^.right := nil;
                            end;
                        AddElement := AddElement^.right;
                        end;
                end;
        end
    else
        begin
            while (AddElement^.right<> nil) do
                begin
                    if AddElement^.data > data then
                        begin
                            if AddElement^.left = nil then
                                begin
                                    New(AddElement^.left);
                                    AddElement^.left^.left := nil;
                                    AddElement^.left^.right := nil;
                                end;
                                AddElement := AddElement^.left
                        end
                    else
                        AddElement := AddElement^.right;
                end;
        end;
    if data >= AddElement^.Data then
        begin
            New(AddElement^.right);
            AddElement^.right.Data := data;
            AddElement^.right^.left := nil;
            AddElement^.right^.right := nil;
            Listbox1.Items.add(inttostr(data));
        end
    else
        begin
            New(AddElement^.left);
            AddElement^.left.Data := data;
            AddElement^.left^.left := nil;
            AddElement^.left^.right := nil;
            Listbox1.Items.add(inttostr(data));
        end;
end;

hab nochma was verändert...

DaVinciFF7 - Do 29.01.09 19:53

Also wir haben in Informatik von unserem Lehrer mal einen Suchbaum vorgelegt bekommen. Wenn dir der Quelltext was bringt, dann lies ihn ;)

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:

unit Unit1;
interface
uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls, Buttons, ExtCtrls;
const leerBaum=nil;
type
TStrBaum= class(TObject)
          eintrag   :string;
          anzahl    :integer;
          links     :TStrBaum;
          rechts    :TStrBaum;
          constructor pflanzen(wort: string);
          procedure einfuegen(var wo: TStrBaum; wort: string);
          procedure ausgeben;

        end;

 TForm1 = class(TForm)
    Ausgabe: TListBox;
    Eingabe: TEdit;
    EingabeLabel: TLabel;
    EingabeBtn: TBitBtn;
    AusgabeBtn: TBitBtn;
    Memo1: TMemo;
    Button1: TButton;
    Button2: TButton;
    LabeledEdit1: TLabeledEdit;
    procedure FormCreate(Sender: TObject);
    procedure EingabeBtnClick(Sender: TObject);
    procedure AusgabeBtnClick(Sender: TObject);
    procedure EingabeKeyPress(Sender: TObject; var Key: Char);
    procedure Button1Click(Sender: TObject);
    procedure zerstueckeln(Sender: TObject);
    procedure MemoClick(Sender: TObject);
    procedure Memo1DblClick(Sender: TObject);
  private { Private-Deklarationen } public { Public-Deklarationen }
  end;

var
  Form1: TForm1;
  Baum: TStrBaum;

implementation  {$R *.DFM}

constructor TStrBaum.pflanzen(wort: string);
begin
   TObject.create;
   anzahl:=1; links:=leerBaum; rechts:=leerBaum; eintrag:=wort;
end;

procedure TStrBaum.einfuegen(var wo: TStrBaum; wort: string);
     {der Zeiger auf den Baum muss offerbar (zusätzlich)´als var-Parameter}
     {übergeben werden, da self strikt lokal ist. (Ob das elegenter geht??)}
begin
 if wo=leerBaum then wo:=TStrBaum.pflanzen(wort) {erstelle neues Blatt}
 else with wo do if wort<eintrag then
 links.einfuegen(links, wort)
      else if wort>eintrag then rechts.einfuegen(rechts, wort)
           else inc(anzahl);
end; {einfuegen}

procedure TStrBaum.ausgeben;
var zeile: string;
begin
  if assigned(self) then   {gleichwertig mit self<>leerBaum}
      begin
         links.AUSGEBEN;
         zeile:=IntToStr(anzahl);
         zeile:=copy('      '+zeile,6-length(zeile),6)+'  '+eintrag;
         Form1.Ausgabe.items.add(zeile);
         rechts.AUSGEBEN;
      end;
end;  { ausgeben }


procedure TForm1.FormCreate(Sender: TObject);
begin
   baum:=nil;    {Wichtig, da es sonst nicht möglich ist, vor dem Zugriff}
end;             {auf baum.eintrag zu prüfen, ob er nicht ins Leere geht.}

procedure TForm1.EingabeBtnClick(Sender: TObject);
begin
   if Eingabe.text<>'' then Baum.einfuegen(Baum, Eingabe.text);
   Eingabe.clear;  ActiveControl:=Eingabe;
end;

procedure TForm1.AusgabeBtnClick(Sender: TObject);
begin
  Ausgabe.clear;  Baum.ausgeben;  ActiveControl:=Eingabe;
end;

procedure TForm1.EingabeKeyPress(Sender: TObject; var Key: Char);
begin
  if key in[#13{RETURN},#32{Sapce}] then EingabeBtnClick(sender);
end;

procedure TForm1.zerstueckeln(Sender: TObject);
var i:integer;
begin
i:=1;
while i+3<length(memo1.Text) do
begin
eingabe.text:=copy(Memo1.text,i,3);
i:=i+1;
EingabeBtnClick(sender);
end;
eingabe.Text:='Eingabe';
memo1.text:='--->FERTIG<---'+
'                                                               '+
memo1.Text;
memo1.Font.Color:=clgreen;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
if memo1.text<>'' then
zerstueckeln(sender);
end;


procedure TForm1.MemoClick(Sender: TObject);
begin
memo1.font.color:=clblack;
end;


procedure TForm1.Memo1DblClick(Sender: TObject);
begin
memo1.text:='';
end;


end.

Hidden - Do 29.01.09 20:41

Hi :)

Ich hab' das mal formatiert, hatte langeweile :hair:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls, Buttons, ExtCtrls;

const
  leerBaum = nil;

type
  TStrBaum= class(TObject)
  private
    FEintrag: String;
    FAnzahl: Integer;
    FLinks: TStrBaum;
    FRechts: TStrBaum;
  public
    constructor Create(aWort: String);
    procedure Einfuegen(var aWo: TStrBaum; aWort: String);
    procedure Ausgeben;
  end;

 TForm1 = class(TForm)  //die Formularunit und die Programmlogik sollten eigentlich getrennt sein
   Ausgabe: TListBox;
   Eingabe: TEdit;
   EingabeLabel: TLabel;
   EingabeBtn: TBitBtn;
   AusgabeBtn: TBitBtn;
   Memo1: TMemo;
   Button1: TButton;
   Button2: TButton;
   LabeledEdit1: TLabeledEdit;
   procedure FormCreate(Sender: TObject);
   procedure EingabeBtnClick(Sender: TObject);
   procedure AusgabeBtnClick(Sender: TObject);
   procedure EingabeKeyPress(Sender: TObject; var Key: Char);
   procedure Button1Click(Sender: TObject);
   procedure zerstueckeln(Sender: TObject);
   procedure MemoClick(Sender: TObject);
   procedure Memo1DblClick(Sender: TObject);
  private 
    FBaum: TStrBaum;  //also hier(siehe 7 Zeilen weiter unten)
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;
  Baum: TStrBaum;  //besser als Feldvariable von Form1

implementation

{$R *.DFM}

constructor TStrBaum.Create(aWort: String);
begin
  TObject.create;  {ist das ein inherited-Aufruf? Kenne ich so bisher nicht,
                   afaik wird hier ein Rückgabewert von "Create" einfach nicht
                   abgespeichert und hinterlässt ein Speicherloch}
  inherited Create;  //so bin ich's gewohnt
  FAnzahl := 1;  //besser nur eine Anweisung pro Zeile :)
  FLinks := leerBaum;
  FRechts := leerBaum;
  FEintrag := aWort;
end;

procedure TStrBaum.Einfuegen(var aWo: TStrBaum; aWort: String);
  {der Zeiger auf den Baum muss offerbar (zusätzlich)´als var-Parameter
  übergeben werden, da self strikt lokal ist. (Ob das elegenter geht??)}  //ich würde mal tippen durch "with" kommt ihr mit eurem "self" durcheinander ;)
begin
  if aWo = leerBaum then
    aWo := TStrBaum.Create(aWort)  //neues Blatt  //Anmerkung: {..} ist für mehrzeilige Kommentare gedacht
  else begin
    if aWort < FEintrag then  //"with" ist in etwa so böse wie break;, goto; und halt; in einem ;)
      FLinks.Einfuegen(FLinks, aWort)
    else if aWort > FEintrag then
      FRechts.Einfuegen(FRechts, aWort)
    else inc(FAnzahl);  //hier blicke ich nichtmehr durch: welche Feldvariable war nun von self und welche von self.FLinks/self.FRechts? also z.B. FLinks = self.FLinks oder self.FLinks.FLinks? durch with ist hi8er beides möglich
end; {einfuegen}

procedure TStrBaum.Ausgeben;
var
  aZeile: String;
begin
  if Assigned(self) then begin  //gleichwertig mit self <> LeerBaum
    FLinks.Ausgeben;  //capslock? ;)
    aZeile := IntToStr(FAnzahl);
    aZeile := Copy('      ' + aZeile, 6 - length(aZeile), 6) + '  ' + FEintrag;  //Feldvariablen mit F kennzeichnen, Parameter mit a, sonst kann niemand wissen, wo das nun deklariert ist
    Form1.Ausgabe.items.add(aZeile);
    FRechts.Ausgeben;
  end;
end;  { ausgeben }


procedure TForm1.FormCreate(Sender: TObject);
begin
   baum:=nil;    {Wichtig, da es sonst nicht möglich ist, vor dem Zugriff
                 auf baum.eintrag zu prüfen, ob er nicht ins Leere geht.}
end;

procedure TForm1.EingabeBtnClick(Sender: TObject);
begin
  if Eingabe.text <> '' then Baum.Einfuegen(Baum, Eingabe.Text);
  Eingabe.Clear;
  ActiveControl := Eingabe;
end;

procedure TForm1.AusgabeBtnClick(Sender: TObject);
begin
  Ausgabe.clear;  //auch hier wieder besser nur eine Anweisung pro Zeile
  Baum.ausgeben;
  ActiveControl := Eingabe;
end;

procedure TForm1.EingabeKeyPress(Sender: TObject; var Key: Char);
begin
  if key in[#13{RETURN}, #32{Space}] then
    EingabeBtnClick(Sender);
end;

procedure TForm1.Zerstueckeln(Sender: TObject);
var
  i: Integer;
begin
  i := 1;
  while i + 3 < length(memo1.Text) do begin
    Eingabe.Text := Copy(Memo1.Text, i, 3);
    Inc(i);
    EingabeBtnClick(Sender);
  end;
  Eingabe.Text := 'Eingabe';
  Memo1.Text := '--->FERTIG<---' +
              '                                                               ' +
              Memo1.Text;
  Memo1.Font.Color := clGreen;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
  if Memo1.Text <> '' then
    Zerstueckeln(Sender);  //hier fehlt eindeutig ein Kommentar, was "Zerstückweln im Detail bewirkt
end;

procedure TForm1.MemoClick(Sender: TObject);
begin
  Memo1.Font.Color := clBlack;
end;

procedure TForm1.Memo1DblClick(Sender: TObject);
begin
  Memo1.Text := '';
end;

end.

E: Ups, war ja garnicht der Threadsteller :hair:

mfG,

JayEff - Mo 02.02.09 11:43

Da ich deinen letzten Post leider nicht wirklich verstanden habe, geb ich dir hier mal einfach eine Prozedur die dir in einen Binären Integer-Suchbaum einfügt ohne die Suchbaumeigenschaft zu verletzen, und die inorder-Ausgabe hab ich dir auch mal gecoded.

Ich muss dazusagen: dies ist nicht gerade objektorientiert und ich kann ausnahmsweise mal nicht garantieren, dass das sauberer code ist, aber ich finde, man kann die Grundlagen dadurch recht gut erklären, korrigiert mich, wenn ich falsch liege ;) (Dieser code kommt aus meinen ADA-Erfahrungen ;) )

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:

procedure Add(var B: PBaum; value: Integer);
begin
  if Assigned(B) then
  begin
    if value < B^.Content then
      //müssen links hinzufügen, um die Suchbaumeigenschaft zu erhalten
      if not Assigned(B^.left) then //links ist leer, also packen wir's hier rein!
      begin
        New(B^.left); //hier zuweisen, im nächsten rekursionsschritt würde
                      //das nicht gehen!
        //hier wird nun mit New Speicher reserviert, dann wird der Record befüllt.
        B^.left^.Content := value;
        B^.left^.left := nil;
        B^.left^.right := nil;
      end
      else
        Add(B^.left, value) //links ist nicht leer, also rufen wir uns mit links auf
        //und prüfen dann im nächsten rekursionsschritt, ob wir jetzt einfügen dürfen
    else //müssen rechts einfügen
      if not Assigned(B^.right) then //analog zu links ;)
      begin
        New(B^.right);
        B^.right^.Content := value;
        B^.right^.left := nil;
        B^.right^.right := nil;
      end
      else
        Add(B^.right, value);
  end
  else
  begin //dies passiert nur ganz am Anfang einmal, wenn myBaum leer ist
    New(B); //danach sollte dashier nicht mehr aufgerufen werden.
    B.Content := value;
    B.left := nil;
    B.right := nil;
  end;
end;

procedure Inorder(B: PBaum);
begin //wunderbar klassischer Inorder Baumdurchlauf :)
  if Assigned(B) then
  begin
    Inorder(B^.left);
    Form1.Label1.Caption := Form1.Label1.Caption + '-' + IntToStr(B^.content);
    Inorder(B^.right);
  end;
end;

procedure FreeBaum(var B: PBaum);
begin //wunderbar klassisches freigeben in Postorder :)
  if Assigned(B) then
  begin
    FreeBaum(B^.left);
    FreeBaum(B^.right);
    Dispose(B);
  end;
end;

Vielleicht hilft dir der Code, und dazu kann ich dir mehr Hilfe bieten als zu den anderen bisher geposteten codes :)

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!