Algorithmus Listenarbeit

skriiva · Beiträge: 17

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

markieren

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 · Beiträge: 918 Erhaltene Danke: 158 Win 10 VS 2013, VS2015

Moderiert von Narses: Komplett-Zitat des letzten Beitrags entfernt.

Warum machst du ne rekursion? Iteration wäre viel naheliegender

skriiva · Beiträge: 17

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.

markieren

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) // Result bleibt hier undefiniert
// Außerdem: ist liste.next wieder eine Liste? Wasn das für ne komische Liste?
        else

      if(Pointer <> NIL) then
       result:=1;
         else
          result:=0; 

  end;

Tryer · Beiträge: 226 Erhaltene Danke: 7

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.

markieren

Delphi-Quelltext

1:	Result := Pruefe(..)

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 · Beiträge: 17

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 · Verfasst: So 18.04.10 10:00

Pseudocode:

markieren

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;

_________________
Na denn, dann. Bis dann, denn.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme