Temat 3. Listy ich implementacja i przetwarzanie.

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:

n FIFO (First In First Out) - typowa kolejka

n LIFO (Last In First Out) - patrz niżej

- priorytetowe (wcześniej są pobierane elementy o wyższym priorytecie) - te będą omówione póź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

}

 

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();

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:

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.

 

 

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<right? i:i-1;

}

 

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);

}

}

}

- 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 znaleźć w {Bentley J. – „Perełki oprogramowania”]

2. QuickSort jest wyraź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)

 

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();

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 znaleźć 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ównaniudo 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.

 

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

weź kolejny element i umieść go w kolejce wyznaczonej przez wartość klucza

(jeśli klucz ma wartość i to w i-tej kolejce)

2. wyprowadź (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<n; i++) DoKolejki(el[i]);

2. for (i=0; i<n; i++) ZKolejki(element)

Drukuj(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; i<n; i++)

pr=floor (el[i]/X*M)

DoKolejki(pr,el[i])

2. for (pr=0; pr <M;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]

 

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; i<N;i++)

DoKolejki(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(n²)

 

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<K;i++) b[i]=0;

for(i=0; i<n;i++) b[a[i]]++;

for(i=1;i<n;i++) b[i]+=b[i-1];

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 znaleźć 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óź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

Sortowanie polifazowe

 

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)

sprawdź 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. Sprawdź 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.

 

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.

 

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 (i<t.numItems && ((cmp=comparator.compare(item,t.itemArray[i])) >0))

i++; // szukaj klucza >=item

if(i<t.numItems && cmp= =0) return true; // znaleziono

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ęźle t zastąp k przez k'.

b. Symetrycznie, jeśli syn z występujący po k w węź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ęź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ęź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 wskaź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 znaleźć inne drzewa pozycyjne: TRIE, PATRICIA, TST itd.

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ęź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ęź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 wskaź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. Podpowiedź: 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) Znajdź 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.

 

 

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 znajdź 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_i wygląda następująco:

h₀=H(k)

h_i=(h₀+i) mod N

 

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)

h_i=(h₀+i*H’(k)) mod N

 

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ą samą wartość h(el)). Dodatkowo na efektywność tej metody wpływa stopień zapełnienia tablicy (czym mniej wolnych miejsc tym gorzej).

Oznaczając przez a 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+a/2 1+a

adresowanie liniowe 0.5+ 1/(2*(1-a)) 0.5+1/(2*(1-a)²)

mieszanie podwójne -ln(1-a)/a 1/(1-α)

 

Przykładowe wartości liczby sondowań w zależności od

wypełnienia tablicy - a 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 wskaź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; }

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)

 

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;

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;i<m;i++)

res=(res*chars)%q;

return res;

}

 

private int h(CharSequence s)

{ int res=s.charAt(0);

for(int i=1;i<s.length();i++)

res=(res*chars+s.charAt(i))%q;

return res;

}

}

Prosta klasa do testowania wyszukiwarek:

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.

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;

 

// znajdź 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();

}

 

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();

}

}