1

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

1

Struktury statyczne

Tablice jednowymiarowe (wektory):

są zespołem określonej liczby zmiennych o wspólnej

nazwie, które ponumerowano liczbami naturalnymi

−

każda z nich ma przypisany na stałe tzw. indeks,

mogą przechowywać nie większą od ich długości

liczbę elementów zbioru danych jednakowego typu
zgodnego z zadeklarowanym typem tablicy

Np. tablica T :

15 11 24 36 17 15 51

1

2

3

4

5

6

7

−

zmienne

−

indeksy

ΤΤΤΤ

−

nazwa

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

2

W zapisie symbolicznym T(6) oznacza 6 zmienną w tablicy T

Indeks może być określony przez bezpośrednie podanie wartości
w odwołaniu do elementu tablicy, np. T(6),

lub użycie nazwy zmiennej o typie zgodnym z indeksem, np. T(X)

Zmienną X nazywamy wtedy zmienną indeksową i wskazanie
elementu tablicy wymaga odczytania jej aktualnej wartości

15 11 24 36 17 15 51

1

2

3

4

5

6

7

−

zmienne

−

indeksy

ΤΤΤΤ

−

nazwa

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

3

Algorytm sumowania N liczb zapamiętanych w tablicy T :

1. S

←

0 (ustalenie początkowej wartości sumy),

2. K

←

1 (ustalenie początkowej wartości zmiennej indeksowej),

3. wykonaj co następuje N razy:

3.1. S

←

S + T(K),

3.2. K

←

K + 1,

4. odczytaj wartość zmiennej S.

Użyte struktury danych:
tablica jednowymiarowa T o długości co najmniej N,
zmienna N do przechowania ilości liczb,
zmienna indeksowa K do sterowania iteracją i
pomocnicza zmienna S do przechowywania wyniku.

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

4

K=N

TAK

NIE

S

←

S + T(K)

K

←

K + 1

K

←

1

S

←

0

start

stop

po zakończeniu działania
algorytmu zmienna S ma wartość
sumy N liczb z tablicy T

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

5

Algorytm sortowania bąbelkowego N liczb
zapamiętanych w tablicy V :

1. wykonaj co następuje N

−

1 razy:

1.1. X

←

1,

1.2. dopóki X < N , wykonuj co następuje,

1.2.1. jeśli V(X + 1) < V(X) to:

U

←

V(X); V(X)

←

V(X + 1); V(X + 1)

←

U;

1.2.2. X

←

X + 1.

Użyte struktury danych:
tablica jednowymiarowa

V o długości co najmniej N,

zmienna

N do przechowania ilości liczb,

zmienna indeksowa

X do sterowania iteracją wewnętrzną i

pomocnicza zmienna

U.

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

6

Tablice dwu – i więcej wymiarowe (macierze):

są zespołem określonej liczby zmiennych o wspólnej

nazwie, które oznaczono dwoma lub więcej indeksami ,

mogą przechowywać nie większą od ich rozmiaru liczbę

elementów zbioru danych jednakowego typu zgodnego z
zadeklarowanym typem tablicy

Np. tablica

W :

15 11 24 36 17 15 51

1

2

3

4

5

6

7

zmienne

W

nazwa -

14 32 28 26 19 20 43

11 16 13 31 10 15 41

1

2

3

- indeksy kolumn

indeksy wierszy

2

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

7

W zapisie symbolicznym W(2, 5) oznacza zmienną w tablicy W
położoną umownie na przecięciu 2. wiersza i 5. kolumny

15 11 24 36 17 15 51

1

2

3

4

5

6

7

14 32 28 26

19

20 43

11 16 13 31 10 15 41

1

2

3

W

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

8

Algorytm sumowania N

x

M liczb zapamiętanych w tablicy W :

1. S

←

0 (ustalenie początkowej wartości sumy),

2. K

←

1 (ustalenie początkowej wartości 1. zmiennej indeksowej),

3. wykonaj co następuje N razy:

3.1. L

←

1 (ustalenie początkowej wartości 2. zm. indeksowej),

3.2. wykonaj co następuje M razy:

3.2.1. S

←

S + W(K, L),

3.2.2. L

←

L + 1,

3.3 K

←

K + 1,

4. odczytaj wartość zmiennej S.

Użyte struktury danych:
tablica dwuwymiarowa W o rozmiarze co najmniej N

x

M, zmienne N i M

do przechowania liczby zajętych „wierszy’ i „kolumn”, zmienna indeksowa K
do sterowania iteracją zewnętrzną, zmienna indeksowa L do sterowania iteracją
wewnętrzną i pomocnicza zmienna S do przechowywania wyniku.

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

9

start

L = M

stop

K

←

K + 1

K

←

1

L

←

1

L

←

L + 1

NIE

TAK

K = N

NIE

TAK

iteracja zewnętrzna

iteracja wewnętrzna

S

←

S + W(K, L)

S

←

0

po zakończeniu działania
algorytmu zmienna S ma
wartość sumy liczb z N
wierszy i M kolumn tablicy W

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

10

Rekordy:

są zespołem określonej liczby zmiennych różnych typów,

które mają własne nazwy oraz dodatkowo nazwę całego
rekordu (te zmienne są nazywane polami rekordu),

mogą przechowywać określoną liczbę elementów zbioru

danych o różnych typach, ale typ elementu musi być zgodny
z zadeklarowanym typem pola.

ala

pola

R

nazwa rekordu -

7

:

B

C

D

nazwy pól (zmiennych)

12

A

Np. rekord R :

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

11

W zapisie symbolicznym B.R oznacza pole
(zmienną) o nazwie B z rekordu o nazwie R.

Różne rodzaje struktur statycznych można łączyć ze sobą

Można zadeklarować np. tablicę rekordów
i odwoływać się potem do pól w indeksowanych rekordach,
np. B.U(3)

ala

U

7

:

B

C

D

12

A

ma

1

&

9

kot

4

@

41

bez

5

?

24

1

2

3

4

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

12

Struktury dynamiczne (implementacja wskaźnikowa)

Zmienne wskaźnikowe (wskaźniki):

wartością nadawaną zmiennej wskaźnikowej jest adres, pod

którym można znaleźć w pamięci inną zmienną określonego typu,

aby można było zapisać lub odczytać element danych w

zmiennej wskazywanej, trzeba znać jej adres, czyli odczytać
wartość zmiennej, która na nią wskazuje, tzw. wskaźnika.

wartość zmiennej wskazanej

7

P

nazwa wskaźnika

adres

3

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

13

W zapisie symbolicznym [P] oznacza zmienną wskazaną
wartością (adresem) wskaźnika P

Czym różni się posługiwanie się adresami od posługiwania się
nazwami zmiennych?

7

P

2

S

7

X

2

Y

X

←

←

←

←

Y

2

X

2

Y

[P]

←

←

←

←

[S]

2

P

2

S

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

14

7

P

2

S

[P]

←

←

←

←

[S]

2

P

2

S

7

P

2

S

P

←

←

←

←

S

7

P

2

S

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

15

Wskaźnik może zawierać nie tylko adres pojedynczej
zmiennej, ale także adres struktury danych np. rekordu.

Typ zmiennej wskaźnikowej musi zawsze zawierać
dodatkowo określenie rodzaju obiektu, na który ta zmienna
może wskazywać.

Jeśli umieścimy w rekordzie co najmniej jedno pole typu
wskaźnikowego, to uzyskamy możliwość budowania
dynamicznych struktur wskaźnikowych.

Takie struktury powstają z identycznych rekordów o takiej
samej liczbie, nazwach i typach pól, wśród których jest co
najmniej jedno pole wskaźnikowe.

Wartością tego pola jest adres innego rekordu w strukturze
lub symboliczny adres pusty – NIL.

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

16

11

„ala”

NIL

rekord 1

8

„ma”

rekord 2

rekord 3

5

„kota”

NIL

pole kluczowe A -

pole dodatkowe B -

pole wskaźnikowe C -

pole wskaźnikowe D -

wskaźnik na 1. rekord

NIL

– symboliczny adres pusty

G

adres

adres

adres

adres

adres

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

17

W zapisie symbolicznym A.[P] oznacza pole A w rekordzie
wskazanym wartością (adresem) wskaźnika P

Do pól rekordów w strukturze dynamicznej trzeba
odwoływać się za pomocą wskaźników:

A.[P.[P.[X]]]

←

←

←

←

21

A – pole kluczowe

X

P.[X]

P.[P.[X]]

21

P – pole wskaźnikowe X – wskaźnik na 1. rekord

A.[X]

A.[P.[X]]

P.[P.[P.[X]]]

A.[P.[P.[X]]]

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

18

W trakcie działania algorytmu można łatwo modyfikować
dynamiczną strukturę wskaźnikową poprzez zmianę wartości
pól wskaźnikowych w rekordach: poprzez podstawianie
wartości jednych wskaźników pod wartości innych.

Ulega wtedy zmianie wewnętrzną struktura wskazań, która
decyduje o drogach docierania do poszczególnych rekordów.

W oparciu o możliwość kreowania w pamięci nowych
rekordów o zadanym schemacie i zwalniania miejsca
zajmowanego przez niepotrzebne już rekordy można
zdefiniować podstawowe operacje, za pomocą których można
zmieniać liczbę rekordów w strukturze dynamicznej w trakcie
działania algorytmu:

WSTAW

(ang. INSERT) i USUŃ (ang. DELETE)

4

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

19

WSTAW ( S ) – dołącz w miejscu wskazanym w strukturze
wskaźnikiem S nowy rekord, który wcześniej utworzono
w pamięci wg określonego dla tej struktury schematu

Przykładowa realizacja operacji WSTAW ( S )

G

P.[G]

A.[G]

S

T

Utwórz nowy rekord pod wskazaniem T

T – wskaźnik pomocniczy

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

20

P.[S]

S

T

P.[T]

P.[T]

←

←

←

←

P.[S]

P.[S]

←

←

←

←

T

P.[S]

S

T

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

21

USUŃ ( S ) – odłącz od struktury rekord wskazywany
polem wskaźnikowym rekordu wskazanego przez S
i zwolnij zajmowane przez niego miejsce w pamięci

Przykładowa realizacja operacji USUŃ ( S )

G

P.[G]

A.[G]

S

T

T – wskaźnik pomocniczy

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

22

T

←

←

←

←

P.[S]

P.[S]

S

T

P.[S]

←

←

←

←

P.[T]

P.[S]

S

T

P.[T]

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.

23

Zwolnij miejsce w pamięci wskazane prze T

T

←

←

←

←

NIL

T

Możliwość użycia w trakcie działania algorytmu operacji
WSTAW i USUŃ oraz możliwość zmiany powiązań pomiędzy
rekordami poprzez podstawianie wartości pól wskaźnikowych
decyduje o tym, że takie struktury wskaźnikowe są strukturami
dynamicznymi.