tablice.pdf

========================================================================

Wybrane struktury danych w języku Java

==========================================================================

Jeżeli chcemy mieć w programie dane, które będą ze sobą powiązane i będziemy na nich wykonywać podobne

operacje wygodnie jest umieścić je w „jednym miejscu”. Wygodnie jest posłużyć się wbudowanymi w język typem

tablicowym lub klasami kontenerowymi (dynamiczne struktury danych).

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

---

1. Tablice

---

Do przechowywania nie więcej niż określonej liczby elementów typu podstawowego lub dowolnego obiektowego

służą tablice.

1.1 Deklaracja i inicjalizacja zmiennej tablicowej

Deklaracja :

nazwa_typu_elementów [] nazwa_tablicy ;

nazwa_typu_elementów nazwa_tablicy [] ;

// specjalnie dla programistów C++

na przykład:

int [] a;

String [] słowa;

public class punkt {

public punkt(int x, int y) {

X = x;

Y = y;

private double X;

private double Y;

}

punkt [] x;

powoduje ona utworzenie referencji do tablicy obiektów określonego rodzaju. Aby jednak użyć tablicy, musimy

utworzyć nowy obiekt tablicowy (instancję) za pomocą operatora n ew, c zyli zainicjalizować tablicę. Określamy

wówczas rozmiar tablicy:

słowa = new String [4] ;

a = new int [n + 5] ;

// rozmiar możemy określić za pomocą wyrażenia

Random g = new Random();

// albo jako liczbę losową !!!

long [] tab;

tab = new long [g.nextInt()];

W przypadku tablicy obiektów typu podstawowego nastąpi zainicjalizowanie elementów domyślnymi

wartościami (0 dla typów liczbowych i char oraz false dla boolean). Jeżeli elementy są obiektami to tablica będzie

zawierać referencje (do null ) a nie konkretne obiekty.

1.2 Rozmiar i numeracja

Rozmiar tablicy jest przechowywany w polu length . Możemy, zatem w dowolnym miejscu ją odczytać:

nazwaTablicy.length

Elementy tablicy są numerowane od zera . Zatem możemy odwoływać się do elementów z zakresu [0,length-1].

for(int i = 0; i < a.length; i++)

a[i] = i;

W przeciwieństwie do tablic z C++ w języku Java, sprawdza się czy odwołania do składowych tablicy są

poprawne. Jeżeli spróbujemy odwołać się do elementu z poza dozwolonego zakresu zostanie zgłoszony wyjątek

ArrayIndexOutOfBoundException .

1.3 Łączenie deklaracji i inicjalizacji

Deklarację oraz utworzenie obiektu tablicowego możemy połączyć w jedną instrukcję:

typ [] nazwaTablicy = new typ [rozmiar];

Ponadto dozwolone jest również jednoczesne zadeklarowanie i utworzenie tablicy oraz inicjalizacja jej elementów:

int [] pierwsze = {1, 2, 3, 4 + 1, 7, 11};

String [] muszkieterzy = {"Atos", "Portos", "Aramis"};

punkt [] trojkat = puntk { new punkt(0,0),

new punkt(3,0),

new punkt(3,4), };

// ostatni przecinek jest opcjonalny

// dlatego został wcześniej pominięty

Jak widać nie ma konieczności używania operatora new !

1.4 Używanie tablic

Dostęp do składowych tablicy uzyskujemy za pomocą operatora indeksującego [ ] .

nazwaTablicy[indeks_ekenetu];

Kopiowanie fragmentów lub całych tablic możemy wykonać w pętli:

int [] liczby3 = new int[13];

for(int i = 0; i < 8; i++)

// inicjalizujemy elementy tablicy liczbami 0, 3, 6, 9, 12, 15, 18, 21

liczby3[i] = i * 3;

int [] tab = { 24, 27, 30, 33, 36};

// tworzymy drugą tablicę

for(int k=0; k < 5; k++ )

// kopiujemy liczby 24, 27, 30, 33, 36

liczby3[8 + k] = tab[k];

albo możemy wykorzystać funkcję arraycopy() z klasy System:

void System.arraycopy(src, srcPos, dest, destPos, n )

gdzie: src - nazwa tablicy z której kopiujemy elementy

srcPos - początkowy indeks od którego będą odczytywane elementy

dest - tablica do której będą kopiowane argumenty

destPos - początkowy indeks od którego zostaną zapisywane elementy

- ilość elementów do skopiowania

Zatem następuje przekopiowanie skopiowanie n elementów od src[srcPos] do src[srcPos + n - 1] i zostaną one

skopiowane na miejsce elementów od des[destPos] do des[desPos + n - 1] . Dla powyższego przykładu:

System.arraycopy( tab, 0, liczby3, 8, 5 );

W przypadku wywołania funkcji arraycopy dla tablicy zawirającej obiekty a nie typy podstawowe, kopiowane są

referencje a nie same obiekty. Tekie zachowanie nazywa się kopiowaniem płytkim .

Ponadto Java udostępnia kilka ciekawych funkcji do obsługi tablic w klasie java.util.Arrays :

void sort (tab) - sortuje tablicę stosując algorytm QuickSort

void sort (tab, pocz, przedOst) - sortuje fragment tablicy od elementu [pocz, przedOst) od elementu

o indeksie pocz włącznie do elementu przedOst bez niego

czyli dokładnie przedOst-pocz elementów

int binarSearch (tab, elem)

- zwraca indeks elementu elem w tablicy tab , tablica musi być posortowana

jeśli nie jest to wynik jest niezdefiniowany, jeżeli nie znaleziono elementu w

tablicy zwracana jest liczba – (tab.length + 1)

import java.util.Arrays;

import java.util.Random;

class HelloKNI {

public static void main(String[] args) {

Random losuj = new Random();

int [] kilkaNaturalnych ;

kilkaNaturalnych = new int [10];

kilkaNaturalnych[0] = 55;

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

kilkaNaturalnych[i] = losuj.nextInt(101);

Arrays.sort(kilkaNaturalnych);

System.out.println(Arrays.binarySearch(kilkaNaturalnych, 55));

System.out.println(Arrays.binarySearch(kilkaNaturalnych, 101));

}

boolean equals (tab1, tab2)

- porównuje dwie tablice (ilość elementów i wartośći)

String toString (tab)

- wyświetla tablicę

System.out.print("kilkaNauturalnych: ");

System.out.println(Arrays.toString(kilkaNaturalnych));

void fill (tab, wart) - przypisuje wszystkim elementom tablicy tab wartość wart

void fill (tab, pocz, przedOst, wart) - jw. ale w przedziale [pocz, przedOst)

1.5 Tablice wielowymiarowe

Tablice wielowymiarowe to tablice których elementami są tablice.

przykład1:

int [ ] [ ] macierz = { {1, 2, 3},

{4, 5 ,6},

}

przykład2:

boolean [][] szachownica;

szachownica = new boolean [8][8];

szachownica[0][0] = true;

szachownica[1][0] = false;

//...

przykład3:

class Kolor {

private String kolor;

public Kolor(String k) {

kolor = k;

}

//…

}

Kolor [][][] rgb = new Kolor [256][256][256];

rgb[0][0][0] = new Kolor("black");

rgb[255][255][0]

= new Kolor("yellow");

//...

---

2. Kontenery

---

W przypadku konieczności przechowywania nieznanej liczby obiektów lub zapewnienia określonej struktury

elementów wykorzystuje się klasy kontenerowe. Można je podzielić na 2 kategorie: kolekcje (ang. collection ) oraz

odwzorowania (tablice asocjacyjne, ang. map ).

Collection obejmuje kontenery, których elementy podlegają określonym regułom: np. elementy listy list są

przechowywane w określonej kolejności, zaś zbioru set nie mogą się powtarzać.

Odwzorowania to obiekty przechowujące pary typu klucz – wartość. Można je traktować jak tablice,

których elementami są zmienne wartość zaś indeksy to zmienne reprezentowane przez klucze .

Aby wygodnie umieszczać w kontenerze, usuwac z niego lub też po prostu odczytywać elementy możemy

posłużyć się (poza odpowiednimi dla danego kontenera funkcjami) odpowiednim obiektem zwanym iteratorem .

Jest on podobny do wskaźnika z tym, że jest on zaimplementowany tak, iż można nim operować na każdym typie

kontenera (z pewnymi ograniczeniami). On sam "wie" jak przechodzić po elementach danego kontenera. Stąd

napisany w ten sposób kod jest bardziej uniwersalny - można zmienić deklaracją typu kontenera bez zmiany funkcji

na nim operujących. Oprócz uniwersalnej klasy Iterator dla kontenerów ArrayList i LinkedList dostępny jest

ListIterator .

Innym sposobem zachowania ogólności jest zastosowanie interfejsów . Nie jest to pojęcie specyficzne dla

kontenerów jest szczególnym aspektem całego języka Java. Bez wnikania w szczegóły można powiedzieć iż

interfejs klasy to zbiór metod jakie możemy wykonywać na rzecz obiektów danej klasy. Zaleca się stosowanie

ogólnego interfejsu List, Map lub Map dla zadeklarowania referencji a następnie przy tworzeniu instancji

sprecyzowanie o jaką dokładnie klasę chodzi.

np.: List x = new LinkedList();

lub jeszcze bardziej ogólnie: Collection z = new LinkedList();

chociaż oczywiście można tak: LinkedList y = new LinkedList();

2.1 Uproszczona hierarchia klas kontenerowych

Collection

List Set Map

ArrayList LinkedList HashSet TreeSet HashMap WeakHashMap TreeMap

Na powyższym diagramie zaprezentowane są klasy kontenerowe (linie ciągłe) oraz interfajesy (linie przerywane)

implementowane przez dane klasy. Nie uwzglednia on starszych klas kontenerowych: Hashtable implementującej

interfejs Map oraz Vector (jak również dziedziczącej po niej klasy Stack) implementującej interfejs List.

Do wersji 1.4 języka Java nie można było używać jako kontenerów zawierających obiekty a jedynie

zawierające referencje do obiektów klasy Object będącą klasą bazową dla wszystkich pozostałych klas.

2.2. Typy generyczne (parametryzowane, szablonowe)

W wersji 1.5 języka Java wprowadzono kilka istotnych zmian. Jedną z nich jest wprowadzenie

sparametryzowanych typów kontenerowych – tzw. typów generycznych . Do tej pory, aby stworzyć jakąś kolekcję

obiektów musieliśmy utworzyć kolekcję pozwalającą na przechowywania obiektów typu Object . Konsekwencją takiego

podejścia była konieczność żutowania danego elementu danej kolekcji na rozpatrywany typ pomimo tego, iż

programista chciał przechowywać tylko i wyłącznie obiekty tego typu. W przypadku pomyłki błąd zgłaszany był

podczas wykonania programu a nie w czasie kompilacji.

void Duze(Collection c) {

for(Iterator i = c.iterator(); i.hasNext(); ) {

(String)(i.next()).toUpperCase();

}

Typy generyczne pozwalają sparametryzować dany typ klasy kontenerowej za pomocą odpowiedniego obiektu,

przez co jest on określony i rzutowanie nie jest konieczne. Podobne rozwiązanie – szablony - jest stosowane w C++.

void Duze(Collection c) {

for(Iterator<String> i = c.iterator(); i.hasNext(); ) {

i. toUpperCase ();

}

2.3. Interfejs Collection

boolean add (Object) - dodaje element Object do konlekcji sprawdzając czy należy on do tej kolekcji, jeśli

nie zwraca false

boolean addAll (Collection) - dodaje wszystkie elementy kolekcji będącej argumentem do tej na rzecz której jest

wywoływana, zwraca true jeżeli dodano przynajmniej jeden element

void clear () - usuwa wszystkie elementy kolekcji

boolean contains (Object) - sprawdza czy dany element jest elementem kolekcji

boolean containsAll (Collection) - sprawdza czy wszystkie elementy kolekcji będącej parametrem są również

elementami kolekcji na rzecz której wywołujemy funkcję

boolean equals (Object) - sprawdza czy dana kolekcja jest taka sama jak argument

boolean isEmpty () - zwraca true jeżeli kontener nie zawiera elementów

boolean remove (Object) - sprawdza czy dany element jest w kontenerze, jeśli tak to go usuwa lub jeden z nich

jeśli jest ich więcej, zwraca true jeżeli udało się usunąć

boolean removeAll (Collection) - usuwa wszystkie elementy kontenera, które są jednocześni wskazane poprzez

argument (różnica), jeżeli usunięto przynajmniej jedną wartość to zwraca true

boolean retainAll (Collection) – usuwa wszystkie elementy kontenera na rzecz którego jest wywoływana, które nie

znajdują się w kolekcji wskazywanej przez argument (część wspólna), jeżeli usunięto

przynajmniej jedną wartość to zwraca true

int size ()

- zwraca liczbę elementów w kontenerze

Object[] toArray ()

- zwraca tablicę utworzoną z wszystkich elementów danej kolekcji

2.4. Interfejs List

Interfejs List definjuje dodatkowo (poza tymi z interfejsu Collection) metody:

void add (int indeks, Object) - dodaje do listy obiekt na pozycji indeks

Object get ( int indeks) - zwraca element znajdujący się na miejscu o indeksie indeks

int indexOf (Object) - zwraca indeks na którym po raz pierwszy pojawia się dany obiekt -1 jeśli nie

występuje na liście

int lastIndexOf (Object) - zwraca indeks na którym po raz ostatni pojawia się dany obiekt albo -1

Object remove (int indeks) - zwraca element znajdujący się na pozycji indeks a następnie go usuwa

Objest set (int indeks, Object) - zastępuje element występujący na podanej pozycji argumentem

List subList (int pocz, int przedOst) - zwraca listę utworzoną z elementów bieżącej listy o indeksach z

przedziału [pocz, przedOst)

2.4.1. ArrayList

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: