[infostudents] Info 2 Blatt 8 Aufgabe 1 und 3

  • From: Guido Solbach <ich@xxxxxxxxxxxxxxxx>
  • To: infostudents@xxxxxxxxxxxxx
  • Date: Fri, 15 Jun 2007 23:33:31 +0200

Hier schon mal nen paar Aufgaben
/*
 * @author Guido Solbach
 */
public class CircularList {

    private ListElement current;

    /**
     * Erzeugt eine neue, leere Liste.
     */
    public CircularList() {
        current = null;
    }

    /**
     * Gibt an, ob die Liste leer ist.
     */
    public boolean isEmpty() {
        return current == null;
    }

    /**
     * +++NEU HINZUGEFÜGT
     * Wir überprüfen, ob das neue Element kleiner als das aktuelle Current 
ist. 
     * Nur dann wird es zum neuen current. Ansonsten setzen wir es neben das 
current.
     * Das alles geht wie auch zuvor in konstanter Zeit.
     * +++ENDE NEU HINZUGEFÜGT
     * Laufzeiten in allen Fällen O(1), da es eine feste gegebene Anzahl 
     * von Schritten gibt, um ein Element anzufügen.
     * Es gibt daher keine Abhängigkeit von n
     * Fügt ein neues Element mit Wert val ein.
     * (Das Element soll LINKS vom Element current eingefügt werden.)
     */
    public void insert(int val) {
        System.out.println("Element hinzufügen: " + val);
        if(isEmpty()){
          current = new ListElement(val);
          current.next=current;
          current.prev=current;
        } else {
                ListElement element = new ListElement(val);
                if(current.key>val){
                        element.prev = current;
                        element.next = current.next;
                        current.next.prev = element;
                        current.next = element;
                        current=element;
                } else {
                        element.prev = current.prev;
                        current.prev.next = element;
                        current.prev = element;
                        element.next = current;
                }
                
        }
    }
    
    /**
     * Liefert current zurück, da dieses 
     * immer das kleinste Element ist
     */
    public ListElement accessMin(){
        return current;
    }
    
    /*
     * Sucht das kleinste Element, löscht current und
     * setzt das kleinste Element als current
     * und gibt es zurück
     */
    public ListElement deleteMin(){
        ListElement neuesMin = null;
        ListElement hilf = null;
        if (current != null && current.next!= current){
                hilf = current.next;
                neuesMin = hilf;
        } else {
                //current ist das letzte Element oder current ist null 
                current = null;
                return null;
        }
        while(hilf!=current){
                if(hilf.key<neuesMin.key){
                        neuesMin=hilf;
                }
                hilf = hilf.next;
        }
        
                current.prev.next = current.next;
                current.next.prev = current.prev;
                current = neuesMin;
                return current; //hier ist die Aufgabe nicht eindeutig
                // Es hätte auch sein können, dass man das alte current 
                // zurück gibt. Das macht aber keinen Sinn, da das gelöschte
                // Element schon abgearbeitet ist. Und man den nächsten zur 
                //Abarbeitung haben will
   
    }

    /**
     * Laufzeit im Bestcase O(1), wenn das erste Element 
     * das Gesuchte ist. Im Average und Worst Case haben wir O(n)
     * Im Durchschnittsfall muss die halbe Liste durchlaufen werden.
     * Im schlechtesten Fall muss die ganze Liste durchsucht werden. 
     * Gibt das erste gefundene Element zurück, das den Wert val hat
     * oder "null", wenn val nicht in der Liste vorkommt.
     */
    public ListElement find(int val) {
        System.out.println("Element suchen: " + val);
        ListElement search;
        if(current!=null){
                if(current.key==val){
                        System.out.println("Gefunden!");
                        return current;
                }
                search=current.next;
                while(search!=current){
                        if(search.key==val){
                                return search;
                        } else {
                                search = search.next;
                        }
                }
                search = current;
                
        }
        return null;
    }

    /**
     * Da wir find gesondert behandeln, ist es hier 1 Schritt
     * Laufzeiten in allen Fällen O(1), da es eine feste gegebene Anzahl 
     * von Schritten gibt, um ein Element zu löschen.
     * Es gibt daher keine Abhängigkeit von n
     * Entfernt das angegebene Element aus der Liste.
     * Hinweis: Sie dürfen davon ausgehen, dass l in der Liste vorkommt!
     * (Zusammen mit "find" lässt sich dann ein Element mit gegebenem
     * Wert finden und löschen, sofern es vorkommt.)
     */
    public void delete(ListElement l) {
        System.out.println("Lösche Element: " + l.key);
        ListElement element = find(l.key);
        if(element==current){
                current = current.prev;
        }
        if(element !=null){
                if(element.next != element){
                        element.prev.next = element.next;
                        element.next.prev = element.prev;
                } else {
                        current = null;
                }
        }
        
    }

    /**
     * Laufzeiten in allen Fällen O(1), da es eine feste gegebene Anzahl 
     * von Schritten gibt, um eine Liste anzufügen.
     * Es gibt daher keine Abhängigkeit von n
     * Hängt eine andere Liste other an diese an.
     * Hinweis: Sie dürfen davon ausgehen, dass die andere Liste und
     * diese Liste disjunkt sind (also keine gemeinsamen Elemente haben)
     */
    public void merge(CircularList other) {
        System.out.println("Liste hinzufügen: " );
        if(other!=null & current != null){
                ListElement element = other.current.prev;
                ListElement tmp = current.next;
                current.next=other.current;
                tmp.prev = element;
                element.next = tmp;
                
                
        }
    }

    /**
     * Gibt diese Liste als Text aus, beginnend bei current.
     */
    public void printAsText(){
        StringBuffer buffy = new StringBuffer();
        if(current!=null){
                buffy.append(current.key);
        }
        ListElement tmp = current.next;
        while(tmp!=null && tmp != current){
                buffy.append(", ").append(tmp.key);
                tmp=tmp.next;
        }
        System.out.println(buffy.toString());
    }
    public static void main (String[]args){
        CircularList circle1 = new CircularList();
        CircularList circle2 = new CircularList();
        int[] one = {17, 5,     1, 19, 3, 8};
        int[] two = {22, 6, 13};
        fillCircle(circle1,one);
        fillCircle(circle2,two);
        ListElement element = circle1.find(17);
        circle1.printAsText();
        circle1.delete(element);
        circle1.printAsText();
        circle1.merge(circle2);
        circle1.printAsText();
        circle1.deleteMin();
        System.out.println("Deletemin");
        circle1.printAsText();
        System.out.println("min " + circle1.accessMin().key);
        circle1.deleteMin();
        System.out.println("Deletemin");
        circle1.printAsText();
        System.out.println("min " + circle1.accessMin().key);
        circle1.deleteMin();
        System.out.println("Deletemin");
        circle1.printAsText();
        System.out.println("min " + circle1.accessMin().key);
    }
    private static void fillCircle(CircularList circle , int[]arr ){
        for(int i=0;i<arr.length;i++){
                circle.insert(arr[i]);
                circle.printAsText();
        }
    }
}




class ListElement {
    int key;                // der Inhalt des Elements
    ListElement prev, next; // Zeiger auf das vorherige und nächste Element
                            // für die doppelte Verkettung
    
    /**
     * Erzeugt ein neues Listenelement mit dem Wert v
     */ 
    ListElement(int v) {
        key = v;
    }
}

Other related posts: