1
UWAGI WST
PNE :
Zawarty w tym zbiorze program wykładu, ma na celu wyłącznie ułatwienie przygotowania się do zajęć oraz śledzenie
toku wykładu - nie może być traktowany jako pełna wersja wykładu, której znajomość wystarczy do zaliczenia. Również
wykład nie jest kompletnym przedstawieniem omawianych zagadnień, lecz jedynie wprowadzeniem do nich. Reszta jest
w literaturze - na szczęście dość obfitej. Przykładowe pozycje podaję poniżej.
Literatura:
1. Harris S., Ross J., Od podstaw Algorytmy.
2. Wirth N., Algorytmy + struktury danych = programy.
3. Reingold E. M., Nievergelt J., Deo N. Algorytmy kombinatoryczne.
4. Aho A. V., Hopcroft J. E., Ullman J. D. Projektowanie i analiza algorytmów komputerowych.
5. Knuth D., Sztuka programowania, sortowanie i wyszukiwanie.
6. Banachowski L, Diks K, Rytter W Algorytmy i struktury danych.
7. Cormen T H, Leiserson Ch E, Rivest R L Wprowadzenie do algorytmów
8. Sedgewick Robert Algorytmy w Javie
Literatura uzupełniająca:
1. Harel D Rzecz o istocie informatyki - Algorytmika
2. Bentley J Perełki oprogramowania
3. Sysło M M Algorytmy
Uwagi: Pozycja 1 jest najbardziej zgodna z tokiem wykładu - można ją uznać za podstawową. Pozycje 2...4 są nieco
wiekowe co może utrudniać czytanie, jednak zawierają wiele wartościowych informacji. 7 jest chyba najlepszą książką
poświęconą algorytmom w języku polskim (jej wadą jest cena i dla niektórych to ,że zawiera tylko opisy algorytmów -
bez programów). 6 jest najbardziej dostępna jednak jej skrótowość powoduje, że więcej jest myślenia niż czytania. 8 -
bardzo dobra i dostosowana do Javy.
Z uzupełniających chciałbym szczególnie polecić 1 - czyta się prawie jak kryminał.
Wszystkie problemy i wątpliwości można wyjaśnić :
- osobiście pok. 4.12 B-4 ( terminy konsultacji podaję osobno)
- telefonicznie 320-42-19
- przez pocztę elektroniczną [e-mail]
Temat 1. Budowa i wykorzystanie iteratorów.
Dostępne w Javie pętle, nie są w pełni elastyczne. Nie dają również możliwości ukrycia szczegółów związanych ze
sposobem przechodzenia przez kolejne elementy przetwarzanego zbioru. Elastyczniejsze są iteratory. W swojej książce o
wzorcach projektowych, Gamma i inni zaproponowali koncepcję iteratora, który jest bardziej uniwersalny od
standardowego , wbudowanego w Javę.
Interfejs iteratora :
package iterators;
public interface Iterator
{ public void previous();
public void next();
public void first();
public void last();
public boolean isDone();
public Object current();
}
Uwaga : nie zawsze warto budować iterator jako klasę generyczną ( parametryzowaną ), wytarczy tylko pamiętać o
rzutowaniu obiektu zwracanego przez metodę current().
Przykłady wykorzystania iteratora :
- pętla while
Iterator it = ....;
it.first(); //lub it.last()
While(!it.isDone())
{ Object object = it.current();
....
it.next(); //lub it.previous()
}
- pętla for
Iterator it = ....;
for(it.first(); !it.isDone();it.next())
2
{ Object object = it.current();
....
}
- przetwarzanie w odwrotnej kolejności
Iterator it = ....;
for(it.last(); !it.isDone();it.previous())
{ Object object = it.current();
....
}
Przykład implementacji iteratora tablicowego :
package iterators;
public class ArrayIterator implements Iterator
{ final Object[] _array;
final int _first;
final int _last;
int _current=-1;
public ArrayIterator(Object[] array, int start, int length)
{_array=array;
_first=start;
_last=start+length-1;
}
public ArrayIterator(Object[] array)
{_array=array;
_first=0;
_last=array.length-1;
}
public void first()
{ _current=_first; }
public void last()
{ _current=_last; }
public void next()
{++_current;}
public void previous()
{--_current; }
public boolean isDone()
{return _current <_first || _current> _last; }
public Object current()
{ return _array[_current];}
}
Do przetwarzania w odwrotnej kolejności ( zamiast używać previous zamiast next ) możemy zbudować iterator odwrotny
package iterators;
public class ReverseIterator implements Iterator
{ private final Iterator _it;
public ReverseIterator(Iterator it)
{ _it=it; }
public void first()
{ _it.last(); }
public void last()
{ _it.first(); }
public void next()
{_it.previous();}
public void previous()
{_it.next(); }
public boolean isDone()
{return _it.isDone(); }
public Object current()
3
{ return _it.current();}
}
Dzięki wykorzystaniu iteratora odwrotnego nie trzeba zmieniać klasy która go wykorzystuje - wystarczy przekazać jej
albo iterator bazowy albo odwrotny.
Do przetwarzania tylko wybranych ( wg. jakiegoś kryterium ) elementów wygodnie jest użyć iteratora filtrującego :
package iterators;
public class FilterIterator implements Iterator
{ private final Iterator _it;
private final Predicate _pred;
public FilterIterator(Iterator it, Predicate pred)
{ _it=it; _pred=pred; }
public void filterForwards()
{ while( !_it.isDone() && !_pred.accept(_it.current()))
_it.next();
}
public void filterBackwards()
{ while( !_it.isDone() && !_pred.accept(_it.current()))
_it.previous();
}
public void first()
{ _it.first();
filterForwards();}
public void last()
{ _it.last();
filterBackwards();}
public void next()
{_it.next();
filterForwards();}
public void previous()
{_it.previous();
filterBackwards();}
public boolean isDone()
{return _it.isDone(); }
public Object current()
{ return _it.current();}
}
Użyliśmy tutaj klasy Predicate zawierającej jedyną metodę accept() - badającą czy dany element spełnia nasze kryteria -
oczywiście trzeba ją zaimplementować w klasie definiującej elementy które przetwarzamy.
package iterators;
public interface Predicate
{ public boolean accept(Object ob); }
Przykład tworzenia i wykorzystania iteratora tablicowego - do wydruku wszystkich i wybranych elementów tablicy.
package iteracje;
import iterators.*;
public class Zawodnik
{ String nazw;
int punkty;
public Zawodnik(String n, int p)
{nazw=n; punkty=p;}
public String toString()
{ return nazw+" "+punkty;}
}
4
package iteracje;
import iterators.*;
import lists.*;
public class Zawody
{ Zawodnik[] tab=new Zawodnik[5];
public Zawody()
{ }
//do wydruku zawodników którzy mają więcej niż dwa punkty
private class ZawodnikOK implements Predicate
{ public boolean accept(Object z)
{return ((Zawodnik)z).punkty >2;}
}
public void wydruki()
{ // wypełnienie tablicy
//wydruk całej tablicy; można podać indeksy : początku i końca fragmentu tablicy
Iterator it= new ArrayIterator(tab);
it.first();
while(!it.isDone())
{Zawodnik zaw=(Zawodnik)it.current();
System.out.println(zaw);
it.next();
}
//wykorzystano wcześniej utworzony iterator tablicowy
Iterator fit= new FilterIterator(it,new ZawodnikOK());
fit.first();
while(!fit.isDone())
{Zawodnik zaw=(Zawodnik)fit.current();
System.out.println(zaw);
fit.next();
}
}
Zadania :
1) Zdefiniuj iterator tablicowy udostępniający co k-ty element tablicy, rozpoczynając od elementu o indeksie poc.
2) Dane są klasy Grupa ( tablica Studentów), Student ( nazwisko i średnia ocen ). Zdefiniuj iterator filtrujący
udostępniający tych studentów którzy mają średnią powyżej podanej wartości granicznej.
3) Zdefiniuj iterator udostępniający kolejne liczby Fibbonacciego mniejsze od podanego N. Uwaga : liczby należy
generować na bieżąco, nie należy używać tablicy do ich przechowywania.
4) Zdefiniuj iterator udostępniający kolejne liczby pierwsze mniejsze od podanego N. Uwaga : liczby należy
generować na bieżąco, nie należy używać tablicy do ich przechowywania.
Temat 2. Złożoność algorytmów.
- złożoność pamięciowa
- złożoność obliczeniowa:
- średnia
- optymistyczna
- pesymistyczna
Typowe złożoności spotykane w algorytmach :
O(1) - stały czas działania
O(log n)  logarytmiczna , czas bardzo wolno rośnie, przy podwojeniu rozmiaru zadania czas rośnie o stałą, czas
wzrośnie dwukrotnie gdy rozmiar wzrośnie do n2
O(n) - liniowa
O(n log n )  liniowo-logarytmiczna , daje ponad dwukrotny wzrost czasu przy podwojeniu rozmiaru
O(n (log n )2 ) - nieco szybszy wzrost niż liniowo-logarytmiczny
O( n2 ) - kwadratowa , podwojenie rozmiaru  czterokrotny wzrost czasu
O(2n ) - wykładnicza , kwadratowy wzrost czasu przy podwojeniu n. (również n! zalicza się do tej klasy).
5
Przykładowe wartości tych funkcji :
lg n n n lg n n (lg n )2 n2 2n
3 10 33 110 100 1024
7 100 664 4414 10000 1 i 30 zer
10 1000 9966 99317 1000000 1 i 300 zer
13 10000 132877 1765633 100000000 1 i 3000 zer
17 100000 1660964 27588016 10000000000 1 i 30000 zer
20 1000000 19931569 397267426 1000000000000 1 i 300000 zer
Uwaga : lg n oznacza log n.
2
Poniża tabelka pomoże zorientować się w wielkości tych liczb (uwaga : 1000 H" 210 )
sekundy 100 10000 100000 1000000 10000000 100000000 1000000000 10000000000
ile to jest 2 min 3 godz. 1.1 dnia 1.5 tyg. 4 mies. 3 lata 30 lat 3 wieki
Temat 3. Listy ich implementacja i przetwarzanie.
Lista: elementarna struktura danych, w której elementy są ustawione w określonej kolejności ( co nie znaczy, że są
uporządkowane ). Lista może być traktowana jako uogólnienie tablicy.
Rodzaje list :
- proste i cykliczne
- jednokierunkowe , dwukierunkowe i wielokierunkowe
- uporządkowane i nieuporządkowane
W celu uproszczenia działań można wykorzystać elementy organizacyjne : głowę (head) i ogon (tail) - wartownik .
Definicja prostego interfejsu listowego :
package lists;
import iterators.Iterable;
public interface List extends Iterable
{
// dodaj na wskazaną pozycję
public void insert(int index, Object value) throws IndexOutOfBoundsException;
// dodaj na koniec
public void add(Object value);
//usuń element ze wskazanej pozycji
public Object delete(int index) throws IndexOutOfBoundsException;
// usuń pierwsze wystąpienie wskazanej wartości
public boolean delete(Object value);
// usuń wszystkie elementy
public void clear();
// zmień element na wskazanej pozycji
public Object set(int index, Object value) throws IndexOutOfBoundsException;
// daj wartość wskazanego elementu
public Object get(int index) throws IndexOutOfBoundsException;
// znajdz
pozycję podanej wartości; -1 gdy nie ma
public int indexOf(Object value);
// czy dana wartość występuje na liście
public boolean contains(Object value);
// liczba elementów na liście
public int size();
// czy pusta lista
public boolean isEmpty();
6
}
Uwaga : tak naprawdę podstawowymi metodami są : insert, delete, get i size. Pozostałe ułatwiają po prostu korzystanie z
list i można je zrealizować wykorzystując metody podstawowe.
Ponieważ część metod można zdefiniować niezależnie od konkretnej implementacji listy, wygodnie jest zdefiniować
pomocniczą klasę AbstractList.
package lists;
import iterators.Iterator;
// zestaw metod ułatwiających implementację list
public abstract class AbstractList implements List
{
// wydruk wszystkich elementów listy
public String toString() {
StringBuffer buffer = new StringBuffer();
buffer.append('[');
if (!isEmpty()) {
Iterator i = iterator();
for (i.first(); !i.isDone(); i.next())
buffer.append(i.current()).append(", ");
buffer.setLength(buffer.length() - 2);
}
buffer.append(']');
return buffer.toString();
}
// ^ - bitowa różnica symetryczna
public int hashCode() {
int hashCode = 0;
Iterator i = iterator();
for (i.first(); !i.isDone(); i.next())
hashCode ^= i.current().hashCode();
return hashCode;
}
public boolean equals(Object object) {
return object instanceof List ? equals((List) object) : false;
}
public boolean equals(List other) {
if (other == null || size() != other.size())
return false;
else { Iterator i = iterator();
Iterator j = other.iterator();
for(i.first(),j.first();!i.isDone() && !j.isDone() &&
i.current().equals(j.current()); i.next(), j.next());
return i.isDone() && j.isDone();
}
}
}
Elementy list mogą być przechowywane w tablicy lub na liście wiązanej, można więc zaproponować dwie
implementacje list.
- implementacja tablicowa
package lists;
import iterators.*;
public class ArrayList extends AbstractList
{ // domyślna wielkość początkowa tablicy
private static final int DEFAULT_INITIAL_CAPACITY = 16;
// bieżąca wielkość tablicy
private final int _initialCapacity;
private Object[] _array;
// długość listy
private int _size;
public ArrayList()
{ this(DEFAULT_INITIAL_CAPACITY); }
7
public ArrayList(int initialCapacity) {
_initialCapacity = initialCapacity;
clear(); // tworzy pustą tablicę o podanym rozmiarze
}
public ArrayList(Object[] array) {
_initialCapacity = array.length;
clear();
System.arraycopy(array, 0, _array, 0, array.length);
_size = array.length;
}
//jeśli trzeba powiększ tablicę; value nie może być null
public void insert(int index, Object value) throws IndexOutOfBoundsException {
if(index<0 || index>_size) throw new IndexOutOfBoundException();
ensureCapacity(_size + 1);
System.arraycopy(_array, index, _array, index + 1, _size - index);
_array[index] = value;
++_size;
}
public Object delete(int index) throws IndexOutOfBoundsException {
checkOutOfBounds(index);
Object value = _array[index];
int copyFrom = index + 1;
if (copyFrom < _size)
System.arraycopy(_array, copyFrom, _array, index, _size - copyFrom);
--_size;
return value;
}
public boolean delete(Object value) {
int index = indexOf(value);
if (index != -1)
delete(index);
return index != -1;
}
public void add(Object value) {
insert(size(), value);
}
public boolean contains(Object value) {
return indexOf(value) != -1;
}
public boolean isEmpty() {
return _size == 0;
}
public void clear() {
_array = new Object[_initialCapacity];
_size = 0;
}
public Object set(int index, Object value) throws IndexOutOfBoundsException {
checkOutOfBounds(index);
Object oldValue = _array[index];
_array[index] = value;
return oldValue;
}
public Object get(int index) throws IndexOutOfBoundsException {
checkOutOfBounds(index);
return _array[index];
}
public int indexOf(Object value) {
int i =0;
while(i < _size && value.equals(_array[i]))
++i;
return i<_size ? i : -1;
}
8
public Iterator iterator() {
return new ArrayIterator(_array, 0, _size);
}
public int size() {
return _size;
}
// wykorzystywana przy wstawianiu;
private void ensureCapacity(int capacity) {
if (_array.length < capacity) {
Object[] copy = new Object[capacity + capacity / 2];
System.arraycopy(_array, 0, copy, 0, _size);
_array = copy;
}
}
private void checkOutOfBounds(int index) throws IndexOutOfBoundsException {
if (index < 0 || index >= size())
throw new IndexOutOfBoundsException();
}
}
- implementacja wykorzystująca dwukierunkową listę wiązaną z wartownikiem
package lists;
import iterators.*;
// dwukierunkowa lista wiązana z wartownikiem wskazującym na początek i koniec listy
// element listy jest zdefiniowany jako wewnętrzna prywatna klasa
public class LinkedList extends AbstractList {
private final Element _headAndTail = new Element(null); // wartownik
private int _size; // dlugość listy
public LinkedList()
{ clear();}
public void insert(int index, Object value) throws IndexOutOfBoundsException {
if(index<0 || index>_size) throw new IndexOutOfBoundException();
Element element = new Element(value);
element.attachBefore(getElement(index));
++_size;
}
public Object delete(int index) throws IndexOutOfBoundsException {
checkOutOfBounds(index);
Element element = getElement(index);
element.detach();
--_size;
return element.getValue();
}
public boolean delete(Object value) {
Element e = _headAndTail.getNext();
while (e != _headAndTail && ! value.equals(e.getValue()))
e = e.getNext();
if (e != _headAndTail) {
e.detach(); --_size; return true;
}
else return false;
}
public void add(Object value)
{ insert(size(), value); }
public boolean contains(Object value)
{ return indexOf(value) != -1; }
public boolean isEmpty()
{ return _size == 0; }
public void clear() {
9
_headAndTail.setPrevious(_headAndTail);
_headAndTail.setNext(_headAndTail);
_size = 0;
}
public Object set(int index, Object value) throws IndexOutOfBoundsException {
checkOutOfBounds(index);
Element element = getElement(index);
Object oldValue = element.getValue();
element.setValue(value);
return oldValue;
}
public Object get(int index) throws IndexOutOfBoundsException {
checkOutOfBounds(index);
return getElement(index).getValue();
}
public Iterator iterator()
{ return new ValueIterator(); }
public int indexOf(Object value) {
int index = 0;
Element e = _headAndTail.getNext();
while( e != _headAndTail && ! value.equals(e.getValue()))
{ e = e.getNext(); ++index; }
return e!=_headAndTail ? index : -1;
}
public int size() {
return _size;
}
// wybór kierunku przeszukiwania przyspiesza działanie
// zapamiętanie ostatnio odczytywanego elementu i jego indeksu daje większe
przyspieszenie
private Element getElement(int index)
{return index< _size/2 ? getElementForwards(index) : getElementBackwards(index); }
// dojście do podanej pozycji w przód
private Element getElementForwards(int index) {
Element element = _headAndTail.getNext();
for (int i = index; i > 0; --i)
element = element.getNext();
return element;
}
private Element getElementBackwards(int index) {
Element element = _headAndTail;
for (int i = _size - index; i > 0; --i)
element = element.getPrevious();
return element;
}
private void checkOutOfBounds(int index) throws IndexOutOfBoundsException {
if (index < 0 || index >= size())
throw new IndexOutOfBoundsException();
}
// pomocnicza klasa definiująca element listy
private static final class Element {
private Object _value;
private Element _previous;
private Element _next;
public Element(Object value)
{ setValue(value); }
public void setValue(Object value)
{ _value = value; }
public Object getValue()
{ return _value; }
10
public Element getPrevious()
{ return _previous;}
public void setPrevious(Element previous)
{ _previous = previous; }
public Element getNext()
{ return _next; }
public void setNext(Element next)
{ _next = next; }
// wstaw dany (this) element przed element next
public void attachBefore(Element next) {
Element previous = next.getPrevious();
setNext(next);
setPrevious(previous);
next.setPrevious(this);
previous.setNext(this);
}
public void detach() {
_previous.setNext(_next);
_next.setPrevious(_previous);
}
}
// iterator po wartościach elementów listy
// bardziej efektywny od zwykłej pętli po indeksach
private final class ValueIterator implements Iterator {
private Element _current = _headAndTail;
public void first()
{ _current = _headAndTail.getNext(); }
public void last()
{ _current = _headAndTail.getPrevious(); }
public boolean isDone()
{ return _current == _headAndTail; }
public void next()
{ _current = _current.getNext(); }
public void previous()
{ _current = _current.getPrevious(); }
public Object current() throws IndexOutOfBoundsException {
if (isDone())
throw new IndexOutOfBoundsException();
return _current.getValue();
}
}
}
Przykład wydruku elementów listy z wykorzystaniem jej iteratora (klasę Zawodnik zdefiniowano wcześniej :
package iteracje;
import iterators.*;
import lists.*;
import sorting.*;
public class Zawody
{ List lista = new ArrayList();
public Zawody(){ }
private class ZawodnikOK implements Predicate
{ public boolean accept(Object z)
{return ((Zawodnik)z).punkty >2;}
}
public void wydruki()
{ //wypełnienie elementów listy
Iterator it= lista.iterator();
it.first();
11
while(!it.isDone())
{ Zawodnik zaw=(Zawodnik)it.current();
System.out.println(zaw);
it.next();
}
System.out.println("Koniec");
}
Iterator fit= new FilterIterator(lista.iterator(),new ZawodnikOK());
fit.first();
while(!fit.isDone())
{ Zawodnik zaw=(Zawodnik)fit.current();
System.out.println(zaw);
fit.next();
}
System.out.println("Koniec");
}
}
Wybór implementacji zależy od tego jakie działania na liście wykonujemy najczęściej.
Zadania :
5) Można przyspieszyć implementację wiązaną listy przez zapamiętanie indeksu bieżącej pozycji. Zmodyfikuj
odpowiednie metody.
6) Zaimplementuj listę, która do przechowywania wartości elementów wykorzystuje jednokierunkową listę wiązaną z
wartownikiem . Porównaj prostotę i złożoność obliczeniową poszczególnych metod z wesją z wykładu.
7) Zaimplementuj listę, która do przechowywania wartości elementów wykorzystuje jednokierunkową listę wiązaną
bez wartownika . Porównaj prostotę i złożoność obliczeniową poszczególnych metod z wesją z wykładu.
8) Dane są klasy Grupa ( lista Studentów), Student ( nazwisko i średnia ocen ). W klasie Grupa zdefiniuj metody :
- wybierzDobrych , wynikiem powinna być lista studentów mających średnią powyżej podanej wartości granicznej;
- usuńZłych , efektem powinno być usunięcie z listy studentów mających średnią poniżej podanej wartości
granicznej;
- sredniaOcen, obliczającą średnia ocen wszystkich studentów
9) Jaka lista będzie najlepsza do wyznaczania LiczbySzczesliwej ( dla danych N i K ). Piraci ustawili N jeńców w koło
i zaczynając od pierwszego liczyli do K, K-tego jeńca wrzucali do morza i odliczali dalej, zabawa trwała dotąd aż
został tylko jeden jeniec - jego początkowa pozycja w kręgu jest właśnie szukaną LiczbaSzczesliwa dla danych N i
K. Przyjąć najlepszy model i napisać odpowiednie metody. Uwaga: zadanie jest również znane pod nazwą problem
Josephusa, okazuje się, że można zbudować odpowiedni wzór.
10) Rozbuduj interfejs list o operację złożenia list ( konkatenacji ). Operacja ta dołącza podaną ( parametr) listę na
koniec danej ( this) listy . Czy można ją zrealizować jako uniwersalną ( niezależną od implementacji listy) , czy
trzeba definiować oddzielnie dla list bazujących na tablicach i list wiązanych ?
Temat 4. Kolejki ich implementacja i przetwarzanie.
Kolejka - typ abstrakcyjny realizujący następujący interfejs :
package queues;
public interface Queue {
public void enqueue(Object value); //wstaw do kolejki
public Object dequeue() throws EmptyQueueException; //pobierz z kolejki
public void clear(); //usuń wszystkie elementy
public int size(); //długość kolejki
public boolean isEmpty(); // true jeśli kolejka jest pusta
}
Kolejki możemy dzielić na różne kategorie :
- nieograniczone
- ograniczone (dochodzi dodatkowa metoda sprawdzająca czy kolejka jest pełna)
Inny podział :
- zwykłe ( o kolejności pobierania z kolejki decyduje wyłacznie kolejność wstawiania)
stosuje się dwie strategie pobierania :
FIFO (First In First Out) - typowa kolejka
LIFO ( Last In First Out) - patrz niżej
12
- priorytetowe ( wcześniej są pobierane elementy o wyższym priorytecie ) - te będą omówione póz
niej.
Ze względu na złożoność operacji nie wykorzystuje się tablic do przechowywania elementów nieograniczonej kolejki
zwykłej.
Implementacja bazująca na liście wiązanej może wyglądać np. tak :
package queues;
import lists.LinkedList;
import lists.List;
/**
* zwykła kolejka FIFO bazująca na liście wiązanej
*/
public class ListFifoQueue implements Queue {
private final List _list;
public ListFifoQueue() {
this(new LinkedList());
}
public ListFifoQueue(List list)
{ _list = list; }
public void enqueue(Object value)
{ _list.add(value); }
public Object dequeue() throws EmptyQueueException {
if (isEmpty()) {
throw new EmptyQueueException();
}
return _list.delete(0);
}
public void clear()
{ _list.clear(); }
public int size()
{ return _list.size(); }
public boolean isEmpty()
{ return _list.isEmpty(); }
public String toString()
{ return _list.toString();}
}
Zadania :
11) Przedstaw bezpośrednia realizację ( bez wykorzystania klasy List ) zwykłej kolejki nieograniczonej. Do
przechowywania elementów wykorzystaj jednokierunkową listę wiązaną z wartownikiem.
12) Ograniczoną kolejkę zwykłą bazującą na tablicy można efektywnie ( czyli unikając kopiowania dużych porcji
danych) zaimplementować w sposób bezpośredni ( bez wykorzystania klasy List) . Zdefiniuj odpowiednią klasę np.
ArrayFifoQueue.Złożoność wszystkich operacji powinna być stała - O(1).
Temat 5. Stosy ich implementacja i przetwarzanie.
Stos jest typem abstrakcyjnym realizującym następujący intefejs :
package stacks;
import queues.Queue;
public interface Stack extends Queue {
public void push(Object value); // odłóż na stos
public Object pop() throws EmptyStackException; //pobierz ze stosu
public Object peek() throws EmptyStackException; //odczytaj ( nieniszcząco ) ze stosu
public void clear(); //czyść stos
public int size(); // wysokość stosu
public boolean isEmpty(); //true jeśli stos jest pusty
}
13
Stos może być traktowany jako zwykła kolejka ze strategią obsługi LIFO. Podobnie jak kolejki możemy podzielić stosy
na nieograniczone i ograniczone.
Przykładowa implementacja stosu z wykorzystaniem listy wiązanej i wskazaniem, że stos jest rodzajem kolejki.
package stacks;
import lists.LinkedList;
import lists.List;
import queues.EmptyQueueException;
public class ListStack implements Stack {
private final List _list = new LinkedList();
public void push(Object value)
{ _list.add(value);}
public Object pop() throws EmptyStackException {
if (isEmpty()) {
throw new EmptyStackException();
}
return _list.delete(_list.size() - 1);
}
public Object peek() throws EmptyStackException {
Object result = pop();
push(result);
return result;
}
public void enqueue(Object value)
{ push(value); }
public Object dequeue() throws EmptyQueueException {
try {
return pop();
} catch (EmptyStackException e) {
throw new EmptyQueueException();
}
}
public void clear()
{ _list.clear(); }
public int size()
{ return _list.size(); }
public boolean isEmpty()
{ return _list.isEmpty(); }
}
Ponieważ stos ( szczególnie ograniczony ) może mieć efektywną implementację tablicową, może być celowe zastąpieniem
bezpośredniego tworzenia listy odpowiednim konstruktorem, co pozwoli użytkownikowi wybierać rodzaj stosu.
Jako przykład wykorzystania kolejki i stosu podaję kalkulator obliczający wartość wyrażenia zapisanego w notacji ONP
( odwrotna notacja polska, notacja postfiksowa). Wyrażenie jest podane jako kolejka wartości i operatorów.
package calculate;
import java.io.*;
import lists.*;
import queues.*;
import stacks.*;
public class calculate
{ Analyzer analyzer= new Analyzer();
void evaluate() throws IOException
{ //przekształcenie napisu zawierającego postać nawiasową na kolejkę reprezentującą ONP
Queue onp=analyzer.analyze();
//kontrolny wydruk ONP
System.out.println(onp.toString());
Stack st=new ListStack();
Object el;
while(!onp.isEmpty())
{ el=onp.dequeue();
14
if(el instanceof Double)
st.push(el);
else { double right=(Double)st.pop(),left=(Double)st.pop();
switch((Character)el)
{ case '+' : st.push(left+right); break;
case '-' : st.push(left-right); break;
case '*' : st.push(left*right); break;
case '/' : st.push(left/right); break;
}
}
}
System.out.println((Double)st.pop());
}
}
Do otrzymania zapisu w ONP można wykorzystać nieco zmodyfikowany kalkulator z poprzedniego semestru.
package calculate;
import java.io.*;
import queues.*;
public class Analyzer
{StreamTokenizer wej= new StreamTokenizer(new BufferedReader(new
InputStreamReader(System.in)));
Queue onp = new ListFifoQueue();
Queue analyze() throws IOException
{ // ustawiamy analizator tak aby nowa linia (EOL) '/' i '-' były traktowane jako
samodzielne tokeny
// pod pojęciem liczby rozumiemy liczbę bez znaku
wej.eolIsSignificant(true);
wej.ordinaryChar('/');
wej.ordinaryChar('-');
System.out.println(" Wprowadz wyrażenie ");
wej.nextToken();
// każda metoda startuje z wczytanym piewrszym tokenem
expression();
return onp;
}
void expression()throws IOException
{ int oper=wej.ttype;
if(oper!='+' && oper!='-') // liczba lub wyrazenie w () - czyli skladnik
{term(); oper=wej.ttype;}
else onp.enqueue(new Double(0.0));
while(oper=='+' || oper=='-')
{ wej.nextToken();
term();
onp.enqueue(new Character((char)oper));
oper=wej.ttype;
}
}
void term() throws IOException
{factor();
int oper=wej.ttype;
while(oper=='*' ||oper=='/')
{ wej.nextToken();
factor();
onp.enqueue(new Character((char)oper));
oper=wej.ttype;
}
}
void factor()throws IOException
{ if(wej.ttype==wej.TT_NUMBER) onp.enqueue(new Double(wej.nval));
// jeśli nie liczba to musi być wyrażenie w nawiasach
else {wej.nextToken(); expression();}
wej.nextToken();
}
}
Zadania :
15
13) Przedstaw bezpośrednia realizację ( bez wykorzystania klasy List ) stosu nieograniczonego. Do przechowywania
elementów wykorzystaj jednokierunkową listę wiązaną bez wartownika.
14) Przedstaw bezpośrednia realizację ( bez wykorzystania klasy List ) stosu ograniczonego. Do przechowywania
elementów wykorzystaj tablicę.
15) Innym rodzajem stosu ograniczonego jest stos tonący. Jeśli na stosie jest już MAKS elementów, to dołożenie
następnego powoduje utratę elementu leżącego na samym dnie stosu. Jaką inną nazwę ma taka struktura ? Gdzie jest
wykorzystywana ? Zaimplementuj stos tonący. Jaką strukturę danych wykorzystasz do przechowywania elementów.
16) Veloso's Traversable Stack jest to stos, który poza zwykłymi operacjami ma możliwość nieniszczącego odczytu z
pozycji wskazywanej przez kursor (peek). Kursor można ustawić na wierzchołek stosu (top) i przesuwać o jedną
pozycję w dół stosu (down - potrzebna jest sygnalizacja osiągnięcia dna stosu ). Normalne operacje (push i pop )
automatycznie ustawiają kursor na wierzchołek. Zaimplementuj VTS jako rozszerzenie zwykłego stosu.
Temat 6. Algorytmy sortowania.
Porządkowanie : algorytmy , złożoność algorytmów ( czasowa i pamięciowa), poprawność realizacji algorytmu
( niezmienniki i zbieżniki ).
Istnieje wiele różnych algorytmów sortowania. Aby móc je porównywać należy ustalić własności (kryteria ) według
których będziemy to robić. Najważniejsze z nich to:
- stopień skomplikowania algorytmu
- szybkość działania (złożoność obliczeniowa  optymistyczna, średnia i pesymistyczna )
- zapotrzebowanie na dodatkową pamięć (złożoność pamięciowa)
- stabilność algorytmu ( czy elementy o jednakowych kluczach zachowają pierwotną kolejność )
- przydatność do sortowania różnych struktur danych (tablice, listy, pliki).
Oczywiście każdy z algorytmów może mieć wiele różnych realizacji. Raczej nie można powiedzieć, że istnieje jeden
najlepszy algorytm ( czy też jego realizacja), tak więc dobierając algorytm sortowania do konkretnego przypadku należy
uwzględnić takie czynniki jak:
- rodzaj i wielkość porządkowanej struktury (tablica, lista, plik)
- złożoność porównania kluczy
- złożoność przepisywania elementów (wielkość elementu) - w javie ma to znaczenie tylko wtedy gdy tworzymy kopie
elementów
- początkowe uporządkowanie danych ( dane uporządkowane, losowe, prawie uporządkowane, odwrotnie uporządkowane,
o tej samej wartości )
- wielkość dostępnej pamięci operacyjnej
- wymagania dotyczące stabilności itp.
Najpełniejszy przegląd zagadnień związanych z sortowaniem można znalez
ć w :
Knuth D. E. The art of computer programming. Vol 3. Sorting and Searching.
Warto również zajrzeć do :
1.Wirth N. Algorytmy + struktury danych = programy.
2.Reingold E. M., Nievergelt J., Deo N. Algorytmy kombinatoryczne.
3.Aho A. V., Hopcroft J. E., Ullman J. D. Projektowanie i analiza algorytmów komputerowych.
4.Banachowski L., Kreczmar A. Elementy analizy algorytmów.
5.Banachowski L, Diks K, Rytter W Algorytmy i struktury danych.
6. Cormen T H, Leiserson Ch E, Rivest R L : Wprowadzenie do algorytmów.
7. Sedgewick R. :  Algorytmy w C++
8. Bentley J. :  Perełki oprogramowania
Większość (ale nie wszystkie ) algorytmów ustala kolejność elementów na podstawie porównań wartości elementów.
Możemy wykorzystać porządek naturalny ( wyznaczony przez metodę compareTo ) lub użyć odpowiednich komparatorów.
Drugie rozwiązanie jest bardziej uniwersalne i je będziemy wykorzystywać.
Aby sortować w porządku naturalnym elementy sorowane muszą implementować interface Comparable :
public interface Comparable
{ public int compareTo(Object other); }
czyli mieć zdefiniowaną metodę compareTo ( wynik <0 oznacza this0 this > other).
W drugim przypadku musimy zaimplementować interface Comparator :
16
public interface Comparator
{ public int compare(Object left, Object right) throws ClassCastException; }
Metoda compare ma wyniki takie jak compareTo.
Można zdefiniować komparator wyznaczający porządek naturalny :
package sorting;
public final class NaturalComparator implements Comparator {
// wykorzystuje wzorzec singleton
public static final NaturalComparator INSTANCE = new NaturalComparator();
private NaturalComparator() { }
public int compare(Object left, Object right) throws ClassCastException
{ return ((Comparable) left).compareTo(right); }
}
Równie łatwo można utworzyć komparator odwrotny :
package sorting;
public class ReverseComparator implements Comparator {
// podstawowy komparator
private final Comparator _comparator;
public ReverseComparator(Comparator comparator)
{ _comparator = comparator; }
public int compare(Object left, Object right) throws ClassCastException
{ return _comparator.compare(right, left); }
}
W przypadkach bardziej złożonych można komplikować metodę compare lub zbudować komparator złożony
wykorzystujący istniejące, proste komparatory. Pozwala to czasami uzyskać stabilne sortowanie nawet dla algorytmów
niestabilnych.
package sorting;
import iterators.Iterator;
import lists.ArrayList;
import lists.List;
public class CompoundComparator implements Comparator {
//tablica komparatorów ; od najważniejszego
private final List _comparators = new ArrayList();
public void addComparator(Comparator comparator)
{ _comparators.add(comparator); }
public int compare(Object left, Object right) throws ClassCastException {
int result = 0;
Iterator i = _comparators.iterator();
for (i.first(); !i.isDone()&&
(result = ((Comparator) i.current()).compare(left, right))==0; i.next());
return result;
}
}
Algorytmy sortowania.
Rozpoczynamy od algorytmów klasycznych ( o kwdratowej złożoności średniej).
- Na początek najprostszy, ale najgorszy algorytm sortowania przez zamianę (BubbleSort)
Idea algorytmu : 1. powtarzaj aż do całkowitego uporządkowania ciągu
porównuj parę elementów i jeśli ich kolejność jest nieprawidłowa to je zamień
Jego podstawowa realizacja wygląda tak:
Najpierw definicja interfejsu ułatwiającego wykorzystanie algorytmów sortowania :
package sorting;
import lists.List;
17
public interface ListSorter
// wynikiem jest nowa lista lub stara posortowana
{ public List sort(List list); }
Teraz sortowanie bąbelkowe:
package sorting;
import lists.List;
public class BubbleSort implements ListSorter {
private final Comparator _comparator;
public BubbleSort(Comparator comparator)
{ _comparator = comparator; }
// wynikiem jest posortowana lista pierwotna
// najbardziej prymitywna wersja
public List sort(List list) {
int size = list.size();
for (int pass = 1; pass < size; ++pass) {
for (int left = 0; left < (size - pass); ++left) {
int right = left + 1;
if (_comparator.compare(list.get(left), list.get(right)) > 0)
swap(list, left, right);
}
}
return list;
}
private void swap(List list, int left, int right) {
Object temp = list.get(left);
list.set(left, list.get(right));
list.set(right, temp);
}
}
Jest to algorytm prosty ale wolny . Można go przyspieszyć na kilka sposobów:
- ograniczyć pętlę zewnętrzną przez wykrywanie czy ciąg nie został uporządkowany wcześniej
- ograniczyć pętlę wewnętrzną przez zapamiętanie pozycji ostatniej zamiany w poprzednim przebiegu
- zastąpić ciąg zamian elementów ciągiem przepisań
- przechodząc ciąg na przemian w obu kierunkach ( ShakerSort).
Wprowadzając pierwsze trzy usprawnienia otrzymujemy :
package sorting;
import lists.List;
public class BubbleSort1 implements ListSorter {
private final Comparator _comparator;
public BubbleSort1(Comparator comparator)
{ _comparator = comparator; }
// wynikiem jest posortowana lista pierwotna
//wersja ulepszona wykorywająca wcześniejsze uporządkowanie
public List sort(List list) {
int lastSwap = list.size()-1; //pozycja ostatniej zamiany
while(lastSwap>0){
int end=lastSwap;
lastSwap=0;
for (int left = 0; left < end; ++left) {
if (_comparator.compare(list.get(left), list.get(left+1)) > 0)
{ //ciąg zamian jest zastąpiony ciągiem przepisań
Object temp=list.get(left);
while(left 0)
{ list.set(left, list.get(left+1)); left++; }
lastSwap=left;
list.set(left,temp);
}
18
}
}
return list;
}
}
Przykład sortowania listy zawodników według nazwisk i punktów:
//klasa zawodnik uzupełniona o metody porównujące
package iteracje;
import iterators.*;
public class Zawodnik
{String nazw;
int punkty;
public Zawodnik(String n, int p)
{nazw=n; punkty=p;}
public String toString() { return nazw+" "+punkty;}
public int porNazw(Zawodnik z) { return nazw.compareTo(z.nazw);}
public int porPunkty(Zawodnik z) { return punkty-z.punkty;}
}
//klasy komparatorów
package iteracje;
import sorting.*;
public final class NameComparator implements Comparator {
// wykorzystuje wzorzec singleton
public static final NameComparator INSTANCE = new NameComparator();
private NameComparator() { }
public int compare(Object left, Object right) throws ClassCastException
{ return ((Zawodnik)left).porNazw((Zawodnik)right); }
}
package iteracje;
import sorting.*;
public final class PointsComparator implements Comparator {
// wykorzystuje wzorzec singleton
public static final PointsComparator INSTANCE = new PointsComparator();
private PointsComparator() { }
public int compare(Object left, Object right) throws ClassCastException
{ return ((Zawodnik)left).porPunkty((Zawodnik)right); }
}
//sortowanie listy zawodników; najpierw wg nazwisk a potem wg punktów
package iteracje;
import iterators.*;
import lists.*;
import sorting.*;
public class Zawody
{ List lista = new ArrayList();
public Zawody() { }
public void testBubbleSort()
{ // wypełnienie listy
//sortowanie wg nazwisk
ListSorter ls=new BubbleSort(NameComparator.INSTANCE);
lista=ls.sort(lista);
System.out.println(lista);
System.out.println();
// wg punktów
ls=new BubbleSort(PointsComparator.INSTANCE);
lista=ls.sort(lista);
System.out.println(lista);
System.out.println();
//wg punktów i nazwisk (przy równych punktach decyduje nazwisko)
19
Comparator cc=new CompoundComparator();
cc.add(NameComparator.INSTANCE);
cc.add(PointComparator.INSTANCE);
ls=new BubbleSort(cc);
lista=ls.sort(lista);
System.out.println(lista);
System.out.println();
}
Wolne działanie tego algorytmu wynika z faktu że pojedyncza zamiana sąsiednich elementów zmienia stopień
nieuporządkowania ciągu (liczony jako liczba inwersji - ile razy wartość większa występuje przed mniejszą) tylko o 1.
Zamiana elementów odległych o h mogłaby zmniejszyć liczbę inwersji nawet o h.
Wykorzystał to w 1959 roku Shell do opracowania sortowania z malejącymi przyrostami (ShellSort)
Idea : Wybieramy ciąg malejących przyrostów h ,...,h spełniający warunek: h =1 oraz h < h dla i >j;
1 t t i j
Dla i od 1 do t wykonaj
Przyjmij przyrost h
i
Przez proste wstawianie (lub zamianę) uporządkuj wszystkie podciągi elementów odległych od
siebie o h
i
Niestety nie wiadomo jak dobrać dla konkretnego przypadku najlepszy ciąg przyrostów . Ponieważ skomplikowanie tego
algorytmu nie jest duże, a złożoność obliczeniowa nie jest najgorsza więc chętnie jest stosowany praktycznie.
Przykładowa realizacja z ciągiem przyrostów: 1,4,13,40,121,364,1093,3280,9841 .......( h =3* h +1 ), liczbę przyrostów
j+1 j
wyznacza się tak aby sortowane podciągi zawierały conajmniej 3 elementy.
package sorting;
import lists.List;
public class ShellSort implements ListSorter {
private final Comparator _comparator;
// przyrost
private int _h = 1;
public ShellSort(Comparator comparator)
{ _comparator = comparator; }
// ciąg przyrostów : h[0]=1; h[i]=3*h[i-1]+1
// minimalna długość podciągu : 3
// sortowanie podciągów : InsertSort
public List sort(List list) {
int size=list.size();
hMaxSet(size); //znajdz
największy przyrost
do { //dla malejących kolejno przyrostów
for(int i=_h;iinsert(list,i);
}while ((_h/=3) >0);
return list;
}
private void hMaxSet(int size){
while( _h < size/9)
_h=3*_h+1;
}
private void insert( List list, int poz) {
Object temp,value=list.get(poz);
while( poz>=_h && _comparator.compare(value,temp=list.get(poz-_h)) < 0)
{list.set(poz,temp); poz-=_h; }
list.set(poz,value);
}
}
Dla tego ciągu liczba porównań wynosi O(n3/2). Inne stosowane ciągi można znalez
ć w książce Sedgewicka.
Dwa inne elementarne (klasyczne) algorytmy : sortowanie przez wstawianie (InsertSort) oraz
sortowanie przez wybór (SelectSort).
1. Sortowanie przez wstawianie - sposób preferowany przez karciarzy
20
idea: 1. powtarzaj n - razy
wez
kolejny element z ciągu nieuporządkowanego
wstaw go na właściwe miejsce w ciągu uporządkowanym
2. Sortowanie przez wybór
idea: 1. powtarzaj n - razy
zabierz najmniejszy element z ciągu nieuporządkowanego
wpisz go na koniec ciągu już uporządkowanego
Są to dwa bardzo proste, ale wolne (złożoność kwadratowa) algorytmy  stosowane często do niewielkich ciągów. Mimo
podobnej budowy mają bardzo różne własności (jakie ? patrz literatura lub słuchaj wykładu).
Przykładowe realizacje:
package sorting;
import lists.List;
public class InsertSort implements ListSorter {
private final Comparator _comparator;
public InsertSort(Comparator comparator) { _comparator = comparator; }
public List sort(List list) {
for (int i = 1; i < list.size(); ++i) {
Object value = list.get(i),temp;
int j;
for (j = i; j > 0&& _comparator.compare(value, temp=list.get(j - 1))< 0; --j)
list.set(j,temp);
list.set(j, value);
}
return list;
}
}
Jak widać algorytm jest bardzo prosty, nie potrzebuje dodatkowej pamięci. Jest jednak wolny ( dużo porównań i tyle samo
przepisań ). Silnie zależy od natury porządkowanego ciągu (lubi uporządkowane ciągi ), zachowuje przy tym naturalną
kolejność elementów równych. Można poprawić jego efektywność przez zmniejszenie liczby porównań (wyszukiwanie
binarne).
package sorting;
import lists.List;
public class SelectSort implements ListSorter {
private final Comparator _comparator;
public SelectSort(Comparator comparator) { _comparator = comparator; }
public List sort(List list) {
int size = list.size();
for (int slot = 0; slot < size - 1; ++slot) {
int smallest = slot;
for (int check = slot + 1; check < size; ++check)
if (_comparator.compare(list.get(check), list.get(smallest)) < 0)
smallest = check;
swap(list, smallest, slot);
}
return list;
}
private void swap(List list, int left, int right) {
if (left != right) { // podejście optymisty
Object temp = list.get(left);
list.set(left, list.get(right));
list.set(right, temp);
}
}
}
Prosty, wolny (ale ma najmniejszą możliwą liczbę przepisań) ,nie zależy od uporządkowania danych, nie jest stabilny -
czyli nie zachowuje kolejności elementów równych. Można go przyspieszyć znajdując jednocześnie elementy maks i min
(szybciej można znalez
ć maks i min jednocześnie niż szukając ich po kolei) wystarczy 1.5n porównań zamiast 2n.
21
Złożone algorytmy sortowania (liniowo-logarytmiczne) : sortowanie szybkie (QuickSort) sortowanie
przez scalanie (MergeSort) oraz sortowanie stogowe (HeapSort).
Sortowanie szybkie
Opracowany w 1962 roku przez Hoare'a, jest jednym z najlepiej poznanych (matematycznie) algorytmów. Oparty jest na
zasadzie "divide et impera". Jej sens jest następujący: Aby rozwiązać problem wielkości N, rozwiąż rekurencyjnie dwa
podproblemy wielkości N/2 i połącz ich wyniki by otrzymać rozwiązanie całego problemu.
Idea algorytmu jest następująca :
1. wybierz dowolny element z porządkowanego ciągu - X
2. podziel ciąg na podciąg zawierający elementy mniejsze od X i drugi zawierający pozostałe
3. tak samo posortuj pierwszy podciąg
4. posortuj drugi podciąg tą samą metodą
5.połącz rozwiązania
Sortowanie przez scalanie
idea : 1. podziel ciąg na dwa podciągi
2. uporządkuj pierwszy podciąg tą samą metodą
3. uporządkuj drugi podciąg tą samą metodą
4. połącz podciągi zachowując uporządkowanie
Przykładowe realizacje algorytmu szybkiego sortowania ( różnią się sposobem podziału na podciągi):
- podział jednostronny zaproponowany przez Lomuto ( najprostszy)
package sorting;
import lists.List;
public class QuickSort implements ListSorter {
private final Comparator _comparator;
public QuickSort(Comparator comparator) { _comparator = comparator; }
// wynikiem jest posortowana oryginalna lista
public List sort(List list) {
quicksort(list, 0, list.size() - 1);
return list;
}
private void quicksort(List list, int startIndex, int endIndex) {
if (endIndex > startIndex) {
int partition = partition(list, startIndex, endIndex);
quicksort(list, startIndex, partition );
quicksort(list, partition + 1, endIndex);
}
}
// podział według Lomuto
private int partition(List list, int left, int right) {
//jako element dzielący bierzemy ostatni
Object value=list.get(right);
int i=left-1;
while (left <= right){
if( _comparator.compare(list.get(left), value) <= 0)
swap(list, ++i,left);
++left;
}
return i }
private void swap(List list, int left, int right) {
if (left != right) {
Object temp = list.get(left);
list.set(left, list.get(right));
list.set(right, temp);
}
22
}
}
- podział dwustronny ( szybszy ale bardziej skomplikowany) - lekko zmodyfikowana wersja Harrisa i Rossa ( styl !!)
// tylko metody które uległy zmianie
private void quicksort(List list, int startIndex, int endIndex) {
if (endIndex > startIndex) {
//jako element dzielący bierzemy ostatni
Object value=list.get(endIndex);
int partition = partition(list, value, startIndex, endIndex - 1);
if (_comparator.compare(list.get(partition), value) < 0)
++partition;
swap(list, partition, endIndex);
quicksort(list, startIndex, partition - 1);
quicksort(list, partition + 1, endIndex);
}
}
//styl!!
private int partition(List list, Object value, int left, int right) {
while (left < right) {
if( _comparator.compare(list.get(left), value) < 0)
{++left; continue;}
if(_comparator.compare(list.get(right), value) >= 0)
{--right; continue;}
swap(list, left, right); ++left;
}
return left;
}
- poprawiona wersja ( w porządnym strukturalnym stylu)
private void quicksort(List list, int startIndex, int endIndex) {
if (endIndex > startIndex) {
//jako element dzielący bierzemy ostatni
int partition = partition(list, startIndex, endIndex);
quicksort(list, startIndex, partition - 1);
quicksort(list, partition + 1, endIndex);
}
}
private int partition(List list, int left, int right) {
Object value=list.get(right);
int i=left-1,j=right;
while (i < j) {
while( _comparator.compare(list.get(++i), value) < 0);
while( (j>left) &&_comparator.compare(list.get(--j), value) > 0);
if( i < j)
swap(list, i, j);
}
swap(list,i,right);
return i;
}
Program jest prosty, bardzo szybki, potrzebuje niestety pamięci dla wywołań rekurencyjnych ( można zmniejszyć
głębokość rekurencji przez odpowiednie modyfikacje, albo zrealizować wersję iteracyjną ), Jest jednak silnie zależny od
początkowego uporządkowania ciągu (paradoksalnie, najgorszym przypadkiem jest ciąg już uporządkowany; również gdy
wartości wielu elementów się powtarzają działa wolno).
Możliwości usprawnień:
1. efektywność tego algorytmu jest uzależniona od równomierności i szybkości podziału na podciągi  przegląd różnych
metod podziału można znalez
ć w {Bentley J.   Perełki oprogramowania ]
2. QuickSort jest wyraz
nie lepszy od innych przy długich ciągach, stąd pomysł aby przerywać rekurencję przy ciągach
krótszych od M, a następnie wykorzystać prosty algorytm do ostatecznego posortowania (ciąg jest już prawie
uporządkowany, więc dobry będzie InsertSort)
3. Można pozbyć się rekurencji używając własnego stosu do zapamiętania ciągów do posortowania, jeśli zastosujemy
zasadę  odkładaj na stos dłuższy z podciągów, a krótszy obsłuż od razu to zapewnimy sobie co najwyżej
logarytmiczna wysokość stosu (normalnie może być liniowa  w najgorszym przypadku)
23
Prosta rekurencyjna realizacja algorytmu sortowania przez scalanie ( wersja zstępująca - podział ciągu na coraz mniejsze
podciągi , a następnie ich stopniowe scalanie) :
package sorting;
import iterators.Iterator;
import lists.ArrayList;
import lists.List;
public class MergeSort implements ListSorter {
private final Comparator _comparator;
public MergeSort(Comparator comparator) { _comparator = comparator; }
// wynikiem jest nowa lista
public List sort(List list)
{ return mergesort(list, 0, list.size() - 1); }
private List mergesort(List list, int startIndex, int endIndex) {
if (startIndex == endIndex) {
List result = new ArrayList();
result.add(list.get(startIndex));
return result;
}
int splitIndex = startIndex + (endIndex - startIndex) / 2;
return merge(mergesort(list, startIndex, splitIndex),
mergesort(list, splitIndex + 1, endIndex));
}
private List merge(List left, List right) {
List result = new ArrayList();
Iterator l = left.iterator(); Iterator r = right.iterator();
l.first(); r.first();
while (!l.isDone() && !r.isDone()) {
if (_comparator.compare(l.current(), r.current()) <= 0)
{ result.add(l.current()); l.next(); }
else { result.add(r.current()); r.next(); }
}
while(!l.isDone())
{ result.add(l.current()); l.next(); }
while(!r.isDone())
{ result.add(r.current()); r.next(); }
return result;
}
}
Można zastosować iteracyjny algorytm wstępujący (podstawowy jest zstępujący) : podziel listę na listy jednoelementowe i
umieść je w kolejce, następnie do uzyskania jednej listy wykonuj DoKolejki(Merge(Zkolejki,Zkolejki))  w bardziej
rozbudowanej wersji możemy w kolejce umieszczać nie pojedyncze elementy a serie (już uporządkowane podciągi
kolejnych elementów) - wymaga to tylko przebudowy metody createQueue.
package sorting;
import iterators.Iterator;
import queues.*;
import lists.List;
public class IterativeMergeSort implements ListSorter {
private final Comparator _comparator;
public IterativeMergeSort(Comparator comparator) { _comparator = comparator; }
public List sort(List list)
{ return mergeSublists(createQueue(list)); }
private List mergeSublists(Queue q)
while (q.size() > 1)
q.enqueue(mergePair((List)q.dequeue(),(List)q.dequeue());
return (List)q.dequeue();
}
private Queue createQueue(List list) {
Queue result = new ListFifiQueue();
Iterator i = list.iterator();
24
i.first();
while (!i.isDone()) {
List singletonList = new ArrayList(1);
singletonList.add(i.current());
result.enqueue(singletonList);
i.next();
}
return result;
}
private List mergePair(List left, List right) {
List result = new ArrayList(left.size()+right.size());
Iterator l = left.iterator(); Iterator r = right.iterator();
l.first(); r.first();
while (!l.isDone() && !r.isDone()) {
if (_comparator.compare(l.current(), r.current()) <= 0)
{ result.add(l.current()); l.next(); }
else { result.add(r.current()); r.next(); }
}
while(!l.isDone())
{ result.add(l.current()); l.next(); }
while(!r.isDone())
{ result.add(r.current()); r.next(); }
return result;
}
}
Sortowanie stogowe
Opis stogu i definicje metod realizujących działania na stogowej kolejce priorytetowej  (będzie) można znalez
ć w
wykładzie o kolejkach priorytetowych.
package sorting;
import iteration.Iterator;
import lists.ArrayList;
import lists.List;
import queues.HeapPriorityQueue;
import queues.Queue;
public class HeapSort implements ListSorter {
private final Comparator _comparator;
public HeapSort(Comparator comparator) {_comparator = comparator;}
public List sort(List list) {
Queue queue = createPriorityQueue(list);
List result = new ArrayList(list.size());
while (!queue.isEmpty()) {
result.add(queue.dequeue());
}
return result;
}
private Queue createPriorityQueue(List list) {
Comparator comparator = new ReverseComparator(_comparator);
Queue queue = new HeapPriorityQueue(comparator);
Iterator i = list.iterator();
i.first();
while (!i.isDone()) {
queue.enqueue(i.current());
i.next();
}
return queue;
}
}
Jeden z szybszych (ale wolniejszy od sortowania szybkiego) algorytmów (złożoność O(N*log N)),w porównaniu do
najbardziej znanego sortowania szybkiego nie jest rekurencyjny (łatwiej go analizować), nie potrzebuje dodatkowej
pamięci (rekurencja zawsze jej zużywa sporo) i nie jest wrażliwy na uporządkowanie danych wejściowych. Można go
usprawnić optymalizując metody obsługi stogu, ale pogarsza się w ten sposób jego czytelność. Czy to się opłaca zależy od
stopnia przyspieszenia i potrzeb.
25
1. można przyspieszyć fazę budowy stogu ( do O(n))  przez opuszczanie kolejnych elementów od (n div 2) do 0 na
dół
2. można zmniejszyć liczbę porównań w fazie rozbierania stogu wykorzystując spostrzeżenie Floyda, że ostatni element
wstawiany w miejsce korzenia prawie zawsze opada na dno stogu, będzie więc szybciej jeżeli będziemy schodzić od
wierzchołka do dna przesuwając w górę większego z synów ( na każdym poziomie), na wolne miejsce wstawiamy
ostatni element stogu i przesuwamy go WGórę (rzadko zachodzi taka potrzeba)
Zadania :
17) Przeanalizuj zachowanie poszczególnych algorytmów sortowania przy porządkowaniu ciągu liter SORTOWANIE
JEST PROSTE , zwróć uwagę na liczbę porównań i przepisań oraz stabilność.
18) Na wykładzie przedstawiono uniwersalne algorytmy (umożliwiające sortowanie list bez względu na ich
implementację). Zaproponuj bezpośrednie ( definiując odpowiednie struktury danych i potrzebne metody w jednej
klasie ) implementacje algorytmów. Który sposób daje prostszy kod ? Co z efektywnością ?
19) Jeśli znamy kryterium początkowego sortowania można łatwo ( przez wykorzystanie odpowiedniego komparatora
złożonego) doprowadzić do stabilności każdego z algorytmów sortowania. Czy można zaproponować uniwersalne
rozwiązanie zapewniające zachowanie stabilności ?
Algorytmy sortowania specyficznych typów danych  bez porównywania elementów.
Sortowanie przez rozdział
Stosowany wtedy gdy porządkowane elementy (ich klucze) pochodzą z niezbyt dużego zbioru z wyznaczonym
porządkiem liniowym . Załóżmy że klucze mają wartości liczbowe od 1 do M. Elementów do uporządkowania jest N.
Zazwyczaj N >> M. Utwórzmy strukturę M kolejek.
idea: 1. powtarzaj n - razy
wez
kolejny element i umieść go w kolejce wyznaczonej przez wartość klucza
(jeśli klucz ma wartość i to w i-tej kolejce)
2. wyprowadz
(połącz) wszystkie kolejki
1 - kubełkowe (BucketSort) [Aho,Banachowski]
Stosowane gdy wartości porządkowanych elementów pochodzą ze skończonego zbioru wartości np 1 .. M. Wykorzystując
kolejkę priorytetową z ograniczonym zbiorem wartości priorytetów (patrz wykład o kolejkach) możemy zapisać
następujący algorytm (zakładamy, że najmniejsza wartość elementu daje najwyższy priorytet):
1. for (i =0; i 2. for (i=0; iDrukuj(element)
Gdy stosujemy ten algorytm do porządkowania tablicy zużywamy dużo dodatkowej pamięci (tyle ile zajmuje tablica +
struktura kolejki), z tego względu algorytm nadaje się bardziej do sortowania list.
2 - wielolistowe (uogólnienie kubełkowego) [Banachowski]
W poprzednim przypadku mieliśmy do czynienia ze skończonym zbiorem wartości elementu. Rozważmy ciąg w którym
elementy mają ograniczone wartości np. 0<=el < X, ale są liczbami rzeczywistymi (zbiór możliwych wartości jest
nieskończony). Możemy wówczas wykorzystać tablicę M kolejek priorytetowych (o nieskończonym zbiorze wartości
priorytetów (p.wykł. 3).
1. for (i=0; ipr=floor (el[i]/X*M)
DoKolejki(pr,el[i])
2. for (pr=0; pr while (! PustaKolejka(pr))
ZKolejki(pr,elem)
Drukuj(elem)
Oba algorytmy są bardzo szybkie. Ciekawe, że w alg .1 nie wykonuje się żadnych porównań (a w 2 stosunkowo niewiele -
przy wstawianiu do kolejki)
3 - pozycyjne (RadixSort) [Aho]
26
Sytuacja jest bardziej skomplikowana gdy klucz elementu jest określony przez ciąg P wartości z zakresu 0 : M-1.
Możemy wykorzystać tablicę M zwykłych (FIFO) kolejek. Zakładając że mamy procedurę PolaczKolejki, która tworzy
listę dołączając na jej koniec kolejne kolejki od 1 do P otrzymujemy następujący algorytm :
1. for( nrpoz=P; nrpoz >=0; nrpoz--)
for( i= 0; iDoKolejki(el[i].klucz[nrpoz],el[i])
PolaczKolejki
UWAGA: oczywiście klucze (w alg. 1 i 3) nie muszą być liczbami całkowitymi (przyjęto tak dla uproszczenia), co więcej
zakresy wartości dla poszczególnych pozycji klucza (alg. 3) mogą być różne.
Sortowanie przez zliczanie
idea: dla każdego elementu ciągu
oblicz ile jest elementów od niego mniejszych ,
umieść element na wyznaczonej w ten sposób pozycji ciągu wynikowego.
Uwaga: naiwna realizacja tego algorytmu daje złożoność O(n2)
Realizacja algorytmu sortowania przez zliczanie (CountingSort) [Cormen]
Zakładamy, że każdy z n sortowanych elementów jest liczbą całkowitą z przedziału od 0 do K-1. Dane są umieszczone w
tablicy A, wynik zapisujemy w tablicy C, używamy również pomocniczej tablicy liczników B.
void CountingSort(Tablica a, Tablica c, int n)
{ int b[K],i;
for(i=0;i for(i=0; i for( i=1;i for (i=n-1;i>=0;i--) c[(b[a[i]]--]=a[i];
}
Jest to stabilny algorytm o złożoności O(n+k).
Sortowanie zewnętrzne - przeprowadzane bezpośrednio na danych umieszczonych w plikach.
Algorytmy tej klasy (wymienione poniżej) nie będą omawiane na wykładzie (ich szczegółowy opis można znalez
ć w
[Wirth "Algorytmy + Struktury Danych = Programy]). Dlaczego ? Algorytmy te (co prawda efektywne ale dość
skomplikowane) powstały przy założeniu, że sortowany ciąg znajduje się w pliku o dostępie sekwencyjnym (jego elementy
można odczytywać tylko kolejno ) i jest na tyle duży, że nie mieści się w całości w pamięci operacyjnej programu. Od
czasu ich powstania sytuacja się nieco zmieniła :
1. znacznie zwiększyła się pamięć operacyjna dostępna dla programu,
2. używane pliki pozwalają na dostęp bezpośredni (w dowolnej kolejności - Seek) do ich elementów.
Czynnik drugi pozwala efektywnie wykorzystywać pliki indeksowe (specjalne pliki pokazujące uporządkowanie
elementów pliku głównego). Przykład wykorzystania pliku indeksowego zostanie omówiony póz
niej.
Z kolei zwiększenie pamięci powoduje, że większość wykorzystywanych przez nas plików mieści się w pamięci, jeśli nie
to jest duże prawdopodobieństwo, że zmieści się struktura zawierająca tylko klucz (zazwyczaj stanowi on niewielką część
elementu pliku ) i położenie elementu w pliku (numer rekordu ) - wówczas wystarczy posortować taką strukturę i zgodnie z
uporządkowaniem przepisać plik.
1 Sortowanie przez łączenie proste
2 Sortowanie przez łączenie naturalne
3 Sortowanie przez wielokierunkowe łączenie wyważone
4 Sortowanie polifazowe
Temat 7. Kolejki priorytetowe.
Jest to najbardziej ogólny rodzaj kolejek. Spośród elementów stojących w kolejce pobierany jest element o najwyższym
priorytecie, a przy równych priorytetach ten element który wcześniej stanął w kolejce. Zwykła kolejka może być
27
traktowana jako kolejka priorytetowa, w której priorytet jest określony przez czas wejścia do kolejki. Implementacja
kolejki zależy od charakteru zbioru priorytetów.
a)- z nieograniczonym zbiorem wartości priorytetów
- nieuporządkowane
wstawianie na koniec kolejki (złożoność O(1))
usuwanie elementu o najwyższym priorytecie (pierwszego z równych) (złożoność O(N))
- uporządkowane, wykorzystujące :
-- uporządkowaną listę lub tablicę
usuwanie z początku kolejki (złożoność O(1))
wstawianie na właściwe miejsce (za ostatni o takim samym priorytecie) ( złożoność O(N))
- stóg ( złożoność wstawiania i pobierania O(log N))
b)- z priorytetami o wartościach wybranych z niewielkiego zbioru.
W tym wypadku wykorzystujemy tablicę zwykłych kolejek (dla każdego priorytetu osobna).
Implementacja kolejki bazującej na liście nieuporządkowanej :
package queues;
import lists.LinkedList;
import lists.List;
import sorting.Comparator;
public class UnsortedPriorityQueue implements Queue {
private final List _list;
private final Comparator _comparator; //do ustalenia priorytetu
public UnsortedPriorityQueue(Comparator comparator) {
_comparator = comparator;
_list = new LinkedList();
}
public void enqueue(Object value)
{ _list.add(value); }
public Object dequeue() throws EmptyQueueException {
if (isEmpty()) throw new EmptyQueueException();
return _list.delete(getIndexOfLargestElement());
}
private int getIndexOfLargestElement() {
int result = 0;
for (int i = 1; i < _list.size(); ++i)
if (_comparator.compare(_list.get(i), _list.get(result)) > 0)
result = i;
return result;
}
public void clear()
{ _list.clear(); }
public int size()
{ return _list.size(); }
public boolean isEmpty()
{ return _list.isEmpty();}
}
Implementacja wykorzystująca listę uporządkowaną :
package queues;
import lists.LinkedList;
import lists.List;
import sorting.Comparator;
public class SortedPriorityQueue implements Queue {
private final List _list;
private final Comparator _comparator;
public SortedPriorityQueue(Comparator comparator) {
_comparator = comparator;
_list = new LinkedList();
}
28
public void enqueue(Object value) {
int pos = _list.size();
while (pos > 0 && _comparator.compare(_list.get(pos - 1), value) > 0)
--pos;
_list.insert(pos, value);
}
public Object dequeue() throws EmptyQueueException {
if (isEmpty()) throw new EmptyQueueException();
return _list.delete(_list.size() - 1);
}
public void clear()
{ _list.clear(); }
public int size()
{ return _list.size();}
public boolean isEmpty()
{ return _list.isEmpty();}
}
Pojęcie stogu (Heap):
Stogiem zupełnym (stertą ) nazywamy takie drzewo binarne, które ma dwie własności:
- kształtu : jest pełnym drzewem, przy czym ostatni poziom jest zapełniany od lewej strony
- uporządkowania : węzeł jest zawsze większy od swoich potomków.
Najprościej jest realizować stóg w tablicy. Wówczas synami węzła i są węzły 2*i+1 oraz 2*(i+1), a ojcem węzła i jest
węzeł (i-1)/ 2 .
Implementacja kolejki wykorzystującej stóg :
package queues;
import lists.ArrayList;
import lists.List;
import sorting.Comparator;
public class HeapPriorityQueue implements Queue {
private final List _list;
private final Comparator _comparator;
public HeapPriorityQueue(Comparator comparator) {
_comparator = comparator;
_list = new ArrayList();
}
public void enqueue(Object value) {
_list.add(value);
swim(_list.size() - 1);
}
//wynoszenie elementu w górę
private void swim(int index) {
int parent;
while(index != 0 &&
_comparator.compare(_list.get(index), _list.get(parent= (index - 1) / 2)) > 0)
{ swap(index, parent);
index=parent;
}
}
private void swap(int index1, int index2) {
Object temp = _list.get(index1);
_list.set(index1, _list.get(index2));
_list.set(index2, temp);
}
public Object dequeue() throws EmptyQueueException {
29
if (isEmpty()) throw new EmptyQueueException();
Object result = _list.get(0);
if (_list.size() > 1) {
_list.set(0, _list.get(_list.size() - 1));
sink(0);
}
_list.delete(_list.size() - 1);
return result;
}
// opuszczanie elementu w dół stogu
private void sink(int index) {
boolean isDone=false;
int child;
while(!isDone && (child=2*index+ 1 ) < _list.size()) {
if (child < _list.size()- 1 &&
_comparator.compare(_list.get(child), _list.get(child+1)) < 0)
++child;
if (_comparator.compare(_list.get(index), _list.get(child)) < 0)
swap(index, child);
else isDone=true;
}
}
public void clear()
{ _list.clear(); }
public int size()
{ return _list.size(); }
public boolean isEmpty()
{ return _list.isEmpty();}
}
Zadania :
20) Stóg wykorzystywany do sortowania stogowego można zbudować bez wykorzystania metody swim ( przesuwanie w
górę). Jest to znacznie szybszy proces.Zaimplementuj odpowiednią metodę.
21) Flloyd zauważył, że można przyspieszyć usuwanie elementu kolejki stogowej przez modyfikację metody sink.
Zaproponował żeby opuszczać element na sam dół stogu, a następnie jeśli trzeba to go podnieść na odpowiednią
pozycję. Kiedy to podejście przynosi korzyść.
Temat 8. Tablice symboli (słowniki).
Słownik (inne nazwy to : tablica skojarzeniowa, tablica asocjacyjna, tablica indeksowana wartością klucza, odwzorowanie,
mapa - bezmyślne przetłumaczenie angielskiego terminu map czyli odwzorowanie) - typ
abstrakcyjny z określonymi operacjami :
JestElementem - czy dany element występuje w słowniku albo wyszukaj element o danym kluczu
Dodaj - dopisz element do słownika
Usun - usuń element ze słownika
Wybierz - k-ty co do wielkości element
Sortuj - wypisz wszystkie elementy w sposób uporządkowany
Połącz - połącz dwa słowniki w jeden
Należy pamiętać że podstawową operacją na typowym słowniku jest wyszukiwanie elementu; dodawanie i usuwanie albo
nie występują, albo są wykonywane bardzo rzadko. Więc efektywność wyszukiwania decyduje o przydatności danej
realizacji. Metody wyszukiwania elementu zależą od sposobu organizacji słownika. Klucze obiektów ( elementów )
występujących w słowniku nie mogą się powtarzać. Elementy występujące w słowniku mogą się składać albo z samego
klucza (np. słownik słów kluczowych kompilatora, słownik do sprawdzania pisowni ) lub z klucza i danych (np. słownik
polsko-angielski, encyklopedia, książka telefoniczna). Od typu elementu zależy sposób działania operacji JestElementem:
- tylko sprawdzenie gdy element ma tylko klucz
- zwrócenie wartości pola dane dla elementów zbudowanych z klucza i danych.
Operacja dodawania elementu do słownika jest wykonywana znacznie rzadziej. Tylko w specyficznych sytuacjach w czasie
normalnej pracy (on-line) i wówczas jej efektywność jest istotna , zazwyczaj jednak jest wykonywana w trybie off-line i
szybkość nie ma praktycznego znaczenia. Usuwanie elementu prawie zawsze jest wykonywane w trybie off-line.
Można wyróżnić trzy podstawowe klasy struktur służących do przechowywania elementów słownika :
1. ciąg nieuporządkowany ( tablica, plik lub lista)
2. tablica haszowana
3. ciąg uporządkowany (tablica, plik, lista, struktury drzewiaste).
30
Na początek zajmiemy się wyszukiwaniem na listach nieuporządkowanych i uporządkowanych.
Interfejs wyszukiwania :
package searching;
import lists.List;
public interface ListSearcher {
//zwraca pozycję obiektu na liście - jeśli jest
//jeśli nie to - (pozycja_wstawienia + 1)
// plus1 umożliwia wskazanie, że element powinien się znajdować na początku listy
public int search(List list, Object value);
}
Dla list nieuporządkowanych stosujemy wyłącznie proste przeszukiwanie liniowe ( złożonośc O(N)) .
Dla list uporządkowanych możemy zastosować :
- wyszukiwanie liniowe ( O(N)) , szybsze wykrywanie braku elementu w porównaniu do list nieuporządkowanych :
package searching;
import lists.List;
import sorting.Comparator;
public class LinearListSearcher implements ListSearcher {
private final Comparator _comparator;
public LinearListSearcher(Comparator comparator)
{ _comparator = comparator; }
public int search(List list, Object value) {
int cmp=0,i;
for (i=0; i0; i++);
return i }
}
- wyszukiwanie binarne (złożoność O(log N)) :
idea :
Oznaczenia : k- klucz szukanego elementu
poc - pozycja lewego końca przeszukiwanego obszaru k(poc) klucz tej pozycji
kon - pozycja prawego końca k(kon) jej klucz
b - wyznaczony w danym kroku punkt podziału k(b) klucz
do b= (poc+kon) div 2
if ( k >k(b)) b+1 staje się lewym końcem nowego przedziału
else b staje się prawym końcem nowego przedziału
while ( poc >=kon)
sprawdz
element na pozycji poc
implementacja iteracyjna (nieco inna wersja - dla optymistów )
package searching;
import lists.List;
import sorting.Comparator;
public class IterativeBinaryListSearcher implements ListSearcher {
private final Comparator _comparator;
public IterativeBinaryListSearcher(Comparator comparator)
{ _comparator = comparator; }
public int search(List list, Object value) {
int lower = 0;
int upper = list.size() - 1;
int index=0,cmp=0;
while (lower <= upper &&
(cmp = _comparator.compare(value, list.get(index=(lower + upper)/2)))!=0)
if (cmp < 0) upper = index - 1;
31
else lower = index + 1;
return lower<=upper && cmp==0 ? index : -(lower+1);
}
}
implementacja rekurencyjna
package searching;
import lists.List;
import sorting.Comparator;
public class RecursiveBinaryListSearcher implements ListSearcher {
private final Comparator _comparator;
public RecursiveBinaryListSearcher(Comparator comparator)
{ _comparator = comparator; }
public int search(List list, Object value)
{ return search(list, value, 0, list.size() - 1); }
// wersja dla miłośników instrukcji return ( moim zdaniem nienajlepsza )
private int search(List list, Object value, int lower, int upper) {
if (lower > upper) return -(lower + 1);
int index = (lower + upper) / 2;
int cmp = _comparator.compare(value, list.get(index));
if (cmp < 0) return search(list, value, lower, index - 1);
if (cmp > 0) return search(list, value, index + 1, upper);
return index;
}
}
Jeszcze szybsze jest wyszukiwanie interpolacyjne (stosowane gdy klucze mają rozkład równomierny)
do b= poc+(k-k(poc))/(k(kon)-k(poc))*(kon-poc)
if (k >k(b)) b+1 staje się lewym końcem nowego przedziału
else b staje się prawym końcem nowego przedziału
while (poc >=kon)
sprawdz
element na pozycji poc
Złożoność log log(N) - czyli praktycznie stała.
Zadania :
22) Zaimplementuj wyszukiwanie binarne dokładnie według przedstawionej powyżej idei. Sprawdz
swój algorytm dla
wszystkich granicznych przypadków.
23) Zaimplementuj rekurencyjną wersję wyszukiwania liniowego. Chodzi wyłącznie o gimnastykę umysłu - staramy się
unikać rekurencji o głębokości liniowej.
Drzewa : budowa i przetwarzanie.
Drzewo ukorzenione jest to graf skierowany, nie zawierający cykli i spełniający następujące warunki:
1.Istnieje dokładnie jeden wierzchołek (węzeł) do którego nie dochodzi żadna krawędz
- korzeń drzewa
2.Dla każdego wierzchołka grafu istnieje droga ( jedyna) od korzenia do tego wierzchołka
3.Każdy wierzchołek nie będący korzeniem ma jedyną krawędz
dochodzącą do niego.
Jeśli w grafie istnieje krawędz
(gałąz
) od węzła w do węzła v, to w nazywamy poprzednikiem ( przodkiem, ojcem ) v , a
v nazywamy następnikiem (potomkiem, synem) w. Wierzchołek bez potomków nazywamy liściem. Wierzchołek mający
co najmniej jednego potomka nazywamy węzłem wewnętrznym. Wierzchołek reprezentujący elementy nie występujące w
drzewie (oznaczony przez NULL ) nazywamy węzłem zewnętrznym (w niektórych książkach te węzły są nazywane
liśćmi) . Wierzchołek v razem z jego potomkami nazywamy poddrzewem o korzeniu v. Głębokość ( poziom )
wierzchołka v jest to długość drogi (liczba krawędzi) od korzenia do v (korzeń ma głębokość 0 ). Wysokość drzewa jest to
maksymalna długość drogi od korzenia do liści (czyli największa z głębokości liści , wysokość drzewa pustego wynosi -1,
a drzewa jednowęzłowego 0).
Drzewo uporządkowane - drzewo w którym następniki każdego wierzchołka są uporządkowane ( na rysunku - od lewej
do prawej ).
32
W programowaniu najważniejsze znaczenie mają uporządkowane drzewa binarne. Binarne drzewo poszukiwań
(Binary Search Tree) - drzewo uporządkowane spełniające warunki :
1. wśród następników każdego wierzchołka wyróżniamy lewy i prawy następnik
2. każdy wierzchołek ma co najwyżej jeden prawy i jeden lewy następnik
3. w lewym poddrzewie znajdują się wartości mniejsze od korzenia, a w prawym większe.
4. klucze się nie powtarzają.
Podstawowe działania na uporządkowanych drzewach binarnych (patrz BST.java).
Najprostsza postać węzła drzewa ( można ją wzbogacić o dodatkowe informacje) :
class Node{
Object value;
Node left;
Node right;
Node(Object x)
{ value=x; left = right = null; }
}
Do podstawowych działań na drzewach możemy zaliczyć :
1. Przechodzenie przez wszystkie wierzchołki drzewa (w określonej kolejności) - przetwarzanie całego drzewa
2. Wyszukiwanie - sprawdzanie czy w drzewie występuje węzeł o zadanym kluczu
3. Wstawianie - dołączanie nowego węzła do drzewa
4. Usuwanie węzła z drzewa.
1. Przechodzenie przez wszystkie wierzchołki drzewa (o korzeniu t ) :
Przejdz
(Wsk t)
Przejdz
(t->lewe);
przetwórz(t); // wykorzystaj węzeł t
Przejdz
(t->prawe);
Ponieważ trzy czynności - przejdz
lewe, przetwórz korzeń i przejdz
prawe możemy ustawić na 6 różnych sposobów tyle
też jest sposobów przechodzenia drzewa. Dla BST jest najważniejszy sposób pokazany wyżej ponieważ daje wierzchołki
od najmniejszego do największego.
Przykład przechodzenia in-order (PLW) w celu pokazania struktury drzewa jest w BST.java ( metoda toString ).
2. Wyszukiwanie węzła (o zadanej wartości ) w drzewie . Jeśli węzła nie ma zwraca NULL.
public Object find(Object x)
{Node t = search(x);
return t !=null ? t.value : null;
}
private Node search(Object value) {
Node node = _root;
int cmp=0;
while (node != null &&(cmp = _comparator.compare(value, node.value))!=0)
node = cmp < 0 ? node.left : node.right;
return node;
}
Jest to przykład jednej z nielicznych iteracyjnych metod dla drzew.
3. Wstaw węzeł do drzewa .
Należy przeszukać drzewo, i jeśli dodawanego węzła w nim nie ma - dołączyć go (zawsze jako liść). Jeśli jest to
zgłaszany jest wyjątek.
public void insert(Object x)
{ _root= insert(x,_root); }
protected Node insert(Object x, Node t) {
if(t== null) t=new Node(x);
else { int cmp=_comparator.compare(x,t.value);
if(cmp<0) t.left=insert(x,t.left);
else if(cmp>0) t.right=insert(x,t.right);
else throw new DuplicateItemException(x.toString());
33
}
return t;
}
4. Usuń węzeł (o podanej wartości ) z drzewa .
Znajdz
węzeł w drzewie - możliwe są dwa przypadki
- węzła nie ma (błąd) - zgłaszany jest wyjątek
- węzeł jest - i tu rozróżniamy 3 przypadki:
- a) węzeł jest liściem - zwyczajnie go usuwamy
- b) ma tylko jednego syna - zastępujemy go lewym lub prawym poddrzewem
- c) ma dwóch synów (najgorszy przypadek )
- znajdujemy skrajnie lewy węzeł w prawym poddrzewie (bezpośredni następnik - może mięć co najwyżej
jednego syna więc jest łatwy do usunięcia; można wybierać największy w lewym poddrzewie)
,zastępujemy nim usuwany węzeł i usuwamy go.
public void delete(Object x)
{_root=delete(x,_root); }
protected Node delete(Object x, Node t) {
if(t==null) throw new ItemNotFoundException(x.toString());
else { int cmp=_comparator.compare(x,t.value);
if(cmp<0) t.left=delete(x,t.left);
else if(cmp>0) t.right=delete(x,t.right);
else if(t.left!=null &&t.right!=null)
t.right=detachMin(t.right,t);
else t = (t.left != null) ? t.left : t.right;
}
return t;
}
//zastąp usuwany element jego następnikiem i usuń następnik
protected Node detachMin(Node t, Node del) {
if(t.left!=null) t.left=detachMin(t.left,del);
else {del.value=t.value; t=t.right;}
return t;
}
Drzewa BST wyradzają się przy nielosowej kolejności wstawiania elementów (np. uporządkowane).
Zbudowanie optymalnego (gwarantującego minimalną liczbę porównań) jest bardzo trudne - patrz Aho,Hopcroft,Ullman -
"Projektowanie i analiza algorytmów komputerowych . Dlatego zazwyczaj zadowalamy się prawie optymalnymi drzewami
gwarantującymi logarytmiczną wysokość (złożoność wyszukiwania).
1. drzewa wyważone AVL (Adelson-Velski, Landis) - dla każdego węzła wysokości poddrzew różnią się co najwyżej o
1. Stosunkowo proste działania (wystarczy dodać wskaz
nik wyważenia). Gwarantowana wysokość 1.45log n.
2. inne : BB-drzewa (2-3 drzewa) , drzewa czerwono-czarne ( SBB drzewa, 2-3-4 drzewa) - obecnie najczęściej
stosowane, opracowane przez Bayera.
Drzewa wyważone AVL (patrz AVL.java).
// nie będą omawiane na wykładzie ( lekko się zestarzały od 1962 roku
// zamiast nich będzie omówiona implementacja 2-3-4 drzew w postaci drzew czerwono-czarnych.
//aby ułatwić porównanie pozostawiam AVL w treści wykładu
Wyszukiwanie odbywa się jak w zwykłym drzewie BST. Wstawianie i usuwanie węzłów komplikują się, ponieważ trzeba
kontrolować wyważenie i czasami przebudowywać drzewo. Wskaz
nik wyważenia dla każdego z węzłów może
przyjmować jedną z trzech wartości
L- lewe poddrzewo jest wyższe od prawego
R- oba drzewa mają tę samą wysokość
P- prawe poddrzewo jest wyższe
Przebudowa drzewa jest realizowana za pomocą rotacji - tym razem również podwójnych:
//Prosta zamiana węzła z jego lewym potomkiem
34
Node RotRight(Node t)
{ Node t1=t.left;t.left = t1.right; t1.right=t; return t1;}
// Prosta zamiana węzła z jego prawym potomkiem
Node RotLeft(Node t)
{ Node t1=t.right; t.right =t1.left; t1.left = t; return t1;}
//Podwójna rotacja LewaPrawa:
// 1. lewy potomek węzła ze swoim prawym potomkiem
// 2. węzeł z lewym potomkiem(po zamianie 1.)
Node RotLeftRight(Node t)
{ t.left = RotLeft(t.left); return RotRight(t);}
// rotacja PrawaLewa - Symetryczna do rotacji LewaPrawa
Node RotRightLeft(Node t)
{ t.right=RotRight(t.right); return RotLeft(t); }
Wstawianie elementu x do drzewa o korzeniu t , h - wskaz
nik czy drzewo zmieniło wysokość ,
jeśli już był zgłaszany jest wyjątek.
Należy rozpatrzyć następujące przypadki w zależności od wskaz
nika ojca wstawianego węzła przed wstawieniem
( zakładamy że nowy węzeł jest dołączany jako lewy syn - przy wstawianiu do prawego poddrzewa sytuacja jest w pełni
symetryczna)
- P - oba poddrzewa wyrównują się, nowy wskaz
nik ojca jest R
- R - urosło lewe poddrzewo ale warunek wyważenia jest zachowany nowy współczynnik ojca jest L
- L - najgorszy przypadek - urosło wyższe drzewo, należy przywrócić wyważenie, postępowanie zależy od
wyważenia lewego poddrzewa wyważanego węzła :
- L - prosta zamiana węzła z jego lewym potomkiem
- P lub R - podwójna zamiana (LewoPrawo)
1. lewy potomek z prawym potomkiem lewego potomka węzła
2. węzeł z lewym potomkiem (po zamianie 1.) }
W przypadkach R i L należy skontrolować wyważenie przodka wstawianego węzła.
Usuwanie węzła (parametry jak wyżej) odbywa się jak w BST plus wyważanie drzewa.
Tym razem poddrzewo mogło ulec skróceniu - łato zauważyć podobieństwo sytuacji : urosło lewe poddrzewo i prawe
poddrzewo uległo skróceniu.
Podobnie jak przy wstawianiu sytuacja zależy od wyważenia ojca usuwanego węzła (do opisu przyjmijmy że usuwany
węzeł był w lewym poddrzewie, jeśli usunęliśmy z prawego poddrzewa sytuacja jest symetryczna).
- L - wyższe drzewo uległo skróceniu, nowy wskaz
nik - R
- R - skróciło się lewe poddrzewo ale warunek wyważenia jest zachowany nowy wskaz
nik - P
- P - obcięte zostało niższe drzewo, trzeba przywrócić wyważenie, sprawdzamy wskaz
nik wyważenia prawego
poddrzewa wyważanego węzła
- P lub R - prosta zamiana węzła z jego prawym potomkiem
- L - podwójna zamiana (PrawoLewo)
1. prawy potomek z lewym potomkiem prawego potomka
2. węzeł z prawym potomkiem
2-3-4 drzewa i ich implementacja w postaci drzew czerwono-czarnych przechylonych w lewo (LLRBTree Sedgevick
2007) (patrz LLRB.java).
Koncepcję 2-3-4 drzew opracował w 1972 roku Bayer. Są to prawie optymalne drzewa poszukiwań - gwarantują
logarytmiczną złożoność wyszukiwania. W węz
le może być zapisane do 3 elementów. Wszystkie liście są na tym samym
poziomie.
- wyszukiwanie odbywa się podobnie jak w BST
- wstawianie zawsze do liścia; gdy liść jest 4-węzłem następuje jego podział i przeniesienie elementu dzielącego do
ojca . Jest to bardzo kłopotliwe, więc częściej stosuje się eliminację 4-węzłów przy schodzeniu do liścia.
Ciekawostka : drzewo rośnie w stronę korzenia.
35
- usuwanie jest bardziej złożone , należy rozróżnić dwie sytuacje :
usuwanie z liścia ; czasem połączone z pożyczką elementu od sąsiedniego węzła lub połączeniem
węzłów
usuwanie z węzła wewnętrznego - zastępujemy usuwany element jego bezpośrednim następnikiem lub
poprzednikiem (znajduje się on w liściu więc jest łatwy do usunięcia)
Bezpośrednia realizacja węzłów w postaci tablicy elementów byłaby bardzo nieefektywna, dlatego 2-3-4 drzewa
implementuje się jako drzewa czerwono-czarne ( Guibas i Sedgewick 1978).
Jest prosty sposób przedstawienia 2-,3- i 4-węzłów za pomocą węzłów binarnych z dodanym polem koloru.
Własności drzew czerwono czarnych :
- każdy węzeł jest albo czerwony albo czarny
- korzeń i wszystkie węzły zewnętrzne są czarne
- jeśli węzeł jest czerwony to jego synowie są czarni ( nie ma dwóch czerwonych wezłów pod rząd)
- każda ścieżka od ustalonego węzła do liścia ma tyle samo czarnych węzłów.
Drzewa czerwono-czarne mimo dużej złożoności metod realizujących poszczególne działania (co jest spowodowane dużą
liczbą różnych sytuacji) są powszechnie stosowane - ze względu na gwarantowaną logarytmiczną złożoność i szybkość
działania. Dopiero Sedgewick w 2007 zaproponował ograniczenie sposobów przedstawienia węzłów co doprowadziło do
znaczącego uproszczenia kodu - bez pogorszenia szybkości wyszukiwania. Opracowane przez niego LLRBTree (Left Lean
Red Black Tree - drzewa czerwono-czarne przechylone w lewo ) dopuszczają występowanie 4-węzłów tylko chwilowo ( w
czasie wykonywania operacji) i pozwalają na jedną reprezentację 3- węzłów. Przykładowa implementacja :
package rbtree;
public class LLRBTree> {
static final boolean RED=true;
static final boolean BLACK =false;
private Node _root;
public LLRBTree()
{ _root=null;}
private boolean isRed( Node x)
{return x!= null && x.color==RED;}
public Elem find(Elem x)
{Node t = search(x);
return t !=null ? t.value : null;
}
private Node search(Elem value) {
Node node = _root;
int cmp=0;
while (node != null &&(cmp = value.compareTo(node.value))!=0)
node = cmp < 0 ? node.left : node.right;
return node;
}
private Node rotateL(Node t)
{ Node x=t.right;
t.right=x.left;
x.left=t;
x.color=t.color;
t.color=RED;
return x; }
private Node rotateR(Node t)
{ Node x=t.left;
t.left=x.right;
x.right=t;
x.color=t.color;
t.color=RED;
return x; }
36
private void colorFlip(Node t)
{t.color=!t.color; t.left.color=!t.left.color; t.right.color=!t.right.color;
}
public void insert(Elem x)
{ _root= insert(x,_root); _root.color=BLACK;}
protected Node insert(Elem x, Node t) {
if(t== null) t=new Node(x);
else { int cmp=x.compareTo(t.value);
if(isRed(t.left) && isRed(t.right))
colorFlip(t);
if(cmp<0) t.left=insert(x,t.left);
else if(cmp>0) t.right=insert(x,t.right);
else throw new RuntimeException("Duplicate
"+x.toString());
t=fixUp(t);
}
return t;
}
private Node fixUp(Node t)
{ if(isRed(t.right))
t=rotateL(t);
if(isRed(t.left) && isRed(t.left.left))
t=rotateR(t);
if(isRed(t.left) && isRed(t.right))
colorFlip(t);
return t; }
private Node moveRedR( Node t)
{ colorFlip(t);
if(isRed(t.left.left))
{ t=rotateR(t); colorFlip(t); }
return t; }
private Node moveRedL( Node t)
{ colorFlip(t);
if(isRed(t.right.left))
{ t.right=rotateR(t.right); t=rotateL(t); colorFlip(t);}
return t;}
public void delete(Elem x)
{_root=delete(x,_root);
if(_root!=null) _root.color=BLACK;}
protected Node delete(Elem x, Node t) {
if(t==null) throw new RuntimeException("Not found "+x.toString());
else { int cmp=x.compareTo(t.value);
if(cmp<0)
{ if(!isRed(t.left) && !isRed(t.left.left))
t=moveRedL(t);
t.left=delete(x,t.left);
}
else{if( isRed(t.left)) t=rotateR(t);
if(x.compareTo(t.value)==0&&t.right == null) return null;
else { if(!isRed(t.right) && !isRed(t.right.left))
t=moveRedR(t);
if(x.compareTo(t.value)>0)
t.right=delete(x,t.right);
else t.right=detachMin(t.right, t);
}
37
}
}
return fixUp(t);
}
protected Node detachMin(Node t, Node del) {
if(t.left==null) {del.value=t.value; t=null;}
else { if(!isRed(t.left) && !isRed(t.left.left))
t=moveRedL(t);
t.left=detachMin(t.left,del);
t=fixUp(t); }
return t;
}
public String toString()
{return toString(_root,0);}
private String toString(Node t,int pos) {
String result="";
String spaces="
";
if(t!=null) result=result+toString(t.right,pos+4)+spaces.substring(0,pos)
+String.format("%s%s",t.value,(t.color ? "/R" :"/B"))
+toString(t.left,pos+4);
else result=result+String.format("%n");
return result;
}
class Node{
Elem value;
Node left;
Node right;
boolean color;
Node(Elem x)
{ value=x; left = right = null; color = RED;}
}
}
B-drzewa.
Są to zrównoważone drzewa wielokierunkowe - naturalne uogólnienie 2-3-4 drzew.
Stosowane są w przypadku dużych słowników - nie mieszczących się w pamięci operacyjnej. Węzły tych drzew zawierają
więcej niż jeden obiekt (element słownika ) co zmniejsza liczbę odczytów z dysku, przez zmniejszenie
głębokości drzewa, a przez to przyspiesza działanie ( odczyt z dysku odbywa się zazwyczaj większymi porcjami więc
odczytanie 1 bajta i odczytanie kilkuset bajtów zabiera praktycznie tyle samo czasu).
Ponieważ różni autorzy przedstawiają nieco różne warianty tych drzew, wybrałem rozwiązania przedstawione przez
Cormena ("Wprowadzenie do algorytmów").
Węzeł (strona) B-drzewa rzędu M zawiera od M-1 do 2M-1 kluczy (czyli ma od M do 2M potomków, lub jest liściem ).
Wyjątkiem jest korzeń (może mieć mniej kluczy). Wszystkie liście drzewa leżą na tym samym poziomie.
Węzeł B-drzewa rzędu M ma następującą strukturę :
class Node
{ static int Size=... // 2* (rząd drzewa)-1
int numItems; // liczba kluczy na stronie
Object [ ]itemArray =new Object[size]; // tablica kluczy (mogą być kompletne obiekty)
Node[ ] childArray =new Node[size+1] // tablica potomków i-ty element to strona
} // zawierająca klucze mniejsze itemArray[i]
Klasa BTree ma tylko pole root - korzeń drzewa.
Wygodnie jest przyjąć, że puste drzewo to drzewo złożone z pustej (n==0) strony korzenia.
38
Przechodzenie przez drzewo w kolejności rosnących kluczy ( np. w celu wydrukowania wartości) :
void printBTree ( Node t)
{ for (int i=0; i< t.numItems;i++)
{ if ( t.childArray[i]!=null ) printBTree ( t.childArray[i]);
print( t.itemArray[i]);
}
}
Szukanie obiektu o kluczu k w B-drzewie o korzeniu t (sprawdzanie czy jest) :
boolean ( Node t , Object item)
{ int i=0;
int cmp=0;
while ( i0))
i++; // szukaj klucza >=item
if( i if (t.childArray[i]==null) return false; // doszliśmy do liścia, item nie ma
return find(t.childArray[i],item); // szukaj na stronie potomnej
}
Wstawianie nowego obiektu na stronę C. Możliwe są dwa przypadki:
1. Na stronie jest mniej niż 2M-1 kluczy - wstawiamy nowy klucz na odpowiednie miejsce tablicy kl;
2. Strona jest pełna (zawiera 2M-1 kluczy)
- przydzielamy pamięć na nową stronę D
- rozdzielamy 2M kluczy równo (prawie) na strony C i D, klucz środkowy wstawiamy do strony będącej teraz ojcem
stron C i D (powtarzamy krok 2 aż do usunięcia przepełnienia stron).
Ponieważ przenoszenie klucza w górę jest dość kłopotliwe, zastosujemy inne rozwiązanie. Ilekroć przy wyszukiwaniu
miejsca wstawienia mamy wejść na pełną stronę od razu ją dzielimy. Fizyczne wstawianie odbywa się wtedy na niepełną
stronę.
Usuwanie elementu nie jest proste ze względu na możliwość powstania niedomiaru (strony mającej mniej niż M-1 kluczy) ,
mamy trzy główne przypadki :
1. Usuwamy klucz k ze strony t będącej liściem (jest to zwykłe usunięcie elementu z tablicy)
2. Usuwamy klucz k ze strony t nie będącej liściem.
a. Niech y będzie synem t poprzedzającym k. Jeśli y ma co najmniej M kluczy, to w poddrzewie o korzeniu y wyznacz
poprzednik k' klucza k. Rekurencyjnie usuń k" i w węz
le t zastąp k przez k'.
b. Symetrycznie, jeśli syn z występujący po k w węz
le t, ma co najmniej M kluczy, to wyznacz następnik k' dla k w
poddrzewie o korzeniu z . Rekurencyjnie usuń k' i zastąp w x k przez k'.
c. Jeśli obaj synowie y i z mają tylko po M-1 kluczy, to przenieś k i wszystko z węzła z do y. Zwolnij pamięć
przydzieloną z i usuń rekurencyjnie k z y.
3. Jeśli klucz k nie występuje w wewnętrznym węz
le t, to wyznacz korzeń ws[i] poddrzewa w którym musi znajdować sie
k. Jeśli ws[i] ma tylko M-1 węzłów to wykonaj podkrok 3a lub 3b aby zapewnić, że zejdziemy rekurencyjnie do węzła z co
najmniej M kluczami. Usuń rekurencyjnie k z właściwego poddrzewa.
a. jeśli w węz
le ws[i] jest tylko M-1 kluczy, ale jeden z jego sąsiednich braci ma >=M kluczy, to umieść w ws[i]
dodatkowy klucz, przesuwając odpowiedni klucz z t, a w jego miejsce przenosząc klucz z lewego lub prawego brata
- tego który ma >=M kluczy (trzeba również przenieść odpowiadający mu wskaz
nik na syna)
b. jeśli ws[i] i sąsiedni bracia mają po M-1 kluczy to połącz ws[i] z jednym z sąsiednich braci, przesuwając odpowiedni
klucz z x do nowo powstałego węzła (zwolnij pamięć opróżnionej strony).
Tu są (a może będą) realizacje odpowiednich funkcji.
Przedstawione wcześniej 2-3-4 drzewa są odpowiednikami BDrzewa rzędu 2.
Drzewa pozycyjne.
Na koniec przedstawiam przykład pozycyjnego (cyfrowego) drzewa poszukiwań - w literaturze można znalez
ć inne drzewa
pozycyjne : TRIE, PATRICIA, TST itd.
39
Mogą one być stosowane gdy klucz jest ciągiem symboli z niewielkiego alfabetu. Np. ciąg liter, ciąg cyfr, ciąg
niewielkich liczb, czy też kreska-kropka (jak w alfabecie Morse'a). Zakładamy, że łatwo możemy przetworzyć każdy
symbol na wartość liczbową .
Korzeń pustego drzewa stanowi węzeł bez wartości (dane = wartość pusta) który wszystkie adresy ma ustawione na
NULL.
Jak wyglądają poszczególne działania na takim drzewie ?
1. Szukanie węzła o danym kluczu (kl) w drzewie o korzeniu t:
Schodzimy po gałęziach drzewa wyznaczonych przez kolejne pozycje klucza - możliwe są trzy zakończenia :
1. doszliśmy do końca drzewa, a nie wykorzystaliśmy wszystkich pozycji klucza
- węzła o takim kluczu nie ma w drzewie
2. Wyczerpaliśmy klucz (sprawdzamy pole dane w osiągniętym węz
le)
a. ma wartość - jest to szukany węzeł
b. ma wartość nieokreśloną (0) nasz klucz jest przedrostkiem klucza istniejącego w drzewie węzła ale
sam nie ma wartości
2. Wstawianie węzła o kluczu kl do drzewa o korzeniu t.
Najpierw schodzimy po drzewie ( tak jak przy szukaniu ):
1.Skończyl się klucz na węz
le w
a. w ma ustawioną wartość - węzeł już jest w drzewie (błąd ?)
b. węzeł nie ma wartości - wpisujemy do węzła wskaz
nik wartości
2.Skończyło się drzewo - musimy wytworzyć ciąg węzłów odpowiadający niewykorzystanym pozycjom klucza
(wszystkie oprócz ostatniego maja wartość pusta, ostatni ma wartość )
3. Usuwanie z drzewa o korzeniu t węzła o kluczu kl. (zakładamy że węzeł jest w drzewie)
Najpierw schodzimy do usuwanego węzła (rekurencyjnie) i ustawiamy mu wartość pusta. Wracając sprawdzamy czy
dany węzeł jest liściem z pustą wartością : jeśli tak to go usuwamy (nie wolno usunąć korzenia ).
Charakterystyczną cechą drzew cyfrowych jest to że czas znalezienia węzła nie zależy od liczby wierzchołków a jedynie od
długości klucza (zazwyczaj jest mniejszy niż w drzewach binarnych). Każdy zbiór kluczy ma jedyną reprezentację - nie ma
drzew gorszych i lepszych. Niestety wymagają one sporo pamięci - możliwe są różne rozwiązania kombinowane
redukujące tę wadę.
Jako ciekawostkę można dodać, że tak naprawdę to drzewo pozycyjne nie jest drzewem ale lasem ( a jeśli wszystkie klucze
mają jednakową długość to nawet żywopłotem ).
Zadania :
24) Jaką kolejność przechodzenia drzewa wykorzystasz do zapisania elementów drzewa w pliku. Po odczytaniu z pliku i
wykonaniu ciągu wstawień powinna zostać odtworzona struktura drzewa.Nie wykorzystuj możliwości serializacji.
25) Wytwarzany w przykładzie (BST.java) wydruk wymaga przechylania głowy przy czytaniu. Opracuj metodę
drukującą drzewo wierszami. Podpowiedz
: rozważ przydatność wykorzystania kolejki.
26) Jak wygląda drzewo binarne reprezentujące wyrażenie. Jaką kolejność przechodzenia zastosujesz do obliczania
wartości tego wyrażenia.
27) Zaimplementuj inne metody przetwarzające drzewo, których wynikiem będzie :
- liczba węzłów drzewa
- liczba węzłów wewnętrznych
- liczba węzłów z jednym ( dwoma) potomkiem
- liczba liści
- liczba węzłów zewnętrznych
- liczbę węzłów mniejszych od korzenia
- głębokość węzła
- wysokość poddrzewa którego korzeniem jest dany węzeł itp.
28) Zaimplementuj metody wpisującemu każdemu węzłowi drzewa ( w dodatkowym polu) wartości z poprzedniego
zadania.
29) Znajdz
w drzewie największy z węzłów nie większych ( mniejszych ) od danego.
30) Utwórz BDrzewo ( rzędu 2) wstawiając do niego kolejne wartości od 1 do 13. Zwróć uwagę na sytuacje wymagające
przebudowy drzewa. Z tak zbudowanego drzewa usuwaj kolejno elementy : 8, 9, 1, 2, 3 itd.
40
Tablice haszowane.
Gdyby wszystkie klucze były różne i miały wartości z niewielkiego zakresu 0..M-1, można by było zastosować prostą
tablicę indeksowaną kluczem elementów.
Najczęściej jednak możliwych wartości klucza jest zbyt wiele, wówczas stosujemy haszowanie ( mieszanie).
Stosujemy je jeśli potrafimy zbudować funkcję przyporządkowującą każdemu kluczowi wartość z przedziału 0..M-1.
Zazwyczaj zbiór możliwych wartości kluczy jest bardzo duży, o wiele większy od liczby pamiętanych elementów. Np.
zbiór słów o długości mniejszej od 15 liter (polskiego alfabetu ) ma liczność około 2E24, podczas gdy duże słowniki
zawierają około 100000 haseł, duże zbiory indeksowane nazwiskiem mogą mieć np. 10000000 elementów. Idea polega na
tym by element el zapisać w tablicy na pozycji h(el). Oczywiście h nie jest funkcją różnowartościową, więc pojawiają się
kolizje (dwa lub więcej kluczy daje tę samą wartość h(el)) sposób ich rozwiązywania zależy od realizacji tablicy
haszowanej.
a) tablica statyczna
Zapis elementu do tablicy :
IF (pozycja h(el) jest wolna ) zapisz element
ELSE znajdz
pierwszą wolną pozycję (od h(el) cyklicznie)
zapisz element na wolnej pozycji
Wyszukanie (dla uproszczenia - zawsze istnieje jedna wolna pozycja) :
IF (na pozycji h(el) jest właściwy element) znalazłeś
ELSE szukaj cyklicznie do znalezienia lub trafienia na wolną
IF (koniec na wolnej pozycji ) nie ma
ELSE znalazłeś
Wyszukiwanie może być (w najgorszym przypadku) czasochłonne, ale jest proste, trochę gorzej jest z usuwaniem
elementu .
Przedstawiony powyżej algorytm rozstrzygania konfliktów nazywa się adresowaniem ( sondowaniem) liniowym. Jeśli
oznaczymy przez k klucz szukanego elementu ,H funkcję mieszającą, N- liczbę elementów (rozmiar) tablicy oraz h
i
pozycję sprawdzana w i-tym kroku, to ciąg h wygląda następująco :
i
h =H(k)
0
h =(h +i) mod N
i 0
Ta metoda nie zabezpiecza jednak przed grupowaniem się elementów. Lepsze efekty daje mieszanie podwójne (H
oznacza drugą funkcję haszującą):
h =H(k)
0
h =(h +i*H (k)) mod N
i 0
W tym przypadku krok H' i rozmiar tablicy N powinny być względnie proste. Niestety nie ma prostego sposobu usuwania
elementów. W razie konieczności usuwania można zastosować znacznik dla elementów usuniętych. Taki element jest
traktowany jako wolny przy wstawianiu, a jako zajęty ale o wartości pustej przy wyszukiwaniu. Niestety może to
prowadzić do szybszego zapełniania tablicy.
Inną możliwością, jest stworzenie (wspólnego dla wszystkich pozycji tablicy) obszaru przeniesień, przeszukiwanego
liniowo w przypadku wystąpienia kolizji. Jest to rozwiązanie nieco lepsze (dające prostsze algorytmy) lecz wymagające
większej pamięci.
Istnieje jeszcze trzecie rozwiązanie - można przyspieszyć wyszukiwanie łącząc pozycje zawierające elementy o tej samej
wartości w listę.
Naturalnym rozszerzeniem ostatniego podejścia jest :
b. tablica list
Takie rozwiązanie zdecydowanie upraszcza algorytmy (szczególnie usuwanie elementu) dając o wiele lepsze
wykorzystanie pamięci.
Haszowanie jest skuteczną metodą reprezentacji słownika jeśli potrafimy dobrze dobrać funkcję haszującą (tak aby dawała
równomierny rozrzut elementów w tablicy - niestety nie jest to proste). Można to zrobić eksperymentalnie dla słownika
stałego ( bez Wstaw i Usun). Przy zmiennym słowniku sytuacja jest gorsza (najgorsza gdy wszystkie elementy mają taką
41
samą wartość h(el)). Dodatkowo na efektywność tej metody wpływa stopień zapełnienia tablicy (czym mniej wolnych
miejsc tym gorzej).
Oznaczając przez ą stopień zapełnienia tablicy (liczba zapisanych elementów / rozmiar) otrzymujemy następujące wyniki:
algorytm liczba prób dla el " słownika liczba prób dla el " słownika
tablica list 1+ą/2 1+ą
adresowanie liniowe 0.5+ 1/(2*(1-ą)) 0.5+1/(2*(1-ą )2)
mieszanie podwójne -ln(1-ą)/ą 1/(1-ą)
Przykładowe wartości liczby sondowań w zależności od
wypełnienia tablicy - ą 1/2 2/3 3/4 9/10
tablica list  trafione 1,25 1,33 1,38 1,45
tablica list  chybione 1,5 1,67 1,75 1,9
adresowanie liniowe  trafione 1,5 2,0 3,0 5,5
adresowanie liniowe  chybione 2,5 5,0 8,5 55,5
podwójne mieszanie  trafione 1,4 1,6 1,8 2,6
podwójne mieszanie  chybione 2.0 3,0 4,0 9,0
Widać, że liczba prób nie zależy od wielkości tablicy lecz tylko od stopnia jej zapełnienia.
Porównanie złożoności poszukiwania dla różnych sposobów implementacji słownika :
pesymistyczny średni
wstawianie wyszukiwanie wstawianie wyszukiwanie
trafione chybione
tablica indeksowana kluczem 1 1 1 1 1
tablica (lista) uporządkowana n n n/2 n/2 n/2
tablica (lista) nieuporządkowana 1 n 1 n/2 n
wyszukiwanie binarne n lg n n/2 lg n lg n
BST n n lg n lg n lg n
AVL lub czarno-czerwone lg n lg n lg n lg n lg n
BST randomizowane n* n* lg n lg n lg n
mieszanie 1 n* 1 1 1
* - oznacza sytuację możliwą ale bardzo mało prawdopodobną
Zadania :
31) Dla wybranego przez siebie ciągu elementów, wielkości tablicy i funkcji haszujących zbadaj różnice w liczbie
konfliktów przy sondowaniu liniowym i podwójnym haszowaniu.
Temat 9. Algorytmy grafowe.
Zbiory rozłączne
Dane jest n elementów pogrupowanych w pewną liczbę zbiorów rozłącznych. Każdy zbiór jest identyfikowany przez
swojego reprezentanta. Wykonujemy na nich tylko dwie operacje : znajdowanie zbioru do którego należy dany element
oraz łączenie dwóch zbiorów.
MAKE_SET(x) - tworzy zbiór, którego jedyny element jest wskazany przez x.
UNION(x,y) - łączy dwa zbiory zawierające odpowiednio x i y, w jeden.
FIND(x) - zwraca wskaz
nik do reprezentanta zbioru zawierającego x.
A. Prosta realizacja lasu zbiorów rozłącznych.
Struktura elementu : class Elem { Object val; Elem parent; ...};
void MAKE_SET( Elem x)
{x.parent = x; }
42
void UNION ( Elem x , Elem y)
{ LINK(FIND(x),FIND(y)); }
void LINK ( Elem x, Elem y)
{ y.parent = x; }
Elem FIND( Elem x )
{ return x = = x.parent ? x : FIND(x.parent) ;}
B. Realizacja lasu z równoważeniem wysokości drzew.
Struktura elementu : class Elem {Object val; Elem parent; int height;};
void MAKE_SET( Elem x)
{x.parent = x; x.height=0; }
void UNION ( Elem x , Elem y)
{ LINK(FIND(x),FIND(y)); }
void LINK ( Elem x, Elem y)
{ if (x.height > y.height) y.parent=x;
else {x.parent=y;
if (x.height == y.height)
y.height++;
}
Elem FIND( Elem x )
{ return x == x.parent ? x : FIND(x.parent) ;}
C. Realizacja lasu z kompresją ścieżki.
Struktura elementu : class Elem {Object val ; Elem parent; };
void MAKE_SET( Elem x)
{x.parent = x; }
void UNION ( Elem x , Elem y)
{ LINK(FIND(x),FIND(y)); }
void LINK ( Elem x, Elem y)
{ y.parent = x; }
Elem FIND( Elem x )
{ if (x != x.parent) x.parent = FIND(x.parent);
return x.parent ;}
Można połączyć rozwiązania B i C.
Grafy - reprezentacje grafów, podstawowe algorytmy grafowe
Reprezentacje grafów :
1. Lista sąsiedztwa (LS)
2. Macierz sąsiedztwa (MS)
3. Lista krawędzi (LK)
A. Przeszukiwanie (przechodzenie) grafu.
43
Przyjmujemy, że graf jest reprezentowany przez listę sąsiedztwa (LS) oraz każdy wierzchołek ma pole "odwiedzony".
1. Przeszukiwanie grafu wszerz (algorytm BFS - Breadth First Search)
Pomocniczo wykorzystujemy procedury obsługi kolejki:
CLEAR - utwórz pustą kolejkę
IS_EMPTY - czy kolejka jest pusta ?
ENQUEUE - wstaw do kolejki
DEQUEUE - pobierz z kolejki (funkcja)
Przechodzenie rozpoczynamy od wierzchołka s. Zakładamy, że graf jest spójny. Jeśli nie należy dodać zewnętrzną pętlę.
BFS(s)
for each u" V- {s}
u.odwiedzony = false
s.odwiedzony = true
CLEAR
ENQUEUE(s)
while not IS_EMPTY
u = DEQUEUE
//wykorzystaj u
for each v"LS[u]
if not v.odwiedzony then v.odwiedzony = true
ENQUEUE(v)
2. Przeszukiwanie grafu wzdłuż (algorytm DFS - Deep First Search)
DFS(s) { Przechodzenie rozpoczynamy od wierzchołka s.}
for each u" V-{s}
u.odwiedzony = FALSE
s.odwiedzony = TRUE
DFS_V(s)
DFS_V(u);
//wykorzystaj u
u.odwiedzony = true
for each v"LS[u]
if not v.odwiedzony then DSF_V(v)
B. Minimalne drzewo rozpinające.
Algorytm Kruskala.
Danymi dla tego algorytmu są: zbiór wierzchołków grafu (V) i lista jego krawędzi (LK) uporządkowana rosnąco ze
względu na wagi. Wynikiem jest zbiór MST (Minimal Spanning Tree) zawierający krawędzie tworzące drzewo rozpinające
o minimalnej sumie wag krawędzi.
Pomocniczo wykorzystamy procedury obsługi zbiorów rozłącznych MAKE_SET,FIND i UNION.
Przedstawiony algorytm należy do klasy algorytmów zachłannych.
MST_KRUSKAL
MST = {} {zbiór pusty}
for each v"V
MAKE_SET(v)
for each " LK
if FIND(u) <> FIND(v) then
MST = MST *" {}
UNION(u,v)
Złożoność O( |E| log|E| ).
Inny algorytm został zaproponowany przez Prima.
44
Dane to: zbiór wierzchołków grafu (V), każdy wierzchołek v jest wzbogacony o dwa pola : prev - wskazuje wierzchołek
drzewa z którym łączy się v, pr - priorytet, czyli odległość wierzchołka od już zbudowanej części drzewa. Algorytm
wykorzystuje kolejkę priorytetową wierzchołków uporządkowaną według rosnącego pola pr i listę sąsiedztwa (LS).
Dodatkowe operacje kolejki :
IN_QUEUE (v) - czy element v jest w kolejce
MOD_PRIORITY(v, prior) - ustaw nowy priorytet elementu v i przebuduj kolejkę.
Budowę drzewa rozpoczyna się od wskazanego wierzchołka startowego s .
Pomocnicza operacja to :
INIT (s)
for each v"V-{s}
v.pr =
ENQUEUE(v)
s.pr = 0 s.prev = null ENQUEUE(s)
MST_PRIM( s )
INIT(s)
while not IS_EMPTY
u=DEQUEUE
for each v" LS(u)
if IN_QUEUE(v) and (w < v.pr )
v.prev = u
MOD_PRIORITY( v, w )
Złożoność obliczeniowa : O( |E| log |V| ).
Tym razem MST jest zapisane w sposób niejawny - poprzez pola prev.
C. Najkrótsza ścieżka między dwoma wierzchołkami.
Algorytm Dijkstry.
Zakładamy, że mamy ważony graf skierowany o nieujemnych wagach krawędzi. Należy znalez
ć najkrótszą drogę od
z
ródła s do ujścia w. Danymi do tego algorytmu jest lista sąsiedztwa grafu(LS- z zapisanymi wagami krawędzi ).
Dodatkowymi danymi związanymi z każdym węzłem (należącym do zbioru V) są : pr - priorytet wierzchołka czyli
odległość od z
ródła, oraz prev - węzeł poprzedzający na najkrótszej ścieżce. Wykorzystujemy zbiór S - węzłów już
wykorzystanych oraz kolejkę priorytetową (uporządkowaną według niemalejącej odległości od z
ródła) .
Pomocnicze operacje :
INIT(s) // patrz wyżej
RELAX(u,v)
if v.pr > u.pr + w
then MOD_PRIORITY(v, u.pr + w)
v.prev=u
DIJKSTRA(s ,w)
INIT(s)
while not IS_EMPTY
u=DEQUEUE
for each v"LS[u]
RELAX(u,v)
PRINT(s,w)
PRINT ( s, v)
if v = s then write s
else PRINT (s, v.prev)
write v
Jeśli wykorzystamy kolejkę priorytetową wykorzystując kopiec, to złożoność wynosi O(|E|log|V|). Algorytm ten jest
bardzo podobny do algorytmów BSF i MST_PRIM.
Algorytm Bellmana-Forda.
Tym razem wagi krawędzi mogą być ujemne, ale nie mogą istnieć cykle o ujemnej wadze ( algorytm sam wyjrywa czy są
takie). Znajdujemy najkrótszą drogę od z
ródła s do ujścia w. Danymi do tego algorytmu jest lista krawędzi (LK- z
45
zapisanymi wagami krawędzi ). Dodatkowymi danymi związanymi z każdym węzłem (należącym do zbioru V) są : pr -
priorytet wierzchołka czyli odległość od z
ródła, oraz prev - węzeł poprzedzający na najkrótszej ścieżce. Tym razem nie
wykorzystujemy kolejki więc upraszcza się metoda MOD_PRIORITY ( modyfikuje tylko pole pr ).
BELLMAN_FORD (s ,w)
INIT(s)
for i =1 to |V|-1
for each "LK
RELAX(u,v)
for each "LK
if v.pr > u.pr +w
return false
PRINT(s,w)
return true
Złożoność tego algorytmu to O(|V|*|E|).
Uwaga : w obu algorytmach można zrezygnować z pola prev - ścieżkę zawsze można odtworzyć korzystając z
wyznaczonych wartości pola pr i wag krawędzi.
Temat 10. Algorytmy geometryczne.
Pojęcia podstawowe : punkt, odcinek, wektor, prosta.
Problemy :
- po której stronie wektora p->q leży punkt r
- czy punkty x i y leżą po tej samej stronie prostej p-q
- czy punkt r należy do odcinka p-q
- czy podcinki p-q i r-s przecinają się
- czy punkt p leży wewnątrz wielokąta W
a. W jest wielokątem wypukłym
b. W jest dowolnym wielokątem
- Znajdowanie otoczki wypukłej zbioru punktów
a. algorytm Grahama
b. algorytm Jarvisa
c. algorytm przyrostowy
Temat 11. Przetwarzanie tekstów .
- wyszukiwanie wystąpień wzorca w tekście
Prosty interfejs do wyszukiwania wzorca w tekście począwszy od wskazanej pozycji :
package ssearching;
public interface StringSearcher { public int search(CharSequence text, int from); }
a. algorytm naiwny (siłowy - brute force)
package ssearching;
public class BruteForceSearcher implements StringSearcher {
private final CharSequence _pattern;
public BruteForceSearcher(CharSequence pattern)
{ _pattern = pattern; }
public int search(CharSequence text, int from) {
int s = from;
while (s <= text.length() - _pattern.length()) {
int i = 0;
while (i < _pattern.length() && _pattern.charAt(i) == text.charAt(s + i))
++i;
if (i == _pattern.length()) return s;
++s;
}
return -1;
46
}
}
b. algorytm Knutha-Morrisa-Pratta
package ssearching;
public class KnuthMorrisPrattSearcher implements StringSearcher
{ private final CharSequence _pattern;
private final int[] _shuffle;
public KnuthMorrisPrattSearcher(CharSequence pattern)
{ _pattern = pattern;
_shuffle = computeShuffle(pattern);
}
public int search(CharSequence text, int from) {
int s = from;
int i = 0;
while (s <= text.length() - _pattern.length()) {
i=_shuffle[i];
while (i <_pattern.length() && _pattern.charAt(i) == text.charAt(s + i))
++i;
if (i >=_pattern.length())
return s;
s += Math.max(1,i-_shuffle[i]);
}
return -1;
}
private static int[] computeShuffle(CharSequence pattern) {
int[] shuffle = new int[pattern.length()];
shuffle[0]=0;
int tmp=0;
for (int i = 1; i < pattern.length(); ++i){
while (tmp>0 && pattern.charAt(tmp) != pattern.charAt(i))
tmp=shuffle[tmp];
if(pattern.charAt(tmp)==pattern.charAt(i))
tmp++;
shuffle[i]=tmp;
}
return shuffle;
}
}
c. algorytm Boyera-Moore'a
package ssearching;
public class BoyerMooreSearcher implements StringSearcher {
/** The supported character set size (ASCII). */
private static final int CHARSET_SIZE = 256;
private final CharSequence _pattern;
/** The position (0, 1, 2...) of the last occurrence of each character within the pattern. */
private final int[] _lastOccurrence;
public BoyerMooreSearcher(CharSequence pattern) {
_pattern = pattern;
_lastOccurrence = computeLastOccurrence(pattern);
}
public int search(CharSequence text, int from) {
int s = from;
47
while (s <= text.length() - _pattern.length()) {
int i = _pattern.length() - 1;
char c = 0;
while (i >= 0 && _pattern.charAt(i) == (c = text.charAt(s + i)))
--i;
if (i < 0)
return s;
s += Math.max(i - _lastOccurrence[c], 1);
}
return -1;
}
private static int[] computeLastOccurrence(CharSequence pattern) {
int[] lastOccurrence = new int[CHARSET_SIZE];
for (int i = 0; i < lastOccurrence.length; ++i)
lastOccurrence[i] = -1;
for (int i = 0; i < pattern.length(); ++i)
lastOccurrence[pattern.charAt(i)] = i;
return lastOccurrence;
}
}
d. algortym Karpa-Rabina
package ssearching;
public class KarpRabinSearcher implements StringSearcher {
private final CharSequence _pattern;
private static int chars=256; //liczność alfabetu
private static int q=8388607; //liczba pierwsza taka że q*chars < MAX_INT
private int cm; //chars do potęgi pattern.length()-1 modulo q
private int hp; //funkcja haszująca wzorca
public KarpRabinSearcher(CharSequence pattern)
{_pattern = pattern;
hp=h(pattern);
cm=computeCM(pattern.length());}
public int search(CharSequence text, int from) {
int s = from;
int ht=h(text.subSequence(s,s+_pattern.length()));
while (s <= text.length() - _pattern.length()) {
if(hp==ht) return s;
if(s < text.length() - _pattern.length())
ht=((ht-text.charAt(s)*cm)*chars+text.charAt(s+_pattern.length()))%q;
s++;
}
return -1;
}
private int computeCM(int m)
{ int res=1;
for(int i=1;ires=(res*chars)%q;
return res;
}
private int h(CharSequence s)
{ int res=s.charAt(0);
for(int i=1;ires=(res*chars+s.charAt(i))%q;
return res;
}
}
Prosta klasa do testowania wyszukiwarek :
48
package ssearching;
import java.io.*;
public class TestStringSearcher
{ void test(){
CharSequence text= "aaaaaaaaaaaaaababababacaaaaaa";
CharSequence pattern = "ababababac";
StringSearcher ss1 = new BruteForceSearcher(pattern),
ss2 = new BoyerMooreSearcher(pattern),
ss3 = new KnuthMorrisPrattSearcher(pattern),
ss4 = new KarpRabinSearcher(pattern);
System.out.println(" ss1 = " + ss1.search(text,0));
System.out.println(" ss2 = " + ss2.search(text,0));
System.out.println(" ss3 = " + ss3.search(text,0));
System.out.println(" ss4 = " + ss4.search(text,0));
}
}
- kompresja tekstu ( kodowanie )
a. algorytm Huffmana
I to by było na tyle - na razie, bo parę rzeczy wymaga uzupełnienia.
jr
Będę wdzięczny za wszelkie ( poza wytykaniem literówek ) uwagi dotyczące przedstawionego materiału.