Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Algorithmus Listenarbeit
skriiva - Sa 17.04.10 21:47
Titel: Algorithmus Listenarbeit
N'abend, ich würde mal gerne Wissen wo in meinem Algorithmus der Käfer steckt. Es geht darum zu Prüfen, ob ein Wert bereits in einer Liste vorhanden ist. Es gibt dabei drei Regeln zu beachten:
1. Wenn die Liste leer ist (NIL) ist das Ergebnis 0
2. Wenn der Wert nicht vorhanden ist, dann ist das Ergebnis ebenfalls 0
3. Wenn der Wert vorhanden ist, dann ist das Ergebnis 1
Hier mein Lösungsansatz
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
| function pruefe(liste:MyList; wert:MyWert):byte;
begin
if liste = NIL then
result:=0
else
if (liste <> NIL) and (liste.Key.Zeichen <> wert) then
pruefe(liste.next, wert)
else
if(Pointer <> NIL) then
result:=1;
else
result:=0;
end; |
jfheins - Sa 17.04.10 21:58
Moderiert von 
Narses: Komplett-Zitat des letzten Beitrags entfernt.
Warum machst du ne rekursion? Iteration wäre viel naheliegender ;)
skriiva - Sa 17.04.10 22:13
Also ich wollte es rekursiv lösen auch wenn das andere näher liegt. Result ist undefiniert? Wenn die Liste zu Ende ist oder das Zeichen entspricht dem Zeichen in der Liste geht er in else über. Wenn also wirklich das Zeichen gleich ist( pointer <> nil) dann kommt Result. Mit liste.next ist das anders gemeint. Eine Liste baut sich über pointer auf. Ein Knoten besteht aus einem Schlüssel und einer Adresse. Sprich Liste.Adresse vom nächsten Knoten.
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
| function pruefe(liste:MyList; wert:MyWert):byte;
begin
if liste = NIL then
result:=0
else
if (liste <> NIL) and (liste.Key.Zeichen <> wert) then
pruefe(liste.next, wert) else
if(Pointer <> NIL) then
result:=1;
else
result:=0;
end; |
Tryer - Sa 17.04.10 22:20
Ein rekursiver Ansatz kann nur für sehr kurze Listen funktionieren, da es bei längeren zum Stacküberlauf kommmt. Der Ansatz ist also schlichtweg falsch.
Also Iterativ. Da das Ergebnis der Funktion eh gesetzt werden muss und in den meisten Fällen "0" ist, sollte Result so vorinitialisiert werden. Dann wird durchgegangen bis der Wert gefunden wurde (Break) oder das nächste Element "NIL" ist (Ende erreicht).
Zu deinem Fehler: Wenn man das Ergebnis einer Funktion nicht auswertet geht es verloren.
Zwecks besserer Übersichtlichkeit solltest Du MyList zu TMyListItem o.ä. umbenennen, schliesslich ist es selber keine Liste sondern halt nur ein Element daraus.
Grüsse, Dirk
skriiva - Sa 17.04.10 23:21
Hallo Dirk, ich verrstehe und weiß auch, dass es zum Stacküberlauf kommt. Mir ging es nur um kurze Listen und wenig Informationen um die Rekursion wieder aufzufrischen.
Ich werde es einfach mal iterativ versuchen. Vorinitialiserung habe ich nun im Code. Der Funktionsaufruf findet auch statt ein paar Zeilen weiter unten, wo die Informationen dann ausgewertet werden.
lg. skriiva
alzaimar - So 18.04.10 09:00
Pseudocode:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
| Function Prüfe (Liste, GesuchterWert) : TErgebnis;
Begin
If Liste.IstLeer Then
Result := WertIstNichtEnthalten
Else If Liste.ErstesElement.Wert = GesuchterWert Then
Result := WertIstEnthalten
Else
Result := Prüfe (Liste.ListeAbdemZweitenElement, GesuchterWert)
End; |
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!