ALG9

5.B. Zbiory 159

5.8. Zbiory

Implementacja programowa zbiorów matematycznych napotyka na szereg ograniczeń związanych z używanym językiem programowania. Miłośnicy Pascala znają zapewne definicje zbliżone do:

typa Litery *• 'A' .. 'Z';

Zbiór Li ter = set of T.itery; vax Alfabet:ZbiorLi ter;

c: char; begin

Alfabet:^[ 'A'..'Z'1; read (c) :

if c i-n Alfabet then (itd. / end.

Oczywiście, to co dla programisty pascalowego jest zbiorem, wcale nim nie jest dla matematyka, z uwagi na wymóg jednakowego typu zapamiętywanych elementów.

Niemniej, dla podstawowych zastosowań, konwencje istniejące w Pascalu nadają się znakomicie, gdyż możliwe jest np. wykonywanie operacji typu: dodawanie elementu do zbioru, mnożenie (iloczyn) zbiorów, odejmowanie zbiorów', testowanie przynależności do zbiorów...

W tej książce do opisu algorytmów' i prezentacji struktur danych używamy języka C++, który na ogół spełnia swoje zadanie dość dobrze. Niestety, nie posiada on ..wbudowanej” obsługi zbiorów i w związku z tym należy ją dołożyć w sposób jawny, używając przy okazji różnorodnych technik, zależnych od aktualnie realizowanych zadań.

Weźmy dla przykładu implementację zbioru znaków, która nie wymaga użycia struktur listowych i dynamicznego przydzielania pamięci. Załóżmy, że w komputerze występuje ,.tylko’’ 256 znaków (między innymi znaki alfabetu duże i małe, cyfry oraz tzw. znaki kontrolne niedrukowalne). Do „zasymulowania” zbioru wystarczy wówczas najzwyklejsza tablica typu unsigned char, tak jak w przykładzie poniżej:

sct.cpp

class Zfcicr (

unsigned char zbiór[256];    // cała tablica ASCII

public:

Zbiór!) // konstruktor, „zeruje" zbiór {

for(int i—0;i<256;i++) zbiórli J =U;

)