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.