Finde das Maximum einer verketteten Liste (mit rekursiver Funktion)

[DesWeeedert]

Hallo zusammen,

meine Aufgabe ist es eine rekursive Funktion zu schreiben, die in einer linear verketteten Liste die größte Zahl findet.

In meinem Programm heißt diese Funktion ZeigListMax.

Hier ist mein bisheriger Ansatz:

Code:

program FindeListMax (input, output);
{ testet die Funktion ZeigListMax }

  type
  tRefListe = ^tListe;
  tListe = record
             info : integer;
             next : tRefListe
           end;
  var
  Liste,
  MaxZeig : tRefListe;

  function ZeigListMax (inRefAnfang : tRefListe) : tRefListe;
  { bestimmt rekursiv einen Zeiger auf das Listenelement mit
    der groessten Zahl }
   
    var
    HilfszeigerEins :tRefListe;
   
    begin
    if inRefAnfang = nil then
      ZeigListMax := nil
    else
      if inRefAnfang^.next = nil then
      begin
        ZeigListMax := inRefAnfang;
      end
      else
        begin
        HilfszeigerEins := inRefAnfang;
        repeat 
          HilfszeigerEins := HilfszeigerEins^.next;
          if HilfszeigerEins^.info > inRefAnfang^.info then
          inRefAnfang := HilfszeigerEins;
          ZeigListMax := ZeigListMax(inRefAnfang);
        until HilfszeigerEins^.next =nil;
        ZeigListMax := inRefAnfang;
        end;      
  end;

  procedure LiesListe(var outListe : tRefListe);
  { Liest eine (evtl. leere) Liste ein und gibt deren
    Anfangszeiger outListe zurueck. }

    var
    Anzahl : integer;
    i : integer;
    neueZahl : integer;
    Listenanfang,
    Listenende : tRefListe;
    
    begin
    Listenanfang := nil;
    repeat
      write ('Wie viele Zahlen wollen Sie eingeben? ');
      readln (Anzahl);
    until Anzahl >= 0;
 
    write ('Bitte geben Sie ', Anzahl, ' Zahlen ein: ');

    { Liste aufbauen }
    for i := 1 to Anzahl do
    begin
      read (neueZahl);
      if Listenanfang = nil then
      begin
        new (Listenanfang);
        Listenanfang^.next := nil;
        Listenanfang^.info := neueZahl;
        Listenende := Listenanfang;
      end
      else
      begin
        new (Listenende^.next);
        Listenende := Listenende^.next;
        Listenende^.next := nil;
        Listenende^.info := neueZahl
      end  { if Liste = nil }
    end; { for }
    outListe := Listenanfang;
    writeln
  end; { LiesListe }

  begin 
  LiesListe (Liste);
  { Die zu testende Funktion wird zweimal aufgerufen, damit tatsaechlich
    ein Fehler auftritt, wenn die Liste durch den Aufruf zerstoert wird. }
  MaxZeig := ZeigListMax (Liste);
  MaxZeig := ZeigListMax (Liste);
  if MaxZeig = nil then
    writeln('Leere Eingabefolge!')
  else
    writeln ('Das Maximum ist ', MaxZeig^.info, '.')
end. { testeZeigListMax }

Das Programm funktioniert leider nur bei Listen, die bereits aufsteigend sortiert sind. In diesem Fall spuckt es bei meinen Tests immer die richtige Zahl aus.

Ich weiß leider nicht genau, woran es liegt. Ein bisschen komisch kommt mir die repeat-schleife vor, weil ja sozusagen diese repeat-schleife immer wieder die Funktion aufruft.
Ich weiß nicht genau, was das da genau passiert. Also wird die repeat-Schleife sozusagen abgebrochen, wenn innerhalb der repeat-Schleife die Funktion erneut aufgerufen wird?
Oder wie verhält sich das?

Hat vielleicht jemand einen kleinen Tipp, was verkehrt ist?


Vielen Dank, falls sich denn jemand die Mühe macht, wäre super!

LG

[SneakyBagels]

Zitat:

Ein bisschen komisch kommt mir die repeat-schleife vor, weil ja sozusagen diese repeat-schleife immer wieder die Funktion aufruft.
Ich weiß nicht genau, was das da genau passiert

Ist der Code von dir?

[himitsu]

Zitat:

Ein bisschen komisch kommt mir die repeat-schleife vor, weil ja sozusagen diese repeat-schleife immer wieder die Funktion aufruft.

Ja was ist denn der Unterschied zwischen einer rekursiven und einer iterativen Funktion, bzw. was ist das Merkmal einer Rekursion?

Nicht der innere Funktionsaufruf kommt mir komisch vor, sondern die Schleife drumrum.
Kommt einem fast so vor, als sei das ein Mischmasch aus Rekursion und Iteration.

Zuerst dachte ich das die Listendefinition sei falsch.
Das ist doch eine einfach verkettete lineare Liste ohne Unterverzweigungen?
Also wozu die Schleife?

Delphi-Quellcode:

  ZeigListMax := ZeigListMax(inRefAnfang);
until HilfszeigerEins^.next = nil;
ZeigListMax := inRefAnfang;

Delphi-Quellcode:

ZeigListMax := ...

fällt dir da was auf?
Die erste Zuweisung wird niemals verwendet und vermutlich sollte der Compiler das dir auch sagen. Also höre besser auf ihn.

PS: Den Funktionsnamen als "Ergebnis"-Variable zu verwenden ist nicht sonderlich übersichtlich.
Verwende besser

Delphi-Quellcode:

Result := ...

, welches es seit bestimmt schon über 25 Jahren gibt, auch wenn die alte Variante nicht unbedingt "falsch" ist.

[DesWeeedert]

Zitat:

Zitat von SneakyBagels (Beitrag 1371671)

Zitat:

Ein bisschen komisch kommt mir die repeat-schleife vor, weil ja sozusagen diese repeat-schleife immer wieder die Funktion aufruft.
Ich weiß nicht genau, was das da genau passiert

Ist der Code von dir?

Von mir ist nur derjenige Code, der zu der Funktion ZeigListMax gehört. Also sozusagen alles das, was Quatsch ist, ist von mir.

Der Rest ist durch die Aufgabenstellung vorgegeben. Ich solldie Funktion so einbauen, dass sie mit dem Rest funktioniert.

[DesWeeedert]

Zitat:

Zitat von himitsu (Beitrag 1371673)

Zitat:

Ein bisschen komisch kommt mir die repeat-schleife vor, weil ja sozusagen diese repeat-schleife immer wieder die Funktion aufruft.

Ja was ist denn der Unterschied zwischen einer rekursiven und einer iterativen Funktion, bzw. was ist das Merkmal einer Rekursion?

Nicht der innere Funktionsaufruf kommt mir komisch vor, sondern die Schleife drumrum.
Kommt einem fast so vor, als sei das ein Mischmasch aus Rekursion und Iteration.

Zuerst dachte ich das die Listendefinition sei falsch.
Das ist doch eine einfach verkettete lineare Liste ohne Unterverzweigungen?
Also wozu die Schleife?

Erstmal vielen Dank für deinen Input!

Vielleicht hätte ich dazu sagen sollen, dass ich absoluter Programmier-Neuling bin. Also wundert euch bitte nicht, wenn ich vielleicht etwas wirre Ansätze drin habe :D


Iterative Funktionen sind soweit ich aktuell weiß, solche Funktionen, die eine bestimmte Anweisung (oder Folgen von Anweisungen) immer wieder ausführen, bis eine festgelegte Bedingung erfüllt ist.
Also z.B. die repeat, for und while Schleifen. Kann man das so sagen?

Und bei den rekursiven Funktionen ist die Idee meines Wissens, das Problem in kleinere Häppchen zu zerteilen, auf die man dann wieder die selbe rekursive Funktion anwendet. Richtig?

So wie ich dich verstehe, ist es für meine Aufgabe nicht sinnvoll, die Konzepte der Rekursion und der Iteration zu vermischen?
Also sollte wahrscheinlich am besten gar keine repeat-Schleife dort auftauchen.

Ich werde morgen mal versuchen, ob mir was in die Richtung einfällt, ohne repeat-Schleife.

[Ghostwalker]

Eine Rekursion ist bei einer einfach verketteten Liste überhaupt nicht nötig. Hier reicht eine einfache
Schleife die die Liste durcharbeitet und den größten Wert ermittelt. Ob die Liste sortiert ist oder nicht,
ist dabei auch nicht wirklich relevant.

Pseudo-Code:

Delphi-Quellcode:

function ListMax:Integer;
var
  PWork : TReflist;

begin
  result := 0;
  pWork := PListenAnfang;
  while (pWork <> PListenEnde) do
  begin
    if (pWork^.info > result) then
     result := pWork^.info;
    pWork := pWork^.next;
  end; 
  if (PWork^.info > result) then
   result := pWork^.info;
end;

Kleiner Tip.....gibt da ein Tutorial zum Thema Zeiger und Zeigerketten :)

http://www.delphipraxis.net/112240-z...-tutorial.html

[Der schöne Günther]

Zitat:

Zitat von Ghostwalker (Beitrag 1371693)

Eine Rekursion ist bei einer einfach verketteten Liste überhaupt nicht nötig.

Das ist der Punkt den ich auch nicht verstehe.

[himitsu]

Iteration mit einer Schleife gucksich alles an

Rekursion ... die Funktion guckt den übergebenen Parameter an und ruft sich selber auf, wenn es einen Folgeknoten gibt. (xxx ist nicht unbedingt nötig, da die Funktion bereits den Eingamgsparameter prüft)


Kombinieren tut man Iteration und Rekursion oftmals, wenn man in Bäumen sucht. (Geschwister in einer Schleife und Kinder rekursiv)
Aber bei einem Baum in verketten Listen könnte man ganz gut iterativ suchen und bräuchte dafür auch keinen Stack, um sich die vorhergehenden Zwischenschritte zu speichern.

[Sherlock]

Zitat:

Zitat von Der schöne Günther (Beitrag 1371695)

Zitat:

Zitat von Ghostwalker (Beitrag 1371693)

Eine Rekursion ist bei einer einfach verketteten Liste überhaupt nicht nötig.

Das ist der Punkt den ich auch nicht verstehe.

Das Schulaufgaben nicht immer das absolut nötige wiedergeben, sollte doch nun wirklich Allgemeinwissen sein.

Sherlock

[Jasocul]

Es ist eine Aufgabe des TE. Also vermutlich Schule.
Ob es sinnvoll ist, dass mit einer einfach verketteten Liste zu machen, kann man in Frage stellen.

Ich habe die Funktion mal schnell fertig gemacht (mir war gerade danach):

Delphi-Quellcode:

function ZeigListMax (inRefAnfang : tRefListe) : tRefListe;
begin
  Result := inRefAnfang;
  if inRefAnfang <> nil then
  begin
    if inRefAnfang^.next <> nil then
    begin
      if inRefAnfang^.info >= ZeigListMax(inRefAnfang^.Next).info then
      begin
        Result := inRefAnfang;
      end
      else
      begin
        Result := ZeigListMax(inRefAnfang^.Next);
      end;
    end;
  end;
end;

Nicht hübsch, aber sollte funktionieren und ohne Schleifen.

Übrigens ist der doppelte Aufruf um Hauptprogramm so nicht erforderlich.