2008-11-04

1

Podstawowe struktury dynamiczne

Algorytmy i struktury danych

Wykład 3.

Rok akademicki: 2008/2009

2

Struktura dynamiczna

•

Struktura dynamiczna – struktura, która:

–

tworzona jest w programie poprzez jawne użycie odpowiedniej
instrukcji (np. operatora new),

–

może zmieniać swoją wielkość – liczbę elementów składowych (zmiana
ilości zajmowanej pamięci operacyjnej),

–

jej likwidacja prowadzi do odzyskania zajmowanej przez nią pamięci.

2008-11-04

2

3

Struktury dynamiczne w języku Java

•

kolekcja (Collection) - grupa obiektów (obiekty mogą się powtarzać),

•

zbiór (Set) - grupa elementów (obiekty nie mogą się powtarzać),

•

zbior posortowany (SortedSet) - jak zbiór, ale kolejność elementów jest
określona, możliwe jest pobranie następnego lub poprzedniego elementu
zbioru (np. uporządkowany alfabetycznie zbiór liter lub zbiór łańcuchów),

•

lista (List) - kolekcja, w której elementy mogą się powtarzać, elementy listy
są uporządkowane; dostęp do nich jest również możliwy poprzez indeks.
Rodzaje struktur listowych: stos, kolejka, lista jednokierunkowa, lista
dwukierunkowa, lista cykliczna,

•

tablica asocjacyjna (Map) – zbiór par (klucz, wartość), dostęp do elementu
jest możliwy po podaniu klucza,

•

posortowana tablica asocjacyjna (SortedMap) - tablica asocjacyjna
zawierająca elementy uporządkowane według klucza.

•

drzewa i grafy

kolejne wykłady!!!

4

Definicja struktur dynamicznych w postaci interfejsów

2008-11-04

3

5

Interfejs Collection

6

Interfejs Iterator

public interface Iterator {

boolean hasNext();

Object next();

void remove();

}

2008-11-04

4

Wykorzystanie iteratora do usuwania elementów

Collection collection = ...;

Iterator iterator = collection.iterator();

while (iterator.hasNext()) {

Object element = iterator.next();

if (removalCheck(element)) {

iterator.remove();

}

}

7

8

Klasa AbstractCollection

•

public abstract class AbstractCollection extends Object
implements Collection

•

przy tworzeniu kolekcji niezbędne jest:

–

określenie sposobu przechowywania danych

–

zdefiniowanie metody iterator()

–

zdefiniowanie metody size()

–

zdefiniowanie metody add() - dostępna metoda add() generuje
wyjątek UnsupportedOperationException

–

zdefiniowanie konstruktorów: Kolekcja() oraz Kolekcja(Collection
c)

2008-11-04

5

9

Kolekcja – przykład 1/6

import java.util.Collection;
import java.util.AbstractCollection;
import java.util.Iterator;
import java.util.NoSuchElementException;
class KolekcjaLiterA extends AbstractCollection implements Iterator
{

private int ileLiter;
private int aktualnaLitera;
private boolean czyMoznaUsunac;
KolekcjaLiterA()
{

ileLiter = 0;
czyMoznaUsunac = false;
aktualnaLitera = 0;

}

10

Kolekcja – przykład 2/6

KolekcjaLiterA(Collection c) {

addAll(c);

}

public Iterator iterator()

{

aktualnaLitera = 0;

return this;

}

public boolean hasNext() {

return (aktualnaLitera < ileLiter);

}

2008-11-04

6

11

Kolekcja – przykład 3/6

public Object next()

{

if (aktualnaLitera < ileLiter) {

aktualnaLitera++;
czyMoznaUsunac = true;
return new Character('A');

}
else

{
czyMoznaUsunac = false;
throw new NoSuchElementException("Brak

nastepnego elementu");

}

}

12

Kolekcja – przykład 4/6

public void remove() {

if (czyMoznaUsunac) {

ileLiter--;
czyMoznaUsunac = false;

}

}
public int size() {

return ileLiter;

}
public boolean add(Object o)

{

if(o == null)

throw new NullPointerException("Pusty wskaznik");

if(!(o instanceof Character))

throw new ClassCastException("Tylko obiekty typu Character");

Character znak = (Character) o;
if (znak.charValue() != 'A')

throw new IllegalArgumentException("Tylko A");

ileLiter++;
return true;

}

2008-11-04

7

13

Kolekcja – przykład 5/6

public String toString()

{

StringBuffer buf = new StringBuffer();

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

buf.append('A');

return buf.toString();

}

}

14

Kolekcja – przykład 6/6

public class TestKolekcjiLiterA {

public static void main(String [] args) {

KolekcjaLiterA pierwsza = new KolekcjaLiterA();
pierwsza.add(new Character('A'));
pierwsza.add(new Character('A'));
System.out.println("Pierwsza kolekcja: " + pierwsza);
KolekcjaLiterA druga= new KolekcjaLiterA();
druga.add(new Character('A'));
druga.add(new Character('A'));
druga.add(new Character('A'));
druga.add(new Character('A'));
System.out.println("Druga kolekcja: " + druga);
druga.removeAll(pierwsza);
System.out.println("Druga kolekcja: " + druga);
druga.add(new Character('A'));
System.out.println("Druga kolekcja: " + druga);
KolekcjaLiterA trzecia = new KolekcjaLiterA(druga);
System.out.println("Trzecia kolekcja: " + trzecia);

}

}

2008-11-04

8

15

Interfejs Set

Elementy w zbiorze nie mogą się powtarzać!

•

Do sprawdzenia, czy dany element występuje w zbiorze służy
zdefiniowana w klasie Object metoda:

public boolean equals(

Object

obj)

•

implementacja zawarta w klasie Object sprawdza, czy
referencja do bieżącego obiektu jest równa referencji do
obiektu reprezentowanego przez parametr (czyli, czy te dwa
obiektu zajmują to samo miejsce w pamięci) – dla klas
definiowanych przez programistę zwykle konieczne jest
zredefiniowanie metody equals.

16

2008-11-04

9

17

Klasa AbstractSet

•

public abstract class AbstractSet extends AbstractCollection
implements Set

•

Klasa AbstractSet jest wykorzystywana w podobny sposób jak
klasa AbstractCollection.

Klasa HashSet - implementacja zbioru

import java.util.*;
public class PrzykladZbioru {

public static void main(String args[]) {

Set set = new HashSet();
set.add("Wiosna");
set.add("Lato");
set.add("Jesien");
set.add("Zima");
set.add("Zima");
set.add("Zima");
set.add("Zima");
System.out.println(set);

set.remove("Lato");

System.out.println(set);
}

}

18

Wynik działania programu:
[Jesien, Wiosna, Zima, Lato]
[Jesien, Wiosna, Zima]

2008-11-04

10

Implementacja zbiorów typu HashSet

•

Do przechowywania elementów zbioru typu HashSet
wykorzystywana jest struktura danych nazywana tablicą z
haszowaniem.

•

Podstawowe cechy tablicy z haszowaniem:

–

pozwala na szybki dostęp do jej elementów składowych,

–

pozwala na efektywne zarządzanie pamięcią operacyjną.

–

W tablicy z haszowaniem mogą być przechowywane obiekty, dla
których można wyznaczyć wartość klucza.

19

20

Cechy klucza haszującego (skrótu)

•

klucz jest liczbą całkowitą,

•

wartość klucza jest uzależniona od wartości przechowywanych w obiekcie;

•

dwa identyczne obiekty (ze względu na metodę equals – czyli tego samego
typu i przechowujące takie same wartości) mają identyczne wartości
kluczy;

•

dwa różne obiekty mogą posiadać identyczne lub różne wartości kluczy
(zaleca się, aby były one różne)

•

w języku Java do wyznaczenia wartości klucza służy funkcja z klasy Object:

public int hashCode()

•

funkcja hashCode jest dziedziczona przez wszystkie inne klasy (może być
redefiniowana)

2008-11-04

11

Funkcja hashCode() dla klasy String

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

class Test {

public static void main(String [] args) {

String s = "Java";
System.out.println(s.hashCode());

}

}

Efekt działania:
2301506

21

Funkcja hashCode() w klasie Object

•

funkcja hashCode() zdefiniowana w klasie Object zwraca
informację o położeniu obiektu (adres obiektu przekształcony
do wartości typu int) – zwykle dla klas definiowanych przez
programistę konieczna jest redefinicja, gdyż nie jest spełniony
warunek głoszący, że równe obiekty (equals) posiadają
identyczne kody

•

jeśli obiekty mają być przechowywane w zbiorze typu HashSet
to muszą mieć poprawnie zdefiniowaną funkcję hashCode().

22

2008-11-04

12

23

Struktura tablicy z haszowaniem

funkcja haszująca: hashCode() % n

gdzie: n – liczba elementów w wektorze

24

Przykład 1/4

import java.util.*;
class Lancuch
{

String s;
Lancuch(String s)
{

this.s = s;

}
public String toString()
{

return s;

}

}

2008-11-04

13

25

Przykład 2/4

public class Test
{

public static void main(String args[])
{

Set set = new HashSet();

set.add(new Lancuch("Szczecin"));
set.add(new Lancuch("Olsztyn"));
set.add(new Lancuch("Opole"));
set.add(new Lancuch("Katowice"));
set.add(new Lancuch("Katowice"));
System.out.println(set);

}

}

26

Przykład 3/4

Efekt działania programu:

[Olsztyn, Szczecin, Katowice, Opole, Katowice]

WYNIK JEST BŁĘDNY – W ZBIORZE WYSTĘPUJĄ DWA
IDENTYCZNE ELEMENTY!!!

Konieczna jest modyfikacja klasy Lancuch

2008-11-04

14

27

Przykład 4/4

class Lancuch {

String s;
Lancuch(String s) {

this.s = s;

}
public String toString() {

return s;

}
public boolean equals(Object obj) {

if (!(obj instanceof Lancuch))

return false;

if (((Lancuch) obj).s.equals(s))

return true;

else

return false;

}
public int hashCode() {

return s.hashCode();

}

}

Efekt działania programu:
[Szczecin, Katowice, Opole, Olsztyn]

28

Interfejs SortedSet

Interfejs SortedSet implementowany jest przez klasę TreeSet.

2008-11-04

15

29

Interfejs Comparable

Operację porządkowania elementów definiuje interfejs Comparable

Porównuje dany obiekt z obiektem reprezentowanym przez parametr
i zwraca:
• wartość ujemną, jeśli dany obiekt jest mniejszy,
• zero, jeśli są równe,
• wartość dodatnią, jeśli dany obiekt jest większy.

Jeśli elementami zbioru typu TreeSet są obiekty implementujące interfejs
Comparable, to są one porządkowane zgodnie ze sposobem działania
metody compareTo().

30

Przykład 1/2

import java.util.*;

public class PrzykladZbioru

{

public static void main(String args[])

{

Set set = new TreeSet();

set.add("Wiosna");

set.add("Lato");

set.add("Jesien");

set.add("Zima");

2008-11-04

16

31

Przykład 2/2

System.out.println(set);

set.remove("Lato");

System.out.println(set);

}

}

Efekt działania programu:

[Jesien, Lato, Wiosna, Zima]

32

Interfejs Comparable

Jeśli elementami zbioru mają być obiekty, które nie implementują
interfejsu Comparable, to sposób ich porównania dokonywany jest za
pomocą metod interfejsu Comparator.

Utworzony obiekt pozwalający na porównanie elementów zbioru
(komparator) jest przekazywany jako parametr konstruktora
obiektu TreeSet.

2008-11-04

17

33

Przykład 1/2

import java.util.*;

class PorownajDlugosciTekstow implements Comparator

{

public int compare(Object element1, Object element2)

{

int dlugosc1 = ((String) element1).length();

int dlugosc2 = ((String) element2).length();

return dlugosc1 - dlugosc2;

}

}

34

Przykład 2/2

public class Porownania {

public static void main(String [] args)

{

PorownajDlugosciTekstow p = new PorownajDlugosciTekstow();
TreeSet zbior = new TreeSet(p);

zbior.add("Andrzej");
zbior.add("Basia");
zbior.add("Jan");
zbior.add("Boleslaw");

System.out.println(zbior);

}

}

Wynik działania programu:
[Jan, Basia, Andrzej, Boleslaw]

2008-11-04

18

35

Implementacja zbioru typu TreeSet

10

5

14

7

12

18

15

Zbiory typu TreeSet przechowywane są w postaci
drzewa poszukiwań binarnych - Dla każdego węzła, wszystkie
elementy jego lewego poddrzewa (jeżeli takie istnieją)
reprezentują elementy mniejsze od elementu reprezentowanego
przez ten węzeł, zaś wszystkie elementy jego prawego poddrzewa
(jeżeli takie istnieją) reprezentują elementy większe od elementu
reprezentowanego przez rozpatrywany węzeł.

36

Wyświetlanie elementów drzewa

10

5

14

7

12

18

15

Wędrówka po drzewie rozpoczyna się od korzenia
if (węzeł istnieje)

{

wedrowka_po_drzewie(lewy potomek bieżącego węzła)
wypisz bieżący węzeł
wedrowka_po_drzewie(prawy potomek bieżącego węzła)

}

2008-11-04

19

37

Reprezentacja struktur listowych

38

Listy

•

kolekcja uporządkowanych elementów (z możliwością
powtórzeń);

•

elementy listy są ponumerowane (od zera);

•

podstawowe cechy listy opisane są w interfejsie List.

2008-11-04

20

39

Interfejs List

40

Interfejs ListIterator

2008-11-04

21

41

Implementacja list w języku Java

•

ArrayList - implementacja interfejsu List jako wektora o
zmieniających się wymiarach

•

LinkedList - implementacja interfejsu List jako struktury
listowej.

42

Klasa ArrayList

•

Elementy listy przechowywane są wektorze

•

w przypadku braku miejsca w wektorze tworzony jest
nowy wektor o wielkości:

n

nowy

= 1,5 * n

stary

+ 1

do którego kopiowane są elementy z dotychcza-sowego
wektora; po przekopiowaniu dotychczasowy wektor jest
usuwany z pamięci.

2008-11-04

22

43

Zastosowania klasy ArrayList

•

stosowanie list typu ArrayList jest zalecane wtedy, gdy:

–

często zachodzi potrzeba odwoływania się do elementów listy,

–

rzadko zachodzi potrzeba modyfikacji wielkości listy.

44

ArrayList – przykładowy program

import java.util.*;

public class Wektor {

public static void main(String[] args) {

ArrayList w = new ArrayList(5);

for (int i = 1; i <= 10; i++)

w.add(new Integer(i));

//wyswietlenie wektora

System.out.println("Wektor: " + w);

2008-11-04

23

45

ArrayList – przykładowy program

//korzystanie z ListIteratora
ListIterator iter = w.listIterator(0);

while (iter.hasNext())

if (((Integer) iter.next()).intValue() % 2 != 0)

iter.remove();

//wyswietlenie wektora
System.out.println("Wektor: " + w);

}

}

46

Klasa LinkedList

•

lista typu LinkedList przechowywana jest jako lista
dwukierunkowa,

2008-11-04

24

47

Zastosowanie klasy LinkedList

•

stosowanie listy typu LinkedList jest zalecane wtedy, gdy:

–

rzadko zachodzi potrzeba odwoływania się do elementów listy za
pomocą indeksów,

–

często zachodzi potrzeba dodawania i usuwania elementów
znajdujących się na liście.

48

Klasa LinkedList – przykład 1/3

import java.util.*;

public class LiczbyPierwsze {

static boolean czyPierwsza(int liczba)

{

for (int i = 2; i <= Math.min(

(int) Math.sqrt(liczba) + 1,liczba-1); i++)

if (liczba % i == 0)

return false;

return true;

}

2008-11-04

25

49

Klasa LinkedList – przykład 2/3

public static void main(String[] args) {

LinkedList lista = new LinkedList();
for (int i = 1; i <= 20; i++)

lista.add(new Integer(i));

System.out.println("Lista: " + lista);
ListIterator iter = lista.listIterator();
Integer element;
while (iter.hasNext())

if (czyPierwsza((element = (Integer) iter.next()).intValue()))

iter.set("{" + element.intValue() + "}");

System.out.println("Lista: " + lista);
iter = lista.listIterator();
while (iter.hasNext())

if (!(iter.next() instanceof String))

iter.remove();

System.out.println("Lista: " + lista);

}

}

50

Klasa LinkedList – przykład 3/3

•

Efekt działania programu:

Lista: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,

20]

Lista: [{1}, {2}, {3}, 4, {5}, 6, {7}, 8, 9, 10, {11}, 12, {13}, 14, 15, 16,

{17}, 18, {19}, 20]

Lista: [{1}, {2}, {3}, {5}, {7}, {11}, {13}, {17}, {19}]

2008-11-04

26

LinkedList jako stos oraz jako kolejka

•

metody zdefiniowane w klasie LinkedList pozwalające na
wykorzystanie obiektu w charakterze stosu lub kolejki (metody
te nie są częścią interfejsu List)

51

52

Stos

wierzchołek
stosu

2008-11-04

27

53

Stos – przykładowy program 1/3

import java.util.*;
public class Stos {

public static void main(String[] args) {

LinkedList st = new LinkedList();

st.addFirst("Poniedzialek");
st.addFirst("Wtorek");
st.addFirst("Sroda");

//sprawdzenie elementu znajdujacego się
//na wierzcholku stosu (bez usuwania go ze stosu)
System.out.println("Na wierzcholku stosu znajduje sie: " +

st.getFirst());

54

Stos – przykładowy program 2/3

//wyswietlenie stosu
System.out.println("Elementy: " + st);

//pobieranie elementow ze stosu (z usuwaniem)
System.out.println("\nPobieranie elementow ze

stosu\n");

while(!st.isEmpty())
{

System.out.println(" Pobrany element to: " +

st.removeFirst());

System.out.println(" Zawartosc stosu: " + st);
System.out.println();

}

}

}

2008-11-04

28

55

Stos – przykładowy program 3/3

Efekt działana programu:

Na wierzcholku stosu znajduje sie: Sroda

Elementy: [Sroda, Wtorek, Poniedzialek]

Pobieranie elementow ze stosu

Pobrany element to: Sroda

Zawartosc stosu: [Wtorek, Poniedzialek]

Pobrany element to: Wtorek

Zawartosc stosu: [Poniedzialek]

Pobrany element to: Poniedzialek

Zawartosc stosu: []

56

Kolejka

początek
kolejki

koniec
kolejki

2008-11-04

29

Kolejka – przykładowy program 1/4

import java.util.*;

public class Kolejka {

public static void main(String[] args) {

LinkedList kol = new LinkedList();

kol.addLast("Poniedzialek");

kol.addLast("Wtorek");

kol.addLast("Sroda");

57

Kolejka – przykładowy program 2/4

//sprawdzenie elementu znajdujacego się

//na poczatku kolejki (bez usuwania go z kolejki)

System.out.println("Na poczatku kolejki

znajduje sie:" + kol.getFirst());

//wyswietlenie kolejki

System.out.println("Elementy: " + kol);

//pobieranie elementow z kolejki (z usuwaniem)

System.out.println("\nPobieranie elementow

z kolejki\n");

58

2008-11-04

30

Kolejka – przykładowy program 3/4

while(!kol.isEmpty()) {

System.out.println(" Pobrany element to: " +

kol.removeFirst());

System.out.println(" Zawartosc kolejki: " +

kol);

System.out.println();

}

}

}

59

Kolejka – przykładowy program 4/4

Efekt działania programu:

Na poczatku kolejki znajduje sie: Poniedzialek

Elementy: [Poniedzialek, Wtorek, Sroda]

Pobieranie elementow z kolejki

Pobrany element to: Poniedzialek

Zawartosc kolejki: [Wtorek, Sroda]

Pobrany element to: Wtorek

Zawartosc kolejki: [Sroda]

Pobrany element to: Sroda

Zawartosc kolejki: []

60

2008-11-04

31

61

Tablica asocjacyjna

•

tablica asocjacyjna: kolekcja par: klucz - wartość (wartości
klucza nie mogą się powtarzać),

•

tablica asocjacyjna jest opisana za pomocą interfejsu Map.

62

Interfejsy Map oraz Map.Entry

metoda entrySet zwraca zbiór elementów tablicy asocjacyjnej.
Każdy element implementuje interfejs Map.Entry.

2008-11-04

32

Implementacja tablic asocjacyjnych

•

Tablice asocjacyjne zaimplementowane są w postaci klas:

–

HashMap

–

TreeMap – uporządkowana tablica asocjacyjna

63

64

Klasa HashMap

•

do przechowywania kluczy stosowana jest tablica z
haszowaniem; w związku z tym obiekty spełniające rolę kluczy
muszą posiadać prawidłowo zaimplementowaną funkcję
hashCode() oraz equals().

•

klucze nie mogą się powtarzać;

•

przeszukiwanie zbioru kluczy jest znacznie szybsze niż
przeszukiwanie zbioru obiektów.

2008-11-04

33

65

HashMap – przykład 1/4

import java.util.*;
public class TablicaAsocjacyjna
{

public static void main(String [] args)
{

Map asoc = new HashMap();

asoc.put(new Integer(1),"Jeden");
asoc.put(new Integer(2),"Dwa");
asoc.put(new Integer(3),"Trzy");
asoc.put(new Integer(4),"Cztery");
asoc.put(new Integer(5),"Piec");

System.out.println("Tablica asocjacyjna: " + asoc);

66

HashMap – przykład 2/4

System.out.println("czy jest klucz '44' - " +

asoc.containsKey(new Integer(44)));

System.out.println("czy jest klucz '1' - " +

asoc.containsKey(new Integer(1)));

System.out.println("element o kluczu '44': " +

asoc.get(new Integer(44)));

System.out.println("element o kluczu '1': " +

asoc.get(new Integer(1)));

System.out.println("czy jest wartosc 'Dwa': " +

asoc.containsValue("Dwa"));

System.out.println("czy jest wartosc 'Siedem': " +

asoc.containsValue("Siedem"));

2008-11-04

34

67

HashMap – przykład 3/4

Set zawartosc = asoc.entrySet();
Iterator iter = zawartosc.iterator();
Map.Entry element;
System.out.println("\nZawartosc tablicy asocjacyjnej\n");

while(iter.hasNext())
{

element = (Map.Entry) iter.next();
System.out.print("klucz=" + element.getKey());
System.out.println(" wartosc=" +
element.getValue());

}

}

}

68

HashMap – przykład 4/4

Efekt działania programu:

Tablica asocjacyjna: {2=Dwa, 4=Cztery, 1=Jeden, 3=Trzy, 5=Piec}
czy jest klucz '44' - false
czy jest klucz '1' - true
element o kluczu '44': null
element o kluczu '1': Jeden
czy jest wartosc 'Dwa': true
czy jest wartosc 'Siedem': false
Zawartosc tablicy asocjacyjnej
klucz=2 wartosc=Dwa
klucz=4 wartosc=Cztery
klucz=1 wartosc=Jeden
klucz=3 wartosc=Trzy
klucz=5 wartosc=Piec

2008-11-04

35

69

Klasa TreeMap

•

elementy uporządkowane są według wartości kluczy

•

do przechowania kluczy wykorzystywane jest drzewo
poszukiwań binarnych

•

Porządkowanie obiektów:

–

naturalne (kluczami są obiekty implementujące interfejs Comparable),

–

zdefiniowane za pomocą komparatora

70

Porządkowanie naturalne

import java.util.*;
public class TreeMapTest1 {

public static void main(String [] args) {

Map kraje = new TreeMap();

kraje.put("Niemcy","Berlin");
kraje.put("Polska","Warszawa");
kraje.put("Czechy","Praga");
kraje.put("Hiszpnia","Madryt");
kraje.put("Grecja","Ateny");
kraje.put("Wlochy","Rzym");
System.out.println(kraje);

}

}

Wyniki działania programu:
{Czechy=Praga, Grecja=Ateny, Hiszpnia=Madryt, Niemcy=Berlin, Polska=Warszawa,

Wlochy=Rzym}

2008-11-04

36

71

Zastosowanie komparatora 1/2

import java.util.*;

class Porzadkowanie implements Comparator

{

public int compare(Object o1, Object o2)

{

return -1 * ((String) o1).compareTo((String) o2);

}

}

72

Zastosowanie komparatora 2/2

public class TreeMapTest2 {

public static void main(String [] args) {

Porzadkowanie p = new Porzadkowanie();

Map kraje = new TreeMap(p);

kraje.put("Niemcy","Berlin");
kraje.put("Polska","Warszawa");
kraje.put("Czechy","Praga");
kraje.put("Hiszpnia","Madryt");
kraje.put("Grecja","Ateny");
kraje.put("Wlochy","Rzym");

System.out.println(kraje);

}

}

Wyniki działania programu:
{Wlochy=Rzym, Polska=Warszawa, Niemcy=Berlin, Hiszpnia=Madryt, Grecja=Ateny, Czechy=Praga}

2008-11-04

37

Wyznaczanie wartości wyrażenia przy wykorzystaniu ONP

•

Sposób realizacji obliczeń:

–

określenie postaci wyrażenia,

–

przekształcenie wyrażenia do postaci równoważnej zapisanej za pomocą
Odwrotnej Notacji Polskiej (ONP),

–

sprawdzenie poprawności wyrażenia zapisanego w ONP,

–

wyznaczenie wartości wyrażenia zapisanego w ONP.

•

Podstawową strukturą danych wykorzystywaną w trakcie obliczeń
jest stos.

73

Odwrotna Notacja Polska

•

Twórcą jest Jan Łukasiewicz, 1921

•

ONP jest notacją postfiksową (operator podawany jest po

argumentach)

•

Przykłady wyrażeń w notacji infiksowej i postfiksowej:

A + B

A B +

(B - C) * D

B C - D *

74

2008-11-04

38

Konwersja do postaci postfiksowej

•

Podstawowe zasady obowiązujące w trakcie konwersji:

–

Kolejność argumentów w postaci infiksowej i postfiksowej jest taka sama.

–

Zmianie ulega kolejność operatorów.

–

Wyrażenie w postaci infiksowej jest analizowane od lewej do prawej
strony.

–

Po odczytaniu argumentu jest on natychmiast zapisywany do wyrażenia w
postaci postfiksowej.

–

Odczytane operatory przechowywane są na stosie.

75

Konwersja do postaci postfiksowej

•

Algorytm konwersji:

1.

Usunięcie wszystkich elementów ze stosu (na początku konwersji stos musi być pusty).

2.

Jeżeli odczytany został operator i stos jest pusty to operator jest umieszczany na
stosie.

3.

Jeżeli odczytany został operator o wyższym priorytecie niż operator znajdujący się na
wierzchołku stosu to odczytany operator jest umieszczany na stosie. W przeciwnym
przypadku ze stosu usuwany jest operator znajdujący się na jego wierzchołku i
umieszczany jest on na końcu wyrażenia w postaci postfiksowej. Dalszy sposób
postępowania z odczytanym operatorem jest określony przez ponowna realizację
punktu 2 lub punktu 3.

4.

Jeżeli został osiągnięty koniec analizowanego wyrażenia zapisanego w postaci
infiksowej to ze stosu usuwane są kolejno znajdujące się tam operatory i są
dopisywane do wyrażenia w postaci postfiksowej.

76

2008-11-04

39

Analiza przykładowego wyrażenia

77

Wyrażenia z nawiasami

1.

Jeżeli odczytanym elementem wyrażenia zapisanego w postaci infiksowej jest
lewy nawias to jest on umieszczany na stosie. Nawiasy traktowane są w
podobny sposób jak operatory. Priorytet nawiasu jest niższy od priorytetu
każdego innego operatora.

2.

Jeżeli odczytanym elementem wyrażenia zapisanego w postaci infiksowej jest
prawy nawias to ze stosu usuwane są kolejno znajdujące się na nim
operatory i dopisywane są one do wyrażenia w postaci postfiksowej.
Operacja usuwania operatorów ze stosu jest wykonywana aż do chwili, gdy
na wierzchołku stosu znajdzie się lewy nawias. Wówczas odpowiadające
sobie nawiasy są usuwane (prawy z wyrażenia infiksowego, zaś lewy ze
stosu).

78

2008-11-04

40

Przykład 1/3

79

Przykład 2/3

80

2008-11-04

41

Przykład 3/3

81

Ranga wyrażenia

•

Przez stopień operatora rozumie się liczbę wymaganych przez niego
argumentów (np. stopień operatora * wynosi 2).

•

Każdemu wyrażeniu postfiksowemu można przypisać współczynnik
zwany rangą wyrażenia.

•

Sposób obliczania rangi:

1.

Ranga symbolu (wartości występującej w wyrażeniu) wynosi 1.

2.

Ranga operatora n-tego stopnia wynosi 1 - n.

3.

Ranga ciągu symboli i operatorów jest równa sumie rang poszczególnych
symboli i operatorów.

82

2008-11-04

42

Poprawność wyrażenia arytmetycznego

•

Konwersja błędnie zapisanego wyrażenia w postaci infiksowej
prowadzi do utworzenia błędnego wyrażenia w postaci
postfiksowej.

•

Procedura sprawdzająca poprawność wyrażenia może
analizować wyłącznie postać postfiksową.

•

Wyrażenie postfiksowe jest poprawne wtedy i tylko wtedy,
gdy ranga tego wyrażenia jest równa 1 i ranga dowolnej
głowy właściwej wyrażenia jest większa lub równa 1.

83

Poprawność przykładowych wyrażeń

Infix: a - b * c
Postfix: a b c * -
poprawny

Infix: a + * b
Postfix: a b * +
błędny

Infix: a*+bc
Postfix: a * bc+
błędny

84

2008-11-04

43

Wartość wyrażenia w ONP

•

W trakcie analizy wyrażenia od lewej do prawej strony:

–

odczytane argumenty są umieszczane na stosie,

–

po odczytaniu operatora odczytywana jest ze stosu odpowiednia liczba
argumentów, wykonywane jest działanie i wynik umieszczany jest
ponwnie na stosie.

85

Wartość przykładowego wyrażenia

86