Δομές δεδομένων

Διομήδης Σπινέλλης
 Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Συμβολοσειρές

Συμβολοσειρές: παράδειγμα

class Book {
    public String toString() { return "Book"; }
    static public void main(String args[]) {
        var b = new Book();
        String k = "*" + b + "*";
        System.out.println(k);
        System.out.println(b);
    }
}

String: μέθοδοι κατασκευής

String()
Κατασκευάζει μια άδεια συμβολοσειρά.
String(char[] value)
Κατασκευάζει μια συμβολοσειρά από τον πίνακα value.
String(char[] value, int offset, int count)
Κατασκευάζει μια συμβολοσειρά από count στοιχεία του πίνακα value αρχίζοντας από τη θέση offset.
String(String original)
Κατασκευάζει ένα αντίγραφο συμβολοσειράς
String(StringBuffer buffer)
Κατασκευάζει μια συμβολοσειρά από ένα αντικείμενο StringBuffer

String: μέθοδοι επεξεργασίας

Οι θέσεις σε μια συμβολοσειρά αριθμούνται από το 0.
h e l l o
0 1 2 3 4
Η μη ύπαρξη θέσης συμβολίζεται με το -1.
String substring(int beginIndex)
Επιστρέφει το τμήμα που αρχίζει στη θέση beginIndex
String substring(int beginIndex, int endIndex)
Επιστρέφει το τμήμα που αρχίζει στη θέση beginIndex και τελειώνει στη θέση endIndex - 1
char charAt(int index)
Επιστρέφει το χαρακτήρα στη θέση index
String concat(String string2)
Επιστρέφει τη συμβολοσειρά ενωμένη με το string2

String: μέθοδοι ερωτήσεων

int length()
Μήκος
boolean equals(String string2)
Σύγκριση
boolean StartsWith(String string2)
Σύγκριση αρχής
boolean endsWith(String string2)
Σύγκριση τέλους
int compareTo(String string2)
Λεξικογραφική σύγκριση (απλή)
int indexOf(String string2)
Επιστρέφει τη θέση της συμβολοσειράς string2

String: μέθοδοι μετατροπής

static String valueOf(int i)
Μετατρέπει το όρισμα i σε συμβολοσειρά
static String valueOf(double d)
Μετατρέπει το όρισμα d σε συμβολοσειρά
static String valueOf(boolean b)
Μετατρέπει το όρισμα b σε συμβολοσειρά
static String valueOf(long l)
Μετατρέπει το όρισμα l σε συμβολοσειρά
static String valueOf(float f)
Μετατρέπει το όρισμα f σε συμβολοσειρά
static String valueOf(char c)
Μετατρέπει το όρισμα c σε συμβολοσειρά

Η κλάση StringBuffer

StringBuffer append(String string2)
Προσθήκη της συμβολοσειράς string2 στο τέλος
StringBuffer insert(int offset, String string2)
Προσθήκη της συμβολοσειράς string2 στη θέση offset
StringBuffer delete(int start, int end)
Διαγραφή των χαρακτήρων από τη θέση start μέχρι την end - 1
StringBuffer replace(int start, int end, String string2)
Αντικατάσταση των χαρακτήρων από τη θέση start μέχρι την end - 1 με τη συμβολοσειρά string2

Εσωτερική χρήση της StringBuffer

Η κλάση StringBuilder παρέχει τις ίδιες δυνατότητες με την StringBuffer, χωρίς όμως να παρέχει ασφάλεια σε πολυνηματική επεξεργασία.

Η κλάση StringBuilder χρησιμοποιείται και από το μεταγλωττιστή για την υλοποίηση ένωσης συμβολοσειρών. Η ακολουθία 

x = "a" + 4 + "c"
μεταγλωττίζεται εσωτερικά σε 
x = new StringBuilder().append("a").append(4).append("c").toString()

Πλαίσια συλλογών

Πλεονεκτήματα

Τα πλεονεκτήματα της υποστήριξης και του προγραμματισμού με βάση ένα πλαίσιο συλλογών είναι:

Το πλαίσιο συλλογών της Java

Το πλαίσιο συλλογών της βιβλιοθήκης της Java περιλαμβάνει:

Διεπαφές συλλογών

Υλοποιήσεις συλλογών

Διαθέσιμες υλοποιήσεις στη Java

Για τις διεπαφές των συλλογών υπάρχουν οι παρακάτω υλοποιήσεις:

Set:
HashSet, TreeSet, LinkedHashSet
SortedSet:
TreeSet
List:
ArrayList, LinkedList
Map:
HashMap, TreeMap, LinkedHashMap
SortedMap:
TreeMap

Πίνακας διεπαφών και υλοποιήσεων

  Υλοποιήσεις
ΠΚΠίνακας ΙΔΣΛ ΣΛ και ΠΚ
Διεπαφές SetHashSet   TreeSet   LinkedHashSet
SortedSet    TreeSet    
List   ArrayList   LinkedList  
Map HashMap   TreeMap   LinkedHashMap
SortedMap     TreeMap    
(Οι υλοποιήσεις που συνδιάζουν συνδεδεμένη λίστα και πίνακα κατακερματισμού επιτρέπουν την πρόσβαση των στοιχείων με τη σειρά που έγινε η εισαγωγή τους.)

Διάγραμμα UML

Η δομή των διεπαφών και κλάσεων που έχουμε εξετάσει μπορεί να παρασταθεί σε μορφή UML ως εξής.
UML diagram of Java's Collection and Maps
Σημείωση: στην πράξη η υλοποίηση της Java χρησιμοποιεί και άλλες ενδιάμεσες κλάσεις, όπως AbstractCollection, AbstractSequentialList, AbstractSet.

Collection: επεξεργασία

Η γενικευμένη διεπαφή 

Collection <E>
ορίζει μεταξύ άλλων τις παρακάτω μεθόδους (κατά περίπτωση επιστρέφουν αληθές αν η συλλογή μεταβλήθηκε):

void clear()
Αφαιρεί όλα τα αντικείμενα από τη συλλογή
boolean add(E o)
Προσθήκη στοιχείου
boolean addAll(Collection <? extends E> c)
Προσθήκη συλλογής
boolean remove(Object o)
Αφαίρεση στοιχείου
boolean removeAll(Collection <?> c)
Αφαίρεση συλλογής

Collection: ερωτήσεις

boolean contains(Object o)
Επιστρέφει αληθές αν το στοιχείο περιέχεται
boolean containsAll(Collection <?> c)
Επιστρέφει αληθές αν τα στοιχεία της συλλογής περιέχονται
Iterator <E> iterator()
Επιστρέφει έναν επαναλήπτη για διάσχιση της συλλογής
boolean isEmpty()
Επιστρέφει αληθές αν η συλλογή είναι άδεια
int size()
Επιστρέφει τον αριθμό των στοιχείων στη συλλογή

Παράδειγμα της διεπαφής Collection

import java.util.Collection;
import java.util.LinkedList;

public class CollectionTest <E> {
    static <E> void testContain(Collection <E> c, E o) {
        System.out.print("The collection " + c);
        if (c.contains(o))
            System.out.print(" contains");
        else
            System.out.print(" does not contain");

        System.out.println(" the object " + o);
    }

    public static void main(String args[]) {
        var list = new LinkedList <String>();

        list.add("Petros");
        list.add("Maria");

        testContain(list, "Maria");
        testContain(list, "John");
        testContain(list, "Petros");
        System.out.println("Number of elements = " + list.size());
    }
}

Η διεπαφή Iterator

Η διεπαφή 
Iterator <E>
υποστηρίζει τη διάσχιση και μεταβολή συλλογών. Ορίζει τις παρακάτω μεθόδους:
boolean hasNext()
Επιστρέφει αληθές αν υπάρχει επόμενο στοιχείο
Object next()
Επιστρέφει το επόμενο στοιχείο
void remove()
Διαγράφει το τελευταίο στοιχείο που επιστρέφτηκε

Η διεπαφή ListIterator

Η διεπαφή ListIterator επεκτείνει την Iterator με τις παρακάτω μεθόδους:
boolean hasPrevious()
Επιστρέφει αληθές αν υπάρχει προηγούμενο στοιχείο
Object previous()
Επιστρέφει το προηγούμενο στοιχείο
void add(Object o)
Προσθέτει ένα στοιχείο
void set(Object o)
Αντικαθιστά το τελευταίο στοιχείο που επιστρέφτηκε

Παράδειγμα της διεπαφής Iterator

import java.util.*;

public class IteratorTest {

    static void fill(Collection <String> c) {
        c.add("Kerkyra");
        c.add("Zakynthos");
        c.add("Kythira");
        c.add("Santorini");
        c.add("Dilos");
        c.add("Samos");
        c.add("Rodos");
        c.add("Kastelorizo");
    }

    static void printAll(Collection <?> c) {
        for (var i = c.iterator(); i.hasNext(); )
            System.out.print(i.next() + " ");
    }

    public static void main(String args[]) {
        var hash = new HashSet<String> ();
        var list = new LinkedList<String> ();

        fill(hash);
        fill(list);

        System.out.println("Hash contains:");
        printAll(hash);
        System.out.println("\nList contains:");
        printAll(list);
    }
}

Διάσχιση δομών με την εντολή foreach

Παραδείγματα foreach

Παράδειγμα διάσχισης συλλογής: 
static void printAll(Collection <?> c) {
    for (Object o : c)
        System.out.print(o + " ");
}
Παράδειγμα διάσχισης πίνακα: 
class Echo {
    public static void main(String args[]) {
        for (var s : args)
            System.out.print(s + " ");
        System.out.println();
    }
}

Παράδειγμα: διάσχιση της ακολουθίας Fibonacci

import java.util.Iterator;
import java.math.BigInteger;

/**
 * An Iterable interface over the Fibonacci sequence.
 * @author Diomidis Spinellis
 */
class FibonacciSequence implements Iterable<BigInteger> {

    /** The iterator over the Fibonacci sequence. */
    private class  FibonacciIterator implements Iterator<BigInteger> {
        /** Integer n-2 of the series. */
        private BigInteger n0 = null;
        /** Integer n-1 of the series. */
        private BigInteger n1 = null;

        /**
         * Return true.
         * The FibonacciSequence sequence is infinite.
         */
        public boolean hasNext() { return true; }

        /** Return the next FibonacciSequence integer. */
        public BigInteger next() {
            if (n0 == null) {
                n0 = BigInteger.ZERO;
                return n0;
            } else if (n1 == null) {
                n1 = BigInteger.ONE;
                return n1;
            } else {
                BigInteger r = n0.add(n1);
                n0 = n1;
                n1 = r;
                return r;
            }
        }

        /**
         * Remove an element.
         * Nothing to see here; move on.
         */
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    /** Return an iterator for the FibonacciSequence series. */
    public Iterator<BigInteger> iterator() {
        return new FibonacciIterator();
    }

    /** A simple test harness. */
    public static void main(String argv[]) {
        var fib = new FibonacciSequence();

        for (BigInteger i : fib)
            System.out.println(i);
    }
}
Βλέπε και το βίντεο για την εμφάνιση της ακολουθίας στη φύση (http://www.youtube.com/watch?v=kkGeOWYOFoA).

Η διεπαφή Map

Η διεπαφή 
Map <K, V>
ορίζει μια απεικόνιση από ένα κλειδί (key) K σε μια τιμή (value) V. Η διεπαφή ορίζει μεταξύ άλλων τις παρακάτω μεθόδους:
void clear()
Αφαιρεί όλα τα αντικείμενα από τη συλλογή
Object put(Object key, Object value)
Προσθήκη στοιχείου (επιστρέφει την προηγούμενη τιμή ή null)
void putAll(Map <? extends K, ? extends V> m)
Προσθήκη στοιχείων
boolean remove(Object key)
Αφαίρεση στοιχείου (επιστρέφει την προηγούμενη τιμή ή null)

Ερωτήσεις διεπαφής Map

V get(Object key)
Επιστρέφει την τιμή του στοιχείου με το κλειδί key
boolean containsKey(Object key)
Επιστρέφει αληθές αν το στοιχείο με το κλειδί key περιέχεται
boolean containsValue(Object value)
Επιστρέφει αληθές αν το στοιχείο με την τιμή value περιέχεται (αργή)
Set<K> keySet()
Επιστρέφει το σύνολο των κλειδιών
Collection<V> values()
Επιστρέφει μια συλλογή με τις αποθηκευμένες τιμές
boolean isEmpty()
Επιστρέφει αληθές αν η συλλογή είναι άδεια
int size()
Επιστρέφει τον αριθμό των στοιχείων στη συλλογή

Παράδειγμα: νομισματικές ισοτιμίες

import java.util.TreeMap;

public class FXConvert {

    private static TreeMap<String, Double> FXRate = new TreeMap<String, Double>();

    static double FXconvert(String from, String to, double value) {
        double euro = value / FXRate.get(from);
        return euro * FXRate.get(to);
    }

    public static void main(String args[]) {

        // Euro rates
        FXRate.put("USD", 1.27);
        FXRate.put("JPY", 126.0);
        FXRate.put("GBP", 0.68);
        FXRate.put("CHF", 1.57);
        FXRate.put("CAD", 1.53);
        FXRate.put("SEK", 9.03);

        System.out.println("5 SEK = " + FXconvert("SEK", "JPY", 5) + " JPY");
        System.out.println("100 GBP = " + FXconvert("GBP", "CHF", 100) + " CHF");
    }
}

Η κλάση Stack

Η κλάση 
Stack <E>
υλοποιεί τη δομή δεδομένων που ονομάζεται στοίβα (stack) με το χαρακτηριστικό τύπο πρόσβασης τελευταίο μέσα πρώτο έξω (last in first out) (LIFO). H κλάση Stack υλοποιεί τη διεπαφή Collection και ορίζει τις παρακάτω μεθόδους:
boolean empty()
Αληθές αν η στοίβα είναι άδεια
E push(E item)
Προσθέτει το αντικείμενο item στην κορυφή της στοίβας
E pop()
Αφαιρεί και επιστρέφει το αντικείμενο από την κορυφή της στοίβας
E peek()
Επιστρέφει το αντικείμενο από την κορυφή της στοίβας

οι πύργοι του Ανόι

Μπορείτε να δοκιμάστε το παιγνίδι εδώ (https://www.mindgames.com/game/Tower+of+Hanoi).

Παράδειγμα: οι πύργοι του Ανόι

import java.util.Stack;
import java.util.Iterator;
import java.util.Collection;

public class Hanoi {
    static Stack<Integer> A, B, C;

    /** Display the contents of a collection with a given name */
    static <E> void showCollection(String name, Collection <E> c) {
        System.out.print(name + ": ");
        for (E e : c)
            System.out.print(e + " ");
        System.out.println();
    }

    /** Display the hanoi towers */
    static void showConfiguration() {
        showCollection("A", A);
        showCollection("B", B);
        showCollection("C", C);
        System.out.println();
    }

    /** Move n blocks from to using tmp */
    static <E> void move(int n, Stack<E> from, Stack<E> to, Stack<E> tmp) {
        if (n == 1) {
            to.push(from.pop());
            showConfiguration();
        } else {
            move(n - 1, from, tmp, to);
            to.push(from.pop());
            showConfiguration();
            move(n - 1, tmp, to, from);
        }
    }

    public static void main(String args[]) {
        final int N = 64;
        A = new Stack<Integer>();
        B = new Stack<Integer>();
        C = new Stack<Integer>();

        for (int i = N; i > 0; i--)
            A.push(i);
        showConfiguration();
        move(N, A, C, B);
    }
}

Άσκηση: προγραμματισμός με συμβολοσειρές και συλλογές

Άσκηση 7

Μπορείτε να κατεβάσετε το αντίστοιχο αρχείο και να στείλετε τους βαθμούς σας από τους δεσμούς που βρίσκονται στη σελίδα των ασκήσεων.

Βιβλιογραφία

Περιεχόμενα