Collections funktionale Listen (ListNode<E>) review und problem beim clone

  • Themenstarter studentaccount3
  • Beginndatum
S

studentaccount3

Mitglied
hallo leute ich studiere informatik im 2en semester und hab die aufgabe bekommen da unten steht mein lösung:

Aufgabe Stellung:
Beim funktionalem Ansatz kann man eine Liste einfach als eine Verkettung von Knoten (z. B. vom Typ ListNode) auffassen.

Diese Datenstruktur ist selbstähnlich, da der Rest (Tail) einer Liste selbst wieder eine Liste ist. Deshalb liegt es nahe, die folgenden Funktionen in funktionaler, rekursiver Form zu entwickeln:

• boolean contains(E e): Hier wird ermittelt, ob der Wert e in der Liste vorhanden ist. Z. B. liefert der Aufruf l.contains(3) wahr für eine Liste aus int-Zahlen l = 1, 2, 3, 1.

• int countIf(E e) Diese Methode zählt, wie häug der Wert e in der Liste vorkommt. Z. B. ergibt l.countIf(1) 2.


• ListNode clone(): Diese Methode soll eine Kopie der Liste zurückgeben. Hierbei soll nur die Listenstruktur neu erzeugt werden. Die enthaltenen Elemente sollen jedoch nicht neu erzeugt werden. Hier sollen die Referenzen auf die bestehenden Elemente kopiert werden. Dies nennt man eine eache Kopie (shallow copy) der Datenstruktur.


• ListNode invert(): Liefert eine neue, umgedrehte Liste zurück. Z. B. wird für die Liste l = 1, 2, 3 die neue Liste k = 3, 2, 1 zurückgegeben. Auch hier soll nur die Struktur verändert werden, die Elemente in der Liste sollen die gleichen bleiben. Wichtig: Funktional bedeutet hier, dass Sie nur lokale Variablen nutzen, keine Variablen verändern dürfen und Schleifen nur über Rekursion erreichen können. Nutzt Ihre Lösung z. B. normale Schleifen, gibt es Punktabzug.


• Implementieren Sie einen Iterator für die Klasse **List** und testen Sie diesen mit einigen Testfällen.


**mein lösung:**



Java:
package linkedli;


import java.util.Iterator;

public class Liste<E> implements Iterable<E>{
    
    private ListNode<E> first;
    

    public Liste() {
        first = null;
    }

    public Liste(ListNode<E> head) {
        this.first = head;
    }

    public Liste(E data) {
        ListNode head = new ListNode(data);
        this.first = head;
    }

    @Override
    public Iterator<E> iterator() {
        return new LL_Iterator<>(first);
    }
 
    private static class ListNode<E> {

        private E data;
        private ListNode next;

        public ListNode() {
            this.data = null;
            this.next = null;
        }

        public ListNode(E data) {
            this.data = data;
            next = null;
        }

        public ListNode(E data, ListNode next) {
            this.data = data;
            this.next = null;
        }

        public E getData() {
            return data;
        }

        public void setData(E val) {
            this.data = val;
        }

        public ListNode getNext() {
            return next;
        }

        public void setNext(ListNode next) {
            this.next = next;
        }

        @Override
        public String toString() {
            if(data==null)
                return null;
            return data.toString();
        }
    }
    
    private class LL_Iterator<E> implements Iterator<E> {

        private ListNode<E> curr;

        public LL_Iterator(ListNode head) {
            curr = head;
        }

        @Override
        public boolean hasNext() {
            return curr != null;
        }

        @Override
        public E next() {
            if (hasNext()) {
                E data = curr.getData();
                curr = curr.getNext();
                return data;
            }
            return null;
        }

    }

    
    public ListNode<E> getHeadNode(){
        return first;
    }
    
    public ListNode<E> getLastNode(){
        return getLast(first);
    }
    
    private ListNode<E> getLast(ListNode<E> head) {
        if (head == null)
            return null;

        ListNode temp = head;
        if (temp.getNext() != null)
            temp = getLast(temp.getNext());
        
        return temp;
    }
    
  
    public void insertAtEnd(E data) {
        first = insertAtEnd(first, data);
    }

    private ListNode insertAtEnd(ListNode head, E data) {
        if (head == null)
            return new ListNode(data);
        else
            head.setNext(insertAtEnd(head.getNext(), data));
        
        return head;
    }
    
    public void insertAtFirst (E data) {
        ListNode t= new ListNode (data);
        t.setNext(first);
        first=t;   
    }

    public void printList(){
        if(first==null) {
            System.out.println("Empty");
            return;
        }   
        LL_Iterator it= new LL_Iterator(first);
        printUsingIterator(it, (E) it.next());
    }
    
    private void printUsingIterator (LL_Iterator it, E data){
        System.out.print(data+"->");
        
        if (!it.hasNext()) {
            System.out.print(it.next()+"\n");//THIS WILL PRINT NULL!!!
            return;
        }
        printUsingIterator(it, (E) it.next());
    }

    
    public int size() {
        return size(first);
    }

    private int size(ListNode head) {
        if (head == null)
            return 0;
        else
            return 1 + size(head.getNext());
    }

    public boolean contains(E data) {
        return contains(first, data);
    }

    public boolean contains(ListNode<E> head, E data) {
        if (head == null)
            return false;
      
        if ( head.getData()==null && data ==null )
            return true;
        
        else if (head.getData().equals(data))
            return true;
        
        return contains(head.getNext(), data);
    }

    public int countIf(E t) {
        return countIf(first, t);
    }

    private int countIf(ListNode<E> head, E data) {
        if(head==null)
            return 0;
        
        if (head.getData() == null && data ==null)
            return 1+ countIf(head.getNext(),data);
        
        else if ( head.getData().equals(data) )
            return 1 + countIf(head.getNext(), data);
        
        return countIf(head.getNext(), data);
    }
    /*   
    public Liste<E> depp_clone() {
        first = depp_clone(first);
        Liste<E> copy = new Liste<>(first);
        return copy;
    }

    private ListNode depp_clone(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode temp = new ListNode(head.getData());
        temp.setNext(depp_clone(head.getNext()));

        return temp;
    }
    */
    
    public Liste shallow_clone (){
        Liste<E> cloned=new Liste<>(shallow_clone(first));
        return cloned;
    }
    private ListNode shallow_clone(ListNode head) {
        if (head == null)
            return null;
        
        ListNode temp = new ListNode(head.getData());
        temp.setNext(head.getNext());  // Just copy the reference

        return temp;
    }
    
    public Liste<E> invert(){
        Liste<E> inverted=new Liste<>();
        
        inverted = invert(this.getHeadNode(),inverted);
        
        return inverted;
    }
    public Liste<E> invert(ListNode<E> head, Liste<E> x ){
        if(head==null)
            return x;
        
        x.insertAtFirst(head.getData());
        return invert(head.getNext() , x);
    }
    
    public void reset(){
        first=null;
    }
    
    public static void main(String[] args) {
        
        //tests insert
        System.out.println("original list:");
        Liste<Integer> original= new Liste <>();
        
        for (int i = 0; i < 10; i++)
            original.insertAtEnd(i);
        
        System.out.println("original ");
        original.printList();
        
        Liste<Integer> cloned = original.shallow_clone();
        System.out.println("cloned list ");
        cloned.printList();
        
        System.out.println("add 44 to the original list");
        original.insertAtEnd(44);
        
        System.out.println("the 44 shall not be in the cloned!!!!!");
        cloned.printList();
        
    }
}


**Fragen**
1. wie soll ich ohne Head bzw. objekt der klasse ListNode, alle methoden in Klasse ListNode reinschreiben? das macht mir keinen sinn.
2. Prinzipiell, habe ich was gewollt rechtig codiert (außer clone() ist immer noch problematisch)
3. beim clone() will der Professor eine flache Kopie aber gleichzeitig sagt er dass wenn der User ein Element auf der Originale Liste addiert nachdem die Liste koppiert wurde soll dieser Element in der koppierte Liste nicht auftauchen!!!. wie kann mann dass ereichen verstehe ich einfach nicht?



paar notizen:
1. das ist ein homework ich brauch kein vollständige lösung aber ich brauch nur halt ein bisschen feedback von profies wie ihr :).
2.ich bin kein deutscher daher fällt es mir schwer manch mals die Aufgaben die in Deutsche sprache gut zu verstehen daswegen bitte wenn Sie fehlern im code sehen bitte bescheid sagen.
danke im voraus.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
M Funktionale Interfaces Java Basics - Anfänger-Themen 3
S Lineare listen verkettung Java Basics - Anfänger-Themen 7
S Listen Java Basics - Anfänger-Themen 12
S Listen , Nodes am ende anängen Java Basics - Anfänger-Themen 6
P Sortieren von Listen nach Attributen Java Basics - Anfänger-Themen 3
M Java Listen Java Basics - Anfänger-Themen 4
V einfach verkettete Listen Java Basics - Anfänger-Themen 10
A PhoneBook mit verketteten listen Java Basics - Anfänger-Themen 48
F ich brauche Hilfe bei Listen Java Basics - Anfänger-Themen 13
M (Sehr großes Problem) Listen als static in anderen Klassen verwendet Java Basics - Anfänger-Themen 12
G Java Listen und Iterator Java Basics - Anfänger-Themen 2
S Erklaerung Listen Java Basics - Anfänger-Themen 27
J Implementierung Listen-ADT Java Basics - Anfänger-Themen 131
I Alle Elemente von zwei Listen vergleichen Java Basics - Anfänger-Themen 1
L Skip Listen Java Basics - Anfänger-Themen 5
L Wie testet man (selbstgeschriebene) Listen sinnvoll? Java Basics - Anfänger-Themen 2
F Problem mit Listen Java Basics - Anfänger-Themen 5
J Listen Operationen Java Basics - Anfänger-Themen 4
O Unterschied Arrays, Listen, Mengen Java Basics - Anfänger-Themen 24
J Eine Liste von Listen erstellen Java Basics - Anfänger-Themen 11
A Sortierte Listen Java Basics - Anfänger-Themen 4
L Datenstrukturen/ Listen Java Basics - Anfänger-Themen 17
A Was könnten typische Prüfungsaufgaben zum Thema lineare, verkettete Listen sein? Java Basics - Anfänger-Themen 5
L Listen und Felder Java Basics - Anfänger-Themen 2
M Fragen zum Anlegen und Benutzen von Listen Java Basics - Anfänger-Themen 9
R Arrays und Listen Java Basics - Anfänger-Themen 1
R Listen richtig implementieren Java Basics - Anfänger-Themen 3
F Multidimensionale Listen Java Basics - Anfänger-Themen 3
F Wie String in unterschiedliche Listen teilen Java Basics - Anfänger-Themen 7
R Interface Eigene Objekte in Listen sortieren mit Interface Comparable Java Basics - Anfänger-Themen 5
T Objekte in Listen vererben Java Basics - Anfänger-Themen 3
A Klassen Klassen und Listen... Java Basics - Anfänger-Themen 5
Hacer Operationen einfach verketteter Listen Java Basics - Anfänger-Themen 22
S Methoden Vergleichen von zwei Listen in der Geschwindigkeit von O(n+m) Java Basics - Anfänger-Themen 32
P Listen sortieren mit Binärbaum gibt keine Ausgabe ab 10000 Integern Java Basics - Anfänger-Themen 14
C Listen Java Basics - Anfänger-Themen 3
C Zwei Listen verbinden Java Basics - Anfänger-Themen 1
C Zahlen merken mit Hilfe von Arrays/Listen Java Basics - Anfänger-Themen 2
E Feld von verketteten Listen Java Basics - Anfänger-Themen 11
T Überprüfung einer Aufgabe zu verketteten Listen Java Basics - Anfänger-Themen 5
S Liste mit Objekten und Listen Java Basics - Anfänger-Themen 9
JarJarBigs Frage zu Listen Java Basics - Anfänger-Themen 2
N verkettete Listen Java Basics - Anfänger-Themen 4
O Listen sort-Methode Java Basics - Anfänger-Themen 1
I Listen sortieren bei mehreren Listen zu einer Java Basics - Anfänger-Themen 2
L Lineare Listen Java Basics - Anfänger-Themen 2
S Listen Objekte nach LocalDateTime sortieren Java Basics - Anfänger-Themen 2
D Methoden Listen generieren Java Basics - Anfänger-Themen 4
A Sichtbarkeit in Methoden/Listen Java Basics - Anfänger-Themen 3
M verkettete Listen Java Basics - Anfänger-Themen 1
D Klausur Vorbereitung: Listen, Rekursion, Bäume & Vererbung Java Basics - Anfänger-Themen 3
S Vergleich von Listen Java Basics - Anfänger-Themen 6
I Zwei Listen vergleichen Java Basics - Anfänger-Themen 2
M Listen erstellen mit unterschiedlichen Reihenfolgen Java Basics - Anfänger-Themen 3
I Zwei Listen vergleichen bei n:m Beziehung Java Basics - Anfänger-Themen 2
I Zwei Listen: Wenn nicht vorhanden löschen Java Basics - Anfänger-Themen 4
I Prüfen von zwei Listen Java Basics - Anfänger-Themen 1
K Interface Generics, Interfaces und Listen - ich bin verwirrt. Java Basics - Anfänger-Themen 7
L Best Practice Alle Kombinationen aus Listenelementen, Anzahl Listen unterschiedlich Java Basics - Anfänger-Themen 6
llabusch Verkette Listen - Einfach und Doppelt Java Basics - Anfänger-Themen 3
S Unsortierte Listen - Frage zur "Verkettung" Java Basics - Anfänger-Themen 1
I Zwei Listen vergleichen Java Basics - Anfänger-Themen 7
I Listen, for - Schleifen Java Basics - Anfänger-Themen 8
P Listen Size stimmt nicht Java Basics - Anfänger-Themen 5
O Objekt Listen serialisierung und deserialisieren Java Basics - Anfänger-Themen 5
L Collections Objekte in Listen speichern Java Basics - Anfänger-Themen 3
G 2 Listen kombinieren und nach abc sortieren Java Basics - Anfänger-Themen 9
D Annonyme Innere Klasse: Listen mit geradem Index ausgeben Java Basics - Anfänger-Themen 6
G Listen sortieren Java Basics - Anfänger-Themen 3
G Generic und Listen Java Basics - Anfänger-Themen 8
R SQL ähnlicher Filter für Java Listen Java Basics - Anfänger-Themen 2
Y Collections 4 Listen Java Basics - Anfänger-Themen 14
S OOP/ Listen...etc... Java Basics - Anfänger-Themen 14
E Listen Java Basics - Anfänger-Themen 2
V Methoden Verkettete Listen Index eines Elementes ausgeben Java Basics - Anfänger-Themen 10
B Listen Java Basics - Anfänger-Themen 3
B eigene klasse in listen eintragen Java Basics - Anfänger-Themen 6
B Map per Listen Java Basics - Anfänger-Themen 2
S Erfahrungswerte von schnelles durchlaufen von Listen mit 2 Werten Java Basics - Anfänger-Themen 10
Joew0815 Problem mit Listen: add() Java Basics - Anfänger-Themen 11
P Zeichenorientierte & Serialisierte Datenverarbeitung Listen Java Basics - Anfänger-Themen 8
E Listen und Generics Java Basics - Anfänger-Themen 9
L dynamisches erzeugen von array Listen Java Basics - Anfänger-Themen 7
E Listen und Duplikate Java Basics - Anfänger-Themen 2
R Hilfe bei Listen Java Basics - Anfänger-Themen 10
F Collections Liste von Listen Java Basics - Anfänger-Themen 21
A Methoden Anfängerfrage: 2 Listen Vergleichen Java Basics - Anfänger-Themen 7
walker23m C++ Listen iteratoren in Java umwandeln Java Basics - Anfänger-Themen 3
X Listen und verschiedene Methoden Java Basics - Anfänger-Themen 6
N Listen Java Basics - Anfänger-Themen 5
S Listen Klasse selbst schreiben Java Basics - Anfänger-Themen 6
propra Objekte in mehreren Listen Java Basics - Anfänger-Themen 6
M Input/Output JAXB XML Output von Objekt-Listen? Java Basics - Anfänger-Themen 2
C Programm stürzt bei größeren Listen ab Java Basics - Anfänger-Themen 13
T Listen sortieren Java Basics - Anfänger-Themen 4
X ADS Listen in JAVA Java Basics - Anfänger-Themen 2
M GUI JList - Objekte listen u. Feld anzeigen? Java Basics - Anfänger-Themen 16
B Listen umkehrung Java Basics - Anfänger-Themen 8
D Collections Verkettete Listen und Fußball... Java Basics - Anfänger-Themen 11
B Methoden Traverse Methode bei verketteten Listen Java Basics - Anfänger-Themen 3

Ähnliche Java Themen

Anzeige

Neue Themen


Oben