среда, 1 августа 2012 г.

module: dynamic data structures



Подтемы
    - бинарное дерево


    Структуры данных делятся на обладающие статичной структурой и динамичной структурой.
    К данным со статичной структурой относят массив и "запись" (record). Они встроены в синтаксис Java. Статичность означает, что хотя можно менять данные в структуре данных, тем не менее нельзя менять структурные свойства структуры данных. Основное структурное свойство массива - его длина. Она неизменна.
    Динамические структуры данных (односвязный массив, двусвязный массив, бинарное дерево, стек, очередь, ...) в синтаксис языка не входят, но богато представлены в библиотеках (JDK).
    java.util.ArrayList - "динамический массив".
    java.util.LinkedList - двусвязный список.
    java.util.TreeMap - бинарное сбалансированное дерево (Красно-Черное дерево).
    ...

    "Динамический массив"
СИНТАКСИС: static import
ИДИОМА: вызов перегруженного (overloaded) метода с "обогащением аргументами по умолчанию"
ПРИНЦИП: косвенность 

    Эмуляция "динамичности" у массива.
import static java.lang.System.arraycopy;

public class DynamicArray {
    int[] data = {};

    void add(int elem) {
        add(data.length, elem);
    }

    void remove() {
        remove(data.length - 1);
    }

    void add(int index, int elem) {
        int[] tmp = new int[data.length + 1];
        arraycopy(data, 0, tmp, 0, index);
        arraycopy(data, index, tmp, index + 1, data.length - index);
        tmp[index] = elem;
        this.data = tmp;
    }

    void remove(int index) {
        int[] tmp = new int[data.length - 1];
        arraycopy(data, 0, tmp, 0, index);
        arraycopy(data, index + 1, tmp, index, data.length - index - 1);
        this.data = tmp;
    }
}
    Тестируем "динамический массив":

class DynamicArrayTest {
    public static void main(String[] args) {
        DynamicArray dynArray = new DynamicArray();
        System.out.println(Arrays.toString(dynArray.data));

        dynArray.add(10);
        dynArray.add(20);
        dynArray.add(30);
        dynArray.add(40);
        dynArray.add(50);
        System.out.println(Arrays.toString(dynArray.data));

        dynArray.remove();
        System.out.println(Arrays.toString(dynArray.data));

        dynArray.remove(2);
        System.out.println(Arrays.toString(dynArray.data));

        dynArray.add(1, 0);
        System.out.println(Arrays.toString(dynArray.data));
    }
}
>> []
>> [10, 20, 30, 40, 50]
>> [10, 20, 30, 40]
>> [10, 20, 40]
>> [10, 0, 20, 40]

    Односвязный список

    Звено:    
public class Node {
    public int value;
    public Node next;

    Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }
}

    "Ручное" создание списка (первая попытка) + итеративный перебор:
public class SingleLinkedListTest0 {
    
    public static void main(String[] args) {
        Node node0 = new Node(0, null);
        Node node1 = new Node(1, null);
        Node node2 = new Node(2, null);
        Node node3 = new Node(3, null);
        
        node0.next = node1;
        node1.next = node2;
        node2.next = node3;

        Node ref = node0;
        while (ref != null) {
            System.out.print(" " + ref.value);
            ref = ref.next;
        }
    }
}
>>  0 1 2 3

    "Ручное" создание списка (вторая попытка) + итеративный перебор:

public class SingleLinkedListTest1 {
    
    public static void main(String[] args) {
        Node node4 = new Node(3, null);
        Node node2 = new Node(2, node4);
        Node node1 = new Node(1, node2);
        Node node0 = new Node(0, node1);

        Node ref = node0;
        while (ref != null) {
            System.out.print(" " + ref.value);
            ref = ref.next;
        }
    }
}
>>  0 1 2 3

    "Ручное" создание списка (третья попытка) + итеративный перебор:

public class SingleLinkedListTest2 {
    
    public static void main(String[] args) {
        Node node0 = new Node(0, new Node(1, new Node(2, new Node(3, null))));

        Node ref = node0;
        while (ref != null) {
            System.out.print(" " + ref.value);
            ref = ref.next;
        }
    }
}
>>  0 1 2 3

ШАБЛОН: Фабричный Метод (Factory Method)

    "Ручное" создание списка (четвертая попытка) с использованием Фабричного Метода + итеративный перебор:
public class SingleLinkedListTest3 {

    public static void main(String[] args) {
        Node node0 = node(0, node(1, node(2, node(3, null))));

        Node ref = node0;
        while (ref != null) {
            System.out.print(" " + ref.value);
            ref = ref.next;
        }
    }

    public static Node node(int value, Node next) {
        return new Node(value, next);
    }
}
>>  0 1 2 3

    Итеративное создание списка + итеративный перебор:

public class SingleLinkedListTest10 {

    public static void main(String[] args) {
        Node tail = null;
        for (int k = 0; k < 10; k++) {
            tail = new Node(k, tail);
        }

        Node ref = tail;
        while (ref != null) {
            System.out.print(" " + ref.value);
            ref = ref.next;
        }
    }
}
>> 9 8 7 6 5 4 3 2 1 0
    Обратите внимание на выделенную строку - ссылка ref в левой части читается, а в правой изменяется.

    Итеративное создание списка + итеративный перебор + рекурсивный перебор:
public class SingleLinkedListTest11 {

    public static void main(String[] args) {
        Node tail = null;
        for (int k = 0; k < 10; k++) {
            tail = new Node(k, tail);
        }

        System.out.println(toStringIter(tail));
        System.out.println(toStringRec(tail));
    }

    public static String toStringIter(Node ref) {
        String result = "";
        while (ref != null) {
            result += "(" + ref.value + ")->";
            ref = ref.next;
        }
        result += "null";
        return result;
    }

    public static String toStringRec(Node ref) {
        if (ref == null) {
            return "null";
        } else {
            return "(" + ref.value + ")->" + toStringRec(ref.next);
        }
    }
}
>> (9)->(8)->(7)->(6)->(5)->(4)->(3)->(2)->(1)->(0)->null
>> (9)->(8)->(7)->(6)->(5)->(4)->(3)->(2)->(1)->(0)->null
    Примечание: в случае применения к "зацикленной" структуре
        Node node = new Node(0, null);
        node.next = node;
    Итеративный перебор - упадет, съев всю память "кучи".
    Рекурсивный перебор - упадет, съев всю память "стека".

    Итеративное создание списка в прямом порядке + итеративное создание списка в обратном порядке + рекурсивное создание списка в прямом порядке + рекурсивное создание списка в обратном порядке + итеративный перебор + рекурсивный перебор:
public class SingleLinkedListTest12 {

    public static void main(String[] args) {
        Node tailA = generateIter0(9);
        Node tailB = generateIter1(9);
        Node tail0 = generateRec0(9);
        Node tail1 = new Node(9, null); generateRec1(tail1);

        System.out.println(toStringRec(tailA));
        System.out.println(toStringRec(tailB));
        System.out.println(toStringIter(tail0));
        System.out.println(toStringIter(tail1));
    }

    public static Node generateIter0(int max) {
        Node result = null;
        for (int k = 0; k <= max; k++) {
            result = new Node(k, result);
        }
        return result;
    }

    public static Node generateIter1(int max) {
        Node tail = new Node(max, null);
        Node head = tail;
        for (int k = max; k > 0; k--) {
            head.next = new Node(k - 1, null);
            head = head.next;
        }
        return tail;
    }

    public static Node generateRec0(int value) {
        if (value >= 0) {
            return new Node(value, generateRec0(value - 1));
        } else {
            return null;
        }
    }

    public static void generateRec1(Node node) {
        if (node.value > 0) {
            node.next = new Node(node.value - 1, null);
            generateRec1(node.next);
        }
    }

    public static String toStringIter(Node ref) {
        String result = "";
        while (ref != null) {
            result += "(" + ref.value + ")->";
            ref = ref.next;
        }
        result += "null";
        return result;
    }

    public static String toStringRec(Node ref) {
        if (ref == null) {
            return "null";
        } else {
            return "(" + ref.value + ")->" + toStringRec(ref.next);
        }
    }
}
>> (9)->(8)->(7)->(6)->(5)->(4)->(3)->(2)->(1)->(0)->null
>> (9)->(8)->(7)->(6)->(5)->(4)->(3)->(2)->(1)->(0)->null
>> (9)->(8)->(7)->(6)->(5)->(4)->(3)->(2)->(1)->(0)->null
>> (9)->(8)->(7)->(6)->(5)->(4)->(3)->(2)->(1)->(0)->null



    Дополнительные методы для работы со списками:
public class CrazySingleLLUtils {

    public static Node copy(Node tail) {
        return tail == null ? null : new Node(tail.value, copy(tail.next));
    }

    public static boolean isEqual(Node t0, Node t1) {
        if (t0 != null && t1 != null) {
            return (t0.value == t1.value) && isEqual(t0.next, t1.next);
        } else {
            return t0 == t1;
        }
    }

    public static Node invert(Node tail) {
        if (tail == null || tail.next == null) {
            return tail;
        } else {
            Node result = invert(tail.next);
            Node ref = result;
            while (ref.next != null) {ref = ref.next;}
            ref.next = new Node(tail.value, null);
            return result;
        }
    }
}
Тестирующий класс:
import static CrazySingleLLUtils.*;

public class CrazySingleLLUtilsTest {

    public static void main(String[] args) {
        // toString test
        System.out.println(toString(copy(null)));
        System.out.println(toString(copy(generate(0))));
        System.out.println(toString(copy(generate(1))));
        System.out.println(toString(copy(generate(2))));
        System.out.println(toString(copy(generate(3))));
        // isEqual test
        System.out.println(isEqual(generate(3), generate(3)));
        System.out.println(isEqual(generate(3), generate(4)));
        System.out.println(isEqual(generate(3), null));
        // invert test
        System.out.println(toString(generate(3)));
        System.out.println(toString(invert(generate(3))));
    }

    public static Node generate(int value) {
        if (value >= 0) {
            return new Node(value, generate(value - 1));
        } else {
            return null;
        }
    }

    public static String toString(Node ref) {
        if (ref == null) {
            return "null";
        } else {
            return "(" + ref.value + ")->" + toString(ref.next);
        }
    }
}
>> null
>> (0)->null
>> (1)->(0)->null
>> (2)->(1)->(0)->null
>> (3)->(2)->(1)->(0)->null
>> true
>> false
>> false
>> (3)->(2)->(1)->(0)->null
>> (0)->(1)->(2)->(3)->null

    Лабораторные
    Задания лабораторных можно прочитать на этой странице.