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

studentaccount3

Grünschnabel
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.
 
Zurück