1

Informatyka

Algorytmy i programowanie

Wykład 5-6

Struktury danych

Programowanie obiektowe

Jerzy Duda, 2010

Jerzy Duda, WZ AGH, 2009-2010

Struktury danych

Struktury danych (ang. data structure) – sposób uporz

ą

dkowania

informacji w komputerze; na strukturach danych operuj

ą

algorytmy

Przykładowe popularne struktury danych:

rekord (ang. structure, record)

tablica

lista

stos

kolejka

grafy

drzewo i jego liczne odmiany (np. drzewo binarne)

zbiory, mapy, słowniki

klasy/obiekty

2

Jerzy Duda, WZ AGH, 2009-2010

Rekord

Rekord (zwany w niektórych j

ę

zykach struktur

ą

) to obiekt

programistyczny, grupa danych tego samego lub ró

ż

nego typu

Posiada ustalon

ą

struktur

ę

, oraz mo

ż

liwo

ść

odczytania i zmiany jego

elementów

Składow

ą

rekordu mo

ż

e by

ć

inny rekord

Składow

ą

rekordu mo

ż

e by

ć

tak

ż

e tablica

Przykładowa struktura:

Numer_albumu

– integer

Imi

ę

– string

Nazwisko

– string

Data_urodzenia

– DateTime

Adres_zamieszkania

– string

Rok_studiów

– integer

Ś

rednia_ocen

– float

Jerzy Duda, WZ AGH, 2009-2010

Rekordy w VBA

Zło

ż

one typy danych mo

ż

na definiowa

ć

poprzez słowo kluczowe w

bloku Type ... Type End

Type Osoba

Imi

ę

As String

Nazwisko As String
Rok_studiów As Integer

End Type

Sub test()

Dim os As Osoba
os.Imi

ę

= "Jan"

os.Nazwisko = "Kowalski"
os.Rok_studiów = 1
MsgBox os.Imi

ę

End Sub

3

Jerzy Duda, WZ AGH, 2009-2010

Rekordy w VBA (tablica rekordów)

W bloku Type ... Type End mo

ż

na stosowa

ć

tablice oraz wcze

ś

niej

zdefiniowane rekordy

Type Grupa

Prowadz

ą

cy As String

Studenci(1 To 15) As Osoba

End Type

Sub test2()

Dim gr1 As Grupa
gr1.Prowadz

ą

cy = "Duda"

gr1.Studenci(1).Imi

ę

= "Anna"

gr1.Studenci(1).Nazwisko = "Anna"
gr1.Studenci(2).Imi

ę

= "Jan"

gr1.Studenci(2).Nazwisko = "Kowalski"
gr1.Studenci(3).Imi

ę

= "Adam"

gr1.Studenci(3).Nazwisko = "Kwiecie

ń

"

MsgBox g1.Studenci(1).Imi

ę

(2)

End Sub

Jerzy Duda, WZ AGH, 2009-2010

Lista

Lista jest uporz

ą

dkowan

ą

kolekcj

ą

elementów zapewniaj

ą

c

ą

dost

ę

p

do dowolnego elementu

W przeciwie

ń

stwie do tablicy rozmiar listy mo

ż

e si

ę

zwi

ę

ksza

ć

lub

zmniejsza

ć

w miar

ę

potrzeby

Ka

ż

da lista musi implementowa

ć

przynajmniej 4 operacje

insert

– wstawia element na wskazan

ą

pozycj

ę

listy i zwi

ę

ksza rozmiar

listy o 1

delete

– usuwa element ze wskazanej pozycji listy i zmniejsza jej

rozmiar

get

– zwraca warto

ść

elementu znajduj

ą

cego si

ę

na wskazanej pozycji

size

– zwraca rozmiar listy

Wszystkie pozostałe operacje mog

ą

by

ć

zaimplementowane na

bazie tych 4 operacji

Np. zmiana warto

ś

ci elementu na wskazanej pozycji

set

–

kombinacja delete i insert;

add

– doł

ą

czenie elementu na ko

ń

cu listy

(kombinacja size i insert)

4

Jerzy Duda, WZ AGH, 2009-2010

Lista – implementacja (1)

Listy implementuje si

ę

na 2 podstawowe sposoby

listy tablicowe – oparte na tablicach

listy wi

ą

zane – oparte na wska

ź

nikach

Lista tablicowa wykorzystuje tablic

ę

do przechowywania elementów

Odczyt i modyfikacja elementów jest bardzo prosta

Operacje wstawiania i usuwania wymagaj

ą

natomiast przesuwania

(kopiowania) elementów

Ponadto zwi

ę

kszenie rozmiaru tablicy wymaga ka

ż

dorazowego

utworzenia nowej wi

ę

kszej tablicy i skopiowania do niej całej

zawarto

ś

ci listy

Implementacja tablicowa jest efektywna w przypadku, gdy dost

ę

p do

listy odbywa si

ę

na podstawie indeksów lub w sposób sekwencyjny

Jerzy Duda, WZ AGH, 2009-2010

Lista – implementacja (2)

Lista wi

ą

zana stanowi ła

ń

cuch elementów poł

ą

czonych ze sob

ą

wska

ź

nikami

Ka

ż

dy element posiada wska

ź

nik na elementy poprzedni i nast

ę

pny

Jest to lista podwójnie wi

ą

zana (dwukierunkowa)

Wstawianie i usuwanie elementów w takiej li

ś

cie wymaga jedynie

modyfikacji wska

ź

ników

Problemem jest natomiast dost

ę

p do elementu na wskazanej pozycji

– wymaga to przegl

ą

dania ła

ń

cucha wska

ź

ników

A

B

C

indeks 0

indeks 1

indeks 2

nast

ę

pny (next)

nast

ę

pny (next)

poprzedni (previous)

poprzedni (previous)

5

Jerzy Duda, WZ AGH, 2009-2010

Kolekcje w VBA (1)

List

ę

tablicow

ą

mo

ż

na zaimplementowa

ć

w VBA za pomoc

ą

obiektu Collections

1.

Nale

ż

y zadeklarowa

ć

obiekt kolekcji

2.

Nast

ę

pnie utworzy

ć

obiekt kolekcji

Do kolekcji obiekty dodawane s

ą

metod

ą

Add (kolekcja sama si

ę

powi

ę

ksza)

Dim KolekcjaOsób As Collection

Sub test3()

Dim KolekcjaOsób As Collection
Set KolekcjaOsób = New Collection
KolekcjaOsób.Add "Jan Kowalski"
KolekcjaOsób.Add "Anna Nowak"

End Sub

Set KolekcjaOsób = New Collection

Jerzy Duda, WZ AGH, 2009-2010

Kolekcje w VBA (2)

Dost

ę

p do poszczególnych obiektów – wła

ś

ciwo

ść

Item

Ilo

ść

elementów mo

ż

na odczyta

ć

poprzez wła

ś

ciwo

ść

Count

Obiekty mo

ż

na usuwa

ć

metod

ą

Remove

Sub test4()

Dim Kolekcja2 As Collection
Set Kolekcja2 = New Collection
Kolekcja2.Add "Jan Kowalski"
Kolekcja2.Add "Anna Nowak"
Kolekcja2.Add "Ewa Maj"
MsgBox Kolekcja2.Count
MsgBox Kolekcja2.Item(2)
Kolekcja2.Remove(1)
MsgBox Kolekcja2.Count

End Sub

6

Jerzy Duda, WZ AGH, 2009-2010

Stos

Stos (ang. Stack) jest list

ą

, której elementy dost

ę

pne s

ą

tylko z

jednego ko

ń

ca

Kraniec stosu, do którego mo

ż

na doł

ą

cza

ć

elementy i z którego

mo

ż

na je pobiera

ć

nazywany jest wierzchołkiem stosu

Stos mo

ż

e by

ć

rozpatrywany tak

ż

e jako kolejka LIFO

(Last-In, First-Out)

Podstawowe operacje wykonywane na stosie

push – odło

ż

enie elementu na stos; zwi

ę

kszenie rozmiaru o 1

pop – zdj

ę

cie elementu z wierzchołka; zmniejszenie rozmiaru o 1

size – zwraca liczb

ę

elementów na stosie

C

B

A

Wierzchołek

Jerzy Duda, WZ AGH, 2009-2010

Stos – implementacja i wykorzystanie

Stos mo

ż

na zaimplementowa

ć

wykorzystuj

ą

c

tablice

listy

Przykłady wykorzystania stosów

wie

ż

e Hanoi

kalkulator wykorzystuj

ą

cy odwrotn

ą

notacj

ę

polsk

ą

odwracanie wyrazów w ci

ą

gu

stos wywoła

ń

(call stack)

przetwarzanie dokumentów XML

zarz

ą

dzanie ekranami aplikacji (Wstecz, Dalej)

wycofywanie i ponawianie wykonanych operacji

(2+3)*5

2
3
+
5

*

7

Jerzy Duda, WZ AGH, 2009-2010

Kolejka

Kolejka (ang. Queue) to lista, której elementy przechowywane s

ą

w

sposób umo

ż

liwiaj

ą

cy ich przetwarzanie w okre

ś

lonej kolejno

ś

ci

Najcz

ęś

ciej kolejno

ść

pobierania elementów z kolejki to

ż

sama jest

z kolejno

ś

ci

ą

ich umieszczania (zasada FIFO – First-In First-Out)

W przeciwie

ń

stwie do listy, z której mo

ż

emy pobiera

ć

dowolny

element, w danej chwili dost

ę

pny jest tylko element z czoła kolejki

Podstawowe operacje kolejkowe

enqueue – umieszcza element w kolejce; rozmiar zostaje zwi

ę

kszony o 1

dequeue – pobiera element z czoła kolejki; rozmiar zostaje zmniejszony

size – zwraca rozmiar kolejki

Funkcjonowanie kolejek cz

ę

sto opisywane w kategoriach producenta i

konsumenta

Producent

Producent

Konsument

Konsument

kolejka

Jerzy Duda, WZ AGH, 2009-2010

Kolejka – implementacja
i wykorzystanie

Kolejk

ę

najłatwiej zaimplementowa

ć

za pomoc

ą

listy

Kolejki mog

ą

by

ć

ograniczone (liczba elementów znajduj

ą

ca si

ę

w

kolejce nie mo

ż

e przekracza

ć

okre

ś

lonej warto

ś

ci) lub nieograniczone

Przykłady wykorzystania kolejek

kolejka zada

ń

na routerze – kolejka ograniczona

komunikacja mi

ę

dzyprocesowa i mi

ę

dzyw

ą

tkowa – kolejka blokuj

ą

ca

obsługa zgłosze

ń

np. w call center – kolejka blokuj

ą

ca

Kolejka blokuj

ą

ca jest kolejk

ą

ograniczon

ą

W przypadku gdy producent b

ę

dzie próbował doda

ć

element do

zapełnionej kolejki, zostanie zablokowany do czasu zwolnienia miejsca
w kolejce

Zgłoszenie

1

Klient 4

Konsultant

Konsultant

Call center

Zgłoszenie

2

Zgłoszenie

3

Konsultant

8

Jerzy Duda, WZ AGH, 2009-2010

Kolejka priorytetowa

Kolejka priorytetowa (ang. Priority Queue) to kolejka zapewniaj

ą

ca

dost

ę

p do swych elementów od najwi

ę

kszego do najmniejszego

W danej chwili dost

ę

pny jest tylko najwi

ę

kszy element

Najwi

ę

kszy oznacza pewne kryterium porz

ą

dkuj

ą

ce (komparator)

Zwykła kolejka FIFO – kryterium jest czas przebywania w kolejce

Stos (LIFO) – kryterium jest moment poło

ż

enia elementu na stosie

Podobnie jak dla zwykłych kolejek najwa

ż

niejsze operacje to

enqueue – umieszcza element w kolejce; rozmiar zostaje zwi

ę

kszony o 1

dequeue – pobiera element z czoła kolejki; rozmiar zostaje zmniejszony

peek – udost

ę

pnia element z czoła kolejki

Jerzy Duda, WZ AGH, 2009-2010

8

0

5

3

Kolejka priorytetowa – implementacja

Kolejk

ę

priorytetow

ą

mo

ż

na zaimplementowa

ć

na wiele sposobów

Najłatwiej wykorzysta

ć

list

ę

posortowan

ą

, w której elementy

przechowywane s

ą

w odwrotnej kolejno

ś

ci priorytetów

Operacja pobrania elementu o najwi

ę

kszym priorytecie jest

natychmiastowa, natomiast operacja zakolejkowania elementu ma
liniow

ą

zło

ż

ono

ść

Bardziej efektywn

ą

obliczeniowo implementacj

ą

jest wykorzystanie

stogu (kopiec, ang. heap)

Stóg (inaczej kopiec, sterta) to drzewo binarne, w którym ka

ż

dy w

ę

zeł

ma od 0 do 2 dzieci

X

M

K

A

D

B

E

A

0

1

2

E

4

6

7

8

X

M

K

E

A

F

D

D

B

9

Jerzy Duda, WZ AGH, 2009-2010

Kolejka priorytetowa – implementacja
(2)

Wstawianie elementu do kolejki (wynurzanie) – O(log

2

n)

Zdj

ę

cie elementu korzenia (zatapianie) – O(log

2

n)

X

M

K

A

D

B

F

D

E

P

X

M

K

P

D

B

F

D

E

A

X

P

K

M

D

B

F

D

E

A

A

P

K

M

D

B

F

D

E

X

P

A

K

M

D

B

F

D

E

X

P

M

K

A

D

B

F

D

E

X

Warunek stogowy: ka

ż

dy w

ę

zeł jest wi

ę

kszy od wi

ę

kszego ze swych synów

Jerzy Duda, WZ AGH, 2009-2010

Graf (1)

Graf to struktura G=(V, E) składaj

ą

ca si

ę

z w

ę

złów (wierzchołków V)

poł

ą

czonych za pomoc

ą

kraw

ę

dzi (E)

Grafy dzieli si

ę

na

nieskierowane

skierowane – kraw

ę

dzie skierowane nazywane łukami (A)

Grafy mo

ż

na przechowywa

ć

w pami

ę

ci na kilka sposobów

macierz s

ą

siedztwa

●

lista incydencji

1

0

1

1

3

4

2

1

0

0

0

4

1

1

1

3

0

0

1

2

0

1

0

1

•

1: 2,3

•

2: 1,3

•

3: 1,2,4

•

4: 3

Zło

ż

ono

ść

pami

ę

ciowa O(V

2

)

Zło

ż

ono

ść

pami

ę

ciowa O(V+E)

10

Jerzy Duda, WZ AGH, 2009-2010

Graf (2)

lista kraw

ę

dzi

●

macierz incydencji

•

1 - 2

•

1 - 3

•

3 - 2

•

3 - 4

•

4 - 3

Zło

ż

ono

ść

pami

ę

ciowa O(E

2

)

Zło

ż

ono

ść

pami

ę

ciowa O(V*E)

0

1

-1

0

3-2

-1

1

0

0

3-4

4-3

1-3

1-2

1

0

0

4

-1

-1

0

3

0

0

-1

2

0

1

1

1

Jerzy Duda, WZ AGH, 2009-2010

Binarne drzewo wyszukiwawcze

Drzewo (ang. tree) jest zbiorem poł

ą

czonych w

ę

złów (ang. nodes), w ten

sposób,

ż

e ka

ż

dy posiada zero lub wi

ę

cej w

ę

złów-dzieci i co najwy

ż

ej

jednego rodzica

W

ę

zły nie posiadaj

ą

ce dzieci nazywane s

ą

li

ść

mi (ang. leaves)

Drzewo binarne – w

ę

zeł mo

ż

e mie

ć

co najwy

ż

ej 2 dzieci (lewe i prawe)

Binarne drzewo wyszukiwacze – to drzewo binarne, w którym w

ę

zły

poło

ż

one na lewo od danego w

ę

zła s

ą

od niego mniejsze, a poło

ż

one na

prawo – wi

ę

ksze

Warunek ten umo

ż

liwia efektywne wstawianie, usuwanie i wyszukiwanie

w

ę

złów w drzewie

Ś

redni czas wyszukiwania w drzewie binarnym jest proporcjonalny do

jego wysoko

ś

ci (równy O(h))

W drzewie wywa

ż

onym (ang. balanced) wysoko

ść

drzewa wynosi

O(log N)

11

Jerzy Duda, WZ AGH, 2009-2010

Binarne drzewo wyszukiwawcze (2)

Przykładowe drzewo

Minimum – skrajny lewy w

ę

zeł (A)

Maksimum – skrajny prawy w

ę

zeł (P)

Nast

ę

pnik – w

ę

zeł o warto

ś

ci bezpo

ś

rednio wi

ę

kszej (A

→

D, H

→

I, I

→

K)

Poprzednik – w

ę

zeł o warto

ś

ci bezpo

ś

rednio mniejszej (P

→

M, F

→

D,

I

→

H)

Demo

I

D

L

F

H

K

M

A

korze

ń

lewy

(mniejszy)

prawy

(wi

ę

kszy)

P

li

ś

cie

Jerzy Duda, WZ AGH, 2009-2010

Wyszukiwanie elementu K

Wstawianie (identycznie ja wyszukiwanie)

Binarne drzewo wyszukiwawcze (3)

Demo

I

D

L

F

H

K

M

A

P

I

D

L

F

H

K

M

A

P

K>I
schodzimy
po prawym

I

D

L

F

H

K

M

A

P

K<L
schodzimy
po lewym

I

D

L

F

H

K

M

A

P

J

Usuwanie zale

ż

y od poło

ż

enia w

ę

zła

12

Jerzy Duda, WZ AGH, 2009-2010

Zbiór

Zbiór (ang. set) to nieuporz

ą

dkowana pula danych niedopuszczaj

ą

c

ą

do dublowania elementów

Na zbiorze wykonywane s

ą

nast

ę

puj

ą

ce operacje

add – dodaje warto

ść

do zbioru; zwraca false jak ju

ż

jest

delete – usuwa warto

ść

ze zbioru

contains – sprawdza czy podana warto

ść

jest w zbiorze

size – zwraca rozmiar zbioru

clear – usuwa wszystkie elementy ze zbioru

I

D

L

F

H

K

M

A

P

Jerzy Duda, WZ AGH, 2009-2010

Mapa

Mapa (ang. map) to obiekt ustanawiaj

ą

cy zwi

ą

zek pomi

ę

dzy kluczami

a warto

ś

ciami

Ka

ż

dy klucz musi by

ć

ró

ż

ny od pozostałych

Mapy cz

ę

sto nazywane s

ą

słownikami (dictionaries)

Operacje wykonywane na mapach

get(klucz) – odnajduje warto

ść

skojarzon

ą

z kluczem

set(klucz,warto

ść

) – przypisuje danemu kluczowi now

ą

warto

ść

delete(klucz) – usuwa warto

ść

przypisan

ą

do klucza

contains – sprawdza istnienie klucza w mapie

size – zwraca liczb

ę

par "klucz-warto

ść

"

clear – usuwa z mapy wszystkie pary

123-456

555-444

777-890

Ala

Ewa

Ela

13

Jerzy Duda, WZ AGH, 2009-2010

Tablica haszuj

ą

ca (1)

Tablica haszuj

ą

ca lub mieszaj

ą

ca (ang. hash table) to struktura danych

słu

żą

ca do przechowywania informacji, w taki sposób aby mo

ż

liwy był do

nich szybki dost

ę

p – idealnie O(1)

Odwołania do przechowywanych obiektów dokonywane s

ą

na podstawie

klucza, który dany obiekt (informacj

ę

) identyfikuje

W tablicy mieszaj

ą

cej stosuje si

ę

funkcj

ę

mieszaj

ą

c

ą

(haszuj

ą

c

ą

), która

dla danego klucza wyznacza indeks w tablicy zwany wyci

ą

giem, skrótem

lub znacznikiem haszowania

Przykład: haszowanie ła

ń

cucha znakowego

E+L+V+I+S = 5+12+22+9+19 = 67

M+A+D+O+N+N+A = 13+1+4+15+14+14+1 = 62

S+T+I+N+G = 19+20+9+14+7 = 69

Główna wada – kolizyjno

ść

L+I+V+E+S = 12+9+2+5+19 = 67 (= ELVIS)

Jerzy Duda, WZ AGH, 2009-2010

Tablica haszuj

ą

ca (2)

Lepsze haszowanie ła

ń

cucha – algorytm CRC (implementowane w Java)

31

4*

E+31

3

*L+31

2

*V+31

1

*I+S = 4 996 537

31

4*

L+31

3

*I+31

2

*V+31

1

*E+S = 11 371 687

W celu zredukowania rozmiaru indeksów stosuje si

ę

operator modulo

ELVIS = 4 996 537 % 17 = 16

LIVES = 11 371 687 % 17 = 13

Haszowanie doskonałe (perfect hashing) – funkcja, która nie powoduje
kolizji; w rzeczywisto

ś

ci nieosi

ą

galne

Rozwi

ą

zywanie kolizji

metoda ła

ń

cuchowa – elementy przechowuje si

ę

nie w tablicy lecz na li

ś

cie

zwi

ą

zanej z danym indeksem

metoda adresowania otwartego – je

ż

eli jest kolizja dla nowego elementu

dodaje si

ę

warto

ść

pewnej funkcji przyrostu (np. próbkowanie liniowe)

14

Jerzy Duda, WZ AGH, 2009-2010

Model obiektowy Excela

Jerzy Duda, WZ AGH, 2009-2010

Ka

ż

dy obiekt posiada unikatowe dla niego wła

ś

ciwo

ś

ci oraz

metody

Podstawowa hierarchia obiektów w Excelu

Application – obiekt aplikacji Excel

obiekt Workbooks – kolekcja wszystkich obiektów Workbook

obiekt Workbook – obiekt skoroszytu (mo

ż

e by

ć

obiekt Worksheets – kolekcja wszystkich obiektów Worksheet

obiekt Worksheet – obiekt arkusza Excela

Model obiektowy Excela (1)

15

Jerzy Duda, WZ AGH, 2009-2010

Podstawowa hierarchia obiektów w Excelu (c.d.)

obiekt Sheets – kolekcja wszystkich obiektów Worksheet
(arkuszy) oraz obiektów Chart (wykresów)

obiekt Worksheet – obiekt arkusza Excela składa si

ę

z

kolekcji obiektów Rows – poszczególne wiersze arkusza

kolekcji obiektów Columns – kolumny arkusza

obiektu Range – zakres komórek

Model obiektowy VBA dla Excel (2)

Jerzy Duda, WZ AGH, 2009-2010

Podstawowe metody i wła

ś

ciwo

ś

ci obiektu

Worksheets

Add – dodaje arkusz do arkusz

Close – zamyka arkusz

Delete – usuwa arkusza

Activate – uaktywnia arkusz

Count – podaje liczb

ę

arkuszy

Name – zwraca/ustawia nazw

ę

arkusza

Model obiektowy VBA dla Excel (3)

Sub test6()

MsgBox Worksheets.Count
Worksheets.Add
Worksheets(1).Name = "Test"
Worksheets("Test").Rows(1).Select

End Sub

16

Jerzy Duda, WZ AGH, 2009-2010

Podstawowe metody i wła

ś

ciwo

ś

ci obiektu

Range

Value – odczytuje/ustawia warto

ść

dla zakresu

Formula – odczytuje/ustawia formuł

ę

dla zakresu

Select – zaznacza zakres

Font – formatuje czcionk

ę

Cells(x,y) – odwołuje si

ę

do komórki (x,y) z podanego zakresu

Offset(x,y) – adres jako przesuni

ę

cie w pionie o x i w poziomie o y

Model obiektowy VBA dla Excel (4)

Sub test7()

Worksheets(1).Activate
Range("A1:C5").Value = "*"
Range("A1:C5").Cells(2, 2) = "@"
Range("B3").Offset(-2, 2) = "$"

End Sub

Jerzy Duda, WZ AGH, 2009-2010

Projektowanie obiektowe

Projektowanie zorientowane obiektowo (OOP)

Projektowanie zorientowane obiektowo (OOP)

-

podział aplikacji na kilka autonomicznych
komponentów, które pracuj

ą

razem

Mimo,

ż

e istnieje wiele metodologii takiego

podziału projektowanie obiektowe to bardziej
sztuka ni

ż

nauka

*

Proces projektowania zorientowanego obiektowo
składa si

ę

z trzech podstawowych zada

ń

:

1.

podział dziedziny problemu na typy obiektów (klasy)

2.

modelowanie zwi

ą

zków pomi

ę

dzy tymi typami

3.

projektowanie pól oraz metod dost

ę

pu w typach

*

Ź

ródło: Patrick Niemeyer, Jonathan Knudsen: Java. Wprowadzenie

17

Jerzy Duda, WZ AGH, 2009-2010

Obiekt

Definicja powszechna:

Obiekt w j

ę

zyku obiektowym reprezentuje obiekt w

ś

wiecie

rzeczywistym; jest struktur

ą

posiadaj

ą

c

ą

to

ż

samo

ść

, stan

(pola) i zachowanie (metody)

Definicja ogólniejsza:

Obiekt jest elementem modelu poj

ę

ciowego obdarzonym

odpowiedzialno

ś

ci

ą

za pewien obszar

ś

wiata

rzeczywistego; sposób realizacji tej odpowiedzialno

ś

ci

zale

ż

y od samego obiektu

*

Ź

ródło: http://wazniak.mimuw.edu.pl/

Jerzy Duda, WZ AGH, 2009-2010

Poj

ę

cia OOP

Worksheet.Name

Jaka

ś

cecha „rzeczy”

Wła

ś

ciwo

ść

(Property)

Worksheet.Add

Czynno

ść

, któr

ą

„rzecz” mo

ż

e wykona

ć

Metoda

Worksheet

Jaka

ś

„rzecz”

Obiekt

Przykład

Opis

Poj

ę

cie

18

Jerzy Duda, WZ AGH, 2009-2010

Odpowiedzialno

ść

*

Ź

ródło: http://wazniak.mimuw.edu.pl/

Hermetyzacja

Polimorfizm

Dziedziczenie

Abstrakcja

Elastyczność

Modularyzacja

Powtórne użycie

Odpowiedzialność

Jerzy Duda, WZ AGH, 2009-2010

Metodyka CRC

Class – Responsibilty – Collaboration) 1/2

Zaproponowana przez jednego z propagatorów tzw.
zwinnych metodyk – Warda Cunninghama

Karty CRC s

ą

kartkami papieru podzielonymi na trzy cz

ęś

ci,

opisuj

ą

cymi nast

ę

puj

ą

ce własno

ś

ci klasy:

nazw

ę

klasy (ang. Class), intuicyjnie opisuj

ą

c

ą

jej

odpowiedzialno

ść

,

odpowiedzialno

ść

(ang. Responsibility), zawieraj

ą

c

ą

dłu

ż

szy

opis zada

ń

, jakie b

ę

d

ą

powierzone klasie,

współdziałanie (ang. Collaboration), przedstawiaj

ą

ce

interakcje obiektu z innymi klasami.

*

Ź

ródło: http://wazniak.mimuw.edu.pl/

19

Jerzy Duda, WZ AGH, 2009-2010

Metodyka CRC

Class – Responsibilty – Collaboration) 2/2

Szczególnie przydatna na etapie definiowania
odpowiedzialno

ś

ci poszczególnych klas i okre

ś

lania

sposobu współpracy

Pomija całkowicie wewn

ę

trzn

ą

struktur

ę

klas, skupiaj

ą

c si

ę

wył

ą

cznie na ich zachowaniu i odpowiedzialno

ś

ci

Zło

ż

ono

ść

procesu projektowania schematu klas jest

ograniczona do minimum

*

Ź

ródło: http://wazniak.mimuw.edu.pl/

Jerzy Duda, WZ AGH, 2009-2010

Przykład:

Ś

rednia ocen dla grupy studentów

Podział na klasy i zwi

ą

zki mi

ę

dzy nimi

Cel:
Stworzenie aplikacji, która
zapami

ę

tuje podstawowe

dane dotycz

ą

ce grupy

studentów, prowadz

ą

cego

oraz liczy

ś

redni

ą

ocen dla

tej grupy

+UstawDateUr()
+PobierzDateUr() : Date
+UstawNazwisko()
+PodajNazwisko() : string
+UstawImie()
+PodajImie() : string

-nazwisko : string
-imie : string
-data_ur : Date

Osoba

+PodajOcene() : float
+PodajDate() : Date

-ocena : float
-data_oceny : Date

Student

+podajTytul() : string
+ustawTytul()
+ustawOcene()
+ustawDateOceny()

+tytuł : string

Pracownik

+DodajOsobe()
+PrzypiszPrac()
+LiczSrednia() : float

-studenci[] : Student
-pracownik : Pracownik
+numer : int

Grupa

1

1..*

1..*

1

20

Jerzy Duda, WZ AGH, 2009-2010

Tworzenie klasy w VBA

Menu

Insert



Class Module

Ustawiamy Name
– Nazwa klasy

Deklarujemy zmienne
prywatne (ukryte)

Jest to mechanizm

hermetyzacji

zmiennych

Jerzy Duda, WZ AGH, 2009-2010

Hermetyzacja

Definicja powszechna

Ukrywanie danych przed niepo

żą

danym dost

ę

pem

Wystarczy zadeklarowa

ć

pola jako niepubliczne oraz

stworzy

ć

metody dost

ę

pu do nich, aby osi

ą

gn

ąć

wła

ś

ciwy

poziom ukrycia implementacji

*

Ź

ródło: http://wazniak.mimuw.edu.pl/

+UstawDateUr()
+PobierzDateUr() : Date
+UstawNazwisko()
+PodajNazwisko() : string
+UstawImie()
+PodajImie() : string

-nazwisko : string
-imie : string
-data_ur : Date

Osoba

Private pNazwisko As String
Private pImie As String
Private pData As Date

Public Property Get Nazwisko() As String

Nazwisko = pNazwisko

End Property
Public Property Let Nazwisko(Value As String)

pNazwisko = Value

End Property
...

21

Jerzy Duda, WZ AGH, 2009-2010

Wła

ś

ciwo

ś

ci w VBA (1)

Dla zhermetyzowanych zmiennych nale

ż

y utworzy

ć

metody

dost

ę

powe (wła

ś

ciwo

ś

ci)

Property Get

Property Get

dla zwrotu warto

ś

ci ukrytej zmiennej skalarnej lub

obiektowej

Property

Property

Let

Let

dla ustawienia warto

ś

ci ukrytej zmiennej skalarnej

Property Set

Property Set

dla ustawienia warto

ś

ci ukrytej zmiennej obiektowej

Private string nazwisko
Public Property Get

Get

Nazwisko() As String

Nazwisko = nazwisko

End Property
Public Property Let

Let

Nazwisko(Value As String)

nazwisko = Value

End Property

Private Pracownik prowadz

ą

cy

Public Property Ge

Ge

t

t

Prowadz

ą

cy()

Set Prowadz

ą

cy = pracownik

End Property
Public Property S

S

et

et

Prowadz

ą

cy(Value As Pracownik)

set prowadz

ą

cy = Value

End Property

Jerzy Duda, WZ AGH, 2009-2010

Wła

ś

ciwo

ś

ci w VBA (2)

Je

ż

eli zmienna ma by

ć

tylko do odczytu na zewn

ą

trz klasy,

tworzymy tylko wła

ś

ciwo

ść

Get

Je

ż

eli chcemy tylko da

ć

mo

ż

liwo

ść

tylko jednorazowego

przypisania obiektu do zmiennej stosujemy nast

ę

puj

ą

cy kod

Private string nazwisko
Public Property Get

Get

Nazwisko() As String

Nazwisko = nazwisko

End Property

Dim os As New Osoba
Osoba.Nazwisko = "Kowalski"

'Bł

ą

d

Private Pracownik prowadz

ą

cy

Public Property Set Prowadz

ą

cy(Value As Pracownik)

If prowadz

ą

cy Is Nothing Then

Set prowadz

ą

cy = Value

End If

End Property

22

Jerzy Duda, WZ AGH, 2009-2010

U

ż

ycie wła

ś

ciwo

ś

ci klasy w VBA

1.

Deklaracja obiektu (

Dim obiekt As klasa

)

2.

Utworzenie obiektu (

Set obiekt = New klasa

)

3.

Ustawienie wła

ś

ciwo

ś

ci

(

obiekt.właciwo

ść

= warto

ść

)

Obiekty mo

ż

na równie

ż

tworzy

ć

podczas deklaracji

Dim os As Osoba
Set os = New Osoba
os.Imi

ę

= "Anna"

os.Nazwisko = "Nowak"
os.Data = "20-02-1990"

Dim os As New

New

Osoba

os.Imi

ę

= "Anna"

...

Jerzy Duda, WZ AGH, 2009-2010

Metody w VBA

Dla klas mo

ż

na tworzy

ć

„zwykłe” metody operuj

ą

ce na

zmiennych klasy

...
Public Sub Wy

ś

wietlDane()

MsgBox "Osoba: " & Imi

ę

& " " & Nazwisko

End Sub

Dim os As New

New

Osoba

os.Imi

ę

= "Anna"

os.Nazwisko = "Nowak"
os.Wy

ś

wietlDane

23

Jerzy Duda, WZ AGH, 2009-2010

Konstruktory i destruktory w VBA

Klasa mo

ż

e posiada

ć

te

ż

metod

ę

inicjalizuj

ą

c

ą

–

konstruktor

Metoda ta jest wywoływana w momencie tworzenia obiektu
(operatorem New)

Analogicznie do konstruktorów klasa mo

ż

e posiada

ć

te

ż

destruktor

Destruktory uruchamiane s

ą

w momencie usuwania obiektu z

pami

ę

ci

Destruktory słu

żą

zwalnianiu pami

ę

ci, zamykaniu plików, itp/

Private Sub Class_Initialize()

pOcena = 2.0

End Sub

Private Sub Class_Terminate()

' jaki

ś

kod '

End Sub

Jerzy Duda, WZ AGH, 2009-2010

Dziedziczenie

Mechanizm wyra

ż

ania podobie

ń

stwa

mi

ę

dzy klasami

Upraszcza definicje klas podobnych do ju

ż

zdefiniowanych

Opisuje generalizacj

ę

i specjalizacj

ę

,

czyni

ą

c wspólne atrybuty i usługi jawnymi

wewn

ą

trz hierarchii klas

W VBA nie ma mechanizmu dziedziczenia
klas; zamiast niego mo

ż

na stosowa

ć

interfejsy

*

Ź

ródło: Coad, Yourdon: Analiza obiektowa, ReadMe 1994

24

Jerzy Duda, WZ AGH, 2009-2010

Abstrakcja w OOP

Zasada ignorowania tych aspektów przedmiotu, które
nie s

ą

istotne z punktu widzenia bie

żą

cego celu, by móc

lepiej skoncentrowa

ć

si

ę

na wła

ś

ciwych [Słownik

Oxford]

Zdolno

ść

do ignorowania niektórych decyzji

projektowych lub mo

ż

liwo

ś

ci odło

ż

enia ich w czasie

System zbudowany z abstrakcyjnych komponentów
mo

ż

e by

ć

łatwo rozszerzany, poniewa

ż

zmiany nie s

ą

widoczne poza tym komponentem

*

Ź

ródło: http://wazniak.mimuw.edu.pl/

Jerzy Duda, WZ AGH, 2009-2010

Abstrakcja w VBA

W VBA nie mo

ż

na tworzy

ć

klas abstrakcyjnych, nie ma te

ż

mechanizmu dziedziczenia klas

Zamiast tego mo

ż

na wykorzysta

ć

interfejsy

Interfejs

Interfejs

to zbiór wła

ś

ciwo

ś

ci i metod (a tak

ż

e zdarze

ń

), które

okre

ś

laj

ą

cechy i zachowanie obiektu (odpowiedzialno

ść

)

Mo

ż

na tworzy

ć

interfejsy abstrakcyjne
poprzez nie-
implementowanie
kodu poszczególnych
własno

ś

ci i metod

*

Ź

ródło: http://wazniak.mimuw.edu.pl/

Public Property Get Imi

ę

() As String

End Property
Public Property Let Imi

ę

(Value As String)

End Property
Public Property Get Nazwisko() As String
End Property
Public Property Let Nazwisko(Value As String)
End Property
Public Property Get Data() As Date
End Property
Public Property Let Data(Value As Date)
End Property

25

Jerzy Duda, WZ AGH, 2009-2010

Interfejs i dziedziczenie w VBA

Implementacja interfejsu (dziedziczenie jego
odpowiedzialno

ś

ci, kontraktu) odbywa si

ę

poprzez

wstawienie deklaracji Implements na pocz

ą

tku modułu klasy

Implements

Implements

AOsoba

Private pImi

ę

As String

Private pNazwisko As String
Private pData As Date
Private pOcena As Double
Public Property Get AOsoba_Imi

ę

() As String

AOsoba_Imi

ę

= pImi

ę

End Property
Public Property Let AOsoba_Imi

ę

(Value As String)

pImi

ę

= Value

End Property
Public Property Get AOsoba_Nazwisko() As String

AOsoba_Nazwisko = pNazwisko

End Property
...

Jerzy Duda, WZ AGH, 2009-2010

Polimorfizm

Poly

(gr. wiele)

morph

(gr. posta

ć

)

Mechanizm umo

ż

liwiaj

ą

cy współistnienie ró

ż

nych

metod, które mog

ą

zosta

ć

wykonane w odpowiedzi na

komunikat odebrany przez obiekt

Wybór metody dokonywany jest dynamicznie, na
podstawie typu obiektu odbiorcy

*

Ź

ródło: http://wazniak.mimuw.edu.pl/

26

Jerzy Duda, WZ AGH, 2009-2010

Polimorfizm w VBA – przykład

'Interfejs Figura

Public Sub Rysuj()
End Sub

'Klasa Koło

Implements Figura
Sub Figura_Rysuj()
MsgBox "Rysuj

ę

koło"

End Sub

'Klasa Kwadrat

Implements Figura
Sub Figura_Rysuj()
MsgBox "Rysuj

ę

kwadrat"

End Sub

Sub testF()

Dim ko As New koło
Dim kw As New Kwadrat
Call Maluj(ko)
Call Maluj(kw)

End Sub

Sub Maluj(f As Figura)

f.Rysuj

End Sub

Jerzy Duda, WZ AGH, 2009-2010

Kolekcje obiektów w VBA

Kolekcja obiektów Osoba

Sub testGrupy()

Dim grupa As New Collection
Dim s1 As New Osoba
s1.Imi

ę

= "Jan"

s1.Nazwisko = "Kowalski"
s1.Ocena = 4
grupa.Add s1
Dim s2 As New Osoba
s2.Imi

ę

= "Anna"

s2.Nazwisko = "Nowak"
s2.Ocena = 5
grupa.Add s2

...

...

suma = 0
For Each s In grupa

suma = suma + s.Ocena

Next
MsgBox "

Ś

rednia ocen " &

suma / grupa.Count

End Sub

27

Jerzy Duda, WZ AGH, 2009-2010

Serializacja obiektów

Serializacja

– w programowaniu komputerów proces

przekształcania obiektów do postaci szeregowej (czyli w
strumie

ń

bajtów) z zachowaniem aktualnego stanu

obiektu

Serializowany obiekt mo

ż

e zosta

ć

utrwalony w pliku

dyskowym, przesłany do innego procesu lub innego
komputera poprzez sie

ć

Procesem odwrotnym do serializacji jest

deserializacja

.

Proces ten polega na odczytaniu wcze

ś

niej zapisanego

strumienia danych i odtworzeniu na tej podstawie
obiektu klasy wraz z jego stanem bezpo

ś

rednio sprzed

serializacji

*

Ź

ródło: http://wikipedia.org

Jerzy Duda, WZ AGH, 2009-2010

Serializacja obiektów w VBA (1)

Serializacja

*

Ź

ródło: http://wazniak.mimuw.edu.pl/

Sub Serializuj_Osoba(os As Osoba)

Open "Dane" For Output As #1
Write #1, os.Imi

ę

Write #1, os.Nazwisko
Write #1, os.Data
Close #1

End Sub

Deserializacja

Function Deserializuj_Osoba() As Osoba

Open "Dane" For Input As #1
Input #1, Imi

ę

Input #1, Nazwisko
Input #1, Data
Close #1
Dim os As New Osoba
os.Imi

ę

= Imi

ę

os.Nazwisko = Nazwisko
os.Data = Data
Set Deserializuj_Osoba = os

End Function

28

Jerzy Duda, WZ AGH, 2009-2010

Kod testuj

ą

cy

Plik z danymi – „Dane”

Serializacja obiektów w VBA (2)

Sub Test_Serializuj()

Dim os1 As New Osoba
os1.Imi

ę

= "Anna"

os1.Nazwisko = "Nowak"
Call Serializuj_Osoba(os1)
Dim os2 As Osoba
Set os2 = Deserializuj_Osoba()
MsgBox os2.Imi

ę

End Sub

"Anna"
"Nowak"
#1899-12-30#