1
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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.