1

Wykład III i IV

Tablice, rekordy i zbiory

Algorytmy i struktury danych
Wyższa Szkoła Biznesu
Semestr III Informatyka
stosowana

2

Tablica

Tablica

(ang.

array)

jest

prawdopodobnie

najbardziej znaną strukturą danych, ponieważ w
wielu językach, jest jedyną bezpośrednio dostępną
strukturą.
Tablica jest strukturą jednorodną; jest złożona ze
składowych tego samego typu zwanego typem
podstawowym.
Tablicę zwie się również strukturą o dostępie
swobodnym (ang. random access); wszystkie
składowe mogą być wybrane w dowolnej kolejności i
są jednakowo dostępne.

3

Definiowanie tablicy

W celu wybrania pojedynczej składowej nazwę
całej struktury uzupełnia się tzw. indeksem
wybierającym składową. Indeks ten powinien
być wartością pewnego typu zwanego typem
indeksującym (ang. index type) tablicy.
Definicja typu tablicowego T zawiera więc
zarówno specyfikację typu podstawowego T

0

,

jak i typu indeksującego I.

type T = array[I] of T

0

4

Przykłady definiowania

tablic

type Wiersz = array [1..5]

of real

type Karta = array [1..80]

of char

type alfa = array [1..10] of

char

5

Tablica typu Wiersz

Konkretną wartość

zmiennej

var x: Wiersz

której

każda

składowa

spełnia

równanie

x

i

=2

-t

,

można zobrazować

tak, jak pokazano

na rysunku

X

1

0.5

X

2

0.25

X

3

0.125

X

4

0.0625

X

5

0.03125

6

Konstruktor tablicowy

Złożoną wartość x typu T o
wartościach składowych c

1,

..., c

n

można

oznaczyć

za

pomocą

konstruktora

tablicowego

i

instrukcji przypisania:

x := T(c

1

,...,c

n

)

7

Selektor tablicowy

Operatorem odwrotnym do konstruktora

jest selektor. Służy on do wybrania

konkretnej składowej tablicy.
Dla danej zmiennej tablicowej x selektor

jest oznaczony nazwą tablicy, po której

występuje

indeks

i

wybierający

odpowiednią składową:

x[i]

8

Zmienna

tablicowa=tablica

zmiennych składowych

Działając na tablicach (zwłaszcza zaś na dużych), stosuje

się technikę selektywnego aktualizowania poszczególnych

składowych zamiast konstruowania całkowicie nowych

wartości złożonych. Wyraża się to traktowaniem zmiennej

tablicowej

jako

tablicy

zmiennych

składowych

i

umożliwieniem

wykonywania

przypisań

wybranym

składowym.

PRZYKŁAD

x[i]:= 0.125

Aczkolwiek aktualizacja selektywna powoduje zmianę

jedynie pojedynczej składowej wartości, jednak z

koncepcyjnego punktu widzenia musimy przyjąć, że

zmienia się również całą wartość złożoną.

9

Indeksy tablicy mogą być

obliczane

Niezwykle ważne konsekwencje pociąga za sobą fakt, że

indeksy tablicy, tzn. „nazwy" składowych muszą być

elementami zdefiniowanego typu skalarnego.
Indeksy mogą być, obliczane, tzn. stała indeksowa może

być zastąpiona wyrażeniem indeksowym. Wyrażenie

to ma być obliczone, a jego wynik decyduje o tym, która

składowa zostanie wybrana.
Wspomniana powyżej możliwość stanowi niezwykle

mocne narzędzie programowania, lecz jednocześnie

umożliwia

popełnianie

jednego

z

najczęściej

spotykanych błędów: wartość wynikowa może znaleźć

się poza przedziałem określonym jako możliwy zakres

indeksu tablicy.

10

Porównywanie tablic

Typ indeksujący powinien być typem skalarnym, tzn. typem

niezłożonym, na którym określona jest pewna relacja porządkująca.

Jeśli typ podstawowy tablicy jest również typem uporządkowanym,

to dostajemy naturalne uporządkowanie typu tablicowego.
Naturalne uporządkowanie dwóch tablic jest zdeterminowane

dwoma odpowiadającymi sobie nierównymi składowymi o

najniższych możliwych indeksach. Formalnie wyraża się to

następująco:

– Dla danych dwóch tablic x i y relacja x < y zachodzi wtedy i tylko

wtedy, gdy istnieje indeks k taki, że x[k]<y[k] oraz x[i]=y[i] dla

wszystkich i<k.

– Na przykład

(2, 3, 5, 7, 9)

< (2, 3, 5, 7, 11)

'LABEL' < 'LIBEL'

11

Moc typu tablicowego

W większości zastosowań nie zakłada się istnienia
relacji porządkującej na typach tablicowych.
Moc typu złożonego otrzymuje się jako iloczyn
mocy jego składowych. Ponieważ wszystkie
składowe typu tablicowego A są tego samego
typu podstawowego B, otrzymujemy

moc(A) = (moc(B))

n

gdzie n=moc(I), I zaś jest typem indeksującym
tablicy.

12

Korzystanie z selektora

tablicowego

Poniższy krótki program ilustruje użycie selektora

tablicowego. Zadaniem programu jest znalezienie

najmniejszego indeksu i składowej o wartości x.

Poszukiwania dokonuje się, przeglądając sekwencyjnie

tablicę a, zadeklarowaną jako

var a: array[1..N] of T; {N > 0}
i:=0;
repeat
i := i+1
until (a[i] = x)



(i=N);

if a[i]



x then „nie ma takiego elementu w a"

13

Czasem pomoże

wartownik

Inny wariant tego programu ilustruje znaną

metodę z wartownikiem (ang. sentinel),

ustawionym na końcu tablicy. Zastosowanie

wartownika znacznie upraszcza warunek

zakończenia iteracji.

var a: array[1. .N + 1] of T;
i:=0; a[N + 1]:=x;
repeat i:=i+1 until a[i]=x;
if i>N then „nie ma takiego elementu w a"

14

Aktualizacja selektywna,

niezmiennik pętli

Przypisanie

a[N+1]:=x

jest

przykładem

aktualizacji

selektywnej

(ang.

selective

updating), tzn. zmiany wybranej składowej

zmiennej złożonej.
Niezależnie od tego, jak często powtórzyło się

wykonanie instrukcji i:=i+1, spełniony jest

warunek
a[j]



x, dla j = 1... i - 1

Warunek ten jest spełniony w obu wersjach

programu i nazywany jest niezmiennikiem

pętli (ang. loop invariant).

15

Metoda poszukiwania

połówkowego

Jeżeli

elementy

tablicy

zostały

wcześniej

uporządkowane

(posortowane), przeszukiwanie

można znacznie przyspieszyć. W takim przypadku

najczęściej

stosuje

się

metodę

połowienia

przedziału,

w

którym

ma

się

znajdować

poszukiwany element.
Metodę

tę,

nazywa

się

przeszukiwaniem

połówkowym (przeszukiwaniem binarnym; ang.

binary search). Przy każdym powtórzeniu dzieli się

na połowę przedział między indeksami i oraz j.

Górną granicą wymaganej liczby porównań jest

log

2

(N)

16

Przykład - Poszukiwanie

połówkowe

i:=1; j:=N;
repeat k:=(i+j) div 2;
if x>a[k] then i:=k+1 else j:=k-1
until (a[k]=x)



(i>j)

Odpowiednim warunkiem niezmienniczym na wejściu

do instrukcji iteracyjnej repeat jest

a[h]<x, dla h = 1... i –1

a[h]>x, dla h =j+1 ... N

W związku z tym, jeśli wykonanie programu kończy

się przy i>j, oznacza to, że nie istnieje a[h]=x takie,

że 1hN.

17

Składowe typów

tablicowych mogą być

złożone

Składowe typów tablicowych mogą być również

złożone. Tablica, której składowe są również tablicami,

jest zwana macierzą (ang. matrix). Np.

M: array[1..10] of Wiersz

jest tablicą o dziesięciu składowych (wierszach), z

których każda składa się z pięciu składowych typu real,

i

nazywa

się

macierzą

10x5

o

składowych

rzeczywistych.
Selektory mogą być konkatenowane tak, że

M[i][j]

oznacza j-tą składową wiersza M(i), który jest i-tą

składową macierzy M. Oznaczenie to skraca się zwykle
do postaci

M[i,j].

18

Deklarowanie tablic

wielowymiarowych

Podobnie deklaracja

M: array [1. .10] of array [1. .5] of

real

może być napisana w sposób bardziej
zwarty w postaci

M: array [1..10, 1..5] of real

19

Pętla „dla” często przydaje

się przy tablicach

Gdy pewna operacja ma być wykonana dla wszystkich

składowych tablicy (lub kilku kolejnych składowych), wygodnie

jest stosować instrukcję „dla", co ilustruje przykład (następny

slajd).
Załóżmy, że ułamek f jest reprezentowany za pomocą tablicy d w

ten sposób, że

tzn. przez swoje (k-1)-cyfrowe rozwinięcie dziesiętne. Następnie

ma zostać podzielone przez 2. Dokonuje się tego, powtarzając

operację dzielenia dla wszystkich k-1 cyfr, począwszy od i=1.

Operacja ta polega na podzieleniu cyfry przez 2, z

uwzględnieniem ewentualnego przeniesienia z poprzedniej

pozycji i zachowaniem ewentualnej reszty r do następnego kroku.











1

1

10

*

k

i

i

i

d

f

20

Przykład - Reprezentacja

dziesiętna ujemnych

potęg dwójki

program potęga (output);
{reprezentacja dziesiętna ujemnych potęg liczby 2}
const n=10; type cyfra=0..9; var i, k, r: integer; d: array [1. .n]

of cyfra;

begin for k: = 1 to n do
begin write ('.'); r:= 0;
for i:=1 to k-1 do
begin
r:=10*r+d[i]; d[i]:=r div 2; r:=r-2*d[i]; write(chr(d[i]+ord('0')))
end;
d[k]:=5; writeln('5')
end
end.

21

Przykład - Reprezentacja

dziesiętna ujemnych

potęg dwójki - wyniki

Postępowanie

zastosowano

w

programie (poprzedni slajd) w celu

otrzymania tablicy ujemnych potęg

dwójki.
Powtarzanie

operacji

połowienia

służących do obliczenia wartości 2

-1

,

2

-2

, ..., 2

-n

jest ponownie wyrażone za

pomocą instrukcji „dla", "prowadząc

do zagnieżdżenia dwóch takich

instrukcji.
Wyniki programu dla n = 10

przedstawiono obok.

.5
.25
.125
.0625
.03125
.015625
.0078125
.00390625
.001953125
.0009765625

22

Rekordy

Najbardziej

ogólną

metodą

tworzenia

typów

złożonych jest łączenie w typ złożony elementów o

dowolnych, być może złożonych typach.
Przykładami z matematyki są liczby zespolone

złożone

z

dwóch

liczb

rzeczywistych

bądź

współrzędne punktów złożone z dwóch lub więcej

liczb rzeczywistych w zależności od wymiaru

przestrzeni.
Przykładem z przetwarzania danych jest opis osoby

za pomocą kilku istotnych cech charakterystycznych,

takich jak imię, nazwisko, data urodzenia, płeć i stan

cywilny.

23

Iloczyn kartezjański

W matematyce taki typ złożony zwie się
iloczynem kartezjańskim typów składowych.
Wypływa to z faktu, że zbiór wartości definiujący
ten typ składa się ze wszystkich możliwych
kombinacji wartości wziętych odpowiednio ze
wszystkich typów składowych.
Liczba takich kombinacji jest równa iloczynowi
liczb elementów wszystkich typów składowych,
czyli moc typu złożonego równa jest iloczynowi
mocy typów składowych.

24

Rekord znaczy zapis

W przetwarzaniu danych typy złożone, takie jak
opisy osób czy innych obiektów, służą do
zapisywania

i

rejestracji

ukierunkowanych

problemowo charakterystyk tych osób czy obiektów;
Są one zazwyczaj przechowywane w plikach i
„bankach(bazach) danych". Fakt ten tłumaczy
stosowanie angielskiego słowa record (zapis, rejestr,
nagranie, przechowywany zestaw informacji) do
oznaczania tego rodzaju danych zamiast terminu
„iloczyn kartezjański".

25

Definiowanie typu

rekordowego

Ogólnie, typ rekordowy T jest zdefiniowany

w następujący sposób:
type T = record
s

1

: T

1

;

s

2

: T

2

;

...
s

n

: T

n

;

end
moc(T)=moc(T

1

) *... * moc (T

n

)

26

Przykłady definicji typów

rekordowych

type Zespolona = record
re: real;
im: real
end

type Data=record
dzień: 1.. 31;
miesiąc: 1..12;
rok: 1..3000;
end

type Osoba = record
nazwisko: alfa;
imię: alfa;
dataurodzenia: Data;

płeć:

(mężczyzna,

kobieta);

stancywilny: (wolny,

żonaty,

owdowiały,

rozwiedziony)

end

27

Konstruktor rekordowy

Za

pomocą

konstruktora

rekordowego

można

utworzyć

wartość typu T, a następnie przypisać
ją jakiejś zmiennej tego typu:

x:=T(x

1

, x

2

, ..., x

n

)

gdzie x

i

są odpowiednio wartościami z

typów składowych T

i

.

28

Zespolona z

Data d

Osoba p

1.0

1

WIRTH

-1.0

4

CHRIS

1973

18 1 1966

mężczyzna

wolny

Przypisywanie danych

do zmiennych

rekordowych

Dla danych
zmiennych
rekordowych

z: Zespolona
d: Data
p: Osoba

konkretne wartości mogą być przypisane następująco
z:= Zespolona (1.0, -1.0)
d:= Data (1,4,1973)
p:= Osoba (‘CIENKI', ‘BOLEK', Data (18,1,1966),

mężczyzna, wolny)

29

Selektory rekordowe

Identyfikatory s

1

,..., s

n

wprowadzone w

definicji typu rekordowego stanowią nazwy

przydzielone

poszczególnym

składowym

zmiennych tego typu;
Stosuje się je w selektorach rekordowych

odnoszących sięs do zmiennych rekordowych.
Dla danej zmiennej x: T, jej i-ta składowa jest

oznaczona przez

x.s

30

Aktualizacja selektywna

Aktualizację selektywną x prowadzi
się

przy

użyciu

tego

samego

oznacznika selektora stojącego po
lewej stronie instrukcji przypisania:

x.s

i

:=x

i

gdzie x

i

jest wartością (wyrażeniem)

typu T

i

31

Przykłady selektorów

Dla danych zmiennych rekordowych

z: Zespolona
d: Data
p: Osoba

selektory niektórych składowych są następujące:

z.im

(typu real)

d.miesiąc

(typu 1..12)

p.nazwisko

(typu alfa)

p.dataurodzenia

(typu Data)

p.dataurodzenia.dzień (typu 1..31)

32

Typy złożone można

składać

również z typów złożonych

Przykład typu Osoba dowodzi, że typy składowe
rekordu mogą również mieć pewną złożoną
strukturę. Selektory można zatem składać.
Oczywiście operację składania typów o różnych
składowych można wykonywać wielokrotnie
(wielopoziomowo). Na przykład j-ta składowa
tablicy

a,

będącej

składową

zmiennej

rekordowej r, jest oznaczana przez r.a[i] a
składowa o selektorze s i-tej składowej
rekordowej tablicy a jest oznaczana przez a[i].s

33

Poprawna definicja typu

nie gwarantuje

sensownych danych

Charakterystyczną cechą iloczynu kartezjańskiego jest

to, że zawiera on wszystkie kombinacje elementów

typów składowych.
Trzeba jednak pamiętać, że w praktyce nie wszystkie

muszą

być

„prawidłowe”,

tzn.

sensowne.

Np.

zdefiniowany poprzednio typ Data zawiera mógłby

zawierać wartości (31,4,1973) i (29,2,1815), które

odpowiadają datom nie istniejących nigdy dni.
Jak widać, definicja tego typu nie odzwierciedla sytuacji

rzeczywistej.

Niemniej

jednak

praktycznie

jest

dostatecznie bliska rzeczywistości; od programisty

zależy, aby bezsensowne wartości nigdy nie wystąpiły

podczas wykonania programu.

34

Przykład– korzystanie

ze zmiennych

rekordowych

Przytoczony poniżej krótki fragment programu

ilustruje użycie zmiennych rekordowych. Jego

zadaniem

jest

zliczenie

„Osób”

reprezentowanych w tablicy a jako kobiety stanu

wolnego.

 

var a: array [1.. N] of Osoba
licznik: integer;
licznik:=0; for i:=1 to N do
if (a[i].płeć=kobieta)



(a[i].stancywilny = wolny)

then licznik:=licznik+1

35

Instrukcja wiążąca

W innym wariancie powyższego fragmentu programu

korzysta się z konstrukcji zwanej instrukcją wiążącą

with:

  for i:=1 to N do

with a[i] do
if (płeć=kobieta)



(stancywilny=wolny) then licznik:=licznik

+ 1

Konstrukcja with r do s oznacza, że można używać nazw

selektorów z typu zmiennej r bez poprzedzenia ich nazwą

zmiennej, ponieważ wiadomo, że będą się do niej odnosiły.
Użycie instrukcji with skraca więc tekst programu, jak

również zapobiega wielokrotnemu obliczaniu od nowa

składowej indeksowanej a[i].

36

Łącza

W następnym przykładzie założymy, że (być może w celu

szybszego wyszukiwania) pewne grupy osób w tablicy a

są ze sobą w pewien sposób powiązane.
Informacja wiążąca jest reprezentowana przez dodatkową

składowa rekordu Osoba, nazwaną łączem (wiązaniem;

ang. link).
Łącza, wiążą ze sobą rekordy w liniowy łańcuch, tak że

można łatwo odszukać poprzednika i następnika każdej

osoby.
Interesującą własnością tej metody wiązania jest to, że

łańcuch może być przeglądany w obu kierunkach na

podstawie tylko jednej liczby umieszczonej w każdym

rekordzie.

37

Funkcjonowanie metody

wyszukiwania opartej o

łącza

Załóżmy, że indeksy trzech kolejnych elementów

łańcucha są równe i

k-1

, i

k

, i

k+1

. Wartość łącza dla

k-tego elementu wybiera się jako i

k+1

- i

k

-

1

.

Przeglądając „w przód” łańcuch elementów, i

k+1

określa się na podstawie dwóch aktualnych

zmiennych indeksowanych x=i

k

-

1

i y=i

k

jako

i

k+1

= x + a[y].łącze

a podczas przeglądania „wstecz” i

k

-

1

określone

jest na podstawie x= i

k+1

i y=i

k

jako

i

k-1

=x-a[y].łącze

38

Tablica o elementach typu

osoba

Imię

Płeć

Łącze

1 Karolina

K

2

2 Krzysztof

M

2

3 Paulina

K

5

4 Robert

M

3

5 Janusz

M

3

6 Jadwiga

K

5

7 Ryszard

M

5

8 Maria

K

3

9 Anna

K

1

10 Mateusz

M

3

39

Rekordy vs. Tablice

Strukturę rekordu i strukturę tablicy charakteryzuje

wspólnie cecha „dostępu swobodnego”.
Rekord jest strukturą bardziej ogólną w tym sensie,

że nie ma tu wymagania, aby wszystkie typy

składowe były identyczne.
Jednakże stosowanie tablicy zapewnia większą

elastyczność,

ponieważ

selektory

składowych

tablicy mogą być wartościami obliczanymi w

programie (reprezentowanymi przez wyrażenia),

podczas gdy selektory składowych rekordu są

sztywno

ustalonymi

identyfikatorami

wprowadzonymi w definicji odpowiedniego typu.

40

Rekordy z wariantami

W praktyce okazuje się zazwyczaj wygodne i

naturalne traktowanie dwóch typów po prostu jako

wariantów tego samego typu.
Na przykład typ Współrzędne można traktować jako

sumę dwóch wariantów, mianowicie współrzędnych

kartezjańskich i biegunowych, których składowymi

są odpowiednio (a) dwie wielkości liniowe i (b)

wielkość liniowa i kątowa.
W celu rozpoznania wariantu, który aktualnie jest

wartością zmiennej, wprowadza się trzecią składową

zwaną

wyróżnikiem

typu

albo

polem

znacznikowym.

41

Przykład rekordu

wariantowego

type Współrzędne =

record case rodzaj: (kartezjańskie, biegunowe)

of
kartezjańskie: (x, y: real);
biegunowe: (r: real;



: real)

end
W tym przypadku nazwą pola znacznikowego jest

rodzaj, a nazwy współrzędnych stanowią albo x i

y - wartości współrzędnych kartezjańskich, albo r

i



- wartości współrzędnych biegunowych.

42

Zbiór wartości typu i jego

moc

Zbiór wartości typu Współrzędne jest
sumą dwóch typów:
T

1

= (x, y: real);

T

2

= (r: real;



: real)

a jego moc jest sumą mocy T

1

i T

2

43

Rekordy o częściowo

identycznych składowych

Bardzo często jednak nie mamy do czynienia z dwoma

całkowicie różnymi typami, lecz raczej z typami o

częściowo identycznych składowych.
Fakt ten zadecydował o nazwie takiego typu - rekord z

wariantami (ang. variant record).
Przykładem jest typ Osoba zdefiniowany na jednym z

poprzednich slajdów, w którym informacje mogłyby

zależeć od płci osoby.
Na przykład dla mężczyzny charakterystycznymi

informacjami mogą być jego waga oraz to, czy jest

brodaty, podczas gdy dla kobiety informacjami tymi

mogą być trzy charakterystyczne wymiary figury

(natomiast waga może pozostać nieujawniona).

44

Przykład – nowa definicja

typu osoba

Definicja takiego typu wyglądałaby więc następująco:
type Osoba=

record
nazwisko, imię: alfa
dataurodzenia: data;
stancywilny: (wolny, żonaty, owdowiały, rozwiedziony);
case płeć: (mężczyzna, kobieta) b
mężczyzna:

(waga: real;

brodaty: Boolean);
kobieta: (wymiary: array [1..3] of integer)
end

45

Ogólna postać definicji

rekordu z wariantami

type T =

record s

1

: T

1

;...; s

n-1

: T

n-1

;

case s

n

: T

n

of

c

1

: (s

1,1

: T

1,1

; ...; s

1,n1

: T

1,n1

);

……………………………….
c

m

: (s

m,1

: T

m,1

; ...; s

m,nm

: T

1,nm

);

end
Identyfikatory s

i

i s

ij

są nazwami składowych dla typów T

i

i T

ij

, a s

n

jest nazwą wyróżniającego pola znacznikowego o typie T

n

. Stałe

c

1

...c

m

oznaczają wartości typu (skalarnego) T

n

.

Zmienna x typu T zawiera składowe x.s

1

, x.s

2

, …, x.s

n

, x.s

k,1

, ...,

x.s

k,nk

wtedy i tylko wtedy, gdy (bieżąca) wartość x.s

n

jest równa

c

k

. Składowe x.s

1

, ..., x.s

n

tworzą część wspólną m wariantów.

46

Brodata pani

Wynika stąd, że użycie selektora składowej

x.s

k,h

(1≤h≤n

k

),

gdy

x.s

n

≠c

k

,

należy

traktować jako poważny błądd programu,

gdyż

może

to

prowadzić

do

wielu

paradoksalnych konsekwencji.
Dla zdefiniowanego poprzednio typu Osoba

może to spowodować np.

– zapytanie, czy pani jest brodata,
– lub (w przypadku aktualizacji selektywnej)

żądanie, aby taką była.

47

Jeśli chcemy uniknąć

problemów dobrze jest

skorzystać z instrukcji

wyboru

Jak widać, rekordy z wariantami wymagają niezwykle

uważnego programowania. Odpowiednie operacje na

poszczególnych wariantach najlepiej grupować w

instrukcję wybiórczą, tzw. instrukcję wyboru, której

struktura odzwierciedla strukturę definicji rekordu z

wariantami.

case x.s

n

of

c

1

: S

1

;

c

2

: S

2

;

…
c

m

: S

m

;

end

48

Przykład – obliczanie

odległości pomiędzy

dwoma punktami

Przytoczony

dalej

fragment programu ma

za zadanie obliczenie

odległości

między

punktami

A

i

B

zadanymi

w

postaci

zmiennych a i b typu

Współrzędne, będącego

rekordem z wariantami.

Procedura obliczeń jest odpowiednio odmienna dla każdej

z czterech możliwych kombinacji określania zmiennych za

pomocą współrzędnych kartezjańskich lub biegunowych.

49

Kod realizujący zadanie z

przykładu

case a.rodzaj of

kartezjańskie:case b.rodzaj of
kartezjańskie: d:=sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
biegunowe:d:=sqrt(sqr(a.x-b.r*cos(b.



))+sqr(a.y-

b.r*sin(b.



)))

end;

biegunowe: case b.rodzaj of
kartezjańskie: d:=sqrt(sqr(a.r*sin(a.



)-b.x)+sqr(a.r*cos(a.



)-

b.y))
biegunowe: d:=sqrt(sqr(a.r)+sqr(b.r)-2*a.r*b.r*cos(a.



-b.



))

end
end

50

Zbiory

Trzecią podstawową strukturą danych - oprócz

tablicy i rekordu - jest struktura zbioru (ang. set

structure). Definiuje się ją za pomocą deklaracji o

podanej poniżej postaci:

type T = set of T

0

Wartościami zmiennej x typu T są zbiory

elementów typu T

0

.

Zbiór

wszystkich

możliwych

podzbiorów

elementów T

0

nazywa się zbiorem potęgowym

T

0

. W związku z tym typ T stanowi zbiór potęgowy

swego typu podstawowego T

0

.

51

Przykłady typów

zbiorowych

type zbiórcalk

= set of 0..30

type zbiórznaków = set of char
type kolorytęczy = set of kolor

Podstawę

dla

drugiego

przykładu

stanowi

standardowy zbiór znaków oznaczony typem char,

podstawą dla trzeciego przykładu jest zbiór kolorów,

który można zdefiniować jako typ skalarny

type kolor=(żółty, pomarańczowy, czerwony,

zielony, niebieski, fioletowy)

opisujący różne kolory, jakie mogą wchodzić w skład

tęczy.

52

Przypisywanie wartości

zmiennym typu

zbiorowego

Dla danych zmiennych
zc

:

zbiórcałk

zz

:

zbiórznaków

t : array [1. .6] of kolorytczy
można wykonać przypisania dla poszczególnych wartości

typu zbiorowego:
zc:= [1, 4, 9, 16, 25] zz := ['+','-','*','/']
t[3]

:

= [żółty] t[5]=[ ]

t[6]=[czerwony..fioletowy]

Wartość

przypisania

zmiennej

t[3]

stanowi

zbiór

jednoelementowy zawierający pojedynczy element żółty;

zmiennej t[5] jest przypisany zbiór pusty, co oznacza, że w

skład piątej tęczy nie wchodził żaden kolor (nie istniała?),

natomiast zmiennej t[6] przypisano zbiór złożony z czterech

spośród możliwych kolorów.

53

Moc typu zbiorowego

Moc typu zbiorowego T jest określona wzorem

Wzór ten wynika bezpośrednio z faktu, że każdy z

elementów T

0

musi być reprezentowany przez jedną

z dwóch wartości: „jest” lub „nie ma” oraz stąd, że

wszystkie elementy są wzajemnie niezależne.
Dla efektywnej i ekonomicznej realizacji jest istotne,

aby typ podstawowy był nie tylko skończony, ale

aby jego moc była stosunkowo niewielka.

 

 

0

2

T

moc

T

moc 

54

Elementarne działania na

zbiorach

Na wszystkich typach zbiorowych są określone

następujące operatory elementarne:

*

przecięcie zbiorów

+

suma zbiorów

-

różnica zbiorów

in

przynależność do zbioru

55

Przykłady działań na

zbiorach

Konstruowanie przecięcia (iloczynu) i sumy zbiorów

nazywa się też często, odpowiednio, mnożeniem i

dodawaniem zbiorów.
Zgodnie z tą analogią określa się też priorytety operatorów

zbiorowych: największy priorytet otrzymuje operator

przecięcia zbiorów, następnie - operator sumy i różnicy,

najmniejszy zaś priorytet - operator przynależności do

zbioru, klasyfikowany na równi z operatorami relacyjnymi.
Poniżej podano przykłady wyrażeń zbiorowych i ich

odpowiedników z nawiasami:
r*s+t=(r*s)+t r-s*t=r-(s*t)
r-s+t=(r-s)+t x in s+t=x in (s+t)

56

Podstawowe statyczne

złożone struktury danych

Strukt

ura

Deklaracja Selektor

Dostęp do

składowych

Typ

składwy

ch

Moc

Tablica

a: array [/]

of T

0

a[i]
(iI)

Selektor

z

obliczanym

indeksem i

Wszystk

ie

jednako

we (T

0

)

moc(T

0

)

m

oc(l)

Rekord

r: record
s

1

: T

1

;

...
s

n

: T

n

;

end

r.s
(s[s

1

,...,

s

n

])

Selektor

z

deklarowaną

nazwą

składowej s

Mogą

być

różne

Zbiór

s : set of

T

0

nie

istnieje

Test

przynależność

za

pomocą

operatora

relacyjnego in

Wszystk

ie

jednako

we

(typu

T

0

)

 





n

i

i

T

moc

1

 

0

2

T

moc