Autor wykładu : Wojciech Drabik



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

binarySearch(List,Object) – poszukiwanie binarne na liście uporządkowanej



reverse(List) – odwracanie porządku elementów na liście
shuffle(List) – losowa permutacja elementów (tasowanie)
fill(List,Object) – zamiana elementów listy innym elementem
copy(List dest,List src) – kopiowanie jednej listy na drugą listę
min(Collection) – zwraca najmniejszy element kolekcji
max(Collection) - zwraca największy element kolekcji

klasa Collections
void sort(List list)

void sort(List list, Comparator comp)

Sortuje kolekcję listową list.

Do porównywania obiektów stosuje funkcję compareTo(),

zdefiniowaną w klasach sortowanych obiektów albo

funkcję compare() zdefiniowaną w komparatorze comp.

Jako komparator można podać rezultat funkcji Collections.reverseOrder().

Zapewni to wówczas sortowanie w porządku odwrotnym.

np. Collections.sort(list, Collections.reverseOrder());
int binarySearch(List list, Object key)

int binarySearch(List list, Object key, Comparator comp)

Dostarcza indeks tego elementu listy list, który jest opatrzony kluczem key.

Jeśli lista nie zawiera takiego elementu, to dostarcza liczbę ujemną.

Wymaga się aby lista była posortowana w naturalnym porządku rosnącym.

Jeśli użyto parametru comp, to do porównywania używa się

obiektu klasy implementującej interfejs Comparator.

np. int pos = Collections.binarySearch(list, "Ewa");



Następująca aplikacja, ilustruje użycie funkcji sort() i binarySearch()


import java.util.*;
public class Program {

public static void main(String[] args)

{

new Program();

}

class Person implements Comparable {

private String name;

private int age;

public Person(String name, int age)

{

this.name = name;

this.age = age;

}

public String getInfo()

{

return name + ' ' + age;

}
//porównanie ze względu na imię a potem na wiek

public int compareTo(Object obj)

{

Person p1 = this,

P2 = (Person)obj;
int res = p1.name.compareTo(p2.name);
if (res != 0) return res;
return (p1.age – p2.age);

}

}

public Program()

{

//utworzenie listy z dowiązaniami

List persons = new LinkedList();

Person ania;

//dodanie elementów do listy

persons.add(new Person("Kowalska Ania", 30));

persons.add(ania= new Person("Kowalska Ania", 12));

persons.add(new Person("Kowalski Robert", 36));

showPersons(persons);

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

//sortowanie listy rosnąco

Collections.sort(persons);

showPersons(persons);

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

//przeszukiwanie binarne posortowanej listy

int index =

Collections.binarySearch(persons, ania);

if (index > -1)

System.out.println(

((Person)persons.get(index)).getInfo()

);

else

System.out.println("Element missing");

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

//sortowanie listy malejąco

Collections.sort(

persons, Collections.reverseOrder()

);

showPersons(persons);

}

public void showPersons(List persons)

{

Iterator iterator = persons.iterator();

while (iterator.hasNext()) {

System.out.println(

((Person)iterator.next()).getInfo()

);

}

}

}

5. Algorytmy tablicowe (klasa Arrays) :
algorytmy do:

-sortowania,

-wyszukiwania,

-porównywania

-wypełniania

tablic zmiennych podstawowych i tablic obiektów.


Uwaga-1 :

Wszystkie metody klasy Arrays są statyczne.


Uwaga-2:

Jeśli sortowanie albo wyszukiwanie dotyczy tablicy obiektów oraz odbywa się

bez użycia komparatora (obiektu klasy implementującej interfejs Comparator),

to każdy jej element musi implementować interfejs Comparable.


klasa Arrays
static List asList(Object[] a)
Przekształca tablicę w listę o stałych rozmiarach.

Np. List list=Array.asList(new Integer[10])


void sort(int[] array)

void sort(double[] array)

Sortuje rosnąco tablicę array. Stosuje udoskonaloną metodę quick-sort.

np. Arrays.sort(new int[] { 20, 10, 30 });


void sort(Object[] array)

void sort(Object[] array, Comparator comp)

Sortuje rosnąco tablicę array. Stosuje metodę merge-sort.

Jeśli użyto parametru comp, to do porównywania użyje się

obiektu klasy implementującej interfejs Comparator.

np. Arrays.sort(new int[] { "Ania", "Ala", "Robert" });


int binarySearch(int[] array, int key)

int binarySearch(double[] array, double key)

Dostarcza indeks tego elementu tablicy array, który ma wartość key.

Jeśli tablica nie zawiera takiego elementu, to dostarcza liczbę ujemną.

Wymaga się aby tablica była posortowana w naturalnym porządku rosnącym.

np. int pos=Arrays.binarySearch(new int[] { 20, 10 }, 10);


int binarySearch(Object[] arr, Object key)

int binarySearch(Object[] arr,Object key,Comparator comp)

Dostarcza indeks tego elementu tablicy array, który ma wartość key.

Jeśli tablica nie zawiera takiego elementu, to dostarcza liczbę ujemną.

Wymaga się aby tablica była posortowana w naturalnym porządku rosnącym.

Jeśli użyto parametru comp, to do porównywania użyje się

obiektu klasy implementującej interfejs Comparator.



np. int pos=Arrays.binarySearch(new int[] {20,10 },10);
Następująca aplikacja, ilustruje użycie funkcji sort() i binarySearch().


import java.util.*;
public class Program {

public static void main(String[] args)

{

new Program();

}
// klasa Person nie implementuje Comparable,lecz Comparator

// rozwiązanie możliwe lecz trochę sztuczne

class Person implements Comparator {

private String name;

private int age;

public Person(){ }

public Person(String name, int age)

{

this.name = name;

this.age = age;

}

public String getInfo()

{

return name + ' ' + age;

}
//porównanie ze względu na imię a potem na wiek

public int compare(Object obj1, Object obj2)

{

Person p1 = (Person)obj1,

P2 = (Person)obj2;

int res = p1.name.compareTo(p2.name);

if (res != 0)return res;

return (p1.age – p2.age);

}

} //class Person


public Program()

{

Object person[] = new Person[3];
// zainicjowanie tablicy obiektów

person[0] = new Person("Kowalska Ania", 30);

person[1] = new Person("Kowalska Ania", 12);

person[2] = new Person("Kowalski Robert", 36);
// wypisanie elementów tablicy

for (int i = 0; i < 3 ; i++) {

System.out.println(

((Person)person[i]).getInfo()

);

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

// sortowanie tablicy wg komparatora Person

Arrays.sort(person, new Person());
// wypisanie tablicy po posortowaniu

for (int i = 0; i < 3 ; i++) {

System.out.println(

((Person)person[i]).getInfo()

);

}

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

Object obj = person[2];
//poszukiwanie binarne obiektu obj

// w posortowanej tablicy wg komparatora Person

int index =

Arrays.binarySearch(person, obj, new Person());
// komunikat o znalezieniu obiektu

if (index > -1)

System.out.println(

((Person)person[index]).getInfo()

);

else

System.out.println("Element missing");

}

}

1   2   3   4   5


©operacji.org 2017
wyślij wiadomość

    Strona główna