Grundlagen Der Informatik / Algorithmen . - Team.FH-KL.de

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132AufgabenstellungGehen Sie bei der Bearbeitung der folgenden Teilaufgabenstellungen von denBeispiel-Implementierungen der Klassen ListNodeSL und LinkedList für einfachverkettete Listen aus, wie sie in der Vorlesung vorgestellt wurden. Insbesondere enthaltedie Klasse ListNodeSL zur Speicherung eines Elementdatums das int-Attribut key. Diezu erstellenden Methoden sollen zu der Klasse LinkedList gehören. Es dürfen nurHilfsmethoden aus der Klasse ListNodeSL verwendet werden.

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132aa) Entwerfen Sie schriftlich eine rein iterative Funktion getMinIter als Java-Methode,die den minimalen Datenwert in einer einfach verketteten Liste bestimmt.Beachten Sie, dass die Liste auch leer sein kann! In diesem Fall soll eineListEmptyException erzeugt werden, wobei Sie die entsprechende Exception-Klasseals gegeben voraussetzen können.Vervollständigen Sie die folgende Methodendeklaration:public int getMinIter () throws L i s t E m p t y E x c e p t i o n{// v a r i a b l e d e c l a r a t i o n s and program c o d e . . .}

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132aIdee:1Überprüfe, ob die Liste leer ist. Wenn ja ListEmptyException!2Merke Dir den Wert des ersten Knotens in einer Hilfsvariable.3Durchlaufe die Liste von Knoten zu Knoten bis zum Ende und überprüfe jeweils, obder aktuelle Wert kleiner als der gemerkte Wert ist. Wenn ja, merke Dir diesen Wert.4Gib den gemerkten Wert zurück.

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132aProgrammcode:public int getMinIter () throws L i s t E m p t y E x c e p t i o n{int minhelp ;// H i l f s v a r i a b l eListNodeSL current ;// d e r a k t u e l l e Knotenif ( anchor null )// Ü b e r p r ü f e n , ob L i s t ethrow new L i s t E m p t y E x c e p t i o n ( " Liste ist Leer ! " );}leercurrent anchor ;minhelp current . getKey ();// Anfangsannahme : e r s t e s// E l e m e n t i s t Minimumwhile (( current current . getNext ()) ! null ){if ( minhelp current . getKey ())minhelp current . getKey ();}////////return minhelp ;// H i l f s v a r i a b l e z u r ü c k g e b .solange es ein nächstesElement g i b tk l e i n s t e s Element i nminhelp s c h r e i b e nist

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132bb) Entwerfen Sie schriftlich eine rein rekursive Hilfsfunktion getMinRecHelp alsJava-Methode, die den minimalen Datenwert in einer einfach verketteten Listebestimmt. Diese private Hilfsfunktion wird von der öffentlichen Funktion getMinRecaufgerufen; implementieren Sie auch diese entsprechend.Beachten Sie, dass die Liste auch leer sein kann! In diesem Fall soll eineListEmptyException erzeugt werden, wobei Sie die entsprechende Exception-Klasseals gegeben voraussetzen können.Vervollständigen Sie die folgende Methodendeklarationen:public int getMinRec () throws L i s t E m p t y E x c e p t i o n{// s t a r t e t d i e r e k u r s i v e H i l f s m e t h o d e an}private int getMinRecHelp ( ListNodeSL listnode ){// V a r i a b l e n D e k l a r a t i o n e n und Programmcode . . .// r e i n r e k u r s i v e Methode}

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132bIdee:1Hilfsmethode: Überprüfe, ob die Liste leer ist.Wenn ja ListEmptyException!Wenn nicht ruf die Hilfsmethode auf und starte beim Anker-Knoten.2Rekursionsaufruf: Jeder Knoten merkt sich in einer Hilfsvariable den kleinsten Wertder Restliste.3Überprüfung: Jeder Knoten vergleicht seinen Wert mit dem kleinsten Wert derRestliste und gibt den kleineren von beiden zurück.4Rekursionsabbruch (zu Beginn): Der letzte Knoten gibt einfach nur seinen Wertzurück.

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132bProgrammcode:// Hauptmethodepublic int getMinRec () throws L i s t E m p t y E x c e p t i o n{if ( anchor null )// Ü b e r p r ü f e n , ob L i s t ethrow new L i s t E m p t y E x c e p t i o n ( " Liste ist Leer ! " );return getMinRecHelp ( anchor );leer// A u f r u f d e r H i l f s f u n k t i o n}// H i l f s m e t h o d eprivate int getMinRecHelp ( ListNodeSL current ){int minhelp ;if ( current . getNext () null )return current . getKey ();// wenn d i e s d a s l e t z t e// E l e m e n t i s t// g i b a k t u e l l e n Wert z u r ü c kminhelp getMinRecHelp ( current . getNext ());// Minimum d e r R e s t l i s t eif ( minhelp current . getKey ())//////////return minhelp ;elsereturn current . getKey ();}// H i l f s v a r i a b l ewenn i n m i n h e l p d e rk l e i n e r e Wert s t e h tgib minhelp zurücksonstg i b a k t u e l l e n Wert z u r ü c kist

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132cc) Entwerfen Sie schriftlich eine rein rekursive Hilfsfunktion printReversedRecHelpals Java-Methode, die den Inhalt einer einfach verketteten Liste rückwärts (d. h. vomletzten zum ersten Element) auf die Standardausgabe ausgibt, also den Elementwertdes Ankers zuletzt. Diese private Hilfsfunktion wird von der öffentlichen FunktionprintReversedRec aufgerufen; implementieren Sie auch diese entsprechend.Beachten Sie, dass die Liste auch leer sein kann! In diesem Fall soll nichtsausgegeben werden.Vervollständigen Sie die folgende Methodendeklarationen:public void printReversedRec (){// s t a r t e t d i e r e k u r s i v e H i l f s m e t h o d e an}private void p r i n t R e v e r s e d R e c H e l p ( ListNodeSL listnode ){// V a r i a b l e n D e k l a r a t i o n e n und Programmcode . . .// r e i n r e k u r s i v e Methode}

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132cIdee:Jedes Element, falls vorhanden, lässt zuerst die restliche Liste in umgekehrterReihenfolge ausgeben (Rekursionsaufruf), dann erst gibt es seinen Wert aus.

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132cProgrammcode:// Hauptmethodepublic void printReversedRec (){p r i n t R e v e r s e d R e c H e l p ( anchor );System . out . println ();}// H i l f s m e t h o d eprivate void p r i n t R e v e r s e d R e c H e l p ( ListNodeSL current ){// wenn e s k e i n e n Wert g i b t , t u e n i c h t s und b r e c h e abif ( current null )return ;// R e s t l i s t e r ü c k w ä r t s a u s g e b e np r i n t R e v e r s e d R e c H e l p ( current . getNext ());// zum S c h l u ß : a k t u e l l e n Wert a u s g e b e nSystem . out . print ( current . getKey () " " );}

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132dd) Entwerfen Sie schriftlich eine rein iterative Java-Methode reverseIter, welche dieReihenfolge der Elemente in einer einfach verketteten Liste umkehrt. Beachten Sie,dass dabei tatsächlich die Referenzen zwischen den Listenknoten geändert werdensollen, einfaches Umsortieren der Elementinhalte ist nicht erlaubt! DieMethodendeklaration lautet wie folgt:public void reverseIter (){// V a r i a b l e n D e k l a r a t i o n e n und Programmcode . . .}

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132dIdee (Variante 1):Man verwendet beim Durchlaufen der Liste drei Variablen um die Referenzen auf dasaktuelle Element sowie Vorgänger und Nachfolger zwischenzuspeichern.

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132dProgrammcode (Variante 1):public void reverseIter (){ListNodeSL previous , current , next ;if ( anchor null )return ;current anchor ;next current . getNext ();// k ö n n t e N u l l s e i ncurrent . setNext ( null );// t a i lwhile ( next ! null ){previous current ;current next ;next current . getNext ();current . setNext ( previous );}anchor current ;}of the r e v e r s e dlist

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132dBeispiel (Variante 1):Ausgangssituation

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132dBeispiel (Variante 1):current anchor ;next current . getNext ();current . setNext ( null );

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132dBeispiel (Variante 1):Nach erstem Schleifendurchlaufwhile ( next ! null ){previous current ;current next ;next current . getNext ();current . setNext ( previous );}

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132dBeispiel (Variante 1):Nach zweitem Schleifendurchlaufwhile ( next ! null ){previous current ;current next ;next current . getNext ();current . setNext ( previous );}

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132dBeispiel (Variante 1):Abbruch der Schleife (da next null),danachanchor current ;

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132dIdee (Variante 2):1Erzeuge eine (leere) Hilfsliste2Nimm den key-Wert des ersten Knotens der Originalliste3Füge mit diesem Wert einen neuen Knoten am Anfang der Hilfsliste hinzu4Lösche den ersten Knoten der Originalliste5Wiederhole Schritt 2-4 bis die Originalliste leer ist6Referenziere den ersten Knoten der Hilfsliste als Anker der Originalliste

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132dProgrammcode (Variante 2):public void reverseIter2 (){LinkedList listTemp new LinkedList ();try{while (! this . isEmpty ()){int x this . getFirst (). getKey ();listTemp . insertFirst ( x );this . delete4 ( x );}this . anchor listTemp . getFirst ();}catch ( Exception e ){}}

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132ee) Entwerfen Sie schriftlich eine rein rekursive Hilfsfunktion reverseRecHelp alsJava-Methode, welche die Reihenfolge der Elemente in einer einfach verketteten Listeumkehrt. Beachten Sie, dass dabei tatsächlich die Referenzen zwischen denListenknoten geändert werden sollen, einfaches Umsortieren der Elementinhalte istnicht erlaubt! Diese private Hilfsfunktion wird von der öffentlichen FunktionreverseRec aufgerufen; implementieren Sie auch diese entsprechend.Vervollständigen Sie die folgende Methodendeklarationen:public void reverseRec (){// s t a r t e t d i e r e k u r s i v e H i l f s m e t h o d e an}private void reverseRecHelp ( ListNodeSL listnode ){// V a r i a b l e n D e k l a r a t i o n e n und Programmcode . . .// r e i n r e k u r s i v e Methode}

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132eIdee:Jeder aufgerufene Knoten bekommt zusätzlich seinen Vorgänger mitgeteilt macht aus seinem Vorgänger-Knoten seinen Nachfolger gibt die umgekehrte Restliste zurück

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132eProgrammcode:// Hauptmethodepublic void reverseRec (){anchor reverseRecHelp ( anchor , null );}// H i l f s m e t h o d eprivate ListNodeSL reverseRecHelp ( ListNodeSL current , ListNode SL previous ){if ( current null )return previous ;ListNodeSL next current . getNext ();current . setNext ( previous );return reverseRecHelp ( next , current );}

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132ff) Bestimmen Sie die mittlere Zeitkomplexität für die im Skript implementiertenMethoden insertFirst, insertLast und insert zum Einfügen eines Elements ineine einfach verkettete Liste. Verwenden Sie als Maß für den Aufwand die Anzahl derwährend der Operation referenzierten („besuchten“) Knoten der ursprünglichen Listeder Länge n.

Grundlagen der Informatik / Algorithmen und DatenstrukturenAufgabe 132zu Aufgabe 132fLösung:insertFirst: cavg 1 O(1)insertLast: cavg n O(n)insert: cavg nn 11 Xi · O(n)n2i 1