Algorytmy i Struktury Danych - Reprezentacja zbiorów w mapach bitowych

Mapa bitowa (ang. bitmap) jest ciągiem bitów. Poszczególne bity w mapie bitowej posiadają swoje numery. Umówmy się, że bity będziemy zawsze numerować od strony prawej do lewej. Numeracja rozpoczyna się od 0. Poniżej mamy mapę bitową zbudowaną z 26 bitów:

b₂₅

b₂₄

b₂₃

b₂₂

b₂₁

b₂₀

b₁₉

b₁₈

b₁₇

b₁₆

b₁₅

b₁₄

b₁₃

b₁₂

b₁₁

b₁₀

b₉

b₈

b₇

b₆

b₅

b₄

b₃

b₂

b₁

b₀

Każdy bit mapy może przyjąć wartość 0 lub 1.

Zbiór da się odwzorować mapą bitową. Stosujemy tutaj podobną umowę, jak przy tablicach:

wartości v elementów zbioru są liczbami całkowitymi z przedziału od vmin do vmax.
element v zbioru jest odwzorowany bitem o numerze (v-vmin).
element v jest w zbiorze, jeśli jego bit b_v-vmin = 1.
elementu v nie ma w zbiorze, jeśli jego bit b_v-vmin = 0.

b₂₅

b₂₄

b₂₃

b₂₂

b₂₁

b₂₀

b₁₉

b₁₈

b₁₇

b₁₆

b₁₅

b₁₄

b₁₃

b₁₂

b₁₁

b₁₀

b₉

b₈

b₇

b₆

b₅

b₄

b₃

b₂

b₁

b₀

Jeśli nasza mapa bitowa odwzorowuje zbiór elementów o wartościach od 0 do 25 (wartość elementu odpowiada numerowi bitu), to w zbiorze znajdują się elementy: 20, 19, 14, 5 i 0.

Z mapami bitowymi wiąże się pewien prosty problem. Otóż w tablicy mogliśmy się odwołać bezpośrednio do elementu zbioru za pomocą indeksu. Tutaj jest nieco gorzej (a może lepiej?), ponieważ bity mapy są przechowywane w komórkach pamięci grupami po 8:

bajt nr 3	bajt nr 2	bajt nr 1	bajt nr 0
b₃₁	b₃₀	b₂₉	b₂₈	b₂₇	b₂₆	b₂₅	b₂₄	b₂₃	b₂₂	b₂₁	b₂₀	b₁₉	b₁₈	b₁₇	b₁₆	b₁₅	b₁₄	b₁₃	b₁₂	b₁₁	b₁₀	b₉	b₈	b₇	b₆	b₅	b₄	b₃	b₂	b₁	b₀

bajt nr 3

bajt nr 2

bajt nr 1

bajt nr 0

b₃₁

b₃₀

b₂₉

b₂₈

b₂₇

b₂₆

b₂₅

b₂₄

b₂₃

b₂₂

b₂₁

b₂₀

b₁₉

b₁₈

b₁₇

b₁₆

b₁₅

b₁₄

b₁₃

b₁₂

b₁₁

b₁₀

b₉

b₈

b₇

b₆

b₅

b₄

b₃

b₂

b₁

b₀

W bajcie nr 3 wykorzystujemy tylko dwa bity: b₂₄ i b₂₅. Pozostałe nie należą do mapy bitowej, jednak i tak muszą być zarezerwowane w pamięci.

Umówmy się, że najmniejszą jednostką przydziału pamięci dla mapy bitowej będzie 4 bajty, czyli 32 bity. Taka organizacja jest podyktowana większą szybkością pracy na danych 32 bitowych niż na 8 bitowych we współczesnych mikroprocesorach (w jednym rozkazie procesor może naraz przetworzyć 32 bity, czyli 32 elementy zbioru!). Również dostęp do danych 32 bitowych jest szybszy w procesorach Pentium od dostępu do danych 8 bitowych. Zatem mapę bitową będziemy przechowywali w tablicy, której elementy są 32 bitowe.

Do określenia mapy bitowej będziemy potrzebowali dwóch wielkości całkowitych:

vmin : minimalna wartość elementu zbioru.
vmax : maksymalna wartość elementu zbioru.

Liczbę bitów obliczymy ze wzoru:

liczba_bitów = vmax-vmin+1

Liczbę komórek 32 bitowych obliczymy ze wzoru:

n = ((liczba_bitów-1) shr 5)+1

Ta ostatnia informacja będzie potrzebna dla operacji blokowych na zbiorach (suma, iloczyn, różnica, podzbiór).

Aby znaleźć bit odpowiadający elementowi o wartości v, wykonujemy następujące operacje:

Najpierw przekształcamy wartość v na numer bitu:

numer_bitu = v-vmin

Teraz wyznaczamy indeks komórki tablicy, która zawiera dany bit (dzielenie jest całkowitoliczbowe):

indeks = numer_bitu shr 5

Na koniec obliczamy numer bitu w komórce (wydzielając młodsze 5 bitów):

nb = numer_bitu and 31

Jeśli mamy indeks komórki tablicy mapy bitowej oraz numer bitu nb wewnątrz tej komórki, to wartość elementu zbioru skojarzonego z tym bitem obliczymy następująco:

Obliczamy numer bitu w mapie bitowej:

numer_bitu = (indeks shl 5) or nb

Obliczamy wartość elementu zbioru:

v = numer_bitu+vmin

Powyższe wzory pozwalają nam obsługiwać pojedyncze elementy zbioru. Mając wartość elementu, potrafimy określić numer reprezentującego go bitu, a dalej położenie tego bitu w tablicy mapy bitowej. Również na odwrót, mając położenie bitu w tablicy, potrafimy określić element, który ten bit reprezentuje w zbiorze.

Zbiór jest reprezentowany przez strukturę BSet zawierającą pola:

vmin : dolna granica wartości elementów, vmin ∈ C.
nmax : ostatni indeks komórki tablicy, nmax ∈ C.
T : tablica elementów 32 bitowych o rozmiarze nmax = 1.

Pascal

type
  BSet =  record
    vmin  : integer;
    nmax  : integer;
    T     : array of cardinal;
  end;

C++

struct BSet
{
  int vmin, nmax;
  unsigned int * T;
};

Basic

Type BSet
  vmin As Integer
  nmax As Integer
  T As UInteger Ptr
End Type

Python (dodatek)

class BSet:


    def __init__(self)
        self.vmin = 0
        self.nmax = 0
        self.t = []

Poniżej przedstawiamy algorytmy podstawowych operacji dla zbioru zaimplementowanego mapą bitową.

Algorytmy operacji dla zbiorów reprezentowanych mapami bitowymi

s_add(A, x) – dodaje element x do zbioru A.

Algorytm ustawia na 1 bit reprezentujący w mapie bitowej element zbioru o wartości v.

Wejście:

A : referencja do struktury BSet.
x : element do dodania do zbioru, x ∈ C.

Wyjście:

Zbiór A z dodanym elementem x.

Elementy pomocnicze:

b : numer bitu w mapie bitowej, b ∈ C.
i : indeks elementu tablicy mapy bitowej, i ∈ C.

Lista kroków:

K01: b ← x-A→vmin ; obliczamy numer bitu
K02: i ← b shr 5 ; obliczamy indeks
K03: A→T[i] ← A→T[i] or (1 shl (b and 31)) ; ustawiamy bit na 1
K04: Zakończ

s_remove(A, x) – usuwa element x ze zbioru A

Algorytm ustawia na 0 bit reprezentujący w mapie bitowej element zbioru o wartości v.

Wejście:

A : referencja do struktury BSet.
x : element do usunięcia ze zbioru, x ∈ C.

Wyjście:

Zbiór A z usuniętym elementem x.

Elementy pomocnicze:

b : numer bitu w mapie bitowej, b ∈ C.
i : indeks elementu tablicy mapy bitowej, i ∈ C.

Lista kroków:

K01: b ← x - A→vmin ; obliczamy numer bitu
K02: i ← b shr 5 ; obliczamy indeks
K03: A→T[i] ← A→T[i] and not (1 shl (b and 31)) ; ustawiamy bit na 0
K04: Zakończ

s_clear(A) – usuwa wszystkie elementy ze zbioru A, zbiór A staje się zbiorem pustym

Algorytm wypełnia tablicę A→T[...] zerami. W ten sposób powstanie zbiór pusty.

Wejście:

A : referencja do struktury BSet.

Wyjście:

Pusty zbiór A.

Elementy pomocnicze:

i : indeksowanie komórek, i ∈ C.

Lista kroków:

K01: Dla i = 0, 1, …, A→nmax: ; zerujemy komórki tablicy
     wykonuj: A.T→[i] ← 0
K02: Zakończ

s_create(A, vmin, vmax) – tworzy pusty zbiór A o odpowiednim rozmiarze

Algorytm wypełnia strukturę zbioru A, tworzy tablicę dynamiczną o wyliczonym rozmiarze nmax i wypełnia ją wartością 0, co daje w efekcie pusty zbiór A.

Wejście:

A : referencja do struktury BSet.
vmin : minimalna wartość elementu zbioru, vmin ∈ C.
vmax : maksymalna wartość elementu zbioru, vmax ∈ C.

Wyjście:

Pusty zbiór A.

Elementy pomocnicze:

s_clear(Z) : usuwa ze zbioru Z wszystkie elementy.

Lista kroków:

K01: A→vmin ← vmin ; wypełniamy strukturę BSet odpowiednimi wartościami
K02: A→nmax ← (vmax-vmin) shr 5 ; obliczamy indeks ostatniego elementu tablicy
K03: Utwórz obszar dla nmax = 1 komórek ; tworzymy tablicę dynamiczną
K04: A→T ← adres utworzonego obszaru
K05: s_clear(A) ; tworzymy pusty zbiór
K06: Zakończ

s_union(A, B, C) – zwraca sumę zbiorów A i B

Algorytm umieszcza w zbiorze C wszystkie elementy zbiorów A i B. Wszystkie trzy zbiory muszą mieć ten sam rozmiar nmax.

Wejście:

A, B, C : referencje do struktur BSet.

Wyjście:

Zbiór C zawiera sumę zbiorów A i B.

Elementy pomocnicze:

i : indeksowanie komórek, i ∈ C.

Lista kroków:

K01: Dla i = 0, 1, …, A→nmax:
     wykonuj krok K02
K02:   C→T[i] ← A→T[i] or B→T[i] ; łączymy zbiory A i B w zbiór C
K03: Zakończ

s_intersection(A, B, C) – zwraca iloczyn zbiorów A i B

Algorytm tworzy w zbiorze C iloczyn zbiorów A i B. Wszystkie trzy zbiory muszą mieć ten sam rozmiar nmax.

Wejście:

A, B, C : referencje do struktur BSet.

Wyjście:

Zbiór C zawiera iloczyn zbiorów A i B.

Elementy pomocnicze:

i : indeksowanie komórek, i ∈ C.

Lista kroków:

K01: Dla i = 0, 1, …, A→nmax:
     wykonuj krok K02
K02:   C→T[i] ← A→T[i] and B→T[i] ; wyznaczamy w C część wspólną A i B
K03: Zakończ

s_difference(A, B, C) – zwraca różnicę zbioru A i B

Algorytm tworzy w zbiorze C różnicę zbiorów A i B. Wszystkie trzy zbiory muszą mieć ten sam rozmiar nmax.

Wejście:

A, B, C : referencja do struktur BSet.

Wyjście:

Zbiór C zawiera różnicę zbiorów A i B.

Elementy pomocnicze:

i : indeksowanie komórek, i ∈ C.

Lista kroków:

K01: Dla i = 0, 1, …, A→nmax:
     wykonuj krok K02
K02:   C→T[i] ← A→T[i] and not B→T[i] ; wyznaczamy w C różnicę A i B
K03: Zakończ

s_subset(A, B) – zwraca true, jeśli zbiór A jest podzbiorem zbioru B, inaczej zwraca false.

Algorytm sprawdza, czy iloczyn logiczny A i B jest równy A. Jeśli tak, to zbiór B zawiera zbiór A. Oba zbiory A i B muszą posiadać ten sam rozmiar nmax.

Wejście:

A, B : referencja do struktur BSet.

Wyjście:

true : zbiór A jest podzbiorem zbioru B.
false : nie jest.

Elementy pomocnicze:

i : indeksowanie komórek, i ∈ C.

Lista kroków:

K01: Dla i = 0, 1, …, A→nmax:
     wykonuj krok K02
K02:   Jeśli (A→T[i] and B→T[i]) ≠ A→T[i], ; sprawdzamy, czy element z A jest w B.
       to zakończ z wynikiem false ; Jeśli nie, to kończymy z wynikiem false
K03: Zakończ z wynikiem true

s_size(A) – zwraca liczbę elementów zawartych w zbiorze A

Algorytm zlicza elementy zbioru A i zwraca ich liczbę.

Wejście:

A : referencja do struktury BSet.

Wyjście:

Liczba elementów w A

Elementy pomocnicze:

i : indeksowanie komórek, i ∈ C.
c : licznik komórek, c ∈ C.
m : maska bitowa, m ∈ N.

Lista kroków:

K01: c ← 0 ; zerujemy licznik
K02: Dla i = 0, 1, …, A→nmax, ; zliczamy komórki z elementami
     wykonuj kroki K03…K06
K03:   m ← A.T[i] ; zapamiętujemy w m bity komórki A→T[i]
K04:   Dopóki m > 0, ; pomijamy puste komórki
       wykonuj kroki K05…K06
K05:   Jeśli (m and 1) = 1, ; zliczamy bity o wartości 1
       to c ← c+1
K06:   m ← m shr 1 ; przesuwamy bity o 1 pozycję w prawo
K07: Zakończ z wynikiem c

s_empty(A) – zwraca true, jeśli zbiór A jest pusty, inaczej zwraca false

Algorytm sumuje logicznie wszystkie komórki tablicy A→T[...]. Jeśli suma jest równa zero, zwraca true, inaczej zwraca false.

Wejście:

A : referencja do struktury BSet.

Wyjście:

true : zbiór A jest pusty.
false : zbiór A nie jest pusty.

Elementy pomocnicze:

i : indeksowanie komórek, i ∈ C.
m : maska bitowa, m ∈ N.

Lista kroków:

K01: m ← A→T[0] ; ustawiamy bity w masce
K02: Dla i = 1, 2, …, A→nmax: ; sumujemy bity
     wykonuj: m ← m or A→T[i]
K03: Jeśli m = 0, 
     to zakończ z wynikiem true
     inaczej zakończ z wynikiem false

s_isin(A, x) – zwraca true, jeśli element x jest w zbiorze A, inaczej zwraca false

Algorytm wyszukuje bit, który reprezentuje w zbiorze wartość x. Jeśli bit ma stan 1, to zwraca true, w przeciwnym razie zwraca false.

Wejście:

A : referencja do struktury BSet.
x : element badany na obecność w zbiorze, x ∈ C.

Wyjście:

true : element x jest w zbiorze A.
false : elementu x nie ma w zbiorze A.

Elementy pomocnicze:

b : numer bitu w mapie bitowej, b ∈ C.

Lista kroków:

K01: b ← x-A→vmin ; obliczamy numer bitu
K02: Jeśli A→T[b shr 5] and (1 shl (b and 31)) > 0, 
     to zakończ z wynikiem true
     Inaczej zakończ z wynikiem false

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program testuje wszystkie funkcje obsługi zbiorów opartych na bitmapach. Wyjaśnienie wykonywanych operacji znajduje się w komentarzach wewnątrz programu.

Pascal

// Zbiory zaimplementowane
// w mapach bitowych
// Data: 30.06.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program sets;

// Definicja struktury zbioru

type
  BSet =  record
    vmin : integer;
    nmax : integer;
    T    : array of cardinal;
  end;

// Procedura dodaje element x
// do zbioru A
//---------------------------
procedure s_add(var A : BSet;
                    x : integer);
var
  b, i : integer;
begin
  // Obliczamy numer bitu
  b := x-A.vmin;
  // Obliczamy indeks
  i := b shr 5;
  // Ustawiamy bit na 1
  A.T[i] := A.T[i] or (1 shl (b and 31));
end;

// Procedura usuwa element x
// ze zbioru
//--------------------------
procedure s_remove(var A : BSet;
                       x : integer);
var
  b, i : integer;
begin
  // Obliczamy numer bitu
  b := x-A.vmin;
  // Obliczamy indeks
  i := b shr 5;
  // Ustawiamy bit na 0
  A.T[i] := A.T[i] and not (1 shl (b and 31));
end;

// Procedura usuwa wszystkie elementy
// ze zbioru
//-----------------------------------
procedure s_clear(var A : BSet);
var
  i : integer;
begin
  // Zerujemy tablicę
  for i := 0 to A.nmax do A.T[i] := 0;
end;

// Procedura tworzy zbiór
//-----------------------
procedure s_create(var A : BSet;
              vmin, vmax : integer);
begin
  // Wypełniamy strukturę danymi
  A.vmin := vmin;
  // Indeks ostatniego elementu tablicy
  A.nmax := (vmax-vmin) shr 5;
  // Tworzymy dynamicznie
  // tablicę mapy bitowej
  SetLength(A.T, A.nmax+1);
  // Tworzymy zbiór pusty
  s_clear(A);
end;

// Procedura wyznacza w C sumę
// zbiorów A i B
//----------------------------
procedure s_union(var A, B, C : BSet);
var
  i : integer;
begin
  for i := 0 to A.nmax do
    C.T[i] := A.T[i] or B.T[i];
end;

// Procedura wyznacza część wspólną
// zbiorów A i B
//---------------------------------
procedure s_intersection(var A, B, C : BSet);
var
  i : integer;
begin
  for i := 0 to A.nmax do
    C.T[i] := A.T[i] and B.T[i];
end;

// Procedura wyznacza różnicę
// zbiorów A i B
//---------------------------
procedure s_difference(var A, B, C : BSet);
var
  i : integer;
begin
  for i := 0 to A.nmax do
    C.T[i] := A.T[i] and not B.T[i];
end;

// Funkcja sprawdza, czy zbiór A
// jest podzbiorem zbioru B
// true  - tak, jest
// false - nie, nie jest
//------------------------------
function s_subset(var A, B : BSet)
                           : boolean;
var
  i : integer;
begin
  // Przeglądamy kolejne elementy tablicy
  for i := 0 to A.nmax do
    if(A.T[i] and B.T[i]) <> A.T [i] then
      // Jeśli elementu A nie ma w B,
      // kończymy z false
      Exit(false);
  s_subset := true;
end;

// Funkcja oblicza liczbę elementów w A
//-------------------------------------
function s_size(var A : BSet) : integer;
var
  i, c : integer;
  m    : cardinal;
begin
  // Zerujemy licznik
  c := 0;
  // Przechodzimy przez kolejne komórki
  for i := 0 to A.nmax do
  begin
    // Pobieramy bity do m
    m := A.T[i];
    // Zliczamy bity równe 1
    while m > 0 do
    begin
      if(m and 1) = 1 then inc(c);
      m := m shr 1;
    end;
  end;
  s_size := c;
end;

// Funkcja sprawdza, czy
// zbiór A jest pusty
// true  - tak, jest pusty
// false - nie, nie jest pusty
//----------------------------
function s_empty(var A : BSet)
                       : boolean;
var
  i : integer;
  m : cardinal;
begin
  // Pobieramy bity do m
  m := A.T[0];
  for i := 1 to A.nmax do
    // Sumujemy logicznie bity
    m := m or A.T[i];
  s_empty := (m = 0);
end;

// Funkcja bada, czy element x
// należy do zbioru A
// true  - tak, należy
// false - nie, nie należy
//----------------------------
function s_isin(var A : BSet;
                    x : integer)
                      : boolean;
var
  b : integer;
begin
  // Obliczamy numer bitu
  // w mapie bitowej
  b := x-A.vmin;
  if A.T[b shr 5] and
    (1 shl (b and 31)) > 0 then
    Exit(true);
  s_isin := false;
end;

// Procedura wyświetla elementy
// zbioru A
//-----------------------------
procedure s_print(var A : BSet);
var
  i, nb : integer;
  m : cardinal;
begin
  for i := 0 to A.nmax do
  begin
    nb := 0;
    m  := A.T[i];
    while m > 0 do
    begin
      if(m and 1) = 1 then
        write((i shl 5)+nb+A.vmin, ' ');
      m := m shr 1;
      inc(nb);
    end
  end;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  A, B, C : BSet;
  i, x    : integer;

begin
  randomize;
  // Tworzymy puste zbiory o zakresie
  // elementów od -20 do 20
  s_create(A, -20, 20);
  s_create(B, -20, 20);
  s_create(C, -20, 20);
  // Do zbioru A dodajemy 10
  // losowych elementów
  for i := 1 to 10 do
    s_add(A, -20+random(41));
  // Do zbioru B dodajemy 15
  // losowych elementów
  for i := 1 to 15 do
    s_add(B, -20+random(41));
  // Wyświetlamy je
  writeln('A:');
  s_print(A); writeln;
  writeln('SIZE OF A IS ', s_size(A));
  writeln;
  writeln('B:');
  s_print(B); writeln;
  writeln('SIZE OF B IS ', s_size(B));
  // Suma zbiorów
  writeln;
  writeln('UNION OF A AND B:');
  s_union(A, B, C);
  s_print(C); writeln;
  writeln('SIZE OF UNION IS ', s_size(C));
  // Iloczyn zbiorów
  writeln;
  writeln('INTERSECTION OF A AND B:');
  s_intersection(A, B, C);
  s_print(C); writeln;
  writeln('SIZE OF INTERSECTION IS ',
          s_size(C));
  // Różnica zbiorów
  writeln;
  writeln('DIFFERENCE OF A AND B:');
  s_difference(A, B, C);
  s_print(C); writeln;
  writeln('SIZE OF DIFFERENCE IS ',
          s_size(C));
  // Podzbiór
  // Kopiujemy A do C
  s_union(A, A, C);
  // Usuwamy 7 elementów
  for i := 1 to 7 do
    s_remove(C, -20+random(41));
  writeln;
  writeln('IS:');
  s_print(C);
  writeln(' SUBSET OF A?');
  writeln(s_subset(C, A));
  s_difference(B, A, C);
  // Usuwamy 12 elementów
  for i := 1 to 12 do
    s_remove(C, -20+random(41));
  writeln;
  writeln('IS:');
  s_print(C);
  writeln(' SUBSET OF A?');
  writeln(s_subset(C, A));
  // Usuwanie
  writeln;
  write('FROM A WE REMOVE');
  for i := 1 to 5 do
  begin
    x := -20+random(41);
    write(x, ' ');
    s_remove(A, x);
  end;
  writeln;
  writeln('A:'); s_print(A); writeln;
  writeln('SIZE OF A IS ', s_size(A));
  writeln;
  // Sprawdzamy obecność wybranych
  // elementów w B
  for i := 1 to 10 do
  begin
    x := -20+random(41);
    write('IS ELEMENT', x:4, ' IN SET B? ');
    if s_isin(B, x) then
      writeln('YES')
    else
      writeln('NO');
  end;
  writeln;
  // Sprawdzenie testu na zbiór pusty
  writeln('IS SET A EMPTY?');
  writeln(s_empty(A));
  writeln;
  writeln('IS INTERSECTION OF A AND ' +
           'DIFFERENCE OF B AND A EMPTY?');
  s_difference(B, A, C);
  s_intersection(A, C, C);
  writeln(s_empty(C));
  writeln;
  // Usuwamy tablice dynamiczne w zbiorach
  SetLength(A.T, 0);
  SetLength(B.T, 0);
  SetLength(C.T, 0);
end.

C++

// Zbiory zaimplementowane
// w mapach bitowych
// Data: 1.07.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

// Definicja struktury zbioru
struct BSet
{
  int vmin, nmax;
  unsigned int *T;
};

// Procedura dodaje element x
// do zbioru A
//---------------------------
void s_add(BSet & A, int x)
{
  // Obliczamy numer bitu
  int b = x-A.vmin;
  // Obliczamy indeks
  int i = b >> 5;
  // Ustawiamy bit na 1
  A.T[i] |= 1 << (b & 31);
}

// Procedura usuwa element x
// ze zbioru
//--------------------------
void s_remove(BSet & A, int x)
{
  // Obliczamy numer bitu
  int b = x-A.vmin;
  // Obliczamy indeks
  int i = b >> 5;
  // Ustawiamy bit na 0
  A.T[i] &= ~(1 << (b & 31));
}

// Procedura usuwa wszystkie elementy
// ze zbioru
//-----------------------------------
void s_clear(BSet & A)
{
  // Zerujemy mapę bitową
  for(int i = 0; i <= A.nmax; i++)
    A.T[i] = 0;
}

// Procedura tworzy zbiór
//-----------------------
void s_create(BSet & A,
              int vmin,
              int vmax)
{
  // Wypełniamy strukturę danymi
  A.vmin = vmin;
  // Indeks ostatniego elementu tablicy
  A.nmax = (vmax-vmin) >> 5;
  // Tworzymy dynamicznie tablicę
  // mapy bitowej
  A.T = new unsigned int[A.nmax + 1];
  // Tworzymy zbiór pusty
  s_clear(A);
}

// Procedura wyznacza w C sumę
// zbiorów A i B
//----------------------------
void s_union(BSet & A,
             BSet & B,
             BSet & C)
{
  for(int i = 0; i <= A.nmax; i++)
    C.T[i] = A.T[i] | B.T[i];
}

// Procedura wyznacza część wspólną
// zbiorów A i B
//---------------------------------
void s_intersection(BSet & A,
                    BSet & B,
                    BSet & C)
{
  for(int i = 0; i <= A.nmax; i++)
    C.T[i] = A.T[i] & B.T[i];
}

// Procedura wyznacza różnicę
// zbiorów A i B
//---------------------------
void s_difference(BSet & A,
                  BSet & B,
                  BSet & C)
{
  for(int i = 0; i <= A.nmax; i++)
    C.T[i] = A.T[i] & ~B.T[i];
}

// Funkcja sprawdza, czy zbiór A
// jest podzbiorem zbioru B
// true  - tak, jest
// false - nie, nie jest
//------------------------------
bool s_subset(BSet & A, BSet & B)
{
  // Przeglądamy kolejne elementy tablicy
  for(int i = 0; i <= A.nmax; i++)
    if((A.T[i] & B.T[i]) != A.T[i])
      // Jeśli elementu A nie ma w B,
      // kończymy z false
      return false;
  return true;
}

// Funkcja oblicza liczbę elementów w A
//-------------------------------------
int s_size(BSet & A)
{
  // Zerujemy licznik
  int c = 0;
  // Przechodzimy przez kolejne komórki
  for(int i = 0; i <= A.nmax; i++)
    for(unsigned int m = A.T[i]; m; m >>= 1)
      // Zliczamy bity równe 1
      if((m & 1) == 1) c++;
  return c;
}

// Funkcja sprawdza, czy zbiór A jest pusty
// true  - tak, jest pusty
// false - nie, nie jest pusty
//-----------------------------------------
bool s_empty(BSet A)
{
  // Pobieramy bity do m
  unsigned int m = A.T[0];
  for(int i = 1; i <= A.nmax; i++)
    // Sumujemy logicznie bity
    m |= A.T[i];
  return (m == 0);
}

// Funkcja bada, czy element x należy
// do zbioru A
// true  - tak, należy
// false - nie, nie należy
//-----------------------------------
bool s_isin(BSet & A, int x)
{
  // Obliczamy numer bitu w mapie bitowej
  int b = x-A.vmin;
  if(A.T[b >> 5] & (1 << (b & 31)))
    return true;
  return false;
}

// Procedura wyświetla elementy zbioru A
//--------------------------------------
void s_print(BSet A)
{
  int nb;
  unsigned int m;

  for(int i = 0; i <= A.nmax; i++)
    for(nb = 0, m = A.T[i]; m; m >>= 1, nb++)
      if(m & 1)
        cout << (i << 5)+nb+A.vmin << " ";
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  BSet A, B, C;
  int i, x;

  // Inicjujemy generator pseudolosowy
  srand(time(NULL));
  // Tworzymy puste zbiory o zakresie
  // elementów od -20 do 20 i liczebności 30
  s_create(A, -20, 20);
  s_create(B, -20, 20);
  s_create(C, -20, 20);
  // Do zbioru A dodajemy 10
  // losowych elementów
  for(i = 0; i < 10; i++)
    s_add(A, -20+(rand() % 41));
  // Do zbioru B dodajemy 15
  // losowych elementów
  for(i = 0; i < 15; i++)
    s_add(B, -20+(rand() % 41));
  // Wyświetlamy je
  cout << "A:" << endl;
  s_print(A);
  cout << endl << "SIZE OF A IS "
       << s_size(A) << endl << endl
       << "B:" << endl;
  s_print(B);
  cout << endl << "SIZE OF B IS "
       << s_size(B) << endl << endl
  // Suma zbiorów
       << "UNION OF A AND B:" << endl;
  s_union(A, B, C);
  s_print(C);
  cout << endl << "SIZE OF UNION IS "
       << s_size(C) << endl << endl
  // Iloczyn zbiorów
       << "INTERSECTION OF A AND B:" << endl;
  s_intersection(A, B, C);
  s_print(C);
  cout << endl << "SIZE OF INTERSECTION IS "
       << s_size(C) << endl << endl
  // Różnica zbiorów
       << "DIFFERENCE OF A AND B:" << endl;
  s_difference(A, B, C);
  s_print(C);
  cout << endl << "SIZE OF DIFFERENCE IS "
       << s_size(C) << endl << endl;
  // Podzbiór
  // Kopiujemy A do C
  s_union(A, A, C);
  // Usuwamy 7 elementów
  for(i = 0; i < 7; i++)
    s_remove(C, -20+(rand() % 41));
  cout << "IS:" << endl;
  s_print(C);
  cout << " SUBSET OF A?" << endl
       << (s_subset(C, A) ? "YES": "NO")
       << endl << endl;
  s_difference(B, A, C);
  // Usuwamy 12 elementów
  for(i = 0; i < 12; i++)
    s_remove(C, -20+(rand() % 41));
  cout << "IS:" << endl;
  s_print(C);
  cout << " SUBSET OF A?" << endl
       << (s_subset(C, A) ? "YES": "NO")
       << endl << endl
  // Usuwanie
       << "FROM A WE REMOVE ";
  for(i = 0; i < 5; i++)
  {
    x = -20+(rand() % 41);
    cout << x << " ";
    s_remove(A, x);
  }
  cout << endl << "A:" << endl;
  s_print(A);
  cout << endl << "SIZE OF A IS "
       << s_size(A) << endl << endl;
  // Sprawdzamy obecność wybranych
  // elementów w B
  for(i = 0; i < 10; i++)
  {
    x = -20+(rand() % 41);
    cout << "IS ELEMENT" << setw (4) << x
         << " IN SET B? "
         << (s_isin(B, x) ? "YES": "NO")
         << endl;
  }
  // Sprawdzenie testu na zbiór pusty
  cout << endl << "IS SET A EMPTY?" << endl
       << (s_empty(A) ? "YES": "NO")
       << endl << endl
       << "IS INTERSECTION OF A AND "
          "DIFFERENCE OF B AND A EMPTY?"
       << endl;
  s_difference(B, A, C);
  s_intersection(A, C, C);
  cout << (s_empty(C) ? "YES": "NO")
       << endl << endl;
  // Usuwamy tablice dynamiczne w zbiorach
  delete [] A.T;
  delete [] B.T;
  delete [] C.T;
  return 0;
}

Basic

' Zbiory zaimplementowane w mapach bitowych
' Data: 01.06.2014
' (C)2014 mgr Jerzy Wałaszek
'------------------------------------------

' Definicja struktury zbioru
Type BSet
  vmin As Integer
  nmax As Integer
  T As UInteger Ptr
End Type

' Procedura dodaje element x do zbioru A
'---------------------------------------
Sub s_add(ByRef A As BSet, _
          ByVal x As Integer)
  Dim As Integer b, i

  ' Obliczamy numer bitu
  b = x-A.vmin
  ' Obliczamy indeks
  i = b Shr 5
  ' Ustawiamy bit na 1
  A.T[i] = A.T[i] or (1 Shl (b And 31))
End Sub

' Procedura usuwa element x ze zbioru
'------------------------------------
Sub s_remove(ByRef A As BSet, _
             ByVal x As Integer)
  Dim As Integer b, i

  ' Obliczamy numer bitu
  b = x-A.vmin
  ' Obliczamy indeks
  i = b Shr 5
  ' Ustawiamy bit na 0
  A.T[i] = A.T[i] And Not (1 Shl (b And 31))
End Sub

' Procedura usuwa wszystkie elementy
' ze zbioru
'-----------------------------------
Sub s_clear(ByRef A As BSet)
  Dim As Integer i
  For i = 0 To A.nmax
  	 ' Zerujemy mapę bitową
     A.T[i] = 0
  Next
End Sub

' Procedura tworzy zbiór
'-----------------------
Sub s_create(ByRef A As BSet, _
             ByVal vmin As Integer, _
             ByVal vmax As Integer)
  ' Wypełniamy strukturę danymi
  A.vmin = vmin
  ' Indeks ostatniego elementu tablicy
  A.nmax = (vmax-vmin) shr 5
  ' Tworzymy dynamicznie tablicę
  ' mapy bitowej
  A.T = New UInteger [A.nmax+1]
  ' Tworzymy zbiór pusty
  s_clear(A)
End Sub

' Procedura wyznacza w C sumę zbiorów A i B
'------------------------------------------
Sub s_union(ByRef A As BSet, _
            ByRef B As BSet, _
            ByRef C As BSet)
  Dim As Integer i

  For i = 0 To A.nmax
  	 C.T[i] = A.T[i] Or B.T[i]
  Next
End Sub

' Procedura wyznacza część wspólną
' zbiorów A i B
'---------------------------------
Sub s_intersection(ByRef A As BSet, _
                   ByRef B As BSet, _
                   ByRef C As BSet)
  Dim As Integer i

  For i = 0 To A.nmax
  	 C.T[i] = A.T[i] And B.T[i]
  Next
End Sub

' Procedura wyznacza różnicę zbiorów A i B
'-----------------------------------------
Sub s_difference(ByRef A As BSet, _
                 ByRef B As BSet, _
                 ByRef C As BSet)
  Dim As Integer i

  For i = 0 To A.nmax
  	 C.T[i] = A.T[i] And Not B.T[i]
  Next
End Sub

' Funkcja sprawdza, czy zbiór A jest
' podzbiorem zbioru B
' true  - tak, jest
' false - nie, nie jest
'-----------------------------------
Function s_subset(ByRef A As BSet, _
                  ByRef B As BSet) _
                          As Integer
  Dim As Integer i
 
  For i = 0 To A.nmax
    if(A.T[i] And B.T[i]) <> A.T[i] Then
      ' Jeśli elementu A nie ma w B,
      ' kończymy z false
      Return 0
    End If
  Next
  Return 1
End Function

' Funkcja oblicza liczbę elementów w A
'-------------------------------------
Function s_size(ByRef A As BSet) _
                        As Integer
  ' Zerujemy licznik
  Dim As Integer i, c = 0
  Dim As UInteger m
  For i = 0 To A.nmax
    m = A.T[i]
    While m
      ' Zliczamy bity równe 1
      if(m And 1) = 1 Then c += 1
      m shr= 1
    Wend
  Next
  Return c
End Function

' Funkcja sprawdza, czy zbiór A jest pusty
' true  - tak, jest pusty
' false - nie, nie jest pusty
'-----------------------------------------
Function s_empty(ByRef A As BSet) _
                         As Integer
  Dim As Integer i
  ' Pobieramy bity do m
  Dim As UInteger m = A.T[0]
  For i = 1 To A.nmax
  	 ' Sumujemy logicznie bity
     m Or = A.T[i]
  Next
  If m = 0 Then Return 1
  Return 0
End Function

' Funkcja bada, czy element x należy
' do zbioru A
' true  - tak, należy
' false - nie, nie należy
'----------------------------------
Function s_isin(ByRef A As BSet, _
                ByVal x As Integer) _
                        As Integer
  ' Obliczamy numer bitu w mapie bitowej
  Dim As Integer b = x-A.vmin
  If A.T[b Shr 5] And _
    (1 Shl (b And 31)) Then Return 1
  Return 0
End Function

' Procedura wyświetla elementy zbioru A
'--------------------------------------
Sub s_print(ByRef A As BSet)
  Dim As Integer nb, i
  Dim As UInteger m

  For i = 0 To A.nmax
    nb = 0
    m = A.T[i]
    While m
      if(m And 1) = 1 Then _
        Print Using "& "; _
              (i Shl 5)+nb+A.vmin;
      m shr= 1
      nb += 1
    Wend
  Next
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As BSet A, B, C
Dim As Integer i, x

Randomize
' Tworzymy puste zbiory o zakresie elementów
' od -20 i o liczebności 30
s_create(A, -20, 30)
s_create(B, -20, 30)
s_create(C, -20, 30)
' Do zbioru A dodajemy 10 losowych elementów
For i = 1 To 10
  s_add(A, -20+Int(rnd()*41))
Next
' Do zbioru B dodajemy 15 losowych elementów
For i = 1 To 15
  s_add(B, -20+Int(rnd()*41))
Next
' Wyświetlamy je
Print "A:"
s_print(A): Print
Print "SIZE OF A IS";s_size(A)
Print
Print "B:"
s_print(B): Print
Print "SIZE OF B IS";s_size(B)
Print
' Suma zbiorów
Print "UNION OF A And B:"
s_union(A, B, C)
s_print(c): Print
Print "SIZE OF UNION IS";s_size(C)
Print
' Iloczyn zbiorów
Print "INTERSECTION OF A And B:"
s_intersection(A, B, C)
s_print(C): Print
Print "SIZE OF INTERSECTION IS";s_size(C)
Print
' Różnica zbiorów
Print "DIFFERENCE OF A And B:"
s_difference(A, B, C)
s_print(C): Print
Print "SIZE OF DIFFERENCE IS";s_size(C)
Print
' Podzbiór
' Kopiujemy A do C
s_union(A, A, C)
' Usuwamy 7 elementów
For i = 1 To 7
  s_remove(C, -20+Int(Rnd()*41))
Next
Print "IS:";
s_print(C)
Print " SUBSET OF A?"
If s_subset(C, A) = 1 Then
  Print "YES"
Else
  Print "NO"
End If
Print
s_difference(B, A, C)
' Usuwamy 12 elementów
For i = 1 To 12
  s_remove(C, -20+Int(Rnd()*41))
Next
Print "IS:"
s_print(C)
Print " SUBSET OF A?"
If s_subset(C, A) = 1 Then
  Print "YES"
Else
  Print "NO"
End If
Print
' Usuwanie
Print "FROM A WE REMOVE";
For i = 1 To 5
  x = -20+Int(Rnd()*41)
  Print Using "& ";x;
  s_remove(A, x)
Next
Print
Print "A:"
s_print(A): Print
Print "SIZE OF A IS";s_size(A)
Print
' Sprawdzamy obecność wybranych
' elementów w B
For i = 1 To 10
  x = -20+Int(Rnd()*41)
  Print Using "IS ELEMENT#### IN BSet B? ";_
              x;
  If s_isin(B, x) = 1 Then
  	 Print "YES"
  Else
  	 Print "NO"
  End If
Next
Print
' Sprawdzenie testu na zbiór pusty
Print "IS SET A EMPTY?"
If s_empty(A) = 1 Then
  Print "YES"
Else
  Print "NO"
End If
Print
Print "IS INTERSECTION OF A AND" + _
      " DIFFERENCE OF B AND A EMPTY?"
s_difference(B, A, C)
s_intersection(A, C, C)
If s_empty(C) = 1 Then
  Print "YES"
Else
  Print "NO"
End If
Print
' Usuwamy tablice dynamiczne w zbiorach
Delete [] A.T
Delete [] B.T
Delete [] C.T
End

Python (dodatek)

# Zbiory zaimplementowane w mapach bitowych
# Data: 01.06.2014
# (C)2014 mgr Jerzy Wałaszek
#------------------------------------------

import random


# Definicja struktury zbioru
class BSet:
    def __init__(self):
        self.vmin = 0
        self.nmax = 0
        self.t = None

# Procedura dodaje element x
# do zbioru A
#----------------------------
def s_add(a, x):
    # Obliczamy numer bitu
    b = x - a.vmin
    # Obliczamy indeks
    i = b >> 3
    # Ustawiamy bit na 1
    a.t[i] |= 1 << (b & 7)


# Procedura usuwa element x
# ze zbioru
#---------------------------
def s_remove(a, x):
    # Obliczamy numer bitu
    b = x-a.vmin
    # Obliczamy indeks
    i = b >> 3
    # Ustawiamy bit na 0
    a.t[i] &= ~(1 >> (b & 7))


# Procedura usuwa wszystkie
# elementy ze zbioru
#--------------------------
def s_clear(a):
    for i in range(a.nmax+1):
        # Zerujemy mapę bitową
        a.t[i] = 0


# Procedura tworzy zbiór
#-----------------------
def s_create(x, vmn, vmx):
    # Wypełniamy strukturę danymi
    x.vmin = vmn
    # Indeks ostatniego
    # elementu tablicy
    x.nmax = (vmx-vmn) >> 3
    # Tworzymy dynamicznie tablicę
    # mapy bitowej
    x.t = bytearray(x.nmax+1)
    print("nmax = ", x.nmax)


# Procedura wyznacza w C
# sumę zbiorów A i B
#-----------------------
def s_union(a, b, c):
    for i in range(a.nmax+1):
        c.t[i] = a.t[i] | b.t[i]


# Procedura wyznacza część wspólną
# zbiorów A i B
#---------------------------------
def s_intersection(a, b, c):
    for i in range(a.nmax+1):
        c.t[i] = a.t[i] & b.t[i]


# Procedura wyznacza różnicę zbiorów A i B
#-----------------------------------------
def s_difference(a, b, c):
    for i in range(a.nmax+1):
        c.t[i] = a.t[i] & ~b.t[i]


# Funkcja sprawdza, czy zbiór A jest
# podzbiorem zbioru B
# true  - tak, jest
# false - nie, nie jest
#-----------------------------------
def s_subset(a, b):
    for i in range(a.nmax + 1):
        if (a.t[i] & b.t[i]) != a.t[i]:
            # Jeśli elementu A nie ma w B,
            # kończymy z false
            return False
    return True


# Funkcja oblicza liczbę elementów w A
#-------------------------------------
def s_size(a):
    # Zerujemy licznik
    cnt = 0
    for i in range(a.nmax + 1):
        m = a.t[i]
        while m:
            # Zliczamy bity równe 1
            if m & 1:
                cnt += 1
            m >>= 1
    return cnt


# Funkcja sprawdza, czy zbiór A jest pusty
# true  - tak, jest pusty
# false - nie, nie jest pusty
#-----------------------------------------
def s_empty(a):
    # Pobieramy bity do m
    m = a.t[0]
    for i in range(a.nmax + 1):
        # Sumujemy logicznie bity
        m |= a.t[i]
    return not m

# Funkcja bada, czy element x należy
# do zbioru A
# true  - tak, należy
# false - nie, nie należy
#----------------------------------
def s_isin(a, x):
    # Obliczamy numer bitu
    # w mapie bitowej
    b = x - a.vmin
    if a.t[b >> 3] & (1 << (b & 7)):
        return True
    return False


# Procedura wyświetla elementy zbioru A
#--------------------------------------
def s_print(a):
    for i in range(a.nmax + 1):
        nb = 0
        m = a.t[i]
        while m:
           if m & 1:
               print((i << 3)+nb+a.vmin,
                  end=" ")
           m >>= 1
           nb += 1

# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

a = BSet()
b = BSet()
c = BSet()
# Tworzymy puste zbiory o zakresie elementów
# od -20 i o liczebności 30
s_create(a, -20, 20)
s_create(b, -20, 20)
s_create(c, -20, 20)
# Do zbioru A dodajemy 10 losowych elementów
for i in range(10):
    s_add(a, random.randrange(-20,21))
# Do zbioru B dodajemy 15 losowych elementów
for i in range(15):
    s_add(b, random.randrange(-20,21))
# Wyświetlamy je
print("A:")
s_print(a)
print()
print("SIZE OF A IS", s_size(a))
print()
print("B:")
s_print(b)
print()
print("SIZE OF B IS", s_size(b))
print()
# Suma zbiorów
print("UNION OF A And B:")
s_union(a, b, c)
s_print(c)
print()
print("SIZE OF UNION IS", s_size(c))
print()
# Iloczyn zbiorów
print("INTERSECTION OF A And B:")
s_intersection(a, b, c)
s_print(c)
print()
print("SIZE OF INTERSECTION IS", s_size(c))
print()
# Różnica zbiorów
print("DIFFERENCE OF A And B:")
s_difference(a, b, c)
s_print(c)
print()
print("SIZE OF DIFFERENCE IS", s_size(c))
print()
# Podzbiór
# Kopiujemy A do C
s_union(a, a, c)
# Usuwamy 7 elementów
for i in range(7):
    s_remove(c, random.randrange(-20,21))
print("IS:", end=" ")
s_print(c)
print(" SUBSET OF A?")
if s_subset(c, a):
    print("YES")
else:
    print("NO")
print()
s_difference(b, a, c)
# Usuwamy 12 elementów
for i in range(12):
    s_remove(c, random.randrange(-20,21))
print("IS:", end=" ")
s_print(c)
print(" SUBSET OF A?")
if s_subset(c, a):
    print("YES")
else:
    print("NO")
print()
# Usuwanie
print("FROM A WE REMOVE", end=" ")
for i in range(5):
    x = random.randrange(-20,21)
    print(x, end=" ")
    s_remove(a, x)
print()
print("A:")
s_print(a)
print()
print("SIZE OF A IS", s_size(a))
print()
# Sprawdzamy obecność wybranych
# elementów w B
for i in range(10):
    x = random.randrange(-20,21)
    print("IS ELEMENT%4d IN SET B? " % x,
          end="")
    if s_isin(b, x):
        print("YES")
    else:
        print("NO")
print()
# Sprawdzenie testu na zbiór pusty
print("IS SET A EMPTY?")
if s_empty(a):
    print("YES")
else:
    print("NO")
print()
print("IS INTERSECTION OF A AND" +
      " DIFFERENCE OF B AND A EMPTY?")
s_difference(b, a, c)
s_intersection(a, c, c)
if s_empty(c):
    print("YES")
else:
    print("NO")
print()

Wynik:

-17 -15 -11 -7 -6 -3 -2 7 14 15
SIZE OF A IS 10

B:
-18 -17 -14 -13 -12 -9 -7 -5 -1 6 7 10 16 18
SIZE OF B IS 14

UNION OF A AND B:
-18 -17 -15 -14 -13 -12 -11 -9 -7 -6 -5 -3 -2 -1 6 7 10 14 15 16 18
SIZE OF UNION IS 21

INTERSECTION OF A AND B:
-17 -7 7
SIZE OF INTERSECTION IS 3

DIFFERENCE OF A AND B:
-15 -11 -6 -3 -2 14 15
SIZE OF DIFFERENCE IS 7

IS:
-17 -15 -11 -7 -6 -3 14 15 SUBSet OF A?
TRUE

IS:
-13 -9 -5 -1 6 16 18 SUBSet OF A?
FALSE

FROM A WE REMOVE 12 18 -8 -3 -14
A:
-17 -15 -11 -7 -6 -2 7 14 15
SIZE OF A IS 9

IS ELEMENT  -3 IN SET B? NO
IS ELEMENT  15 IN SET B? NO
IS ELEMENT  13 IN SET B? NO
IS ELEMENT -20 IN SET B? NO
IS ELEMENT  13 IN SET B? NO
IS ELEMENT  -7 IN SET B? YES
IS ELEMENT -17 IN SET B? YES
IS ELEMENT   5 IN SET B? NO
IS ELEMENT  19 IN SET B? NO
IS ELEMENT  11 IN SET B? NO

IS SET A EMPTY?
FALSE

IS INTERSECTION OF A AND DIFFERENCE OF B AND A EMPTY?
TRUE

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Reprezentacja zbiorów w mapach bitowych

Rozwiązanie

Algorytmy operacji dla zbiorów reprezentowanych mapami bitowymi

s_add(A, x) – dodaje element x do zbioru A.

Wejście:

Wyjście:

Elementy pomocnicze:

s_remove(A, x) – usuwa element x ze zbioru A

Wejście:

Wyjście:

Elementy pomocnicze:

s_clear(A) – usuwa wszystkie elementy ze zbioru A, zbiór A staje się zbiorem pustym

Wejście:

Wyjście:

Elementy pomocnicze:

s_create(A, vmin, vmax) – tworzy pusty zbiór A o odpowiednim rozmiarze

Wejście:

Wyjście:

Elementy pomocnicze:

s_union(A, B, C) – zwraca sumę zbiorów A i B

Wejście:

Wyjście:

Elementy pomocnicze:

s_intersection(A, B, C) – zwraca iloczyn zbiorów A i B

Wejście:

Wyjście:

Elementy pomocnicze:

s_difference(A, B, C) – zwraca różnicę zbioru A i B

Wejście:

Wyjście:

Elementy pomocnicze:

s_subset(A, B) – zwraca true, jeśli zbiór A jest podzbiorem zbioru B, inaczej zwraca false.

Wejście:

Wyjście:

Elementy pomocnicze:

s_size(A) – zwraca liczbę elementów zawartych w zbiorze A

Wejście:

Wyjście:

Elementy pomocnicze:

s_empty(A) – zwraca true, jeśli zbiór A jest pusty, inaczej zwraca false

Wejście:

Wyjście:

Elementy pomocnicze:

s_isin(A, x) – zwraca true, jeśli element x jest w zbiorze A, inaczej zwraca false

Wejście:

Wyjście:

Elementy pomocnicze:

Przykładowe programy