Algorytmy i programowanie

[ Pobierz całość w formacie PDF ]
Informatyka
Algorytmy i programowanie
Wykład 5-6
Struktury danych
Programowanie obiektowe
Jerzy Duda, 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
Jerzy Duda, WZ AGH, 2009-2010
1
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
Jerzy Duda, WZ AGH, 2009-2010
2
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
)
Jerzy Duda, WZ AGH, 2009-2010
3
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
indeks 1
indeks 2
indeks 0
następny (next)
następny (next)
A
B
C
poprzedni (previous)
poprzedni (previous)
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
Jerzy Duda, WZ AGH, 2009-2010
4
Kolekcje w VBA (1)
Listę tablicową moŜna zaimplementować w VBA za pomocą
obiektu
Collections
1.
NaleŜy zadeklarować obiekt kolekcji
Dim KolekcjaOsób As Collection
2.
Następnie utworzyć obiekt kolekcji
Set KolekcjaOsób = New Collection
Do kolekcji obiekty dodawane sÄ… metodÄ…
Add
(kolekcja sama siÄ™
powiększa)
Sub test3()
Dim KolekcjaOsób As Collection
Set KolekcjaOsób = New Collection
KolekcjaOsób.Add "Jan Kowalski"
KolekcjaOsób.Add "Anna Nowak"
End Sub
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
Jerzy Duda, WZ AGH, 2009-2010
5
[ Pobierz całość w formacie PDF ]