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.

[DesWeeedert]

Hallo!

Ich habs tatsächlich auch selber geschafft, glaube ich:

Code:

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

Ist ein bisschen anders als die Lösung von Jasocul, aber sollte auch funktionieren.

Nochmal vielen Dank euch allen für die Hilfe =)

[Michael II]

Komplett absurde Aufgabe. Wer solche Aufgaben stellt sollte selbst noch einmal die Schule besuchen :-D.
Das ist etwa gleich, wie wenn eine klare Brühe serviert wird und du die Gabel zum Essen verwenden sollst.

[himitsu]

Lernen?
Querdenken und was auch mal mit unpassenderen Mitteln lösen.

[Michael II]

Zitat:

Lernen?
Querdenken und was auch mal mit unpassenderen Mitteln lösen.

Wenn ein Lehrer andere lehrt falsche Mittel zur Lösung einer Aufgabe einzusetzen, dann ist der Lerneffekt irgendwo bei -1000.

Ich nutze für mathematische Probleme (Knotentheorie, Spieltheorie u.s.w.) sehr oft eine Rekursion. Aber für eine Suche nach Listenelementen, welche via Zeiger(!) miteinander verbunden sind ist die Verwendung einer Rekursion absoluter Nonsens [keine Angst: ich schreib nicht nochmal hier rein :evil:]. Querdenken immer - aber verquer...

https://de.wikipedia.org/wiki/Rekursion

[Ghostwalker]

Zitat:

Zitat von himitsu (Beitrag 1371787)

Lernen?
Querdenken und was auch mal mit unpassenderen Mitteln lösen.

Ja, dann kommen Programme auf den Markt, bei der ein einfacher Terminkalender 3 GB Hauptspeicher und min. ein I7 benötigt wird.

Sorry, aber bevor man das Querdenken erlernt, sollte man erstmal die richtigen Lösungsansätze erlernen. Erst, wenn man damit nicht weiterkommt, kann man Querdenken. ;)

[jobo]

Mit einem Hammer kann man einen Nagel einschlagen, aber auch eine Schraube. Ein Schraubendreher eignet sich ausschlielich für die Verwendung mit Schrauben.
Manchmal darf man auch etwas neben der Spur lernen, arbeiten, experimentieren, um das beste Vorgehen wirklich im wahrsten Sinne des Wortes zu begreifen.
Das ist nicht so sehr eine Frage der Lernmethode oder vermittelten Möglichkeiten, sondern m.E. eher eine Frage des individuellen Lernverhaltens.
Am Ende lernt man vielleicht sogar noch, dass es nicht nur auf das richtige Werkzeug und passendes Material ankommt, sondern dass auch das Material verschiedene Wirkungen liefert und damit verschiedene Einsatzzwecke hat.
Die Praxis ist selten schwarz/weiß, wenn die Theorie da etwas mitgeht, finde ich das vollkommen ok.

[himitsu]

Vieles, was in der Schule gelehrt wird, hat mit der Realität selten was gemeinsam.
Klar, wäre es toll, wenn das anders sein würde, aber es kann hier auch nicht verkehrt sein, wenn man das selbe Ergebnis zu Lernzwecken mit verschiedenen Ansätzen löst.
So kann man selber sehn, was wo besser gelöst werden kann.

Möglich ist Beides, auch wenn die Rekursion hier nicht wirklich optimal ist, vorallem bei längeren Listen.

Delphi-Quellcode:

procedure Machen(VerketteteListe);
begin
  while Assigned(VerketteteListe) do begin
    MachWas(VerketteteListe);
    VerketteteListe := VerketteteListe.Nächster;
  end;
end;

procedure Machen(VerketteteListe);
begin
  if Assigned(VerketteteListe) then begin
    MachWas(VerketteteListe);
    Machen(VerketteteListe.Nächster);
  end;
end;

[DesWeeedert]

Zitat:

Zitat von Michael II (Beitrag 1371799)

Zitat:

Lernen?
Querdenken und was auch mal mit unpassenderen Mitteln lösen.

Wenn ein Lehrer andere lehrt falsche Mittel zur Lösung einer Aufgabe einzusetzen, dann ist der Lerneffekt irgendwo bei -1000.

https://de.wikipedia.org/wiki/Rekursion

Ich hätte vielleicht erwähnen sollen, dass ein zweiter Teil der Aufgabe die Frage war, ob denn die Rekursion hier sinnvoll angewendet wird.

Also ich fand die Aufgabe ganz gut, um das Prinzip der Rekursion zumindest ein erstes Mal kennenzulernen.

[jobo]

Zitat:

Zitat von DesWeeedert (Beitrag 1372184)

Zitat:

Zitat von Michael II (Beitrag 1371799)

Zitat:

Lernen?
Querdenken und was auch mal mit unpassenderen Mitteln lösen.

Wenn ein Lehrer andere lehrt falsche Mittel zur Lösung einer Aufgabe einzusetzen, dann ist der Lerneffekt irgendwo bei -1000.

https://de.wikipedia.org/wiki/Rekursion

Also ich fand die Aufgabe ganz gut, um das Prinzip der Rekursion zumindest ein erstes Mal kennenzulernen.

Tadda! Der Lerneffekt stellt sich individuell nicht aufgrund einer(!) einzig richtigen Darstellung von Methoden und Sachverhalten ein, sondern vollzieht sich gemäß individueller Präferenzen, Neigungen und Fertigkeiten.
Dafür gibt es seit langem das Konzept, den gleichen Sachverhalt in unterschiedlichen Formen zu bearbeiten.

Softwareentwicklung ist m.E. ein besonders schillerndes Gebiet, wo auch "gestandene" Fachleute kaum auf Dauer mit dem Spruch "das hab ich so gelernt" durchkommen. Wo gibt es mehr Grundsatzdiskussionen als in der Softwareentwicklung? Was heute hip oder wirklich State of the Art ist, landet morgen bei "so yesterday" und übermorgen im Papierkorb. (ob zu Recht, ist offensichtlich ein anderes Thema).

Eine Ausbildung, die auch solche Probleme spiegelt, kommt mir genau richtig vor.

[himitsu]

Zitat:

Zitat von jobo (Beitrag 1372204)

Was heute hip oder wirklich State of the Art ist, landet morgen bei "so yesterday" und übermorgen im Papierkorb.

Dank Internet und der schnellen Kommunikation ... da hab ich vor Kurzem ein nettes neumodisches Designmuster kennengelernt.
Hype Driven Development (Fefe)

Jemand behauptet etwas Cooles zu haben, alle müssen es sofort bei sich verwenden, egal ob es wirklich zu ihrem Problem passt ... es ist Neu/Cool/Genial, also muß es immer und für Alles gut sein.

[jobo]

Wenn so was auf Befehl "von oben" geschieht, dann ja, empfiehlt sich etwas Informatikunterricht auch für BWLer oder wer sonst solche Dinge entscheidet.
Es gibt ja auch den umgekehrten Fall, die bereits genannten "gestandenen Fachleute" sträuben sich gegen "Neues" (das sich bereits bewährt hat), weil sie es eben anders gelernt haben. Oder wieviel wurde hier schon geklagt über die Schwierigkeiten, neue, andere Technologien bei der IT des Kunden durch zu bekommen...
Mir fallen da 3 groß geschriebene Buchstaben ein, ein Weltunternehmen aus Deutschland. Hier vermischen sich alle diese Dinge zu einem herrlichen Durcheinander.

Hab neulich noch einen Bericht gehört von einem Buchautor, der Werbefilmer war und seine Jobkrise niedergeschrieben hat. Seine Aufgabe: Success Stories eines solchen Unternehmens vor Ort zu drehen, damit der Hype weitergeht. Die 3 Buchstaben und ihre Reihenfolge wurden explizit nicht genannt, es war aber m.E. ziemlich klar, was gemeint war.

[madas]

Zitat:

Zitat von jobo (Beitrag 1372210)

es war aber m.E. ziemlich klar, was gemeint war.

Vielleicht ein Annagramm für eine File-Extension mit der man im Delphi-Umfeld zu tun hat?

[jobo]

Zitat:

Zitat von madas (Beitrag 1372276)

Zitat:

Zitat von jobo (Beitrag 1372210)

es war aber m.E. ziemlich klar, was gemeint war.

Vielleicht ein Annagram für eine File-Extension mit der man im Delphi-Umfeld zu tun hat?

Möglich ist vieles. 3 Buchstaben solange durchtauschen, bis es einem bekannt vorkommt. Aber welche File Extension? Delphi hat ja so viele...

[madas]

Zitat:

Zitat von jobo (Beitrag 1372280)

Aber welche File Extension? Delphi hat ja so viele...

Eine die mit "P" anfängt und mit "S" aufhört. :D Auf diese könnte man dann einen Spezialfall eines Anagramm anwenden. ;)

[p80286]

Zitat:

Zitat von jobo (Beitrag 1372204)

Tadda! Der Lerneffekt stellt sich individuell nicht aufgrund einer(!) einzig richtigen Darstellung von Methoden und Sachverhalten ein, sondern vollzieht sich gemäß individueller Präferenzen, Neigungen und Fertigkeiten.
Dafür gibt es seit langem das Konzept, den gleichen Sachverhalt in unterschiedlichen Formen zu bearbeiten.

Klingt für mich wie "laß sie ruhig auf die heiße Herdplatte fassen, sie werden schon merken wie heiß das ist!"

Da die meisten Softwaredompteure inzwischen die Pubertät hinter sich gelassen haben, wäre ein Erklärung vor dem Experiment vllt. besser?

Gruß
K-H