Algorithmen und Programmierung II

Übungsblatt 7 - Musterlösung

class DVListe {

    final Element anker = new Element();

    void einfuegenNach(Element e, int wert) {
        Element neu = new Element(wert, e, e.nachf);
        e.nachf.vorg = neu;
        e.nachf = neu;
    }
    
    void loeschen(Element e) {
        if (e == anker) return;
        e.vorg.nachf = e.nachf;
        e.nachf.vorg = e.vorg;
    }
}

class Element {
    int wert;
    Element vorg, nachf;

    Element(int wert, Element vorg, Element nachf) {
        this.wert = wert;
        this.vorg = vorg;
        this.nachf = nachf;
    }

    Element() { // erzeugt Anker
        vorg = this;
        nachf = this;
    }
}

    /** precondition: a.length >= b.length */
    static void replace(char[] text, char[] a, char[] b) {
 outer: for (int i = 0; i <= text.length-a.length; i++) {
            for (int j = 0; j < a.length; j++) { // try to match pattern a at
                if (text[i+j] != a[j])           // position i
                    continue outer;
            }
            for (int j = 0; j < b.length; j++)   // match, insert b
                text[i+j] = b[j];
            int diff = a.length - b.length;
            if (diff > 0) {
                for (int j = i+a.length; j < text.length; j++)
                    text[j-diff] = text[j];      // left-shift tail
                for (int j = text.length-diff; j < text.length; j++)
                    text[j] = ' ';               // fill gap
            }
            return; // replace first occurrance only
        }
    }

    static char[] matrixCode(char[] text, int width, boolean encode) {
        char[] matrix = new char[text.length]; // consecutive rows
        int col = 0;   // coordinates in matrix
        int row = 0;
        int inc = 1;   // added to row, 1 -> down, -1 -> up
        int c = 0;     // position in crypted text
        while (c < text.length) {
            if (encode) matrix[c++] = text[row*width + col];
            else        matrix[row*width + col] = text[c++];
            row += inc;
            if (row*width + col >= text.length || row < 0) { // turn around
                inc = -inc;
                col++;
                row += inc;
                if (row*width + col >= text.length) // skip trailing empty slot
                    row--;
            }   
        }
        return matrix;
    }