Algorytmy i programowanie.pdf

(373 KB) Pobierz

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

803183791.061.png

803183791.072.png

803183791.083.png

803183791.094.png

803183791.001.png

803183791.012.png

803183791.013.png

803183791.014.png

803183791.015.png

803183791.016.png

803183791.017.png

803183791.018.png

803183791.019.png

803183791.020.png

803183791.021.png

803183791.022.png

803183791.023.png

803183791.024.png

803183791.025.png

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

803183791.026.png

803183791.027.png

803183791.028.png

803183791.029.png

803183791.030.png

803183791.031.png

803183791.032.png

803183791.033.png

803183791.034.png

803183791.035.png

803183791.036.png

803183791.037.png

803183791.038.png

803183791.039.png

803183791.040.png

803183791.041.png

803183791.042.png

803183791.043.png

803183791.044.png

803183791.045.png

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

803183791.046.png

803183791.047.png

803183791.048.png

803183791.049.png

803183791.050.png

803183791.051.png

803183791.052.png

803183791.053.png

803183791.054.png

803183791.055.png

803183791.056.png

803183791.057.png

803183791.058.png

803183791.059.png

803183791.060.png

803183791.062.png

803183791.063.png

803183791.064.png

803183791.065.png

803183791.066.png

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

803183791.067.png

803183791.068.png

803183791.069.png

803183791.070.png

803183791.071.png

803183791.073.png

803183791.074.png

803183791.075.png

803183791.076.png

803183791.077.png

803183791.078.png

803183791.079.png

803183791.080.png

803183791.081.png

803183791.082.png

803183791.084.png

803183791.085.png

803183791.086.png

803183791.087.png

803183791.088.png

803183791.089.png

803183791.090.png

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

803183791.091.png

803183791.092.png

803183791.093.png

803183791.095.png

803183791.096.png

803183791.097.png

803183791.098.png

803183791.099.png

803183791.100.png

803183791.101.png

803183791.102.png

803183791.103.png

803183791.104.png

803183791.002.png

803183791.003.png

803183791.004.png

803183791.005.png

803183791.006.png

803183791.007.png

803183791.008.png

803183791.009.png

803183791.010.png

803183791.011.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin