Autor wykładu : Wojciech Drabik



Pobieranie 417,97 Kb.
Strona4/5
Data24.02.2019
Rozmiar417,97 Kb.
1   2   3   4   5

Usuwa element listy z podanej pozycji index.


Dostarcza usunięty obiekt.

Np. Object obj=list.remove(4);




Object set(int index, Object element) //operacja opcjonalna

Zamienia element listy z pozycji index na podany element.

Dostarcza usunięty obiekt.
Np. Object obj=list.set(3,new String(”abc”));
List subList(int fromIndex, int toIndex)

Dostarcza fragment listy między pozycjami fromIndex oraz toIndex-1.

Np. List subList=list.subList(3,7);


specyfikacja funkcji

nie zawiera innych funkcji niż interfejs Collection

specyfikacja funkcji


void clear() //operacja opcjonalna

Usuwa z kolekcji wszystkie obiekty (czyni ją pustą).

np. map.clear();


boolean containsKey(Object key)

Sprawdza czy podany klucz znajduje się w kolekcji.

np. boolean contains = map.containsKey("Ala");
boolean containsValue(Object value)

Sprawdza czy kolekcja zawiera obiekt value.

np. boolean contains =

map.containsValue(new Person("Ala", 24));


Set entrySet()

Dostarcza odniesienie do zbioru par kolekcji mapującej.

np. Set set = map.entrySet();
boolean equals(Object obj)

sprawdza czy obiekt mapy równy jest obiektowi obj.

np. boolean b=map.equals(obj);
Object get(Object key)

W odnośniku typu Object dostarcza odniesienie do obiektu

identyfikowanego przez klucz key.

Jeśli takiego obiektu nie ma, to dostarcza null.

np. Person ewa = (Person)map.get("Ewa");
int hashcode()

dostarcza wartość funkcji haszującej dla obiektu mapy.

np. int x=map.hashcode();
boolean isEmpty()

Dostarcza orzeczenie o wartości: "kolekcja jest pusta ".

np. boolean isEmpty = map.isEmpty();
Set keySet()

Dostarcza odniesienie do zbioru kluczy kolekcji mapującej.

np. Set set = map.keySet();
boolean put(Object key,Object value) //operacja opcjonalna

Dołącza do mapy obiekt value identyfikowany przez klucz key.

Dostarcza true jeżeli kolekcja zmieniła stan.

np. map.put("Ewa", new Person("Ewa", 24));


void putAll(Map map) //operacja opcjonalna

Kopiuje wszystke elementy mapy map do tej mapy

Object remove(Object key) //operacja opcjonalna

Usuwa z kolekcji obiekt identyfikowany przez klucz key.

W odnośniku typu Object dostarcza odniesienie do tego obiektu.

Jeśli takiego obiektu nie ma, to dostarcza null.

np. Object obj = map.remove("Ewa");
int size()

Dostarcza liczbę obiektów kolekcji.

np. int count = map.size();
Collection values()

Dostarcza odniesienie do kolekcji wartości tej mapy.

Np. Collection collection=map.values()
Uwaga:

Za pomocą funkcji keySet() , entrySet(),values() można otrzymać

odniesienie do zbioru kluczy, zbioru par albo kolekcji wartości danej mapy

a następnie uzyskać iterator.



Klasy abstrakcyjne : krótka charakterystyka
AbstractCollection – szkieletowa implementacja zbioru lub listy
AbstractSet - szkieletowa implementacja zbioru
AbstractList - szkieletowa implementacja listy z dostępem swobodnym
AbstractSequentialList - szkieletowa implementacja listy z dostępem sekwencyjnym
AbstractMap - szkieletowa implementacja mapy

Klasy abstrakcyjne są doskonałym punktem startowym do budowania
własnych implementacji.


Przykład własnej klasy opartej na AbstractList :

class MyArrayList extends AbstractList { //rozszerzenie AbstractList


private Object[] tab;
MyArrayList(Object[] array) { tab=array; }
// implementacja metody get()

public Object get(int index) { return tab[index] }


// przedefiniowanie metody set()

public Object set(int index,Object element)

{

Object oldValue=tab[index];



tab[index]=element;

return oldValue;

}
// implementacja metody size()

public int size() { return tab.length; }


}

Klasy implementujące : krótka charakterystyka
HashSet – implementacja Set za pomocą tablicy mieszania
TreeSet – implementacja SortedSet za pomocą drzewa czerwono-czarnego

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


ArrayList – implementacja List za pomoca tablicy rozszerzalnej
LinkedList – implementacja List za pomocą listy dwukierunkowej
Vector - synchronizowana implementacja List za pomocą tablicy rozszerzalnej
Stack – wektorowa implementacja stosu (struktury danych typu LIFO)
-------------------------------------------------------------------------------------------
HashMap – implementacja Map za pomocą tablicy mieszania
WeakHashMap – implementacja Map która przechowuje słabe referencje

do kluczy.


TreeMap – implementacja SortedMap za pomocą drzewa czerwono-czarnego
Hashtable – synchronizowana implementacja Map która nie dopuszcza

kluczy i wartości typu ‘null’

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

Uwaga :
Kolektory mieszające (HashMap, HashSet, Hashtable) wykorzystują do przechowywania obiektów tablicę mieszania umieszczając obiekty w

odpowiednim miejscu tej tablicy(w odpowiednim „kubełku”).

Parametry tablicy mieszania to :
- pojemność (liczba komórek tablicy)


  • pojemność początkowa(liczba komórek tablicy po utworzeniu)

  • rozmiar (aktualna ilość elementów w tablicy)

- współczynnik wypełnienia( rozmiar/pojemność).
Niektóre konstruktory tych klas pozwalają na określenie parametrów

tablicy mieszania takich jak pojemność początkowa (initialCapacity)

i współczynnik wypełnienia (loadFactor- domyślnie 0.75).

Podstawowe struktury danych wykorzystawane w klasach implementujących

(tablica,lista dwukierunkowa , tablica mieszania, drzewo czerwono-czarne)





Obj-1

Obj-2

Obj-3

...

...

...

Obj-n

0

1

2

...

...

...

n-1

Tablica



null

O-1

O-2

O-3

O-4

null

głowa(head) ogon(tail)

Lista dwukierunkowa

Zbiór kluczy




0


1



hashcode()
2


...


m-1

Tablica mieszania


Drzewo czer-cz.


Wszystkie kolektory oparte o klasy implementujące można podzielić na:


-kolektory listowe ( ArrayList, LinkedList, Vector, Stack)

-kolektory zbiorowe( HashSet, TreeSet)

-kolektory mapujące( HashMap, TreeMap, Hashtable)
Wybór odpowiedniej implementacji może ułatwić poniższa tabela


Klasa

Elementy,uporządkowanie

Szybkość operacji


ArrayList

Automatycznie rozszerzalna
Akceptuje wszystkie elementy
Z każdym elementem związany jest indeks


Operacje :get(),set(),size(),isEmpty(),

iterator(),listIterator() w czasie stałym
Operacje pozostałe w czasie liniowym O(n)


LinkedList

Akceptuje wszystkie elementy
Z każdym elementem związany jest indeks
Może być używana jako stos/kolejka

Operacje wstawiania,usuwania b.szybkie(zmiana dowiązań)
Operacje dostępu wolne

(przeglądanie sekwencyjne)


HashSet

Elementy nieuporządkowane
Akceptuje elementy różne wg equals()

Operacje add(),remove(),contains(),

size() w czasie stałym
Iteracja wymaga czasu proporcjonalnego do sumy elementów i liczby kubełków


TreeSet

Elementy uporządkowane rosnąco

(wg Comparable lubComparator)
Akceptuje elementy różne wg

compareTo() lub compare()


Operacje add(),remove(),contains()

w czasie O(log n)

Hashtable

Elementy nieuporządkowane
Nie akceptuje kluczy i wartości ‘null’


Operacje get(),put() w czasie stałym
Iteracja proporcjonalna do sumy ilości

kubełków i ilości elementów

HashMap

Elementy nieuporządkowane
Akceptuje wszystkie klucze i wartości


Operacje get(),put() w czasie stałym
Iteracja proporcjonalna do sumy ilości

kubełków i ilości elementów


TreeMap

Elementy uporządkowane rosnąco

(wg Comparable lub Comparator)
Akceptuje wszystkie elementy


Operacje get(),put(),remove()

containsKey() w czasie O(log n)

Następująca aplikacja ilustruje użycie kolektora listowego opartego

na klasie ArrayList.
Uwaga:

Skutek wykonania aplikacji byłby taki sam,

gdyby fabrykator new ArrayList() zastąpiono fabrykatorem new LinkedList().
import java.util.*;
public class Program {

public static void main(String[] args)

{

new Program();

}

public Program()

{

// utworzenie kolektora

Collection collection = new ArrayList();
// dodanie obiektów

collection.add("Ewa");

collection.add("Iza");

collection.add("Jan");

// uzyskanie iteratora kolekcji

Iterator iterator = collection.iterator();
// przeglądanie do przodu

while (iterator.hasNext()) {

String name = (String)iterator.next();

System.out.println(name);

}

System.out.println();

List list = (List)collection;
// uzyskanie iteratora listy

ListIterator listIterator =

list.listIterator(list.size());

// przeglądanie do tyłu

while (listIterator.hasPrevious()) {

String name = (String)listIterator.previous();

System.out.println(name);

}

}

}

Klasa Vector i Stack pochodzi z wcześniejszych wersji Javy,ale ponieważ stare

i niektóre nowe programy wykorzystują tę klasę oto przykład ich zastosowania:
Następująca aplikacja wykorzystuje klasę Vector do utworzenia kolekcji

obiektów reprezentujących "zwierzątka domowe", a następnie informuje o nich.



import java.util.*;
public class Program {
public static void main(String[] args)

{

new Program();

}

public Program()

{

Cat whiteCat = new Cat("White"),

blackCat = new Cat("Black");

Dog lameDog = new Dog("Lame"),

niceDog = new Dog("Nice");

Vector pets = new Vector();
// dodanie do kolekcji

pets.add(whiteCat);

pets.add(lameDog);

pets.add(blackCat);

pets.add(niceDog);

int count = pets.size(); //pobranie rozmiaru

System.out.println("\nCollection contains");
for (int i = 0; i < count ; i++) {
//pobranie obiektu z pozycji i oraz rzutowanie w dół

Object object = pets.get(i);

Pet pet = (Pet)object;

System.out.println(

pet.getKind() + ": " + pet.getName()

);

}

}

}
abstract class Pet {
private String name;

public Pet(String name) { this.name = name; }

public String getName() { return name;}
public abstract String getKind();

}
class Dog extends Pet {

public Dog(String name){ super(name); }
public String getKind(){ return "DOG"; }

}
class Cat extends Pet {

public Cat(String name) { super(name); }
public String getKind() { return "CAT"; }

}
Następująca aplikacja, wykorzystuje klasę Stack do utworzenia

kolekcji obiektów reprezentujących osoby, a następnie informuje o nich.



import java.util.*;
public class Program {
public static void main(String[] args)

{

new Program();

}

public Program()

{

Stack stack = new Stack(); //nowy stos
// umieszczenie na stosie

stack.push(new Person("Ania", 25));

stack.push(new Person("Ala", 17));

stack.push(new Person("Robert", 50));
// podglądanie obiektu z wierzchołka bez zdejmowania

Person p=(Person)stack.peek();

System.out.println(p.getInfo());


// głębokość elementu(odległość od wierzchołka)

System.out.println(stack.search(p));

while (!stack.empty()) {

Person name = (Person)stack.pop();

System.out.println(name.getInfo());

}

}

}
class Person {
private String name;

private int age;

public Person(String name, int age)

{

this.name = name;

this.age = age;

}

public String getInfo()

{

return name + ' ' + age;

}

}

Następująca aplikacja,ilustruje użycie kolekcji zbiorowych: HashSet i TreeSet.


import java.util.*;
public

class Program {

public static void main(String[] args)

{

new Program();

}

public Program()

{

Set hashSet = new HashSet(),

treeSet = new TreeSet();

addTo(hashSet); //funkcja własna addTo()

show(hashSet);

System.out.println("------");

addTo(treeSet);

show(treeSet);

}

public void addTo(Set set) // //funkcja własna addTo()

{

set.add("Ania");
set.add("Ala");

set.add("Ala"); // bez skutku-element taki sam

set.add("Ala"); // be skutku-element taki sam

set.add("Robert");

}

public void show(Set set)

{

// utworzenie iteratora

Iterator iterator = set.iterator();
// przeglądanie do przodu

while (iterator.hasNext()) {

String name = (String)iterator.next();

System.out.println(name);

}

}

}

Następująca aplikacja, ilustruje użycie klas HashMap i TreeMap.

import java.util.*;
public class Program {

public static void main(String[] args)

{

new Program();

}

public Program()

{

Map hashMap = new HashMap(),

treeMap = new TreeMap();

putTo(hashMap); //funkcja własna putTo()

putTo(treeMap); //funkcja własna putTo()

show(hashMap);

System.out.println("-----");

show(treeMap);

System.out.println("-----");

// dostęp wyrywkowy

String info =

//wywołanie getInfo() dopiero po rzutowaniu

((Person)hashMap.get("Robert")).getInfo();

System.out.println(info);
//wywołanie getInfo() dopiero po rzutowaniu

info = ((Person)treeMap.get("Ania")).getInfo();
System.out.println(info);

}

class Person {

private String name;

private int age;

public Person(String name, int age)

{

this.name = name;

this.age = age;

}

public String getInfo()//funkcja własna getInfo()

{

return name + ' ' + age;

}

}

public void putTo(Map map) //funkcja własna putTo()

{

map.put("Ania", new Person("Kowalska", 30));
map.put("Ala", new Person("Kowalska", 12));
// oba polecenia ignorowane-elementy identyczne

map.put("Ala", new Person("Kowalska", 12));

map.put("Ala", new Person("Kowalska", 12));
map.put("Robert", new Person("Kowalski", 36));

}

public void show(Map map)

{

// utworzenie iteratora

Set keySet = map.keySet();

Iterator iterator = keySet.iterator();
// przeglądanie do przodu

while (iterator.hasNext()) {

String name = (String)iterator.next();

System.out.println(name);

}

}

Klasa Hashtable pochodzi z wcześniejszych wersji Javy,ale ponieważ stare

i niektóre nowe programy wykorzystują tę klasę oto przykład jej zastosowania
Następująca aplikacja, tworzy kolekcję obiektów reprezentujących osoby,

a następnie informuje o nich.

import java.util.*;
public

class Program {
public static void main(String[] args)

{

new Program();

}

private Hashtable persons = new Hashtable();

public Program()

{

//dodanie elementów

persons.put("Ania", new Person("Ania", 25));

persons.put("Ala", new Person("Ala", 17));

persons.put("Robert", new Person("Robert", 50));

System.out.println(

getAge("Ala") // funkcja własna getAge()

);


System.out.println(

getAge("Ania") // 25

);

}
public int getAge(String key) //funkcja własna getAge()
{

//pobranie obiektu na podstawie klucza

Object object = persons.get(key);
Person person = (Person)object; //konwersja w dół
//wywołanie getAge() z klasy Person

return person.getAge();

}

}
class Person {
private String name;

private int age;

public Person(String name, int age)

{

this.name = name;

this.age = age;

}

public int getAge()

{

return age;

}

}
Algorytmy kolekcyjne : (klasa Collections)
Algorytmy kolekcyjne to funkcje statyczne zdefiniowane w klasie Collections.
sort(List) – sortowanie listy algorytmem mergeSort (szybki i stabilny)



1   2   3   4   5


©operacji.org 2017
wyślij wiadomość

    Strona główna